戴 麗, 謝 政, 李建平
(國(guó)防科學(xué)技術(shù)大學(xué)理學(xué)院,湖南長(zhǎng)沙410073)
?
粒子群算法課堂教學(xué)案例——求包含所有已知數(shù)據(jù)點(diǎn)的最小橢圓
戴麗,謝政,李建平
(國(guó)防科學(xué)技術(shù)大學(xué)理學(xué)院,湖南長(zhǎng)沙410073)
[摘要]“現(xiàn)代優(yōu)化方法”來(lái)源于各種大規(guī)模的工程實(shí)際問(wèn)題的求解,也正是在工程實(shí)踐問(wèn)題的求解過(guò)程中得到不斷發(fā)展。在該課程的教學(xué)中有必要引入案例。本文以粒子群算法為例,介紹本課程的一個(gè)教學(xué)案例:如何求包含所有已知數(shù)據(jù)點(diǎn)的最小橢圓。該案例在模式識(shí)別中有重要的應(yīng)用.
[關(guān)鍵詞]粒子群算法; 教學(xué)案例; 模式識(shí)別
1案例背景
美國(guó)Cleveland Heart Disease Database 提供了303個(gè)心臟病人的有關(guān)數(shù)據(jù)信息[1].該數(shù)據(jù)庫(kù)記錄了這些病人的血壓(低壓)、膽固醇等13項(xiàng)與心臟病有關(guān)的指標(biāo),同時(shí),也記錄了這些病人是否患有心臟病的確診結(jié)論.現(xiàn)在的問(wèn)題是如何根據(jù)這些數(shù)據(jù)對(duì)新來(lái)的病人只通過(guò)檢查這13項(xiàng)指標(biāo),就推斷該病人是否患有心臟病.該問(wèn)題是病人患病確診問(wèn)題.本質(zhì)上是分類問(wèn)題,也稱為模式識(shí)別問(wèn)題.
假設(shè)只考察是否患有心臟病與人的血壓(低壓)[x]1和膽固醇[x]2這兩項(xiàng)指標(biāo)的關(guān)系.用“+”表示有心臟病,用“o”表示無(wú)心臟病.如果10個(gè)病人的數(shù)據(jù)如圖1所示,則此時(shí),可用一條直線(圖中的粗線)將兩部分?jǐn)?shù)據(jù)分開(kāi).但當(dāng)數(shù)據(jù)如圖2所示時(shí),則無(wú)法用一條直線將兩部分?jǐn)?shù)據(jù)分開(kāi),用一個(gè)橢圓(圖中的粗線部分)區(qū)分兩種數(shù)據(jù).也就是說(shuō),此時(shí),需要構(gòu)造一個(gè)包括所有“o”型數(shù)據(jù)點(diǎn)的面積最小的橢圓.這是一非線性劃分問(wèn)題.
圖1 用直線區(qū)分?jǐn)?shù)據(jù) 圖2 用橢圓區(qū)分?jǐn)?shù)據(jù)
患病確診問(wèn)題是本文的應(yīng)用之一.實(shí)際上,在模式識(shí)別問(wèn)題中經(jīng)常需要構(gòu)造這樣的橢圓.對(duì)于非線性劃分問(wèn)題,通常的做法是采用支持向量機(jī),即構(gòu)造核函數(shù),并求解相應(yīng)的二次規(guī)劃問(wèn)題.也可以借助于一些商業(yè)軟件,如Halcon等解決該問(wèn)題.本文則將現(xiàn)代優(yōu)化算法應(yīng)用于非線性劃分問(wèn)題,給出一個(gè)求面積最小橢圓的粒子群算法.該算法不需要構(gòu)造核函數(shù),也不需要函數(shù)的解析性質(zhì).因此,可廣泛應(yīng)用于問(wèn)題的求解.
2問(wèn)題的數(shù)學(xué)描述
以二維數(shù)據(jù)為例.如圖3所示,設(shè)數(shù)據(jù)點(diǎn)所在的坐標(biāo)系為xoy坐標(biāo)系.設(shè)所求橢圓中心在xoy坐標(biāo)系中為點(diǎn)(a,b).以橢圓的中心(a,b)為坐標(biāo)原點(diǎn),以橢圓對(duì)稱軸為坐標(biāo)軸,建立一個(gè)新坐標(biāo)系XOY.XOY可由xoy經(jīng)過(guò)旋轉(zhuǎn)、平移得到.設(shè)旋轉(zhuǎn)的角度為θ.設(shè)橢圓的兩個(gè)半軸長(zhǎng)分別為A和B.于是,所求橢圓在XOY坐標(biāo)系中方程為標(biāo)準(zhǔn)方程
(1)
且
圖3 坐標(biāo)的建立及參數(shù)說(shuō)明
(2)
由此可見(jiàn),只要確定a,b,θ,A,B的值,橢圓的方程就相應(yīng)確定.
要尋找一個(gè)包含所有已知數(shù)據(jù)點(diǎn)且面積最小的橢圓,每個(gè)已知數(shù)據(jù)點(diǎn)(x,y)代入(2)中得到的(X,Y)滿足
(3)
的前提條件下,使得橢圓的面積πAB盡可能小.
3粒子群算法求解問(wèn)題
粒子群(Particle Swarm Optimization, PSO)算法是由Kennedy和Eberhart于1995年提出的.它與蟻群算法一樣,也是通過(guò)模擬動(dòng)物的群體行為來(lái)求解優(yōu)化問(wèn)題.PSO簡(jiǎn)單易行、收斂速度快、設(shè)置參數(shù)少,在各種優(yōu)化問(wèn)題中都有著良好的表現(xiàn),其天然的實(shí)數(shù)編碼特點(diǎn)使其尤其適合于處理實(shí)優(yōu)化問(wèn)題.PSO已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點(diǎn).
在PSO中,每個(gè)優(yōu)化問(wèn)題的解看作搜索空間中的一只鳥(niǎo),稱之為“粒子”.算法由多個(gè)隨機(jī)產(chǎn)生的粒子(即隨機(jī)解)組成的群體開(kāi)始.每個(gè)粒子都被賦予一個(gè)由優(yōu)化函數(shù)確定的適應(yīng)值.每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離,然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.在搜索時(shí),每個(gè)粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)進(jìn)行位置(狀態(tài)、也就是解)的變化,一個(gè)是粒子個(gè)體本身所找到的歷史最優(yōu)解,另一個(gè)是群體內(nèi)(或鄰域內(nèi))其他粒子的歷史最優(yōu)解,以使粒子能夠飛向解空間,并在最優(yōu)解處降落.
設(shè)第i個(gè)粒子的位置為:xi=(xi1,xi2,…,xin);
第i個(gè)粒子的速度為:vi=(vi1,vi2,…,vin);
第i個(gè)粒子經(jīng)歷過(guò)的歷史最優(yōu)解為:Pi=(pi1,pi2,…,pin);
群體內(nèi)(或鄰域內(nèi))所有粒子所經(jīng)歷過(guò)的歷史最優(yōu)解為:Pg=(pg1,pg2,…,pgn).
一般來(lái)說(shuō),粒子的位置和速度都是在連續(xù)的實(shí)數(shù)空間內(nèi)取值.在找到了兩個(gè)“極值”后,每個(gè)粒子根據(jù)如下公式來(lái)更新自己的速度和位置:
vk+1=c0vk+c1ξ(pk-xk)+c2η(pg-xk),
xk+1=xk+vk+1,
其中c1和c2稱為學(xué)習(xí)因子或加速系數(shù),一般為正常數(shù).學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體學(xué)習(xí)的能力,從而向自己的歷史最優(yōu)解及群體內(nèi)或鄰域內(nèi)的歷史最優(yōu)解靠近.c1和c2通常取為2.ξ和η是在[0,1]區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù).c0稱為慣性因子,其大小決定了粒子對(duì)當(dāng)前速度繼承的多少,合適的選擇c0的值可以使粒子具有均衡的廣域搜索能力(即探索能力)和局部搜索能力(即開(kāi)發(fā)能力).粒子的速度被限制在一個(gè)最大速度Vmax的范圍內(nèi).
下面介紹如何用PSO求解最小橢圓的構(gòu)造問(wèn)題.
問(wèn)題解的表達(dá)方式,稱為編碼方法,也就是將實(shí)際問(wèn)題的解用一種便于算法操作的形式來(lái)描述.實(shí)際應(yīng)用中,應(yīng)當(dāng)根據(jù)問(wèn)題本身的特點(diǎn)和所使用的優(yōu)化算法而采用不同的編碼方法.在算法結(jié)束時(shí),還需要通過(guò)解碼還原到實(shí)際問(wèn)題的解.由問(wèn)題的數(shù)學(xué)描述可見(jiàn),問(wèn)題的關(guān)鍵在于合理確定
a,b,θ,A,B
的值.因此,本文采用五維向量(x1,x2,x3,x4,x5)表示粒子個(gè)體,各分量分別為a,b,θ,A,B的取值.
由于粒子個(gè)體的不同分量表示橢圓的不同參數(shù),因此,各分量應(yīng)分別在其各自區(qū)域內(nèi)初始化.
設(shè)xmin,xmax分別表示已知數(shù)據(jù)點(diǎn)的x軸分量的最小值、最大值;ymin,ymax分別表示已知數(shù)據(jù)點(diǎn)的y軸分量的最小值、最大值.粒子的第一個(gè)分量x1應(yīng)初始化為區(qū)間[xmin,xmax]內(nèi)的隨機(jī)數(shù),粒子的第二個(gè)分量x2應(yīng)初始化為區(qū)間[ymin,ymax]內(nèi)的隨機(jī)數(shù).粒子的第三個(gè)分量x3應(yīng)在[0,2π)內(nèi)取值.粒子的第四、五個(gè)分量x4,x5均在[0,D]內(nèi)取值,其中D為數(shù)據(jù)點(diǎn)間的最大距離.當(dāng)數(shù)據(jù)較大,計(jì)算所有數(shù)據(jù)點(diǎn)的最大距離比較困難,這時(shí)也可取D為最大數(shù)據(jù)點(diǎn)間距離的估計(jì)值.本文取
評(píng)價(jià)解的優(yōu)劣的函數(shù),稱為適應(yīng)值函數(shù).實(shí)際應(yīng)用中,對(duì)目標(biāo)函數(shù)的任何變形都可作為適應(yīng)值函數(shù),但注意這個(gè)變形必須保證與原目標(biāo)函數(shù)的大小順序,即這個(gè)變形必須是嚴(yán)格單調(diào)的.適應(yīng)值函數(shù)的確定原則是要便于算法的執(zhí)行和算法效率的提高.
對(duì)于本文研究的問(wèn)題,顯然,當(dāng)粒子個(gè)體滿足條件(3)時(shí),其適應(yīng)值應(yīng)為πAB;當(dāng)粒子個(gè)體不滿足條件(3)時(shí),意味著該粒子個(gè)體不是問(wèn)題的可行解,定義其適應(yīng)值為+.粒子個(gè)體的適應(yīng)值越小,說(shuō)明粒子個(gè)體越優(yōu)秀.
4仿真算例
為了驗(yàn)證算法的有效性.我們以如下方式生成已知數(shù)據(jù)點(diǎn).首先數(shù)據(jù)點(diǎn)中包含橢圓的四個(gè)頂點(diǎn)(也就是說(shuō),待求橢圓已確定),然后在橢圓內(nèi)隨機(jī)生成其它的數(shù)據(jù)點(diǎn).
設(shè)待求橢圓的中心為(2,2);由xOy旋轉(zhuǎn)45o得XOY坐標(biāo)系;設(shè)其長(zhǎng)、短半軸長(zhǎng)分別為2,1.于是,其四個(gè)頂點(diǎn)分別為
算法中取慣性因子c0=0.1,兩個(gè)學(xué)習(xí)因子c1=c2=2.種群規(guī)模N=100,迭代10000次.算法用6.346秒時(shí)間搜索到
橢圓中心(2.00109,1.9992);旋轉(zhuǎn)角度θ=0.764;
長(zhǎng)半軸為2;短半軸為1.
如圖4所示,從圖中可以看出,算法得到了較理想的結(jié)果.
圖4 實(shí)驗(yàn)效果
5推廣
從仿真算法的實(shí)驗(yàn)效果可以看出,本文給出的算法不需要構(gòu)造核函數(shù),算法模型十分簡(jiǎn)潔,且效果理想.不僅如此,本文給出的算法模型可以推廣到一般的n維空間.
在n維空間直角坐標(biāo)系中,標(biāo)準(zhǔn)橢球方程為
相應(yīng)的“體積”與A1A2…An的值成正比.設(shè)H為n階正交矩陣,b為一個(gè)n維列向量,設(shè)
X=H(x-b),
(4)
于是,要尋找一個(gè)包含所有已知數(shù)據(jù)點(diǎn)且“體積”最小的橢圓,也就是要確定一個(gè)正交矩陣H,以及一個(gè)列向量b,在每個(gè)已知數(shù)據(jù)點(diǎn)(x,y)代入(4)中得到的X都有
(5)
成立的前提條件下,使A1A2…An盡可能小.
以三維數(shù)據(jù)為例說(shuō)明.隨機(jī)生成測(cè)試數(shù)數(shù)點(diǎn)為
p1(-2.9604,0.8617,0.3232);
p2(0.9555,-0.0915,-0.0645);
p3(0.2321,1.5701,-2.5966);
p4(0.5161,1.3619,2.8822);
p5(1.0238,0.6885,-1.0355);
p6(0.5137,2.9083,1.3557);
p7(1.2563,-1.6493,2.4393);
p8(-2.0500,0.5274,1.6582);
p9(-1.2078,1.2676,-1.0486);
p10(0.0593,-1.0815,-2.6735).
這些數(shù)據(jù)點(diǎn)在三維空間中的分布如圖5.
圖5 測(cè)試數(shù)據(jù)點(diǎn)分布圖
算法中取慣性因子c0=0.1,兩個(gè)學(xué)習(xí)因子c1=c2=2.種群規(guī)模N=2000,迭代100次.歷時(shí) 11.6秒搜索得到的正交矩陣H,b及A1,A2,A3分別為
b=(0.2506,-0.1123,-0.3651),
(A1,A2,A3)=(2.6547,3.5119,4.5825),
得到的橢球如圖6所示.
圖6 三維數(shù)據(jù)時(shí),算法搜索到的橢球
將上述算法得到的測(cè)試數(shù)據(jù)、H、b以及(A1,A2,A3)的值代入(5)式的左邊,各點(diǎn)對(duì)應(yīng)的值如表1所示.從表1中可以看出,p1,p4和p6這三個(gè)測(cè)試數(shù)據(jù)點(diǎn)對(duì)應(yīng)的值都在0.95以上,已經(jīng)很接近(5)式右邊的1.這說(shuō)明所得橢球的體積已經(jīng)比較小,改進(jìn)的余地已不大.
表1 效果分析
綜合以上實(shí)驗(yàn)結(jié)果,可以發(fā)現(xiàn),粒子群算法在11.6秒內(nèi)即可得到較好的搜索效果.
6總結(jié)
文中以二維數(shù)據(jù)為例建模,說(shuō)明了如何將本文給出的模型推廣到三維、甚至其它高維空間中相應(yīng)問(wèn)題的求解.對(duì)二維數(shù)據(jù)的算法測(cè)試時(shí),采用事先給定的數(shù)據(jù),即待搜索橢圓是確定的,實(shí)驗(yàn)發(fā)現(xiàn)粒子算法可以很快找到這個(gè)確定的橢圓.在三維數(shù)據(jù)的測(cè)試中,我們則采用程序隨機(jī)產(chǎn)生測(cè)試數(shù)據(jù)點(diǎn),發(fā)現(xiàn)粒子群算法同樣可以在很短的時(shí)間內(nèi)找到一個(gè)體積較小的橢球包含所有已知的數(shù)據(jù)點(diǎn).
總之,本文給出了一種用于求包含所有已知數(shù)據(jù)點(diǎn)的“面積”最小橢圓的粒子群算法.該算法模型十分簡(jiǎn)潔易懂,且搜索算法效果很理想.這也從一個(gè)側(cè)面說(shuō)明粒子群算法求解連續(xù)優(yōu)化問(wèn)題的強(qiáng)大能力.粒子群算法的優(yōu)勢(shì)在于簡(jiǎn)潔、高效.
值得指出的是,實(shí)際問(wèn)題中的分類問(wèn)題并非計(jì)算包含某一類別所有數(shù)據(jù)的最小橢圓.這是因?yàn)榉诸悊?wèn)題中的數(shù)據(jù)往往存在噪聲,真正的分類問(wèn)題需要將這些疑似噪聲的數(shù)據(jù)排除在外,然后再構(gòu)造這樣的橢圓.
[參考文獻(xiàn)]
[1]鄧乃揚(yáng),田英杰.支持向量機(jī)-理論、算法與拓展[M].北京:科學(xué)出版社,2009.
[2]汪定偉,王俊偉,等.智能優(yōu)化方法[M].北京:高等教育出版社,2007.
[3]Duds R O, Hart P E, Stork D G . Pattern Classification[M] . New York: John Wiley and Sons, 2001.
A Case Teaching PSO Algorithm
——to Construct the Least Ellipse Covering All the Datas
DAILi,XIEZheng,LIJian-ping
(College of Science, National University of Defense Technology, Changsha 410073, China)
Abstract:Modern optimize methods are rooted in solving large-scale projects, and tis rapidly progress is owed to solving the large-scale projects, too. It is necessarily to introduce case teaching for the class of modern methods. The paper provided a case which is about how to construct the least ellipse covering all datas using PSO algorithm. This case is widely used in the field of pattern identification.
Key words:PSO; case teaching; pattern identification
[收稿日期]2014-11-12
[中圖分類號(hào)]TP18
[文獻(xiàn)標(biāo)識(shí)碼]C
[文章編號(hào)]1672-1454(2015)01-0081-05