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

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

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

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

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

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

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

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

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

在實際建模過程中，經(jīng)常對一些最優(yōu)化問題進行求解。對于簡單的優(yōu)化問題如線性規(guī)劃和整數(shù)規(guī)劃可以用Lingo或Lindo［4］以及Matlab軟件求解。對一些較復(fù)雜的非線性規(guī)劃問題直接求解比較困難或為得到更優(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］等。本文將重點討論如何用粒子群算法（Particle Swarm Optimization，PSO）算法求解數(shù)學(xué)建模中的優(yōu)化問題。

1　PSO算法簡介

PSO算法是一類基于群體迭代的智能隨機優(yōu)化算法［10-15］。它是由Kennedy和Eberhart對鳥類的群體覓食行為進行建模和仿真結(jié)果中受到啟發(fā)而提出的一種魯棒性很強的仿生學(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)化問題的每個可行解都是搜索空間中的一只鳥，稱其為“粒子”。每個粒子都具有兩個屬性——位置和速度，分別表示其在解空間中的解和解的變化速度。PSO算法首先通過隨機初始化一定數(shù)量的粒子（即隨機解）構(gòu)成粒子群，再利用迭代尋優(yōu)和進化策略獲得問題的最優(yōu)解。每次迭代過程中以粒子位置對應(yīng)的函數(shù)值，一般稱其為適應(yīng)度，確定粒子的優(yōu)劣；每個粒子通過跟蹤兩個最優(yōu)解——全局最優(yōu)解和局部最優(yōu)解——來進行位置和速度的更新。全局最優(yōu)解是指粒子群全體當前尋找到的最優(yōu)解，局部最優(yōu)解是指單個粒子當前找到的最優(yōu)解。

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

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

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

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

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

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

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

Step3：計算每個粒子的目標函數(shù)值f（Pi）。

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

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

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

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

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

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

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

2.2.1飛機定位問題

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

2.2.2模型建立

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

圖2　飛機與各控制臺位置信息圖

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

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

2.2.3模型求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4　的圖像

3　小結(jié)

本文首先簡單介紹了作為一種群集智能算法的PSO算法，而后通過兩個具體實例說明如何使用它解決數(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)化問題需要對它進行改進，使其成為離散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)實踐分析［J］.長春大學(xué)學(xué)報（自然科學(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é)研究重點項目（KJ2015A191，KJ2015A182）；安徽省質(zhì)量工程項目（2014zy138）；阜陽師范學(xué)院質(zhì)量工程項目（2013ZYSD05，2014JXTD01）資助。

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