多目標(biāo)優(yōu)化問(wèn)題的研究

朱 君 蔡延光 湯雅連 楊 軍

多目標(biāo)優(yōu)化問(wèn)題的研究

朱 君 蔡延光 湯雅連 楊 軍

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

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

多目標(biāo)優(yōu)化問(wèn)題；最小生成樹(shù)；遺傳算法

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

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

1 多目標(biāo)優(yōu)化問(wèn)題描述

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

2 兩種求解MOP的方法

2.1 加權(quán)目標(biāo)規(guī)劃

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

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

2.2 基于生成樹(shù)的遺傳算法

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

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

Pareto解集的求解過(guò)程

1）設(shè)置迭代標(biāo)志k=1，當(dāng)前迭代世代t產(chǎn)生的Pareto解集E（t）=｛φ｝；

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

3）評(píng)價(jià)染色體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）。

整個(gè)算法的偽代碼如下：

procedure：st-GA/mtp

begin

t←0；

初始化P（t）；

計(jì)算P（t）的目標(biāo)函數(shù)值；

確定Pareto解集E（t）；

計(jì)算P（t）的適應(yīng)值

while不滿足終止條件do

begin

對(duì)P（t）進(jìn)行雜交和變異，得到C（t）；

更新Pareto解集E（t）；

計(jì)算C（t）的目標(biāo)函數(shù)值；

更新Pareto解集E（t）；

計(jì)算C（t）的適應(yīng)值；

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

t←t+1；

end

end

3 仿真分析

某工廠準(zhǔn)備開(kāi)發(fā)3種產(chǎn)品，重點(diǎn)是確定3種產(chǎn)品的生產(chǎn)計(jì)劃，并盡量達(dá)成目標(biāo)?？偫麧?rùn)不低于120萬(wàn)元，3種產(chǎn)品的單位利潤(rùn)分別為元8、9元和2元；有50名工人，每生產(chǎn)3種產(chǎn)品各1萬(wàn)件分別需要的工人數(shù)量為6、1和5名；總投資資金不超過(guò)60萬(wàn)元，且生產(chǎn)3種產(chǎn)品需要投入成本2、9和6元。各目標(biāo)的懲罰權(quán)重和各產(chǎn)品的單位貢獻(xiàn)如表1和表2所示。

表1 各目標(biāo)的懲罰權(quán)

表2 各產(chǎn)品的單位貢獻(xiàn)

3.1 加權(quán)目標(biāo)規(guī)劃法求解MOP

建立數(shù)學(xué)模型

1）決策變量

產(chǎn)品i的產(chǎn)量xi（i=1，2，3）；

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

2）目標(biāo)函數(shù)

3）約束條件

求解結(jié)果：應(yīng)用Matlab求解界面如圖1所示。生產(chǎn)產(chǎn)品1、2和3的數(shù)量分別為71739件、69565件和0件。除了第3個(gè)目標(biāo)，其他2個(gè)目標(biāo)都能達(dá)成，獲得利潤(rùn)120萬(wàn)元，需要工人50人，投入資金76.96萬(wàn)元。

3.2 應(yīng)用兩種算法求解MOP

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

圖1 應(yīng)用Matlab求解界面

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

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

表3 GA和st-GA求解MOP的結(jié)果

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

4 結(jié)語(yǔ)

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

［1］ 肖曉偉，肖迪，林錦國(guó)，等.多目標(biāo)優(yōu)化問(wèn)題的研究概述倡［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（3）：805-809.

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

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

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

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

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

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

［8］ 玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學(xué)出版社，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

國(guó)家自然科學(xué)基金（61074147；61074185）；廣東省自然科學(xué)基金（S2011010005059；8351009001000002）；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目（2012B091000171；2011B090400460）；廣東省科技計(jì)劃項(xiàng)目（2012B050600028；2010B090301042）。

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