王先超， 韓　波，張開銀， 孫娓娓， 王春生， 王志剛，楊利峰

（阜陽師范學(xué)院 a.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院；b.計(jì)算機(jī)與信息工程學(xué)院；c.物理與電子工程學(xué)院；d.經(jīng)濟(jì)學(xué)院，安徽 阜陽，236037）

粒子群算法在求解數(shù)學(xué)建模最優(yōu)化問題中的應(yīng)用

王先超a， 韓波b，張開銀c， 孫娓娓a， 王春生a， 王志剛a，楊利峰d

（阜陽師范學(xué)院 a.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院；b.計(jì)算機(jī)與信息工程學(xué)院；c.物理與電子工程學(xué)院；d.經(jīng)濟(jì)學(xué)院，安徽 阜陽，236037）

最優(yōu)化問題是數(shù)學(xué)建模常見問題之一。本文探討了如何用群集智能算法粒子群算法求解最優(yōu)化問題。并分別通過無約束和有約束條件的最優(yōu)化問題實(shí)例來討論用粒子群算法求解這類問題的一般步驟。結(jié)果顯示PSO算法具有收斂速度快等優(yōu)勢。

粒子群算法；數(shù)學(xué)建模；局部最優(yōu)解；全局最優(yōu)解

作為聯(lián)系數(shù)學(xué)與工業(yè)的重要橋梁，數(shù)學(xué)建模是數(shù)學(xué)走向應(yīng)用的必經(jīng)途徑［1］。該項(xiàng)實(shí)踐教學(xué)不僅可以提高學(xué)生分析和解決問題的能力，應(yīng)用計(jì)算機(jī)及相關(guān)軟件的能力，而且還可以提高學(xué)生用數(shù)學(xué)語言表達(dá)客觀事物的能力、撰寫科技論文的能力、創(chuàng)新能力和團(tuán)結(jié)協(xié)作精神［2］。同時(shí)，數(shù)學(xué)建模實(shí)踐教學(xué)也是大學(xué)生素質(zhì)教育和能力培養(yǎng)的重要內(nèi)容［3］。因而，越來越受到人們的普遍重視。

在實(shí)際建模過程中，經(jīng)常對一些最優(yōu)化問題進(jìn)行求解。對于簡單的優(yōu)化問題如線性規(guī)劃和整數(shù)規(guī)劃可以用Lingo或Lindo［4］以及Matlab軟件求解。對一些較復(fù)雜的非線性規(guī)劃問題直接求解比較困難或?yàn)榈玫礁鼉?yōu)的解，需要使用現(xiàn)代智能優(yōu)化算法，包括模擬退火算法（Simulated Annealing）［5］、遺傳算法（Genetic Algorithms）［6］、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network）［7-8］、蟻群算法（AntColony Algorithms）［9］等。本文將重點(diǎn)討論如何用粒子群算法（Particle Swarm Optimization，PSO）算法求解數(shù)學(xué)建模中的優(yōu)化問題。

1　PSO算法簡介

PSO算法是一類基于群體迭代的智能隨機(jī)優(yōu)化算法［10-15］。它是由Kennedy和Eberhart對鳥類的群體覓食行為進(jìn)行建模和仿真結(jié)果中受到啟發(fā)而提出的一種魯棒性很強(qiáng)的仿生學(xué)優(yōu)化算法［10-11］。目前PSO算法已廣泛應(yīng)用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練［12-13］、模糊系統(tǒng)控制［14］以及其他的應(yīng)用領(lǐng)域［15］。在PSO算法中，優(yōu)化問題的每個(gè)可行解都是搜索空間中的一只鳥，稱其為“粒子”。每個(gè)粒子都具有兩個(gè)屬性——位置和速度，分別表示其在解空間中的解和解的變化速度。PSO算法首先通過隨機(jī)初始化一定數(shù)量的粒子（即隨機(jī)解）構(gòu)成粒子群，再利用迭代尋優(yōu)和進(jìn)化策略獲得問題的最優(yōu)解。每次迭代過程中以粒子位置對應(yīng)的函數(shù)值，一般稱其為適應(yīng)度，確定粒子的優(yōu)劣；每個(gè)粒子通過跟蹤兩個(gè)最優(yōu)解——全局最優(yōu)解和局部最優(yōu)解——來進(jìn)行位置和速度的更新。全局最優(yōu)解是指粒子群全體當(dāng)前尋找到的最優(yōu)解，局部最優(yōu)解是指單個(gè)粒子當(dāng)前找到的最優(yōu)解。

2　PSO算法求解最優(yōu)化問題

本節(jié)將首先討論用PSO算法求解最優(yōu)化問題的一般步驟，而后通過兩個(gè)實(shí)例來說明如何用PSO算法求解數(shù)學(xué)建模優(yōu)化問題。

2.1用PSO算法求解最優(yōu)化問題的一般步驟

假設(shè)目標(biāo)搜索空間的維度為D，其中有N個(gè)粒子組成的群體，第i個(gè)粒子的位置用一個(gè)D維矢量Pi=（Pi1，Pi2，…，PiD）表示，且Pij∈［Pjmin，Pjmax］，j= 1，…，D。

每個(gè)粒子的運(yùn)動速度也用一個(gè)D維矢量Vi= （Vi1，Vi2，…，ViD）表示，且Vij∈［Vjmin，Vjmax］，j=1，…，D。顯然，每個(gè)粒子的位置就是搜索空間中的一個(gè)解，將其代入目標(biāo)函數(shù)f而得到的函數(shù)值（在PSO算法中稱其為適應(yīng)度）可用于衡量解的優(yōu)劣。用PSO算法求解最優(yōu)化問題的一般步驟如下：

Step1：建立實(shí)際問題的數(shù)學(xué)模型，設(shè)其最優(yōu)化函數(shù)為f。

Step2：種群初始化。產(chǎn)生一個(gè)包含N個(gè)粒子的粒子群，其位置和速度分別為Pi和Vi，i=1，…，N。

Step3：計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值f（Pi）。

Step4：根據(jù)函數(shù)值，計(jì)算全局最優(yōu)值fgb和粒子位置D） 及每個(gè)粒子所經(jīng)歷過的最優(yōu)值fdb和粒子位置

Step5：根據(jù)公式（1）和（2），分別對每個(gè)粒子的速度和位置進(jìn)行更新。其中i=1，…，N，j=1，…，D，t為迭代次數(shù)，S1和S2為學(xué)習(xí)因子常數(shù)且非負(fù)，r1j和r2j為服從［0，1］上均勻分布且彼此獨(dú)立的隨機(jī)數(shù)。

Step6：判斷是否滿足終止條件。若滿足則輸出解，否則轉(zhuǎn)至Step3。

算法具體流程圖，如圖1所示。

圖1　PSO算法求解數(shù)學(xué)建模中最優(yōu)化問題流程圖

2.2用PSO算法求解無約束條件的最優(yōu)化模型

下面通過一個(gè)實(shí)例來說明如何用PSO算法求解無約束條件的最優(yōu)化問題。

2.2.1飛機(jī)定位問題

例1飛機(jī)在飛行過程中能夠根據(jù)接收到地面上各控制臺發(fā)來的飛機(jī)當(dāng)前位置信息，比較精確地確定其位置，如圖2所示。圖中VOR1-3為3個(gè)高頻多向?qū)Ш皆O(shè)備，它們能夠得到飛機(jī)與該設(shè)備連線的角度信息（以弧度表示）；DME為距離測量裝置，它能夠得到飛機(jī)與該設(shè)備的距離信息（以km為單位）。已知4種設(shè)備的坐標(biāo)（假設(shè)飛機(jī)與這些設(shè)備在同一平面），如何根據(jù)圖中信息精確地確定飛機(jī)的當(dāng)前位置？

2.2.2模型建立

設(shè)4種設(shè)備VOR1、VOR2、VOR3、DME的坐標(biāo)分別為（xi，yi），當(dāng)前飛機(jī)的位置為（x，y），VOR1、VOR2、VOR3測得的角度（從正北方向開始，沿順時(shí)針方向的弧度）分別為αi（i=1，2，3）。DME測得的距離為d，根據(jù)數(shù)據(jù)計(jì)算的角度和距離分別為βi（i=1，2，3）和d4，則上述問題即為根據(jù)圖2所給信息求（x，y）。

圖2　飛機(jī)與各控制臺位置信息圖

對VOR設(shè)備，可以根據(jù)下面的公式（3）計(jì)算βi的正切值

利用（3）和（4）確定飛機(jī)的位置坐標(biāo)，即是在最小二乘準(zhǔn)則下使計(jì)算值與測量值誤差的平方和最小。因此，目標(biāo)函數(shù)為

2.2.3模型求解

若使用Lingo軟件求解該模型，可得其目標(biāo)函數(shù)值為 71.085 17，飛機(jī)坐標(biāo)為（277.291 4，69.051 59）。顯然，它是一個(gè)局部最優(yōu)解。若啟動Lingo的“Use Global Solver”選項(xiàng)，可得目標(biāo)函數(shù)的全局最優(yōu)值為 0.058 167 08，飛機(jī)坐標(biāo)為（1 037.831，831.198）。下面將根據(jù)圖1所示的流程圖重點(diǎn)討論如何用PSO算法在Matlab平臺對該模型進(jìn)行求解。

(ⅱ )參數(shù)初始化

參數(shù)初始化包括兩個(gè)學(xué)習(xí)因子s1和s2、進(jìn)化次數(shù)Maxg、種群規(guī)模SizePop、初始速度上下邊界值Vmax和Vmin和種群上下邊界值Xmax、Xmin、Ymax和Ymin，并產(chǎn)生初始粒子位置Pop和速度V以及每個(gè)粒子的適應(yīng)度Fitness，相關(guān)Matlab代碼如下：

%隨機(jī)產(chǎn)生一個(gè)粒子包括位置、速度和適應(yīng)%度

其中fun函數(shù)根據(jù)（5）編寫，其代碼如下：

(ⅰ)最優(yōu)位置初始化

最優(yōu)位置是用粒子的適應(yīng)度值來衡量的。如前所述，最優(yōu)位置初始化包括每個(gè)粒子的最優(yōu)解初始化和所有粒子最優(yōu)解初始化，相關(guān)代碼如下：

迭代尋優(yōu)過程如下：首先運(yùn)用公式（1）和（2）對每一個(gè)粒子的速度和位置進(jìn)行更新，而后計(jì)算每個(gè)粒子的適應(yīng)度值，再根據(jù)適應(yīng)度值更新個(gè)體最優(yōu)和全局最優(yōu)；重復(fù)上述過程，直至迭代次數(shù)Maxg為0。相關(guān)Matlab代碼如下：

用PSO算法求解該模型的運(yùn)行結(jié)果：目標(biāo)函數(shù)值為 0.058 167 13、飛機(jī)坐標(biāo)為（1 037.82，831.12）。整個(gè)過程中適應(yīng)度的變化如圖3所示?？梢钥闯鍪諗克俣仍诘螖?shù)大概小于8次時(shí)很快，之后就比較慢，當(dāng)?shù)螖?shù)達(dá)到61次左右時(shí)適應(yīng)度值基本不再改變。而上述用Lingo求解時(shí)迭代次數(shù)達(dá)到數(shù)萬次。由此可見，用PSO算法求解最優(yōu)化問題具有算法收斂速度快的優(yōu)點(diǎn)。

2.3用PSO算法求解有約束條件的最優(yōu)化模型

例2用PSO算法求解下面具有約束條件的非線性規(guī)律。

在例1的基礎(chǔ)上，用PSO算法求解該問題時(shí)只需對上述代碼稍作修改即可。需要修改的主要內(nèi)容包括重新定義目標(biāo)函數(shù)fun、種群的上下邊界值、迭代尋優(yōu)過程中適應(yīng)度值Fitness的計(jì)算。

圖3　用PSO算法求解飛機(jī)定位問題適應(yīng)度值隨迭代次數(shù)變化圖

fun函數(shù)的定義如下：

根據(jù)約束條件，假設(shè)種群中變量x1和x2的上下邊界相同均為20和0，即相關(guān)代碼為Max=20；Min=0；將例1中適應(yīng)度Fitness的計(jì)算代碼Fitness（j）=fun （Pop（j，：））；用下面帶約束條件的代碼替換

程序的運(yùn)行結(jié)果為：當(dāng)x1=0，x2=0時(shí)的目標(biāo)函數(shù)值為0。由目標(biāo)函數(shù)的圖像圖4可知，該結(jié)果為該非線性規(guī)劃問題的全局最優(yōu)解。當(dāng)然，迭代次數(shù)和種群規(guī)模也可以修改。

圖4　的圖像

3　小結(jié)

本文首先簡單介紹了作為一種群集智能算法的PSO算法，而后通過兩個(gè)具體實(shí)例說明如何使用它解決數(shù)學(xué)建模過程中經(jīng)常遇到的最優(yōu)化問題。從中可以看出PSO算法具有收斂速度快優(yōu)勢。收斂速度的快慢以及能否收斂于全局最優(yōu)解主要取決于種群的規(guī)模。也就是說，為了得到全局最優(yōu)解，種群的規(guī)模不能太小；否則，得到的可能是局部最優(yōu)解。此外，本文討論的PSO算法不能解決像TSP那樣的離散最優(yōu)化問題。要用PSO算法解決TSP等離散最優(yōu)化問題需要對它進(jìn)行改進(jìn)，使其成為離散PSO算法。

［1］ 李大潛.數(shù)學(xué)建模的教育是數(shù)學(xué)與工業(yè)間最重要的教育界面［J］.數(shù)學(xué)建模及其應(yīng)用，2012，1（1）：38-41.

［2］ 孫樹東.數(shù)學(xué)建模融入大學(xué)數(shù)學(xué)相關(guān)實(shí)踐分析［J］.長春大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，24（2）：542-544.

［3］ 李大潛.數(shù)學(xué)建模與素質(zhì)教育［J］.中國大學(xué)教學(xué)，2002（10）：41-43.

［4］ 謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件［M］.北京：清華大學(xué)出版社，2006.

［5］ Wah B W，Chen Y X，Wang T.Simulated annealing with asymptotic convergence for nonlinear constrained optimization［J］.Journal of Global Optimization，2007，39（1）：1-37.

［6］ Gopalakrishnan H，Kosanovic D.Operational planning of combined heat and power plants through genetic algorithms for mixed 0-1 nonlinear programming［J］. Computers&Operations Research，2015，56：51-67.

［7］ Effati S，Ranjbar M.A novel recurrent nonlinear neural network for solving quadratic programming problems［J］.Applied Mathematical Modelling，2011，35 （4）：1688-1695.

［8］ Nazemi A.A neural network model for solving convex quadratic programming problems with some applications［J］.Engineering Applications of Artificial Intelligence，2014，32：54-62.

［9］ Schlüter M，Egea J A，Banga J R.Extended ant colony optimization for non-convex mixed integer nonlinear programming［J］.Computers&Operations Research，2009，36（7）：2217-2229.

［10］Kennedy J，Eberhart R C.Particle swarm optimization ［C］//Proceedings of IEEE International Conference on Neural Networks，1995：1942-1948.

［11］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］//Micro Machine and Human Science，1995.MHS'95.，Proceedings of the Sixth International Symposium on.Nagoya，Japan，1995：39-43.

［12］Green I R，Wang L F，Alam M.Training neural networks using Central Force Optimization and Particle Swarm Optimization：Insights and comparisons［J］.Expert Systems WithApplications，2012，39（1）：555-563.

［13］Tsekouras G E，Tsimikas J.On training RBF neural networks using input-output fuzzy clustering and particle swarm optimization［J］.Fuzzy Sets and Systems，2013，221：65-89.

［14］Siano P，Citro C.Designing fuzzy logic controllers for DC-DC converters using multi-objective particle swarm optimization［J］.Electric Power Systems Research，2014，112：74-83.

［15］Cai Q，Gong M G，Ma L J，et al.Greedy discrete particle swarm optimization for large-scale social network clustering［J］.Information Sciences，2015，316：503-516.

Application of particle swarm optimization to solve optimization problem in mathematics modeling

WANG Xian-chaoa，HAN Bob，ZHANG Kai-yinc，SUN Wei-weia，WANG Chun-shenga， WANG Zhi-ganga， YANG Li-fengd

（a.School of Mathematics and Statistics；b.School of Computer and Imformation Engineering；c.School of Physics and Electronic Engineering；d.School of Economics，F(xiàn)uyang Normal University，F(xiàn)uyang Anhui 236037，China）

Optimization problem is one of the common problems of mathematical modeling.This paper explores how to solve these problems by the use of the particle swarm optimization（PSO）algorithm.At the same time，it discusses the general steps to solve optimization problems by PSO，demonstrating two examples with unconstrained and constrained conditions，respectively.The results illustrate that PSO has the advantages such as fast convergence rate.

particle swarm optimization；mathematics modeling；locally optimal solution；globally optimal solution

G652

A

1004-4329（2016）02-117-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）02-117-05

2015-08-20

安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目（KJ2015A191，KJ2015A182）；安徽省質(zhì)量工程項(xiàng)目（2014zy138）；阜陽師范學(xué)院質(zhì)量工程項(xiàng)目（2013ZYSD05，2014JXTD01）資助。

王先超（1973－），男，博士，副教授，研究方向：光計(jì)算與數(shù)學(xué)建模。