增量極坐標(biāo)編碼的貝賽爾曲線智能優(yōu)化算法

肖琴，張永韡，汪鐳

隸屬度函數(shù)M(x)取值位于[0, 1]，用以表征x屬于M的程度高低。隸屬度函數(shù)常用于模糊評價函數(shù)，其特點是評價結(jié)果不是覺得的肯定或否定，而是用模糊集來表示。確定隸屬度函數(shù)是模糊理論在實際應(yīng)用中的重要環(huán)節(jié)。目前構(gòu)造隸屬函數(shù)的方法主要有：模糊統(tǒng)計法[1-2]、指派方法[3]、二元對比排序法等[1]。然而，傳統(tǒng)方法存在各種各樣的問題[4-5]，文獻(xiàn)[6]對隸屬度函數(shù)的不同確定方法原理進(jìn)行了詳細(xì)闡述。其中，模糊統(tǒng)計方法較直觀地反映了模糊概念中的隸屬程度，但其計算量較大，隸屬度函數(shù)精度直接受離散化的區(qū)間大小的影響；指派法受限于指派者的經(jīng)驗知識；二元比較法中如何實現(xiàn)個體整體隸屬度排序是難點，且二元比較法獲得的隸屬度函數(shù)是離散表示的。為獲得更符合客觀實際的連續(xù)隸屬函數(shù)，文獻(xiàn)[7]嘗試通過最小二乘法來構(gòu)建隸屬度函數(shù)，通過最小化誤差的平方和找到一組數(shù)據(jù)的最佳函數(shù)匹配，需通過試湊確定多項式的最佳階數(shù)；文獻(xiàn)[8]提出采用拋物線作為隸屬度函數(shù)的上升或下降沿，但該方法可能出現(xiàn)局部隸屬度大于1的情況；文獻(xiàn)[9]采用貝塞爾曲線逼近方式，當(dāng)曲線的冪次較低時，該方法修改曲線的功能較弱，靈活性受到限制；文獻(xiàn)[10]設(shè)計了基于貝塞爾曲線理論的備件需求模糊隸屬度函數(shù)構(gòu)建方法，此方法無需事先假設(shè)隸屬度函數(shù)的形態(tài)，簡單易用、使用靈活，但該方法中擬合誤差最小的控制點選擇方法是難點。綜上所述，使用貝塞爾曲線確定隸屬度函數(shù)形態(tài)，可以使曲線經(jīng)過模糊統(tǒng)計結(jié)果規(guī)定的任意點，且可以避免拋物線隸屬度函數(shù)中隸屬度大于1的情況[11]。但是貝塞爾曲線的控制點選擇是難點[12-13]：1）對于經(jīng)過給定點的貝塞爾曲線，控制點的選擇并不是唯一的；2）如果以貝塞爾曲線作為隸屬度函數(shù)上升沿或下降沿，則要求貝塞爾曲線必須為凸的，這將對控制點的選擇附加更多的約束，而文獻(xiàn)[9-10]均沒有就這個問題進(jìn)行討論。對于高階貝塞爾曲線，最佳擬合問題本質(zhì)上是多變量優(yōu)化問題。差分進(jìn)化算法因其簡單的結(jié)構(gòu)和穩(wěn)定的性能，在多變量優(yōu)化領(lǐng)域有著廣泛的應(yīng)用[14-15]。然而，在應(yīng)用差分進(jìn)化算法求解最佳貝塞爾曲線控制點前，必須確定控制點選擇的標(biāo)準(zhǔn)，并解決控制點約束問題[16]。本文采用擬合誤差和控制點與目標(biāo)點距離聯(lián)合的策略評價控制點，使給定目標(biāo)點后最佳控制點唯一。使用新的增量極坐標(biāo)方案對控制點進(jìn)行編碼，保證了所得貝塞爾曲線均為凸的，避免了硬約束方案對計算資源的浪費。仿真結(jié)果證實了本方法的有效性。

1 基于統(tǒng)計分析確定隸屬度函數(shù)

在確定隸屬度函數(shù)形態(tài)前，首先需要確定各隸屬度函數(shù)的區(qū)間。隸屬度函數(shù)區(qū)間的劃分有很多種方法。以評價學(xué)生成績?yōu)槔?，隸屬度函數(shù)確定的原則為使最終的分類滿足規(guī)定的要求或者默認(rèn)的滿足正態(tài)分布，即中間檔次人數(shù)占主要。設(shè)論域，并以優(yōu)、良和差表示上的模糊集，為了確定每個模糊集的隸屬度函數(shù)，需要確定5個區(qū)間的邊界a、b、c和d（圖 1）。

常見的劃分方法有：

1) 基于距離的方法。將論域等距地劃分，每個區(qū)間長度為

式中n為樣本數(shù)量。

圖1 典型隸屬度函數(shù)Fig. 1 Typical membership functions

2) 基于分位數(shù)的方法。使用該方法，可以將每個區(qū)間內(nèi)的數(shù)據(jù)點數(shù)量劃分為相同或不同的，具體選擇可根據(jù)所需分類結(jié)果的統(tǒng)計分布決定。若區(qū)間內(nèi)數(shù)據(jù)數(shù)量相同，則五區(qū)間分位數(shù)取為。

在隸屬度函數(shù)區(qū)間確定后，應(yīng)根據(jù)區(qū)間內(nèi)數(shù)據(jù)的分布，進(jìn)一步確定隸屬度函數(shù)的形態(tài)。以區(qū)間為例，該區(qū)間包含了模糊值“差”的下降沿和“(良”的上)升沿。以區(qū)間中點為界，如果在區(qū)間中的數(shù)據(jù)較多，表明該區(qū)間內(nèi)的數(shù)據(jù)總體偏小，為了使數(shù)據(jù)的隸屬度均衡化，則該區(qū)間內(nèi)對于“良”的隸屬度應(yīng)提升，對于“差”的隸屬度應(yīng)下降?；谖墨I(xiàn)[8]中的方法，為使落入?yún)^(qū)間內(nèi)的數(shù)據(jù)隸屬度滿足上述要求，區(qū)間內(nèi)隸屬度的上升沿和下降沿應(yīng)經(jīng)過下面的點：

1) 直線型。直線型隸屬度構(gòu)成梯形隸屬度函數(shù)。顯然梯形隸屬度函數(shù)無法經(jīng)過任意給定點。

2) z函數(shù)或s函數(shù)。常見的z形下降沿函數(shù)：

由定義可知，該函數(shù)中心對稱，意味著無法做出凸形的下降沿函數(shù)，也無法做出過任意給定點的曲線。

3) 拋物線。文獻(xiàn)[8]提出采用拋物線作為隸屬度函數(shù)的上升或下降沿。同時指出，經(jīng)過給定三點的拋物線是唯一的。但是，過三點的拋物線可能出現(xiàn)局部函數(shù)值大于1的情況，使得下降或上升沿非單調(diào)，這對于隸屬度函數(shù)是不允許的。

4) 貝塞爾曲線。貝塞爾曲線是光滑的連續(xù)曲線，在工程與設(shè)計等領(lǐng)域有廣泛應(yīng)用[17]。貝塞爾曲線可以在端點固定的情況下，通過調(diào)整控制點對曲線形態(tài)進(jìn)行細(xì)致的調(diào)整，且調(diào)整后的曲線仍然是連續(xù)光滑的。有關(guān)貝塞爾曲線的詳細(xì)介紹，可參考文獻(xiàn)[18]。

2 問題描述

貝塞爾曲線的一般參數(shù)公式為

為不失一般性，以求取過3個點的貝塞爾曲線為例，對于二階貝塞爾曲線有

意思為最小化擬合點與目標(biāo)點距離的同時最小化控制點與目標(biāo)點的距離。其中w為第二部分的加權(quán)值。

一般地，過m點的n階貝塞爾曲線可通過最小化式(8)確定：

3 基于差分進(jìn)化算法的貝塞爾曲線控制點優(yōu)化方法

典型的差分進(jìn)化變異操作為[19]

3.1 增量極坐標(biāo)編碼與解碼方法

圖2 兩控制點貝塞爾曲線示意圖Fig. 2 Beizer curve with two control points

為了使得到的控制點與首末端點組成凸多邊形，有如下兩種方法：

1）將所有控制點合并為一點，這樣首末端點與控制點共同組成三角形，可保證所得曲線總是凸的。進(jìn)一步，如果該控制點位于矩形的上半部分，則得到的貝塞爾曲線向上凸起，反之向下。

2）設(shè)計新的編碼與解碼方法保證搜索空間由凸多邊形構(gòu)成。仍然以圖2為例，使用類似極坐標(biāo)的方法對控制點進(jìn)行編碼。每個控制點需要角度和長度兩位進(jìn)行表達(dá)，對于過3點的3階貝塞爾曲線，共需5位編碼。所有編碼的取值范圍均為[0, 1]。對任意的編碼，x1代表第一個控制點角度的編碼。如圖所示，對控制點P1，有

浪漫主義音樂更注重表達(dá)人的情感，對美好事物的追求。他們反對封建，提倡自由、平等。他們側(cè)重對理想世界的描繪，把情感放在第一位。音樂中充滿戲劇性。這些都離不開貝多芬的影響。

為了使任意[0, 1]之間的任意編碼均滿足約束，令x2表示線段的比例，長度為

至于控制點P2，可知允許的角度范圍是的正切減去，以此類推，可得過m點n階貝塞爾曲線的解碼方案。設(shè)有編碼，

3.2 算法流程

對于過m點的n階貝塞爾曲線，使用貝塞爾曲線的n-1個控制點和m-1個參數(shù)的編碼組成向量，使用式 (14)～(17)解碼為控制點坐標(biāo)，并使用式(7)評價候選解，使用差分進(jìn)化算法優(yōu)化貝塞爾曲線控制點的算法流程如下：

2）對每個變量進(jìn)行解碼，并按照式(7)或式(8)計算每個向量的代價函數(shù)；

3）按照式(9)對種群進(jìn)行交叉，生成同等規(guī)模的實驗向量，對實驗向量解碼，并按照(7)或式(8)計算每個向量的代價函數(shù)；

4）種群中相應(yīng)的實驗向量與舊向量進(jìn)行比較，如果代價函數(shù)更小，則用實驗向量代替舊向量；

5）如果達(dá)到停止條件，則退出優(yōu)化并顯示結(jié)果；否則返回 3)。

4 貝塞爾曲線上的隸屬度確定方法

貝塞爾曲線為參數(shù)曲線，在根據(jù)起始端點和中間點得到最佳控制點后，曲線形態(tài)唯一確定，但曲線上的隸屬度（即縱坐標(biāo)）無法直接通過橫坐標(biāo)值計算得出，必須通過的方式確定。由式(4)可知，x是關(guān)于t的n階方程，隨著曲線階次增加，方程求解將愈加困難。根據(jù)貝塞爾曲線的特性可知，當(dāng)參數(shù)t由0～1變化時，沿由端點P0開始沿曲線連續(xù)地移動到Pn。因此，在[0, 1]之間，必存在一個t，使得等于給定的橫坐標(biāo)。據(jù)此可將確定給定橫坐標(biāo)x對應(yīng)參數(shù)t的問題轉(zhuǎn)化為式（18）最小化問題：

當(dāng)貝塞爾曲線為凸時，該最小化問題是凸優(yōu)化問題，可通過基于梯度的優(yōu)化算法求解。為了獲得較快的收斂速度，本文使用BFGS算法求解式(18)給出的最小化問題。BFGS算法是由4位提出者姓氏首字母（Broyden-Fletcher-Goldfarb-Shanno）命名的無約束數(shù)值最優(yōu)化算法。BFGS是一類準(zhǔn)牛頓算法，即通過近似而不是精確計算Hessian矩陣來確定算法搜索方向及步長。由于快速的收斂性，BFGS算法廣泛的應(yīng)用于連續(xù)無約束優(yōu)化問題中[20]。BFGS算法流程在各類數(shù)值優(yōu)化教科書中均有述及，不再贅述。通過優(yōu)化式(18)得到給定橫坐標(biāo)x對應(yīng)參數(shù)t后，可由式(4)求得對應(yīng)的縱坐標(biāo)，也就是隸屬度值。

5 算例

以某班級學(xué)生兩門成績?yōu)槔?，進(jìn)行區(qū)間劃分比較，隸屬度函數(shù)形態(tài)比較和各階貝塞爾曲線之間的對比。第一門課程成績數(shù)據(jù)為{14, 90, 70, 80, 60,66, 60, 36, 39, 76, 60, 33, 60, 81, 46, 65, 60, 40, 86,84, 74, 80, 35, 47, 22, 65, 83, 26, 89, 37, 15, 81, 69,41, 62, 1, 89, 33, 60, 91, 19, 0, 92, 65, 60, 68, 35, 89,35, 64, 24, 71, 40, 35, 31, 40, 71, 46, 40, 40}。第二門課程成績?yōu)閧61, 94, 87, 74, 76, 87, 72, 66, 27, 79, 74,74, 84, 84, 63, 69, 68, 60, 69, 98, 94, 72, 67, 72, 85,84, 91, 79, 94, 87, 67, 73, 91, 41, 84, 21, 96, 89, 83,97, 81, 71, 94, 66, 92, 94, 62, 76, 65, 84, 84, 92, 88,72, 75, 65, 91, 83, 92, 79}。

5.1 實驗 1

以距離、分位數(shù)、均值–距離、均值–分位數(shù)4種不同方式劃分區(qū)間。其中分位數(shù)法采用等分位數(shù)，均值–分位數(shù)法使用中位數(shù)。劃分區(qū)間如表 1。

表1 4種方法分隔點對比Table 1 Separation points of four methods

表格中a表示對于“差”的隸屬度為1的上限，d表示對于“優(yōu)”的隸屬度為1的下限。相應(yīng)地，每個區(qū)間內(nèi)數(shù)據(jù)所占比例如表 2。

表2 4種方法各區(qū)間比例對比Table 2 Proportion of intervals by four methods %

可以發(fā)現(xiàn)，在不同的課程中，基于距離的兩類方法均出現(xiàn)了某區(qū)間比例不均衡的情況。其中課程一單純的距離法大于d的區(qū)間，即對于“優(yōu)”的隸屬度為1的比例占25%，課程二此項比例更是達(dá)到了46%。而在經(jīng)過模糊評價后，占優(yōu)的比例將更高，這樣的評價標(biāo)準(zhǔn)顯然不符合需求。此外，課程–均值–距離法中的[a, b]區(qū)間也存在比例過大的情況。相對而言，單純的分位數(shù)方法得到各區(qū)間比例基本相等，這是由分位數(shù)的特性決定的。最后兩個區(qū)間比例不等是因為有相同的多個數(shù)據(jù)點。

5.2 實驗 2

以均值–分位數(shù)得到的區(qū)間劃分為基礎(chǔ)，分別確定梯形、拋物線和貝塞爾曲線的隸屬度函數(shù)。貝塞爾曲線使用2階曲線，并采用差分進(jìn)化算法求解最佳控制點。所得隸屬度函數(shù)如圖3所示。其中左側(cè)為課程一的隸屬度，右側(cè)為課程二的隸屬度函數(shù)。

圖3 3種隸屬度函數(shù)形態(tài)對比Fig. 3 Comparison of three kind of membership functions

對比兩門課程的隸屬度函數(shù)可以發(fā)現(xiàn)，由于課程二的平均成績更高，故3種隸屬度函數(shù)的上升沿和下降沿均向右移動，且由于課程二的數(shù)據(jù)方差較小，上升沿的與下降沿的區(qū)間都較窄。但不論采用什么樣的數(shù)據(jù)，本文所采用的方法均可以對數(shù)據(jù)集作出合理的評價，使得最終的優(yōu)良率保持一定的穩(wěn)定。最終的優(yōu)良差比例如下：

5.3 實驗 3

為了驗證本方案在高階貝塞爾曲線下的有效性，以課程一數(shù)據(jù)為例，求解2～5階貝塞爾曲線隸屬度函數(shù)。依據(jù)3.2節(jié)的描述，本例為過3點的貝塞爾曲線求解問題，可以對2～5階貝塞爾曲線分別取長度為3、5、7和9的編碼串代表曲線參數(shù)。由于編碼串無約束，可使用任意全局優(yōu)化算法求解。本實驗采用差分進(jìn)化算法求解貝塞爾曲線。選擇[a, b]區(qū)間的局部隸屬度函數(shù)分別繪制2～5階的貝塞爾曲線如圖4。其中折線為連接起的控制點。

表3 3種隸屬度函數(shù)劃分對比Table 3 Proportion of three kind of membership functions %

圖4 2～5階貝塞爾曲線隸屬度Fig. 4 Beizer membership function of order 2～5

可以看出，各階貝塞爾曲線均穿過了指定點，并且保持凸形態(tài)，滿足模糊評價所需的隸屬度函數(shù)要求。隨著曲線階數(shù)增加，曲線與控制點連接的折線越發(fā)靠近。需要指出的是，對于作為隸屬度函數(shù)的貝塞爾曲線，二階曲線已可以滿足所有要求，而高階貝塞爾曲線的求解方法在其他領(lǐng)域可以得到更好的應(yīng)用。

6 結(jié)束語

本文在統(tǒng)計分析確定隸屬度函數(shù)區(qū)間的基礎(chǔ)上，確定了使隸屬度劃分均衡化的區(qū)間內(nèi)關(guān)鍵點，使用貝塞爾曲線擬合區(qū)間起點、終點和關(guān)鍵點。提出了以極坐標(biāo)和線段比例為基礎(chǔ)的增量式編碼方案表達(dá)貝塞爾曲線的控制點。編碼統(tǒng)一為[0, 1]之間的小數(shù)，方便任意全局優(yōu)化算法的應(yīng)用，具有普適性。且任意[0, 1]編碼都可以解碼為滿足約束的控制點，解決了控制點選擇的約束問題。本編碼方案可以簡單的擴(kuò)展至過任意點的任意階貝塞爾曲線上，具備良好的適應(yīng)性。經(jīng)過算例驗證，所得隸屬度函數(shù)可以對不良分布的數(shù)據(jù)集進(jìn)行正確的模糊分類，同時避免了拋物線型函數(shù)隸屬度大于1的情況。

[1]侯世旺, 朱慧明. 基于模糊統(tǒng)計的不確定質(zhì)量特性控制圖研究[J]. 統(tǒng)計與決策, 2016(16): 25–28.HOU Shiwang, ZHU Huiming. Research on uncertain quality control chart based on fuzzy statistics[J]. Statistics and decision, 2016(16): 25–28.

[2]張明, 陳楠, 吳陳. 一種改進(jìn)的模糊統(tǒng)計方法[J]. 華東船舶工業(yè)學(xué)院學(xué)報: 自然科學(xué)版, 2004, 18(4): 58–61.ZHANG Ming, CHEN Nan, WU Chen. An improved fuzzy statistical method[J]. Journal of East China shipbuilding institute: natural science edition, 2004, 18(4): 58–61.

[3]袁力, 姜琴. 隸屬函數(shù)確定方法探討[J]. 鄖陽師范高等?？茖W(xué)校學(xué)報, 2009, 29(6): 44–46.YUAN Li, JIANG Qin. Discussion on the method of determining membership function[J]. Journal of Yunyang normal college, 2009, 29(6): 44–46.

[4]HASUIKE T, KATAGIRI H, TSUBAKI H. A constructing algorithm for appropriate piecewise linear membership function based on statistics and information theory[J]. Procedia computer science, 2015, 60: 994–1003.

[5]董煒, 陳衛(wèi)征, 徐曉濱, 等. 基于可分性測度的模糊隸屬函數(shù)確定方法[J]. 控制與決策, 2014, 29(11): 2089–2093.DONG Wei, CHEN Weizheng, XU Xiaobin, et al. Determining method of fuzzy membership function based on separability measure[J]. Control and decision, 2014, 29(11):2089–2093.

[6]馬萬元, 耿秀麗. 基于概率統(tǒng)計的模糊隸屬函數(shù)計算研究[J]. 數(shù)學(xué)理論與應(yīng)用, 2016(3): 93–100.MA Wanyuan, GENG Xiuli. Research on the fuzzy membership function determination based on probability statistics[J]. Mathematical theory and applications, 2016(3):93–100.

[7]袁杰, 史海波, 劉昶. 基于最小二乘擬合的模糊隸屬函數(shù)構(gòu)建方法[J]. 控制與決策, 2008, 23(11): 1263–1266, 1271.YUAN Jie, SHI Haibo, LIU Chang. Construction of fuzzy membership functions based on least squares fitting[J].Mathematical theory and applications, 2008, 23(11):1263–1266, 1271.

[8]王石青, 邱林, 王志良, 等. 確定隸屬函數(shù)的統(tǒng)計分析法[J].華北水利水電學(xué)院學(xué)報, 2002(1): 68–71.WANG Shiqing, QIU Lin, WANG Zhiliang, et al. Determine the membership function based on statistical analysis[J].Journal of North China institute of water conservancy and hydroelectric power, 2002(1): 68–71.

[9]MEDAGLIA A S L, FANG S C, NUTTLE H L W, et al. An efficient and flexible mechanism for constructing membership functions[J]. European journal of operational research,2002, 139(1): 84–95.

[10]王林, 富慶亮. 基于貝塞爾曲線理論的備件需求模糊隸屬度函數(shù)構(gòu)建模型[J]. 運籌與管理, 2011, 20(1): 87–92.WANG Lin, FU Qingliang. A model for the construction of spare parts dem and fuzzy membership function based on bezier curves theory[J]. Operations research and managent science, 2011, 20(1): 87–92.

[11]ZAKARIA R, WAHAB A F. Fuzzy set theory in modeling uncertainty data via interpolation rational bezier surface function[J]. Applied mathematical sciences, 2013, 45(7):2229–2238.

[12]AZAR M M. Maneuver planning with higher order rational Bezier curves[OL/EB]. [2017-04-02]. http://www.freepatentsonline.com/9785146.html

[13]DERKSEN R W, ROGALSKY T. Bezier-PARSEC: an optimized aerofoil parameterization for design[J]. Advances in engineering software, 2010, 41(7): 923–930.

[14]丁青鋒, 尹曉宇. 差分進(jìn)化算法綜述[J]. 智能系統(tǒng)學(xué)報,2017, 12(4): 431–442.DING Qingfeng, YIN Xiaoyu. Research survey of differential evolution algorithms[J]. CAAI transactions on intelligent systems, 2017, 12(4): 431–442.

[15]DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 4–31.

[16]ZHANG M, JU Z. A novel fuzzy support vector machine based on differential evolution[J]. Icic express letters,2017, 11(7): 1159–1165.

[17]陳成, 何玉慶, 卜春光, 等. 基于四階貝塞爾曲線的無人車可行軌跡規(guī)劃[J]. 自動化學(xué)報, 2015, 41(3): 486–496.CHEN Cheng, HE Yuqing, BU Chunguang, et al. Feasible trajectory generation for autonomous vehicles based on quartic bezier curve[J]. Acta automatica sinica, 2015,41(3): 486–496.

[18]MARSH D. Applied geometry for computer graphics and cad[M]. 2006.

[19]R STORN, K PRICE. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of global optimization, 1997, 11(4):341–359.

[20]Y X YUAN. A modified bfgs algorithm for unconstrained optimization[J]. IMA journal of numerical analysis, 1991,11(3): 325–332.