多目標粒子群算法的影響因素及改進策略

魯欣欣　王淮冬

摘 要：粒子群算法獨特的運算結構和出色的收斂速度被用于各行各業(yè)解決優(yōu)化問題。如今生產模式智能化的速度加快，單目標的粒子群算法已經無法滿足各行業(yè)對算法優(yōu)化的需求，粒子群算法的多目標優(yōu)化應運而生，通過對算法改進實現(xiàn)了粒子群算法解決多目標優(yōu)化問題，但解決多目標優(yōu)化的同時，影響粒子群算法的因素也增多了。文章重點介紹了多目標粒子群算法的影響因素和改進策略。

關鍵詞：粒子群算法;多目標;改進策略

0 ? 引言

多目標粒子群算法在解決多變量的優(yōu)化問題時也加大了算法本身的運算難度，并且影響運算結果的因素也多于單目標粒子群算法。本文主要對多目標粒子群算法的影響因素進行研究闡述，并介紹改進辦法。對多目標粒子群算法運算中遇到主要問題進行分析，并介紹幾種解決算法問題的方法和途徑。

1 基本粒子群算法

PSO基于群體的隨機優(yōu)化，通過一組隨機解初始化，通過迭代搜尋最優(yōu)解。PSO模擬社會，每個可能產生的解表述成群里的一個微粒，每個粒子有屬于自己的最佳速度和最佳位置，以及一個由目標函數(shù)決定的適應度。所有粒子在搜索空間中以一定速度飛行或在規(guī)定的速度范圍變速飛行，以最快的速度追隨當前空間內搜尋到的最優(yōu)值來確定全局最優(yōu)值[1]。具體算法的流程如圖1所示。

速度更新公式為：

vi（t）=w*vi-1（t-1）+c1*r1（xpbest（t-1）-xi（t-1））+c2*r2（xgbest（t-1）-xi（t-1））

位置更新公式為：

xi（t）=xi（t-1）+vi（t）

公式中各算子的含義：

（1）w：慣性權重（為大于零的數(shù)，w越接近0，收斂優(yōu)化越快，取值范圍一般為[0.4，0.8]）。

（2）c1，c2：個體學習因子、群體學習因子（取值范圍[0，4]，一般取值為2）。

（3）r1，r2：兩個隨機函數(shù)，取值范圍[0，1]，以增加更新速度的隨機性。

（4）pbest：個體經歷的最佳位置。

（5）gbest：全局最佳位置。

2 多目標粒子群算法

多目標的粒子群算法主要分為以下六類：復合加權粒子群算法、字典排序粒子群算法、帶有子種群的粒子群算法、基于Pareto方法的粒子群算法、混雜的粒子群算法、其他創(chuàng)新型粒子群算法[2]。

目前的多目標粒子群算法大多采用Pareto最優(yōu)集的方法對多目標解進行尋優(yōu)運算，采用Pareto方法的多目標粒子群算法的運算框架已經成為一種固定的程序流程和理論方法。因為在多目標進化算法中已有成熟的處理相似問題的辦法，所以對這些方法進行有針對性的取舍可解決大部分多目標粒子群優(yōu)化的問題。

MOPSO算法的步驟：

（1）和單目標粒子群算法相同，初始化種群以及參數(shù)設置;

（2）將粒子帶入目標函數(shù)，求得各粒子的函數(shù)值;

（3）初始化各粒子位置以及速度，并用Pareto方法將解以集合的方式儲存;

（4）從集合中選取最優(yōu)值，并用核心更新公式將速度和位置進行更新;

（5）迭代出新的粒子參數(shù)再次帶入目標函數(shù)計算出新粒子的函數(shù)值;

（6）從集合中更新最優(yōu)值;

（7）更新外部儲存的集合;

（8）若沒有達到優(yōu)解的條件返回步驟（4）繼續(xù)運算，直到輸出符合條件的優(yōu)解。

當算法運用到多目標的優(yōu)化上，必然會遇到下面兩個問題。

（1）個體最優(yōu)解（pbest）的選擇問題。

對于單目標優(yōu)化來說選擇pbest，只需要對比一下就可以選擇出哪個較優(yōu)。但是對于多目標來說，兩個粒子的對比，并不能對比出哪個好一些。如果粒子的每個目標都要好的話，則該粒子更優(yōu)。若有些更好，有些更差的話，就無法嚴格地說哪個好些，哪個差些。

（2）全局最優(yōu)解（gbest）的選擇問題。

對于單目標在種群中只有一個最優(yōu)的個體。而對于多目標來說，最優(yōu)的個體有很多個。對粒子群算法來說，每個粒子只能選擇一個作為最優(yōu)的個體（領導者）。

為解決以上兩個問題，多目標粒子群算法（MOPSO）對于第一個問題的做法是在空間中隨機選擇相對優(yōu)秀粒子中的一個作為歷史最優(yōu)，因為多目標的前提下，無法通過嚴格的篩選機制選擇出真正的全局最優(yōu)粒子[3]。對于第二個問題，MOPSO則在最優(yōu)集里面根據粒子的疏密度選擇出全局最優(yōu)。盡量選擇空間中粒子較為稀少的位置作為“精英粒子”帶領其他粒子尋最優(yōu)解。

在設計多目標算法時，處理大部分的影響因素都可借鑒其他成熟的多目標智能算法的解決方法。例如選取個體最優(yōu)時，可用集合的優(yōu)解代替?zhèn)€體的優(yōu)解，或者隨機選擇，將中心放在全局優(yōu)解的選取上。所以處理全局最好位置的選取是MOPSO的重要影響因素，這一步驟也是MOPSO的重要設計環(huán)節(jié)。

對于全局最好位置的選取，研究者們提出了很多有效可行的方法。而最常用到的方法是通過選取領導粒子（也被稱為領袖粒子），將這樣的粒子當作全局的最優(yōu)解，領導其他粒子達到真正的全局最優(yōu)解。而每代的全局最優(yōu)粒子（領導粒子）的選擇主要分3個途徑。

一是通過以集合的方式選取。判斷所含粒子解較好的集合作為選取領導粒子的集，然后用網格法隨機選取粒子作為全局的最優(yōu)解。這種選取方式收斂快，容易使算法陷入局部最優(yōu)的境地。

二是引入兩個粒子群的方法選取。第一個粒子群用于計算粒子的更新速度，調整粒子群飛向全局最優(yōu)解，用另一個粒子群計算目標優(yōu)解，篩選出粒子群要跟隨的優(yōu)秀粒子。這種方法能選取更好的全局最優(yōu)解，但需要大量的數(shù)據作為鋪墊，不適用于數(shù)據量較少的優(yōu)化問題。

三是引入共享概念。可以共享少部分粒子，使他們先成為全局最好的粒子，也可以優(yōu)中選優(yōu)，經過二次篩選，選取全局最優(yōu);或者將適應度共享，根據適應度的值為每個粒子尋找最優(yōu)解。這種尋找全局最優(yōu)的方式比較靈活，不過需要對算法的運算結構進行改進，并且需要注意提高在收斂后期對全局的搜素速度。

3 改進與展望

針對不同領域的優(yōu)化問題，研究人員提出了很多具有針對性的改進方案，提高了MOPSO各方面的性能。預計將來，初代粒子的均衡性、算子的運算機邏輯、最優(yōu)粒子的選擇機制、粒子間信息共享的方式是多目標的粒子群算法優(yōu)化的主要方向。引進新的算法進化機制，提高算法處理復雜問題的能力和算法的運行效率也是改進MOPSO的有效途徑。

雖然MOPSO運用在調度方面已經有有效且成熟的方法策略，但在其他問題如路線選擇的優(yōu)化和多個智能算法組合優(yōu)化的問題上還有欠缺。由于粒子群算法中各粒子的速度和位置是跟隨迭代次數(shù)不斷更新的，是連續(xù)的變量，在求取靜態(tài)優(yōu)化問題時需要對算法的結構和參數(shù)進行更改才能應用。目前對于此方面提出的有效策略還需要繼續(xù)深入研究，創(chuàng)新改進方法。

[參考文獻]

[1]楊明軒.粒子群算法的改進及應用研究[D].長沙：湖南理工學院，2020.

[2]鄭友蓮，樊俊青.多目標粒子群優(yōu)化算法研究[J].湖北大學學報（自然科學版），2008（4）：351-355.

[3]馮茜，李擎，全威，等.多目標粒子群優(yōu)化算法研究綜述[J].工程科學學報，2020（3）：10.

（編輯 何 琳）

Influencing factors and improvement strategies of multi-objective particle swarm optimization algorithm

Lu Xinxin1， Wang Huaidong2

（1. Basic teaching and Research Department of Jilin University of business and technology， Changchun 130507， China; 2. School of electrical and electronic engineering， Changchun University of technology， Changchun 130012， China）

Abstract：Particle swarm optimization algorithm is used to solve optimization problems in all walks of life because of its unique operation structure and excellent convergence speed. Nowadays， the speed of intelligent production mode is accelerating， and the single objective particle swarm optimization algorithm can not meet the needs of various industries for algorithm optimization. The multi-objective optimization of particle swarm optimization algorithm is born. Through the improvement of the algorithm， the particle swarm optimization algorithm is realized to solve the multi-objective optimization problem， but while solving the multi-objective optimization， the factors affecting the particle swarm optimization algorithm are also increasing. This paper focuses on the influencing factors and improvement strategies of multi-objective particle swarm optimization algorithm.

Key words：particle swarm optimization; multi objective; improvement strategy

作者簡介：魯欣欣（1989— ），女，吉林四平人，助教，碩士研究生;研究方向：智能算法，大數(shù)據。