戴　麗，　謝　政，　李建平

(國(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)題.

3.1　個(gè)體編碼

問(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的取值.

3.2　種群的初始化

由于粒子個(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ì)值.本文取

3.3　適應(yīng)值函數(shù)

評(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仿真算例

4.1　實(shí)驗(yàn)數(shù)據(jù)

為了驗(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)分別為

4.2　實(shí)驗(yà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維空間.

5.1　n維數(shù)據(jù)分類問(wèn)題的數(shù)學(xué)模型

在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盡可能小.

5.2　仿真實(shí)驗(yàn)

以三維數(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