熊小華, 馬 良, 寧愛兵

(1.上海理工大學(xué)管理學(xué)院,上海 200093;2.上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,上海 201209)

多目標(biāo)0-1規(guī)劃的元胞競(jìng)爭(zhēng)決策算法

熊小華1,2, 馬 良1, 寧愛兵1

(1.上海理工大學(xué)管理學(xué)院,上海 200093;2.上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,上海 201209)

將元胞演化規(guī)則與競(jìng)爭(zhēng)決策算法相結(jié)合,提出了一種求解多目標(biāo)0-1規(guī)劃問題的元胞競(jìng)爭(zhēng)決策算法.大量數(shù)據(jù)測(cè)試和驗(yàn)證表明,該算法能有效提高非劣解的分布性和多樣性.

競(jìng)爭(zhēng)決策算法;元胞自動(dòng)機(jī);多目標(biāo);0-1規(guī)劃

多目標(biāo)0-1規(guī)劃是以一維背包問題的0-1整數(shù)規(guī)劃為原型發(fā)展起來的多個(gè)約束、多個(gè)目標(biāo)的最優(yōu)化問題,在投資決策、經(jīng)濟(jì)預(yù)算以及資源分配等問題中有著廣泛的應(yīng)用.這種具有多個(gè)約束、多個(gè)目標(biāo)的組合優(yōu)化問題,統(tǒng)稱為多目標(biāo)優(yōu)化問題(MOP)[1-2].針對(duì)多個(gè)彼此沖突的目標(biāo),如何獲取這些問題的最優(yōu)解,一直都是科學(xué)界和工程界關(guān)注的焦點(diǎn)問題.由于多目標(biāo)意義下,使得所有目標(biāo)都達(dá)到最佳的最優(yōu)解往往并不存在,一般所要求的都是一組相互之間無法區(qū)分優(yōu)劣的非劣解(non-dominated solution),也稱有效解或Pareto解.多目標(biāo)優(yōu)化問題的Pareto解只是一個(gè)可以接受的非劣解,并且大多數(shù)的Pareto解的個(gè)數(shù)很多,甚至是無窮大[2].

0-1整數(shù)規(guī)劃屬于NP(非確定多項(xiàng)式)完備問題類,是否存在有效算法尚不可知,已有的精確算法僅能解決小規(guī)模問題,而啟發(fā)式算法又不能保證得到的解是最優(yōu)的.多目標(biāo)0-1規(guī)劃問題相比單目標(biāo)0-1規(guī)劃來說,更增加了問題求解的難度.對(duì)于多目標(biāo)的組合優(yōu)化問題,國(guó)內(nèi)外的有關(guān)研究較少,尤其缺乏實(shí)用算法.本文將對(duì)此作一些探索性的研究,為這類離散型的多目標(biāo)優(yōu)化難題提供若干解決手段,對(duì)這些模型的實(shí)際應(yīng)用奠定方法和技術(shù)上的基礎(chǔ).本文將競(jìng)爭(zhēng)決策算法原理與元胞自動(dòng)機(jī)的演化規(guī)則相結(jié)合來求解多目標(biāo)0-1規(guī)劃問題,更好地發(fā)揮競(jìng)爭(zhēng)決策算法的優(yōu)勢(shì),既能達(dá)到Pareto前沿,又能提高解的分布性和多樣性.

1 競(jìng)爭(zhēng)決策算法簡(jiǎn)介

競(jìng)爭(zhēng)決策算法(competitive decision algorithm,簡(jiǎn)稱CDA)是近幾年來提出的一種求解組合優(yōu)化難題的新型算法[3-8],算法的原理詳見文獻(xiàn)[5].自然界中的競(jìng)爭(zhēng)和決策都是在一定競(jìng)爭(zhēng)規(guī)則下,在競(jìng)爭(zhēng)者的實(shí)力、競(jìng)爭(zhēng)者和環(huán)境間的關(guān)系、多個(gè)競(jìng)爭(zhēng)者實(shí)力的差距和初始競(jìng)爭(zhēng)狀態(tài)等多種因素的共同作用下,經(jīng)過多次競(jìng)爭(zhēng)和決策后,使不同的競(jìng)爭(zhēng)者分別占有一定的資源而達(dá)到一種新的競(jìng)爭(zhēng)狀態(tài),只要新的競(jìng)爭(zhēng)狀態(tài)優(yōu)于初始競(jìng)爭(zhēng)狀態(tài),就能達(dá)到優(yōu)化的目的. CDA算法吸收了達(dá)爾文“優(yōu)勝劣汰”的進(jìn)化思想以及演化博弈論中有限理性競(jìng)爭(zhēng)者的思想,通過構(gòu)造一個(gè)或多個(gè)具有有限理性的競(jìng)爭(zhēng)者參與到對(duì)一個(gè)或多個(gè)資源的競(jìng)爭(zhēng)過程中,通過優(yōu)勝劣汰的原則使一部分競(jìng)爭(zhēng)者獲得資源而增加實(shí)力,一部分競(jìng)爭(zhēng)者失去資源削弱實(shí)力甚至消亡.當(dāng)算法通過競(jìng)爭(zhēng)不能獲得更優(yōu)的結(jié)果時(shí),通過資源交換使算法進(jìn)入下一輪的競(jìng)爭(zhēng).在理論方面,現(xiàn)在已給出了競(jìng)爭(zhēng)決策算法的基本概念和通用流程;在應(yīng)用方面,已利用其通用流程給出了車輛路徑問題、度約束最小生成樹、旅行商問題等NP難題的算法并編程實(shí)現(xiàn).

2 元胞自動(dòng)機(jī)簡(jiǎn)介

元胞自動(dòng)機(jī)(cellular automata,簡(jiǎn)稱CA)最早由馮·諾依曼提出,沃爾夫勒姆等[9-10]將動(dòng)力系統(tǒng)方法、計(jì)算理論及形式化語言方法引入元胞自動(dòng)機(jī)的研究中,促進(jìn)其廣泛應(yīng)用.CA是一個(gè)時(shí)間和空間都離散的動(dòng)力學(xué)系統(tǒng),由元胞、狀態(tài)、鄰居和規(guī)則這4部分組成.按一定拓?fù)浣Y(jié)構(gòu)分布的元胞僅取有限的離散狀態(tài),依據(jù)確定的局部規(guī)則進(jìn)行更新,大量元胞通過簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化.若元胞的狀態(tài)數(shù)為k,鄰居數(shù)為n,則元胞的可能狀態(tài)數(shù)為kkn.元胞在鄰域范圍內(nèi)具有多種變化形態(tài),這增加了種群的范圍,提高了解的搜索空間,可以避免算法陷入局部最優(yōu)的狀況,這也是將元胞自動(dòng)機(jī)引入競(jìng)爭(zhēng)決策算法的原因所在.

3 多目標(biāo)0-1規(guī)劃的元胞競(jìng)爭(zhēng)決策算法

3.1 問題介紹

本文考慮如下形式的多目標(biāo)0-1規(guī)劃問題

式中,zi為第i個(gè)目標(biāo)的值;m為約束的個(gè)數(shù);n為決策變量的個(gè)數(shù);k為目標(biāo)的個(gè)數(shù).

3.2 算法原理

具有n個(gè)決策變量、m個(gè)約束條件以及k個(gè)目標(biāo)的多目標(biāo)0-1規(guī)劃問題,將n個(gè)決策變量看成競(jìng)爭(zhēng)者爭(zhēng)奪的資源,將k個(gè)目標(biāo)看成非虛擬競(jìng)爭(zhēng)者A,另一個(gè)競(jìng)爭(zhēng)者是虛擬競(jìng)爭(zhēng)者N.競(jìng)爭(zhēng)開始時(shí)所有的資源為N所占有,A不占有任何資源.在競(jìng)爭(zhēng)過程中,A按照競(jìng)爭(zhēng)力函數(shù)和決策規(guī)則占有決策變量資源,在競(jìng)爭(zhēng)的過程中要保證滿足所有的m個(gè)約束.競(jìng)爭(zhēng)結(jié)束后A占有的決策變量即是值為1的決策變量.

3.3 基本符號(hào)及含義

為了方便描述,現(xiàn)介紹本文采用的符號(hào).

3.4 競(jìng)爭(zhēng)力函數(shù)、決策函數(shù)和資源交換規(guī)則

3.4.1 競(jìng)爭(zhēng)力函數(shù)

本算法采用6個(gè)競(jìng)爭(zhēng)力函數(shù),現(xiàn)描述所采用的競(jìng)爭(zhēng)力函數(shù)的基本思想.在滿足m個(gè)約束條件的前提下:a.sum_profit(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大;b.min_profit(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大;c.-diff_profit(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大;d.sum_dentisity(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大;e.min_dentisity(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大;f.-diff_dentisity(j)值越大的決策變量競(jìng)爭(zhēng)力函數(shù)越大.限于篇幅,僅給出1個(gè)競(jìng)爭(zhēng)力函數(shù)的定義,其他5個(gè)競(jìng)爭(zhēng)力函數(shù)定義類似.

3.4.2 決策函數(shù)

本文只采用1個(gè)決策函數(shù),即選中競(jìng)爭(zhēng)力函數(shù)power(j)值最大的決策變量.若兩個(gè)決策變量的power(j)值相同時(shí),則選擇編號(hào)小的決策變量.

3.4.3 資源交換規(guī)則

在元胞空間里,元胞按照演化規(guī)則有很多種變化,有助于保持種群的多樣性.在多目標(biāo)問題求解中,為了提高Pareto解集的多樣性和分布性,將元胞自動(dòng)機(jī)的演化規(guī)則用作競(jìng)爭(zhēng)決策算法的資源交換規(guī)則,以使競(jìng)爭(zhēng)進(jìn)入下一個(gè)競(jìng)爭(zhēng)均衡狀態(tài).

定義1 集合X=(x1,x2,…,xn),xi?{0, 1}.X中xi的任意取值的組合構(gòu)成的集合為元胞空間,則元胞空間可以定義為L(zhǎng)={CellX=(x1,x2,…,xn)｜xi?{0,1}},CellX表示一個(gè)元胞.

定義2 元胞鄰居采用擴(kuò)展Moore鄰居類型, N={CellY｜diff(CellY-CellX)≤r,CellX,CellY?L},其中,diff(CellY-Cell X)為兩個(gè)組合的差異.若無差異,為0;有差異時(shí),最大為2.r表示差異的程度,本文中r取2.

定義3 Pareto解集過濾器,用來存放運(yùn)行時(shí)產(chǎn)生的Pareto解.對(duì)于不違反約束的解,若該解支配過濾器中某個(gè)解,則將該解加入過濾器,同時(shí)刪除受支配解;若過濾器中某個(gè)解支配該解,則放棄該解.過濾器的大小可以事先設(shè)定好,過濾器的大小限制了允許保存的最多的Pareto解的個(gè)數(shù).

定義4 元胞演化規(guī)則:將已經(jīng)求得的解看成中心元胞CellX.按照元胞鄰居的定義,計(jì)算其鄰居CellY(CellY?N)的各個(gè)目標(biāo)值.將CellY的各目標(biāo)值通過Pareto解集過濾器進(jìn)行檢測(cè).

3.5 算法流程

現(xiàn)給出多目標(biāo)0-1規(guī)劃的元胞競(jìng)爭(zhēng)決策算法流程.

Step 2.2 本輪競(jìng)爭(zhēng)階段2:資源交換階段.

以本輪求得的解為中心元胞,按照元胞鄰居及演化規(guī)則的定義,在鄰居范圍內(nèi)演化,替換當(dāng)前非劣解或添加新的非劣解.

Step 3 輸出競(jìng)爭(zhēng)得到的結(jié)果.

3.6 時(shí)間復(fù)雜度分析

在Step 1中分別對(duì)sum_profit(j),min_profit(j), diff_profit(j),sum_dentisity(j),min_dentisity(j)和diff_dentisity(j)采用折半插入排序進(jìn)行降序排序,折半插入排序的時(shí)間復(fù)雜度為O(n log);Step 2.1最壞情況下時(shí)間復(fù)雜度為O(nm);Step 2.2中尋找元胞鄰居的時(shí)間復(fù)雜度為O(n2),對(duì)每個(gè)鄰居與保存的最優(yōu)解的比較次數(shù)為O(k*Pareto過濾器大小),則Step 2最壞情況下的時(shí)間復(fù)雜度為O(Pareto過濾器大小*k*n2).由此可知整個(gè)算法的復(fù)雜度為O (Pareto過濾器大小*k*n2).

4 數(shù)值算例

為驗(yàn)證算法的有效性,采用Delphi 7.0在PC機(jī)上實(shí)現(xiàn)了該算法.本算法對(duì)大量的算例進(jìn)行求解,并與其他算法的結(jié)果進(jìn)行比較,總體效果良好,限于篇幅,現(xiàn)給出其中的4個(gè)算例的比較結(jié)果.

算例1 算例1取自文獻(xiàn)[11-12].

本算法與其他算法運(yùn)行的結(jié)果如表1所示,從實(shí)驗(yàn)結(jié)果可以看出,元胞競(jìng)爭(zhēng)決策算法所求Pareto解的個(gè)數(shù)多于One-stage算法和DEA算法.

表1 算例1的計(jì)算結(jié)果Tab.1 Results of example 1

算例2 算例2取自文獻(xiàn)[13-14].

本算法與其他算法運(yùn)行的結(jié)果如表2所示,從結(jié)果可以看出元胞競(jìng)爭(zhēng)決策算法相比于元胞蟻群算法、蟻群算法和遺傳算法,可以找到更多的Pareto解.

表2 算例2的計(jì)算結(jié)果Tab.2 Results of example 2

算例3 算例3取自文獻(xiàn)[14-15].

本算法與其他算法運(yùn)行的結(jié)果如表3所示,相比于文獻(xiàn)[14-15]的算法,可以發(fā)現(xiàn)更多的Pareto解.

算例4 k=2,n=100,m=2,其約束和目標(biāo)函數(shù)由于決策變量個(gè)數(shù)較多不便列出,共求得160個(gè)Pareto解,其所求解集如圖1所示.

表3 算例3的計(jì)算結(jié)果Tab.3 Results of example 3

圖1 算例4的Pareto解集Fig.1 Pareto set of example 4

通過以上測(cè)試發(fā)現(xiàn),對(duì)于較小規(guī)模的問題,可以求出全部Pareto解;對(duì)于較大規(guī)模的問題,Pareto解分布比較稠密,且形成一個(gè)明顯的Pareto前沿.

5 結(jié)束語

多目標(biāo)0-1規(guī)劃問題是很多問題的原始模型,在工程實(shí)踐與科學(xué)研究中都具有非常重要的意義.但是,由于其NP難題以及多目標(biāo)問題本質(zhì)上多個(gè)目標(biāo)相互沖突的特性,限制了精確算法對(duì)較大規(guī)模問題的求解.競(jìng)爭(zhēng)決策算法是一種能廣泛應(yīng)用于求解各類組合優(yōu)化難題的新型尋優(yōu)算法,其通用性和實(shí)用性都比較強(qiáng).本文將元胞自動(dòng)機(jī)原理與競(jìng)爭(zhēng)決策算法相結(jié)合來求解多目標(biāo)0-1規(guī)劃問題,提高了Pareto解集的分布性及多樣性,因此,求解的速度與效果都比較好.

[1] 雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法[M].北京:科技技術(shù)出版社,2009.

[2] 崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2006.

[3] 寧愛兵,馬良.競(jìng)爭(zhēng)決策算法及其在車輛路徑問題中的應(yīng)用[J].管理科學(xué)學(xué)報(bào),2005,8(6):10-18.

[4] 寧愛兵,馬良.度約束最小生成樹(DCMST)的競(jìng)爭(zhēng)決策算法[J].系統(tǒng)工程學(xué)報(bào),2005,20(6):630-634.

[5] 寧愛兵,馬良,熊小華.競(jìng)爭(zhēng)決策算法原理及其應(yīng)用[J].上海理工大學(xué)學(xué)報(bào),2008,30(4):369-373.

[6] 熊小華,郭文夷,寧愛兵.具有偏好選擇的多目標(biāo)TSP競(jìng)爭(zhēng)決策算法[J].上海第二工業(yè)大學(xué)學(xué)報(bào),2005,22 (1):6-12.

[7] 寧愛兵,馬良.最小比率旅行商(MRTSP)問題競(jìng)爭(zhēng)決策算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(11): 30-32.

[8] 寧愛兵,馬良.基于快速下界估算的瓶頸旅行商問題競(jìng)爭(zhēng)決策算法[J].上海理工大學(xué)學(xué)報(bào),2005,27(3): 223-228.

[9] WOLFRAN S.Theory and Application of Cellular Automata[M].Singapore:The World Scientific Publishing Company Limitd,1986.

[10] 朱剛,馬良.函數(shù)優(yōu)化的元胞螞蟻算法[J].系統(tǒng)工程學(xué)報(bào),2007,22(3):305-308.

[11] LIU Fuh-hwa Franklin,HUANG Chueng-chiu,YEN Yu-lee.Using DEA to obtainefficient solutions for multi-objetive 0-1 linear programs[J].European Journal of Operational Research,2000,126(1):51-68.

[12] JAHANSHAHLOO G R,HOSSEINZADEH F,SHOJA N, et al.A method for generatingall efficient solutions of 0-1 multi-objective linear programmingproblem[J]. Applied Mathematics and Computation,2005,169(2): 874-886.

[13] 崔雪麗,馬良.多目標(biāo)0-1規(guī)劃的螞蟻算法[J].計(jì)算機(jī)應(yīng)用與軟件,2007,24(7):23-24.

[14] 劉勇,馬良,許燕秋.多目標(biāo)0-1規(guī)劃問題的元胞蟻群優(yōu)化算法[J].系統(tǒng)工程,2009,27(2):119-122.

[15] 馮愛芬,楊森.一類農(nóng)業(yè)生產(chǎn)問題的多目標(biāo)規(guī)劃模型及其解法[J].黃岡師范學(xué)院學(xué)報(bào),2004,24(3): 32-34.

Cellular competitive decision algorithm for multi-objective 0-1 programming problem

XIONGXiao-hua1,2, MA Liang1, NINGAi-bing1
(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;
2.College of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

Combining the concepts of cellular automata with competitive decision algorithm,a cellular competitive decision algorithmfor multi-objectives 0-1 programming problem was presented.The algorithm was then used to solve many instances of multi-objectives 0-1 programming and the computational results show it can improve effectively the diversity and distribution of Pareto optimal set.

competitive decision algorithm;cellular automata;multi-objectives;0-1 programming

O 223

A

1007-6735(2011)02-0163-05

2011-02-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(70871081);上海市重點(diǎn)學(xué)科建設(shè)資助項(xiàng)目(S30504).

熊小華(1978—),女,博士研究生.研究方向:算法設(shè)計(jì)、系統(tǒng)工程.E-mail:xiong_xiao_hua@163.com;

馬 良(聯(lián)系人),男,教授.研究方向:算法設(shè)計(jì)、系統(tǒng)工程.E-mail:maliang@usst.edu.cn