周瑩，劉云霞

（深圳信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)學(xué)院，廣東 深圳 518172）

【信息技術(shù)理論研究】

一種求解多目標(biāo)無約束0-1二次規(guī)劃問題的文化基因算法

周瑩，劉云霞

（深圳信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)學(xué)院，廣東 深圳 518172）

針對(duì)多目標(biāo)無約束0-1二次規(guī)劃問題，提出一種文化基因算法。該算法采用基于分解的多目標(biāo)演化算法框架，能夠獲得分布均勻的非占優(yōu)解；同時(shí)，采用一種簡(jiǎn)單、有效的禁忌搜索，能夠利用更多問題相關(guān)的信息，獲得質(zhì)量更優(yōu)的非占優(yōu)解。該算法在優(yōu)化的過程中能夠動(dòng)態(tài)地平衡多樣性與收斂性。實(shí)驗(yàn)結(jié)果證明該算法能夠很好地求解多目標(biāo)無約束0-1二次規(guī)劃問題，并且性能優(yōu)于目前求解該問題較先進(jìn)的算法。

多目標(biāo)無約束0-1二次規(guī)劃問題；文化基因算法；基于分解的多目標(biāo)演化算法；禁忌搜索算法

mUBQP具有廣闊的應(yīng)用場(chǎng)景[1]。在實(shí)際生活中，大量難以解決的問題都可轉(zhuǎn)化為mUBQP。此外，許多圖論問題也可轉(zhuǎn)化為mUBQP，如雙目標(biāo)著色問題[1]。mUBQP是一種多目標(biāo)優(yōu)化問題，該類問題通常不存在一個(gè)能使多個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)的解，而是存在一組可供選擇的折中解。因此，需設(shè)計(jì)多目標(biāo)優(yōu)化算法對(duì)其進(jìn)行求解。

mUBQP是一種新的多目標(biāo)優(yōu)化問題，據(jù)我們所知，目前對(duì)mUBQP的研究成果仍然較少。2013年，文獻(xiàn)[1]首先提出一組mUBQP的測(cè)試數(shù)據(jù)集。該測(cè)試數(shù)據(jù)集按照問題規(guī)模、密度、目標(biāo)個(gè)數(shù)以及目標(biāo)之間的相關(guān)性分為50個(gè)算例。其次，作者借鑒成功求解單目標(biāo)UBQP的算法，提出第一個(gè)求解mUBQP的算法：混合型元啟發(fā)式算法（HM）。該算法結(jié)合基于Pareto支配關(guān)系的進(jìn)化算法與禁忌搜索來獲得一組Pareto最優(yōu)解。然而，HM并不能很好地求解大規(guī)模的算例。隨后，Zhou等[2]提出一種邊界解引導(dǎo)的多目標(biāo)優(yōu)化算法（DTS），用于求解mUBQP。該算法優(yōu)先優(yōu)化邊界方向上的解。當(dāng)無法繼續(xù)優(yōu)化邊界解時(shí)，算法逐漸改變優(yōu)化的方向，以填補(bǔ)邊界解之間的間隙。實(shí)驗(yàn)結(jié)果顯示DTS的性能優(yōu)于HM。然而，該算法對(duì)mUBQP的求解效果并不能令人滿意。

為了能夠更好地求解mUBQP，本文提出一種文化基因算法（memetic algorithm，MA）。MA采用基于分解的多目標(biāo)演化算法框架（MOEA/D），能夠獲得分布均勻的非占優(yōu)解。此外，MA采用一種簡(jiǎn)單、有效的禁忌搜索（TS），能夠利用問題相關(guān)的信息進(jìn)行求解，因此能夠獲得質(zhì)量更好的解。為了驗(yàn)證算法的有效性，本文將MA用于求解50個(gè)mUBQP的算例，并將其與目前求解該問題較為先進(jìn)的算法：DTS進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果顯示MA顯著地優(yōu)于DTS。

1 求解mUBQP的文化基因算法

MA采用MOEA/D[3]的算法框架，將mUBQP分解為個(gè)子問題，每一個(gè)子問題關(guān)聯(lián)一個(gè)個(gè)體，并且關(guān)聯(lián)一個(gè)權(quán)重向量。然后，利用進(jìn)化算法與局部搜索算法同時(shí)優(yōu)化這些子問題。在優(yōu)化的過程中，MA采用交叉操作生成新的子代個(gè)體，并且采用一種簡(jiǎn)單的TS來提升解的質(zhì)量。MA的優(yōu)化過程如圖1所示。

圖1 MA的優(yōu)化過程Fig.1 The image of optimization procedure in MA

MA的特點(diǎn)如下：

1）采用MOEA/D的算法框架，可以通過分布均勻的權(quán)重向量生成分布較為均勻的非占優(yōu)解，從而保持良好的多樣性；

2）TS能夠很好地利用問題相關(guān)的信息來有效地提升解的質(zhì)量，從而使算法保持良好的收斂性。

1.1 MA的算法流程

MA使用一組分布均勻的權(quán)重向量，采用加權(quán)法將問題分解為一系列子問題。設(shè)某個(gè)子問題所關(guān)聯(lián)的權(quán)重向量為，該問題的目標(biāo)函數(shù)可描述如下：

交叉操作（步驟10）：用于生成新的后代個(gè)體；優(yōu)化操作（步驟11）：采用TS提升解的質(zhì)量；存檔更新操作（步驟12）：用于更新外部存檔。

接下來將分別介紹這三種操作。

1.2 交叉操作

MA采用均勻交叉操作（uniform crossover）[1]生成新的后代個(gè)體。首先，算法從每個(gè)子問題的鄰域中隨機(jī)選出兩個(gè)父代個(gè)體、；然后，與中共同的決策變量直接由子代個(gè)體繼承，其余的決策變量將以隨機(jī)的方式賦予子代個(gè)體。該操作可由算法2來描述，其中表示隨機(jī)選取0或1。

1.3 優(yōu)化操作

TS直接對(duì)每個(gè)子問題進(jìn)行優(yōu)化。因此，TS使用式2來評(píng)估每個(gè)子問題關(guān)聯(lián)的解的質(zhì)量。TS采用禁忌表(tabu list)來避免迂回搜索，并選擇鄰域中最好的解（best improvement strategy）作為可接受的候選解。翻轉(zhuǎn)決策變量之后，該變量進(jìn)入禁忌表中，并且在之后代內(nèi)不得再次被翻轉(zhuǎn)（禁忌準(zhǔn)則），除非能夠獲得優(yōu)于當(dāng)前最優(yōu)的解（赦免準(zhǔn)則）。在TS中，用參數(shù)控制搜索深度，即經(jīng)過次鄰域操作之后算法停止，最后返回搜索過程中找到的最優(yōu)解。

1.4 存檔更新操作

1.5 初始化與停止條件

MA以停止時(shí)間為停止條件。為了公平對(duì)比算法之間的性能，所有算法的停止時(shí)間都設(shè)為一致。

2 實(shí)驗(yàn)及結(jié)果分析

本節(jié)通過一系列實(shí)驗(yàn)來驗(yàn)證MA的性能。本節(jié)采用的測(cè)試算例為50個(gè)mUBQP算例，可通過網(wǎng)站（http://mocobench.sourceforge.net/index.php?n=）下載。實(shí)驗(yàn)的運(yùn)行環(huán)境描述如下：

1）處理器：Pentium＠ Dual-Core CPU E5400 @ 2.70GHZ

2）內(nèi)存：4.00GB

表1 測(cè)試算例與MA中參數(shù)設(shè)置Tab.1 Parameter setting for instances MA

由于DTS[2]是目前為止求解mUBQP較為先進(jìn)的算法，因此將DTS作為MA的對(duì)比算法。所有算法均用C語言實(shí)現(xiàn)。DTS中所有參數(shù)的設(shè)置均與文獻(xiàn)[2]相同。測(cè)試算例的描述與MA中的參數(shù)設(shè)置見表1。其中，種群規(guī)模由參數(shù)控制。權(quán)重向量的每個(gè)分量的取值為集合：

為了公平地進(jìn)行對(duì)比，兩種算法均在相同的運(yùn)行環(huán)境下運(yùn)行。每個(gè)算法對(duì)每個(gè)算例單獨(dú)運(yùn)行20次。接下來，本節(jié)給出算法的性能指標(biāo)，并給出MA與DTS的算法對(duì)比。

2.1 性能指標(biāo)

多目標(biāo)優(yōu)化算法的性能從兩方面評(píng)價(jià)，分別為多樣性與收斂性。由于單一的性能指標(biāo)無法同時(shí)反映這兩個(gè)評(píng)價(jià)標(biāo)準(zhǔn)[5]，因此本節(jié)分別采用以下兩種性能指標(biāo)來評(píng)價(jià)多目標(biāo)算法的性能：

1）獲得的非占優(yōu)解集與參考集之間的度量（inverted generational distance，IGD）[3]：該指標(biāo)由Zhang和Li提出，定義如下：

2）超體積度量（hypervolume，HV）[6]：該指標(biāo)由Zitzler等提出，用于度量至少被非占優(yōu)解集中的一個(gè)解占優(yōu)的目標(biāo)空間的體積。HV同樣能夠度量算法的多樣性和收斂性。

HV（IGD）的值越大（越?。f明得到的非占優(yōu)解越接近真實(shí)的PF，因此算法的多樣性與收斂性越優(yōu)。由于無法獲取mUBQP真實(shí)的PF，因此對(duì)于每個(gè)算例，將所有算法在該算例上獲得的非占優(yōu)解作為該算例的參考集。此外，由于不同目標(biāo)的取值范圍不同，所有解的目標(biāo)值均做歸一化處理。

2.2 MA與DTS 的對(duì)比

表2-3顯示了兩種算法對(duì)每個(gè)算例獨(dú)立運(yùn)行20次，在IGD與HV上得到的平均值。為了進(jìn)一步顯示算法之間的差異，我們采用Wilcoxon測(cè)試[7]（顯著水平為0.05）對(duì)算法進(jìn)行統(tǒng)計(jì)測(cè)試。表中粗體的數(shù)字代表對(duì)應(yīng)的算法在算例上得到的結(jié)果顯著地優(yōu)于對(duì)比算法。從表2-3中可以看出，MA對(duì)35個(gè)算例在IGD與HV上得到的結(jié)果均顯著地優(yōu)于DTS，尤其對(duì)于IGD指標(biāo)，MA對(duì)所有50個(gè)算例得到的結(jié)果均顯著地優(yōu)于DTS。此外，隨著目標(biāo)數(shù)與問題規(guī)模的增長，DTS的求解能力逐漸下降。因此，從實(shí)驗(yàn)結(jié)果可以看出，MA將MOEA/D與TS結(jié)合，能夠很好地平衡多樣性和收斂性，并且能夠獲得更優(yōu)的非占優(yōu)解。

表2 DTS與MA在IGD上的平均值Tab.2 Average values in terms of IGD for DTS and MA

為了更好地顯示兩種算法的性能，圖2-3顯示了MA與DTS對(duì)，的四組算例，獨(dú)立運(yùn)行20次中得到IGD最好的非占優(yōu)解。從圖中可以看出，MA不論在解的分布還是非占優(yōu)解的數(shù)量上均優(yōu)于DTS。因此，從圖的角度進(jìn)一步反映了MA具有良好的多樣性與收斂性，是一種有效求解mUBQP的方法，并且性能顯著地優(yōu)于DTS。

表3 DTS與MA在HV上的平均值Tab.3 Average values in terms of HV for DTS and MA

3 結(jié)論

本文提出一種用于求解mUBQP的文化基因算法（MA）。MA采用基于分解的演化算法框架（MOEA/D），將問題分為若干個(gè)子問題，并通過分布均勻的權(quán)重向量保持算法的多樣性。此外，MA采用禁忌搜索（TS）進(jìn)一步提升解的質(zhì)量。該TS具有簡(jiǎn)單、有效的特點(diǎn)，能夠較好地利用問題相關(guān)的信息，從而使整個(gè)算法具有良好的收斂性。實(shí)驗(yàn)結(jié)果表明，MA不僅能夠有效地求解mUBQP，而且性能優(yōu)于目前求解MA較為先進(jìn)的算法。

今后的工作可以從以下幾個(gè)方面展開：首先，本文提出的算法為通用性算法，可以用于求解其他0-1組合優(yōu)化問題；其次，可以采用有界存檔，如基于支配關(guān)系[8]的存檔，儲(chǔ)存搜索過程中找到的非占優(yōu)解，從而進(jìn)一步提升算法的效率；最后，可采用自適應(yīng)的參數(shù)，在搜索過程中動(dòng)態(tài)地調(diào)整參數(shù)大小，以獲得更好的結(jié)果。

References)

[1]Liefooghe A,Verel S,Hao J K.A hybrid metaheuristics for multiobjective unconstrained binary quadratic programming[J].Applied Soft Computing,2014,16:10-19.

[2]Zhou Y,Wang J,Yin J.A Directional-biased Tabu Search Algorithm for Multi-objective Unconstrained Binary Quadratic Programming Problem[C].//Proc Six International Conference on Advanced Computational Intelligence (ICACI),Washington,DC,USA:IEEE,2013,pp.281-286.

[3]Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].Evolutionary Computation,IEEE Transactions on,2007,11(6):712-731.

[4]Wang J,Zhou Y,Yin J.Combining tabu Hopfield network and estimation of distribution for unconstrained binary quadratic programming problem[J].Expert Systems with Applications,2011,38(12):14870-14881.

[5]Zitzler E,Thiele L,Laumanns M,et al.Performance assessment of multiobjective optimizers:An analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

[6]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength Pareto evolutionary algorithm[M].//Evolutionary Methods for Design,Optimization and Control with Applications to Industrial Problems.Berlin:Springer,2002:95-100.

[7]Derrac J,García S,Molina D,et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J].Swarm and Evolutionary Computation,2011,1(1):3-18.

[8]Laumanns M,Thiele L,Deb K,et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation,2002,10(3):263-2.

A memetic algorithm for multiobjective unconstrained binary quadratic programming

ZHOU Ying ,LIU Yunxia
（School of Computer Science,Shenzhen Institute of Information Technology,Shenzhen 518172,P.R.China）

This paper proposes a memetic algorithm (MA) for multiobjective unconstrained binary quadratic programming problem.In MA,multiobjective evolutionary algorithm based on decomposition (MOEA/D) framework is adopted to obtain well-distributed nondominated solutions.At the same time,More problem-specific knowledge can be extracted by using a simple and effective tabu search (TS)，and high-quality solutions can be generated.Therefore,MA can balance the diversity and convergence well during the whole optimization process.Experimental results show that MA outperforms the previous state-of-the-art algorithm for mUBQP cases.

multiobjective unconstrained binary quadratic programming;memetic algorithm;multiobjective evolutionary algorithm based on decomposition;tabu search

TP312

：A

1672-6332（2014）03-0001-07

【責(zé)任編輯：高潮】

2014-09-01

廣東省自然科學(xué)基金項(xiàng)目（項(xiàng)目編號(hào)：S2012010008964）；深圳市科技計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：JCYJ20120615103057639）

周瑩（1987-），女（漢），陜西富平人，博士。主要研究方向：計(jì)算智能與數(shù)據(jù)挖掘。E-mail:dyingdy@gmail.com