多目標0-1規(guī)劃的元胞競爭決策算法

熊小華, 馬 良, 寧愛兵

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

多目標0-1規(guī)劃的元胞競爭決策算法

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

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

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

競爭決策算法;元胞自動機;多目標;0-1規(guī)劃

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

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

1 競爭決策算法簡介

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

2 元胞自動機簡介

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

3 多目標0-1規(guī)劃的元胞競爭決策算法

3.1 問題介紹

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

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

3.2 算法原理

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

3.3 基本符號及含義

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

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

3.4.1 競爭力函數(shù)

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

3.4.2 決策函數(shù)

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

3.4.3 資源交換規(guī)則

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

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

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

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

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

3.5 算法流程

現(xiàn)給出多目標0-1規(guī)劃的元胞競爭決策算法流程.

Step 2.2 本輪競爭階段2:資源交換階段.

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

Step 3 輸出競爭得到的結果.

3.6 時間復雜度分析

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

4 數(shù)值算例

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

算例1 算例1取自文獻[11-12].

本算法與其他算法運行的結果如表1所示,從實驗結果可以看出,元胞競爭決策算法所求Pareto解的個數(shù)多于One-stage算法和DEA算法.

表1 算例1的計算結果Tab.1 Results of example 1

算例2 算例2取自文獻[13-14].

本算法與其他算法運行的結果如表2所示,從結果可以看出元胞競爭決策算法相比于元胞蟻群算法、蟻群算法和遺傳算法,可以找到更多的Pareto解.

表2 算例2的計算結果Tab.2 Results of example 2

算例3 算例3取自文獻[14-15].

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

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

表3 算例3的計算結果Tab.3 Results of example 3

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

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

5 結束語

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

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

[2] 崔遜學.多目標進化算法及其應用[M].北京:國防工業(yè)出版社,2006.

[3] 寧愛兵,馬良.競爭決策算法及其在車輛路徑問題中的應用[J].管理科學學報,2005,8(6):10-18.

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

[5] 寧愛兵,馬良,熊小華.競爭決策算法原理及其應用[J].上海理工大學學報,2008,30(4):369-373.

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

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

[8] 寧愛兵,馬良.基于快速下界估算的瓶頸旅行商問題競爭決策算法[J].上海理工大學學報,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)工程學報,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] 崔雪麗,馬良.多目標0-1規(guī)劃的螞蟻算法[J].計算機應用與軟件,2007,24(7):23-24.

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

[15] 馮愛芬,楊森.一類農(nóng)業(yè)生產(chǎn)問題的多目標規(guī)劃模型及其解法[J].黃岡師范學院學報,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

國家自然科學基金資助項目(70871081);上海市重點學科建設資助項目(S30504).

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

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