朱 君 蔡延光 湯雅連 楊 軍

多目標優(yōu)化問題的研究

朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學 自動化學院，廣州 510006）

針對傳統(tǒng)方法求解多目標優(yōu)化問題的局限性，應用一種新的算法求解。遺傳算法從問題解的串集開始搜索，覆蓋面大，可以同時處理群體中的多個個體，利于全局擇優(yōu)，減少陷入局部最優(yōu)的風險，而最小生成樹具有過程簡單清晰、適用性廣泛的特點，結合兩者的優(yōu)點，構造了基于生成樹的遺傳算法。首先通過加權目標規(guī)劃法求出最優(yōu)解，然后通過遺傳算法和基于生成樹的遺傳算法求解，結果表明，對于小規(guī)模的多目標優(yōu)化問題，兩種算法都可以求出最優(yōu)解，在求解時間方面，基于生成樹的遺傳算法比遺傳算法更優(yōu)越。

多目標優(yōu)化問題；最小生成樹；遺傳算法

在現(xiàn)實生活中，某個設計方案只要求某一項目標達到最優(yōu)，這是單目標優(yōu)化問題。如果設計方案期望某幾項指標均能達到最優(yōu)值，這樣的問題就稱為多目標優(yōu)化設計問題。比如廠家生產某種產品，既要求投入資金少，工人少，降低成本，又要工作效率高，利潤高，這就是一個多目標優(yōu)化問題?，F(xiàn)實生活中，多目標優(yōu)化問題［1］中的各個子目標一般是相互矛盾的，也就是同時使所有子目標都達到最優(yōu)是不可能的，最終目標是盡最大可能達到最優(yōu)化，它的解并不是唯一的，而是由多個最優(yōu)解組成的滿意解，集合中的各個元素稱為Pareto最優(yōu)解或非劣最優(yōu)解。由于該問題模型在現(xiàn)實生活中普遍存在，所以本文研究的多目標優(yōu)化問題具有實際應用意義。

目前，多目標優(yōu)化問題也得到了廣泛的研究。謝濤等人［2］介紹了基于Pareto最優(yōu)概念的多目標演化算法中的主要技術和理論結果，詳細介紹了基于偏好的個體排序、適應值賦值及共享函數(shù)等。王躍宣等人［3］考慮了對約束條件的處理問題，提出了求解帶約束的多目標優(yōu)化遺傳算法，利用鄰域比較與存檔操作遺傳算法處理多個相互沖突的目標的優(yōu)化；馬瑞等人［4］提出了解決多目標優(yōu)化問題的新方法和綜合考慮水火協(xié)調及能源、環(huán)境和經濟等多目標優(yōu)化的分組分段電力市場競標新模型，結果表明了算法的正確性和模型的有效性；李寧等人［5］提出了一種新的基于粒子群的多目標優(yōu)化算法，用搜索過程中所發(fā)現(xiàn)非劣解的一部分構成精英集，通過小生境技術和部分變異的方法提高非劣解集的多樣性和分散性；張麗霞等人［6］應用多目標決策理論求解網絡計劃的多目標優(yōu)化模型；王曉鵬［7］在自適應遺傳算法的基礎上引入群體排序技術、小生境技術和Pareto解集過濾器，建立了適用于多目標優(yōu)化設計的Pareto遺傳算法，設計表明Pareto遺傳算法是十分有效的。

1 多目標優(yōu)化問題描述

多目標優(yōu)化問題［8］起源于許多實際復雜系統(tǒng)的設計、建模和規(guī)劃問題，包括工業(yè)制造、城市運輸、森林管理、產品制造、城市布局、網絡布局等。幾乎每個重要的現(xiàn)實決策問題都要考慮不同約束和處理若干相互沖突的子目標。多目標優(yōu)化問題可以表達成下面的形式，如式（1）和（2）所示。

2 兩種求解MOP的方法

2.1 加權目標規(guī)劃

現(xiàn)實的決策環(huán)境中各個目標的重要程度是不可能完全一致的，決策者可以判斷分析各個目標的重要性，而且子目標在總目標中也占不同的重要程度，可以通過加權系數(shù)進行目標規(guī)劃求解。加權系數(shù)是達成函數(shù)中各目標偏差變量的系數(shù)。加權系數(shù)是一種可以用數(shù)量來衡量的指標，對屬于同一優(yōu)先等級的不同目標可按其重要程度分別給予不同的加權系數(shù)來反映各

加權目標規(guī)劃的數(shù)學模型如下，式（3）為目標函數(shù)，式（4）為約束條件。

2.2 基于生成樹的遺傳算法

遺傳算法的基本特點是多方向和全局搜索，帶有潛在解的種群能夠一代代地維持下來。最小生成樹問題（minimim spanning tree problem）由Boruvka［8］于1926年首次提出，此后，最小生成樹問題被廣泛應用于許多組合優(yōu)化問題中。

最小生成樹問題中，考慮連通圖C=（V，E），其中V=｛v1，v2，…，vn｝是頂點的有效集合，E=｛e1，e2，…，em｝是邊的有限集合。邊將頂點之間連接起來。每個邊有一個正實數(shù)權重W=｛w1，w2，…，wm｝表示距離或費用。最小生成樹問題就是尋找圖C中連接所有頂點的具有最小權重的子圖。

Pareto解集的求解過程

1）設置迭代標志k=1，當前迭代世代t產生的Pareto解集E（t）=｛φ｝；

2）若k＞i-size，停止；否則，執(zhí)行3）；

3）評價染色體Ak，得到解Fk=［f1（Ak）f2（Ak）…fQ（Ak）］，將其與E中所有Pareto解比較；

（i）：若任何Pareto優(yōu)于它，執(zhí)行4）；

（ii）：若它優(yōu)于部分Pareto解，則用它代替E中較差的解；

（iii）：若它是新解，則加入E中。

4）：k=k+1，返回2）。

整個算法的偽代碼如下：

procedure：st-GA/mtp

begin

t←0；

初始化P（t）；

計算P（t）的目標函數(shù)值；

確定Pareto解集E（t）；

計算P（t）的適應值

while不滿足終止條件do

begin

對P（t）進行雜交和變異，得到C（t）；

更新Pareto解集E（t）；

計算C（t）的目標函數(shù)值；

更新Pareto解集E（t）；

計算C（t）的適應值；

從C（t）中選擇P（t+1）；

t←t+1；

end

end

3 仿真分析

某工廠準備開發(fā)3種產品，重點是確定3種產品的生產計劃，并盡量達成目標?？偫麧櫜坏陀?20萬元，3種產品的單位利潤分別為元8、9元和2元；有50名工人，每生產3種產品各1萬件分別需要的工人數(shù)量為6、1和5名；總投資資金不超過60萬元，且生產3種產品需要投入成本2、9和6元。各目標的懲罰權重和各產品的單位貢獻如表1和表2所示。

表1 各目標的懲罰權

表2 各產品的單位貢獻

3.1 加權目標規(guī)劃法求解MOP

建立數(shù)學模型

1）決策變量

產品i的產量xi（i=1，2，3）；

正偏差變量d+i、負偏差變量d-i（i=1，2，3）

2）目標函數(shù)

3）約束條件

求解結果：應用Matlab求解界面如圖1所示。生產產品1、2和3的數(shù)量分別為71739件、69565件和0件。除了第3個目標，其他2個目標都能達成，獲得利潤120萬元，需要工人50人，投入資金76.96萬元。

3.2 應用兩種算法求解MOP

st-GA的參數(shù)設置：初始種群pop-size=30，交叉概率pc=0.8，變異概率pm=0.02，最大迭代次數(shù)max gen=1 000，運行30次。

圖1 應用Matlab求解界面

GA的參數(shù)設置：初始種群pop-size=30，交叉概率pc=0.8，變異概率pm=0.02，最大迭代次數(shù)max gen=1 000，運行30次。

在Intel（R）CoreTMi3 CPU 2.53GHz、內存為2.0 G、安裝系統(tǒng)為win7的PC機上采用Matlab R2010b編程實現(xiàn)。

表3 GA和st-GA求解MOP的結果

求解結果：由表3可知，通過兩種算法都可以求得滿意解，但是st-GA比GA消耗更少的時間就可以找到最優(yōu)解，所以，針對多目標優(yōu)化問題，st-GA更適用。

4 結語

本文應用一種新的算法求解多目標優(yōu)化問題。由于遺傳算法從問題解的串集開始搜索，覆蓋面大，可以同時處理群體中的多個個體，利于全局擇優(yōu)，減少陷入局部最優(yōu)的風險，而最小生成樹具有過程簡單清晰、適用性廣泛的特點，構造了基于生成樹的遺傳算法。結果表明，對于小規(guī)模的多目標優(yōu)化問題，雖然兩種算法都可以求出最優(yōu)解，但在求解時間方面，基于生成樹的遺傳算法比遺傳算法更優(yōu)越，應用改進的算法求解大規(guī)模的多目標優(yōu)化問題是下一步要研究的內容。

［1］ 肖曉偉，肖迪，林錦國，等.多目標優(yōu)化問題的研究概述倡［J］.計算機應用研究，2011，28（3）：805-809.

［2］ 謝濤，陳火旺，康立山.多目標優(yōu)化的演化算法［J］.計算機學報，2003，26（8）：997-1003.

［3］ 王躍宣，劉連臣，牟盛靜，等.處理帶約束的多目標優(yōu)化進化算法［J］.清華大學學報：自然科學版，2005，45（1）：103-106.

［4］ 馬瑞，賀仁睦，顏宏文，等.考慮水火協(xié)調的多目標優(yōu)化分組分段競標模型［J］.中國電機工程學報，2004，24（11）：53-57.

［5］ 李寧，鄒彤，孫德寶.基于粒子群的多目標優(yōu)化算法［J］.計算機工程與應用，2005，41（23）：43-46.

［6］ 張麗霞，侍克斌.施工網絡進度計劃的多目標優(yōu)化［J］.系統(tǒng)工程理論與實踐，2003，23（1）：56-61.

［7］ 王曉鵬.多目標優(yōu)化設計中的Pareto遺傳算法［J］.系統(tǒng)工程與電子技術，2003，25（12）：1558-1561.

［8］ 玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學出版社，2003.

Research on Multi objective Optimization Problem

ZHU Jun CA IYan-guang TANG Ya-lian YANG Jun

（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

Aiming at the limitation of the traditional methods to solve the multi-objective optimization problem，this paper applies a new kind of algorithm to it.Genetic Algorithm（GA）starts to search from the set of solution with its big coverage able to handle more than one individual at the same time，beneficial to global optimization，reducing the risk of fall intolocal optimum，while the minimum spanning tree has the characteristics of simple process and wide applicability.Combined with the advantages of the both algorithms，genetic algorithm is constructed on the basis of spanning tree.By finding the optimal solution by weighted goal programming method，and then solving the problem by the genetic algorithm and genetic algorithm based on spanning tree，the result shows that for small-scale multi-objective optimization problem，two algorithms can find out the optimal solution，and interms of solving time，genetic algorithm based on spanning tree is superior to genetic algorithm.

multi objective optimization；minimum spanning tree；genetic algorithm

TP2

A

1009-0312（2014）03-0046-04

2013-12-04

國家自然科學基金（61074147；61074185）；廣東省自然科學基金（S2011010005059；8351009001000002）；廣東省教育部產學研結合項目（2012B091000171；2011B090400460）；廣東省科技計劃項目（2012B050600028；2010B090301042）。

朱君（1991—），男，江西新余人，碩士生，主要從事組合優(yōu)化、物流信息技術與應用方向研究。