基于余弦距離的多目標粒子群優(yōu)化算法

方欣欣,龔如賓,李大為

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海　200093)

?

基于余弦距離的多目標粒子群優(yōu)化算法

方欣欣,龔如賓,李大為

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海200093)

摘要針對粒子群優(yōu)化算法具有的個體分布不均勻以及重復(fù)個體較多等缺陷,提出了一種基于余弦距離的多目標粒子群優(yōu)化算法,該算法根據(jù)外部精英存儲策略,利用余弦距離排擠機制來選取最分散的粒子,擴大 Pareto最優(yōu)解集的收斂性和多樣性,增強算法的全局尋優(yōu)能力。通過采用標準多目標優(yōu)化問題ZDTl～ZDT3進行仿真實驗與粒子群算法、混沌粒子群算法、基于擁擠距離的多目標優(yōu)化算法對比表明,該算法在Pareto前沿的收斂性和多樣性方面均優(yōu)于基于擁擠距離排擠機制,并具有較高的效率。

關(guān)鍵詞余弦距離;擁擠距離;多目標優(yōu)化;粒子群;非支配解

Multi-objective Particle Swarm Optimization Algorithm Based on Cosine Distance

FANG Xinxin,GONG Rubin,LI Dawei

(School of Optica1-Electrical & Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractA multi-objective particle swarm optimization (PSO) algorithm based on cosine distance is proposed to tackle the drawbacks such as uneven individual distribution redundant overlapping individuals existing in standard particle swarm optimization.Based upon external elite storage strategy,this algorithm utilizes cosine distance crowing mechanism to select the most widely distributed particles.It amplifies the convergence and diversity of best solution set and strengthens the capacity of global optimization.Standard multi-objective optimization ZDTl~ZDT3 are adopted in simulation experiments to compare the proposed algorithm with the particle swarm optimization,chaos particle swarm optimization and multi-objective optimization algorithm based on crowing mechanism.Results show that the proposed algorithm not only outperforms other algorithms in terms of Pareto’s frontier convergence and diversity but also obtains preferable efficiency.

Keywordscosine distance;crowding distance;multi-objective optimization;particle swarm;non-dominated solutions

在科學(xué)研究和工程實踐中,常會遇到多目標優(yōu)化問題,如旅行商[1],多播路由[2],車間調(diào)度[3]等。解決多目標問題(Multi-Object Problem,MOP)的方法一般分為兩類:第一類統(tǒng)稱為“目標歸一法”[4],這類求解方法按某種策略確定多個目標之間的權(quán)衡方式,將多目標問題轉(zhuǎn)換為單目標優(yōu)化問題,并用這些單目標優(yōu)化問題最優(yōu)解構(gòu)成的解集去近似MOP的Pareto最優(yōu)集。該類方法包括權(quán)值法、約束法、目標規(guī)劃法等。運用該類方法需要事先已知目標信息,從而在目標之間建立聯(lián)系,因此在求解許多工程問題上具有極限性。第二類是多目標進化算法(Multi-Object Evaluation Algorithm,MOEA),MOEA 無需事先充分了解各目標的詳細信息,而是在搜索空間內(nèi)獲得一組Pareto最優(yōu)解來權(quán)衡各個目標?！?br>