戴　麗，　謝　政，　李建平

(國防科學(xué)技術(shù)大學(xué)理學(xué)院，湖南長沙410073)

?

粒子群算法課堂教學(xué)案例——求包含所有已知數(shù)據(jù)點(diǎn)的最小橢圓

戴麗，謝政，李建平

(國防科學(xué)技術(shù)大學(xué)理學(xué)院，湖南長沙410073)

[摘要]“現(xiàn)代優(yōu)化方法”來源于各種大規(guī)模的工程實(shí)際問題的求解，也正是在工程實(shí)踐問題的求解過程中得到不斷發(fā)展。在該課程的教學(xué)中有必要引入案例。本文以粒子群算法為例，介紹本課程的一個教學(xué)案例：如何求包含所有已知數(shù)據(jù)點(diǎn)的最小橢圓。該案例在模式識別中有重要的應(yīng)用.

[關(guān)鍵詞]粒子群算法； 教學(xué)案例； 模式識別

1案例背景

美國Cleveland Heart Disease Database 提供了303個心臟病人的有關(guān)數(shù)據(jù)信息[1].該數(shù)據(jù)庫記錄了這些病人的血壓(低壓)、膽固醇等13項(xiàng)與心臟病有關(guān)的指標(biāo)，同時，也記錄了這些病人是否患有心臟病的確診結(jié)論.現(xiàn)在的問題是如何根據(jù)這些數(shù)據(jù)對新來的病人只通過檢查這13項(xiàng)指標(biāo)，就推斷該病人是否患有心臟病.該問題是病人患病確診問題.本質(zhì)上是分類問題，也稱為模式識別問題.

假設(shè)只考察是否患有心臟病與人的血壓(低壓)[x]1和膽固醇[x]2這兩項(xiàng)指標(biāo)的關(guān)系.用“+”表示有心臟病，用“o”表示無心臟病.如果10個病人的數(shù)據(jù)如圖1所示，則此時，可用一條直線(圖中的粗線)將兩部分?jǐn)?shù)據(jù)分開.但當(dāng)數(shù)據(jù)如圖2所示時，則無法用一條直線將兩部分?jǐn)?shù)據(jù)分開，用一個橢圓(圖中的粗線部分)區(qū)分兩種數(shù)據(jù).也就是說，此時，需要構(gòu)造一個包括所有“o”型數(shù)據(jù)點(diǎn)的面積最小的橢圓.這是一非線性劃分問題.

圖1　用直線區(qū)分?jǐn)?shù)據(jù)　　　　 圖2　用橢圓區(qū)分?jǐn)?shù)據(jù)

患病確診問題是本文的應(yīng)用之一.實(shí)際上，在模式識別問題中經(jīng)常需要構(gòu)造這樣的橢圓.對于非線性劃分問題，通常的做法是采用支持向量機(jī)，即構(gòu)造核函數(shù)，并求解相應(yīng)的二次規(guī)劃問題.也可以借助于一些商業(yè)軟件，如Halcon等解決該問題.本文則將現(xiàn)代優(yōu)化算法應(yīng)用于非線性劃分問題，給出一個求面積最小橢圓的粒子群算法.該算法不需要構(gòu)造核函數(shù)，也不需要函數(shù)的解析性質(zhì).因此，可廣泛應(yīng)用于問題的求解.

2問題的數(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)，以橢圓對稱軸為坐標(biāo)軸，建立一個新坐標(biāo)系XOY.XOY可由xoy經(jīng)過旋轉(zhuǎn)、平移得到.設(shè)旋轉(zhuǎn)的角度為θ.設(shè)橢圓的兩個半軸長分別為A和B.于是，所求橢圓在XOY坐標(biāo)系中方程為標(biāo)準(zhǔn)方程

(1)

且

圖3　坐標(biāo)的建立及參數(shù)說明

(2)

由此可見，只要確定a，b，θ，A，B的值，橢圓的方程就相應(yīng)確定.

要尋找一個包含所有已知數(shù)據(jù)點(diǎn)且面積最小的橢圓，每個已知數(shù)據(jù)點(diǎn)(x，y)代入(2)中得到的(X，Y)滿足

(3)

的前提條件下，使得橢圓的面積πAB盡可能小.

3粒子群算法求解問題

粒子群(Particle Swarm Optimization， PSO)算法是由Kennedy和Eberhart于1995年提出的.它與蟻群算法一樣，也是通過模擬動物的群體行為來求解優(yōu)化問題.PSO簡單易行、收斂速度快、設(shè)置參數(shù)少，在各種優(yōu)化問題中都有著良好的表現(xiàn)，其天然的實(shí)數(shù)編碼特點(diǎn)使其尤其適合于處理實(shí)優(yōu)化問題.PSO已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點(diǎn).

在PSO中，每個優(yōu)化問題的解看作搜索空間中的一只鳥，稱之為“粒子”.算法由多個隨機(jī)產(chǎn)生的粒子(即隨機(jī)解)組成的群體開始.每個粒子都被賦予一個由優(yōu)化函數(shù)確定的適應(yīng)值.每個粒子還有一個速度決定它們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.在搜索時，每個粒子通過跟蹤兩個“極值”來進(jìn)行位置(狀態(tài)、也就是解)的變化，一個是粒子個體本身所找到的歷史最優(yōu)解，另一個是群體內(nèi)(或鄰域內(nèi))其他粒子的歷史最優(yōu)解，以使粒子能夠飛向解空間，并在最優(yōu)解處降落.

設(shè)第i個粒子的位置為：xi=(xi1，xi2，…，xin)；

第i個粒子的速度為：vi=(vi1，vi2，…，vin)；

第i個粒子經(jīng)歷過的歷史最優(yōu)解為：Pi=(pi1，pi2，…，pin)；

群體內(nèi)(或鄰域內(nèi))所有粒子所經(jīng)歷過的歷史最優(yōu)解為：Pg=(pg1，pg2，…，pgn).

一般來說，粒子的位置和速度都是在連續(xù)的實(shí)數(shù)空間內(nèi)取值.在找到了兩個“極值”后，每個粒子根據(jù)如下公式來更新自己的速度和位置：

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)秀個體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)解及群體內(nèi)或鄰域內(nèi)的歷史最優(yōu)解靠近.c1和c2通常取為2.ξ和η是在[0，1]區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù).c0稱為慣性因子，其大小決定了粒子對當(dāng)前速度繼承的多少，合適的選擇c0的值可以使粒子具有均衡的廣域搜索能力(即探索能力)和局部搜索能力(即開發(fā)能力).粒子的速度被限制在一個最大速度Vmax的范圍內(nèi).

下面介紹如何用PSO求解最小橢圓的構(gòu)造問題.

3.1　個體編碼

問題解的表達(dá)方式，稱為編碼方法，也就是將實(shí)際問題的解用一種便于算法操作的形式來描述.實(shí)際應(yīng)用中，應(yīng)當(dāng)根據(jù)問題本身的特點(diǎn)和所使用的優(yōu)化算法而采用不同的編碼方法.在算法結(jié)束時，還需要通過解碼還原到實(shí)際問題的解.由問題的數(shù)學(xué)描述可見，問題的關(guān)鍵在于合理確定

a，b，θ，A，B

的值.因此，本文采用五維向量(x1，x2，x3，x4，x5)表示粒子個體，各分量分別為a，b，θ，A，B的取值.

3.2　種群的初始化

由于粒子個體的不同分量表示橢圓的不同參數(shù)，因此，各分量應(yīng)分別在其各自區(qū)域內(nèi)初始化.

設(shè)xmin，xmax分別表示已知數(shù)據(jù)點(diǎn)的x軸分量的最小值、最大值；ymin，ymax分別表示已知數(shù)據(jù)點(diǎn)的y軸分量的最小值、最大值.粒子的第一個分量x1應(yīng)初始化為區(qū)間[xmin，xmax]內(nèi)的隨機(jī)數(shù)，粒子的第二個分量x2應(yīng)初始化為區(qū)間[ymin，ymax]內(nèi)的隨機(jī)數(shù).粒子的第三個分量x3應(yīng)在[0，2π)內(nèi)取值.粒子的第四、五個分量x4，x5均在[0，D]內(nèi)取值，其中D為數(shù)據(jù)點(diǎn)間的最大距離.當(dāng)數(shù)據(jù)較大，計(jì)算所有數(shù)據(jù)點(diǎn)的最大距離比較困難，這時也可取D為最大數(shù)據(jù)點(diǎn)間距離的估計(jì)值.本文取

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

評價解的優(yōu)劣的函數(shù)，稱為適應(yīng)值函數(shù).實(shí)際應(yīng)用中，對目標(biāo)函數(shù)的任何變形都可作為適應(yīng)值函數(shù)，但注意這個變形必須保證與原目標(biāo)函數(shù)的大小順序，即這個變形必須是嚴(yán)格單調(diào)的.適應(yīng)值函數(shù)的確定原則是要便于算法的執(zhí)行和算法效率的提高.

對于本文研究的問題，顯然，當(dāng)粒子個體滿足條件(3)時，其適應(yīng)值應(yīng)為πAB；當(dāng)粒子個體不滿足條件(3)時，意味著該粒子個體不是問題的可行解，定義其適應(yīng)值為+.粒子個體的適應(yīng)值越小，說明粒子個體越優(yōu)秀.

4仿真算例

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

為了驗(yàn)證算法的有效性.我們以如下方式生成已知數(shù)據(jù)點(diǎn).首先數(shù)據(jù)點(diǎn)中包含橢圓的四個頂點(diǎn)(也就是說，待求橢圓已確定)，然后在橢圓內(nèi)隨機(jī)生成其它的數(shù)據(jù)點(diǎn).

設(shè)待求橢圓的中心為(2，2)；由xOy旋轉(zhuǎn)45o得XOY坐標(biāo)系；設(shè)其長、短半軸長分別為2，1.于是，其四個頂點(diǎn)分別為

4.2　實(shí)驗(yàn)效果

算法中取慣性因子c0=0.1，兩個學(xué)習(xí)因子c1=c2=2.種群規(guī)模N=100，迭代10000次.算法用6.346秒時間搜索到

橢圓中心(2.00109，1.9992)；旋轉(zhuǎn)角度θ=0.764；

長半軸為2；短半軸為1.

如圖4所示，從圖中可以看出，算法得到了較理想的結(jié)果.

圖4　實(shí)驗(yàn)效果

5推廣

從仿真算法的實(shí)驗(yàn)效果可以看出，本文給出的算法不需要構(gòu)造核函數(shù)，算法模型十分簡潔，且效果理想.不僅如此，本文給出的算法模型可以推廣到一般的n維空間.

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

在n維空間直角坐標(biāo)系中，標(biāo)準(zhǔn)橢球方程為

相應(yīng)的“體積”與A1A2…An的值成正比.設(shè)H為n階正交矩陣，b為一個n維列向量，設(shè)

X=H(x-b)，

(4)

于是，要尋找一個包含所有已知數(shù)據(jù)點(diǎn)且“體積”最小的橢圓，也就是要確定一個正交矩陣H，以及一個列向量b，在每個已知數(shù)據(jù)點(diǎn)(x，y)代入(4)中得到的X都有

(5)

成立的前提條件下，使A1A2…An盡可能小.

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

以三維數(shù)據(jù)為例說明.隨機(jī)生成測試數(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　測試數(shù)據(jù)點(diǎn)分布圖

算法中取慣性因子c0=0.1，兩個學(xué)習(xí)因子c1=c2=2.種群規(guī)模N=2000，迭代100次.歷時 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ù)據(jù)、H、b以及(A1，A2，A3)的值代入(5)式的左邊，各點(diǎn)對應(yīng)的值如表1所示.從表1中可以看出，p1，p4和p6這三個測試數(shù)據(jù)點(diǎn)對應(yīng)的值都在0.95以上，已經(jīng)很接近(5)式右邊的1.這說明所得橢球的體積已經(jīng)比較小，改進(jìn)的余地已不大.

表1　效果分析

綜合以上實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)，粒子群算法在11.6秒內(nèi)即可得到較好的搜索效果.

6總結(jié)

文中以二維數(shù)據(jù)為例建模，說明了如何將本文給出的模型推廣到三維、甚至其它高維空間中相應(yīng)問題的求解.對二維數(shù)據(jù)的算法測試時，采用事先給定的數(shù)據(jù)，即待搜索橢圓是確定的，實(shí)驗(yàn)發(fā)現(xiàn)粒子算法可以很快找到這個確定的橢圓.在三維數(shù)據(jù)的測試中，我們則采用程序隨機(jī)產(chǎn)生測試數(shù)據(jù)點(diǎn)，發(fā)現(xiàn)粒子群算法同樣可以在很短的時間內(nèi)找到一個體積較小的橢球包含所有已知的數(shù)據(jù)點(diǎn).

總之，本文給出了一種用于求包含所有已知數(shù)據(jù)點(diǎn)的“面積”最小橢圓的粒子群算法.該算法模型十分簡潔易懂，且搜索算法效果很理想.這也從一個側(cè)面說明粒子群算法求解連續(xù)優(yōu)化問題的強(qiáng)大能力.粒子群算法的優(yōu)勢在于簡潔、高效.

值得指出的是，實(shí)際問題中的分類問題并非計(jì)算包含某一類別所有數(shù)據(jù)的最小橢圓.這是因?yàn)榉诸悊栴}中的數(shù)據(jù)往往存在噪聲，真正的分類問題需要將這些疑似噪聲的數(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

[中圖分類號]TP18

[文獻(xiàn)標(biāo)識碼]C

[文章編號]1672-1454(2015)01-0081-05