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

戴　麗，　謝　政，　李建平

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

?

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

戴麗，謝政，李建平

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

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

[關鍵詞]粒子群算法； 教學案例； 模式識別

1案例背景

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

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

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

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

2問題的數(shù)學描述

以二維數(shù)據(jù)為例.如圖3所示，設數(shù)據(jù)點所在的坐標系為xoy坐標系.設所求橢圓中心在xoy坐標系中為點(a，b).以橢圓的中心(a，b)為坐標原點，以橢圓對稱軸為坐標軸，建立一個新坐標系XOY.XOY可由xoy經(jīng)過旋轉(zhuǎn)、平移得到.設旋轉(zhuǎn)的角度為θ.設橢圓的兩個半軸長分別為A和B.于是，所求橢圓在XOY坐標系中方程為標準方程

(1)

且

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

(2)

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

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

(3)

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

3粒子群算法求解問題

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

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

設第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ù)空間內(nèi)取值.在找到了兩個“極值”后，每個粒子根據(jù)如下公式來更新自己的速度和位置：

vk+1=c0vk+c1ξ(pk-xk)+c2η(pg-xk)，

xk+1=xk+vk+1，

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

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

3.1　個體編碼

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

a，b，θ，A，B

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

3.2　種群的初始化

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

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

3.3　適應值函數(shù)

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

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

4仿真算例

4.1　實驗數(shù)據(jù)

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

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

4.2　實驗效果

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

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

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

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

圖4　實驗效果

5推廣

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

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

在n維空間直角坐標系中，標準橢球方程為

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

X=H(x-b)，

(4)

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

(5)

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

5.2　仿真實驗

以三維數(shù)據(jù)為例說明.隨機生成測試數(shù)數(shù)點為

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ù)點在三維空間中的分布如圖5.

圖5　測試數(shù)據(jù)點分布圖

算法中取慣性因子c0=0.1，兩個學習因子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)式的左邊，各點對應的值如表1所示.從表1中可以看出，p1，p4和p6這三個測試數(shù)據(jù)點對應的值都在0.95以上，已經(jīng)很接近(5)式右邊的1.這說明所得橢球的體積已經(jīng)比較小，改進的余地已不大.

表1　效果分析

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

6總結

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

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

值得指出的是，實際問題中的分類問題并非計算包含某一類別所有數(shù)據(jù)的最小橢圓.這是因為分類問題中的數(shù)據(jù)往往存在噪聲，真正的分類問題需要將這些疑似噪聲的數(shù)據(jù)排除在外，然后再構造這樣的橢圓.

[參考文獻]

[1]鄧乃揚，田英杰.支持向量機-理論、算法與拓展[M].北京：科學出版社，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

[文獻標識碼]C

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