淺談基于免疫思想GA的多目標(biāo)運(yùn)輸問題
相關(guān)鏈接： 中國(guó)安全網(wǎng) 中國(guó)質(zhì)量網(wǎng) 中國(guó)論文網(wǎng) 中國(guó)資訊網(wǎng)
【摘要】運(yùn)輸問題可引申為多種組合優(yōu)化問題，這類問題屬于NP-hard問題。針對(duì)fuzzy-GA算法求解多目標(biāo)運(yùn)輸問題存在的早熟問題及解的分布性問題，本文在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上加入免疫算法里的濃度抑制思想，實(shí)驗(yàn)證明,通過(guò)利用一系列的遺傳操作和抗體親和度計(jì)算、基于濃度群體更新策略生成下一代抗體群，確保了個(gè)體的多樣性，加強(qiáng)了解群的散布性。
論文關(guān)鍵詞：多目標(biāo)優(yōu)化,模糊規(guī)則,免疫,濃度控制
在求解多目標(biāo)優(yōu)化問題時(shí)，由于目標(biāo)意義不同，存在目標(biāo)之間的無(wú)法比較和沖突現(xiàn)象，不一定在所有目標(biāo)上都是最優(yōu)的解。為了達(dá)到總目標(biāo)的最優(yōu)化，必須折中獲取目標(biāo)值。在多目標(biāo)空間中，空間的代數(shù)結(jié)構(gòu)僅滿足偏序性(partial order)，不再具備單目標(biāo)優(yōu)化的全序優(yōu)良性質(zhì)，從而導(dǎo)致求解的困難性。
Gen，Li和Cheng
討論了用生成樹表示求解運(yùn)輸問題的遺傳算法，使用樹性編碼的Pruefer數(shù)，作為設(shè)計(jì)染色體的可行標(biāo)準(zhǔn)�；赑ruefer數(shù)的GA在求解多目標(biāo)運(yùn)輸問題時(shí)，由于節(jié)省了存儲(chǔ)單元，求解時(shí)也就節(jié)省了計(jì)算時(shí)間。
Zou Shurong和Zhang Hongwei
提出了基于Fuzzy規(guī)則的Fuzzy-GA算法，針對(duì)st-GA算法在分配運(yùn)輸量的過(guò)程上采用的是貪婪法，而貪婪法對(duì)優(yōu)化問題較難得到滿意解的問題， Fuzzy-GA算法在st-GA算法的基礎(chǔ)上引入了表達(dá)顯性知識(shí)的Fuzzy規(guī)則進(jìn)行運(yùn)輸量的分配。從實(shí)驗(yàn)數(shù)據(jù)可以看出，F(xiàn)uzzy-GA算法與st-GA算法相比特別是對(duì)大規(guī)模的運(yùn)輸優(yōu)化問題有明顯的優(yōu)勢(shì)，F(xiàn)uzzy-GA算法不僅得到了更好的Pareto前沿面，而且得出了更優(yōu)的Pareto解。
免疫算法所使用的遺傳結(jié)構(gòu)和遺傳算法類似，采用重組、變異等算子操作解決抗體優(yōu)化的問題，可以看作是對(duì)遺傳算法的補(bǔ)充。它把遺傳算法中的染色體看作抗體。
本文在Fuzzy-GA算法的基礎(chǔ)上，首先抗體群的初始化采用新的判定規(guī)則直接生成可行的初始抗體群，加快了抗體群的迭代速度。其次在分配運(yùn)輸量采用模糊規(guī)則來(lái)指導(dǎo)運(yùn)輸量的分配的情況下，在保證供需平衡的基礎(chǔ)上，進(jìn)一步對(duì)運(yùn)輸量的分配進(jìn)行局部的變異。這樣使得運(yùn)輸量分配更趨于合理，加強(qiáng)了解的局部搜索能力，提高了智能進(jìn)化過(guò)程的精度。以抗體的濃度作為參數(shù)來(lái)調(diào)節(jié)抗體的促進(jìn)和抑制，維持抗體的多樣性，使解的分布性更加均勻，從而得到更優(yōu)Pareto解和更好的Pareto前沿面。
成都信息工程學(xué)院資助項(xiàng)目，基金號(hào)：KYTZ200901。
2 問題描述與符號(hào)約定
多目標(biāo)優(yōu)化問題可有如下數(shù)學(xué)表述：
(1)
(2)
(3)
在上邊式子中，x、y分別表示決策向量和目標(biāo)向量。gj(x)為第j個(gè)約束條件，S為決策變量的可行解域。
在具有m個(gè)工廠，n個(gè)倉(cāng)庫(kù)，q個(gè)目標(biāo)函數(shù)的多目標(biāo)運(yùn)輸問題中，m個(gè)工廠的總生產(chǎn)量應(yīng)等于n個(gè)倉(cāng)庫(kù)的總需求量。用r(i,j)表示第i個(gè)工廠到第j個(gè)倉(cāng)庫(kù)的運(yùn)輸關(guān)系，任一運(yùn)輸關(guān)系r(i,j)上的運(yùn)輸量應(yīng)不大于工廠i的產(chǎn)量，且同時(shí)不大于倉(cāng)庫(kù)j的需求量。具體可用下列式子描述為[2]：
(4)
(5)
(6)
(7)
3 基于免疫思想的遺傳算法
3.1 Fuzzy-GA算法的介紹
Fuzzy-GA是基于Pruefer編碼、解碼
和基于模糊規(guī)則的遺傳算法。Pruefer數(shù)作為一種樹的節(jié)點(diǎn)編碼方法，可用于編碼運(yùn)輸樹。運(yùn)輸樹是一種特殊類型的樹，所以Pruefer數(shù)可能對(duì)應(yīng)不可行的解。Gen和Li設(shè)計(jì)了檢驗(yàn)可行性的準(zhǔn)則
，但是此算法的效率不是很高。文
中Fuzzy-GA使用易于表達(dá)顯性知識(shí)的Fuzzy規(guī)則理論，但解的收斂速度不是太快，而且解的質(zhì)量還可以進(jìn)一步優(yōu)化。
Fuzzy規(guī)則：IF 
is 
and 
is 
THEN 
,這里
是模糊集，隸屬函數(shù)為三角函數(shù)，表示（1）中效用因子的高、中、低等意義。
3.2基于Lamarckian進(jìn)化運(yùn)輸量變異過(guò)程
運(yùn)輸量變異是在根據(jù)Fuzzy規(guī)則對(duì)Puefer樹中運(yùn)輸量的的分配后對(duì)已生成的運(yùn)輸量矩陣按一定的方法做局部的變異，但應(yīng)保證供應(yīng)和需求的平衡。具體算法如下：
輸入為m行n列的運(yùn)輸矩陣
第1步：
for j=1:n列
如果第j列不等于0的元素個(gè)數(shù)為1，則運(yùn)輸量變異不考慮此列元素；
第2步：
for i=1:m 行
如果第i行不等于0的元素個(gè)數(shù)為1，則運(yùn)輸量變異不考慮此行元素；
第3步：
反復(fù)執(zhí)行第1、2步，除去變異不考慮的行和列（即某行某列不等于0的元素的個(gè)數(shù)等于1）;一般執(zhí)行m次即可完成
第4步：
統(tǒng)計(jì)運(yùn)輸矩陣不等于0的元素個(gè)數(shù)，如果統(tǒng)計(jì)后元素為0，則退出，返回原運(yùn)輸矩陣；
第5步：
for i=1:m 行
{
�、� 統(tǒng)計(jì)i行中不為0的個(gè)數(shù)，記為count；
�、� 如果count為偶數(shù)，i行中不為0的元素進(jìn)行隨機(jī)加（減）微量運(yùn)輸量
；
③ 如果count為奇數(shù)，i行中不為0的元素進(jìn)行隨機(jī)加（減）微量運(yùn)輸量
或不
變異；
}
第6步：
for i=1:m 行
統(tǒng)計(jì)變異后i行運(yùn)輸量的行量總和，如果不等于相應(yīng)的行供應(yīng)量，則退出，返回原運(yùn)輸量分配矩陣；
第7步：
for j=1：n列
統(tǒng)計(jì)變異后j列運(yùn)輸量的列量總和，如果不等于相應(yīng)的列需求量，則退出，返回原運(yùn)輸量分配矩陣
第8步：
返回變異后運(yùn)輸分配矩陣；
3.3濃度控制原理
若規(guī)定抗體
在集合
上的距離為：
則抗體濃度的公式可表示為
Density(
)=
=
由此可以推知，
=
根據(jù)上式可知，集合中與抗體
基因相似的抗體越多,抗體被選中的概率就越��；反之，與抗體相似的抗體越少，抗體被選中的概率就越大，這使得差異性大的抗體獲得更好的進(jìn)化機(jī)會(huì)，因此，基于抗體濃度的選擇在理論上保持了抗體多樣性，而從使得抗體在新一代解群中都應(yīng)具有較好的散布性。
3.4本文算法整體流程
本算法采用文
中的擂臺(tái)法（arena’s principle，AP）來(lái)作為選擇評(píng)價(jià)算子，對(duì)于交叉算子和變異算子都采用文獻(xiàn)
中所定義的方法。算法采用擂臺(tái)法來(lái)得到Pareto解，該算法也是構(gòu)造Pareto解或非支配解的快速算法
，也是遺傳算法的適應(yīng)度評(píng)價(jià)方法。本算法也采用新的效率很高的檢驗(yàn)Pruefer數(shù)的可行性準(zhǔn)則，對(duì)于m個(gè)工廠n個(gè)倉(cāng)庫(kù)的運(yùn)輸問題，只要滿足下列條件之一則該P(yáng)rüfer數(shù)就是可行的
：
(1) Pruefer數(shù)(P)中出現(xiàn)的工廠節(jié)點(diǎn)的總個(gè)數(shù)等于n-1
(2) Pruefer余數(shù)(CP)中出現(xiàn)的倉(cāng)庫(kù)節(jié)點(diǎn)總個(gè)數(shù)等于m-1
令P（t）是當(dāng)前t代時(shí)的抗體種群，C（t）是當(dāng)前t代產(chǎn)生的抗體，PSet（t）是當(dāng)前t代為止產(chǎn)生的Pareto解集。
新算法流程如下：
Begin
;
隨機(jī)初始化可行的P（t）;
根據(jù)構(gòu)造生成樹T算法
、運(yùn)輸量的變異算法和AP算法從P（t）得PSet（t）;
While 終止條件不滿足 do
Begin
重組P（t）得C（t）;
根據(jù)構(gòu)造生成樹T算法、運(yùn)輸量的變異算法和AP算法從P（t）和C（t）更新PSet（t）;
基于濃度選擇的群體更新，從P（t）和C（t）中選擇出P（t+1）;
;
end
end
最終得到的PSet（t）便是Pareto邊界PF。
4 算例及結(jié)論
本文算法采用Visual Studio 2005(C#語(yǔ)言)實(shí)現(xiàn)，硬件環(huán)境為PC (Pentium IV 3.0 GHz C內(nèi)存:2G).
4.1 算例一
現(xiàn)有8家工廠、9家倉(cāng)庫(kù)，工廠的供應(yīng)量為：a = (10, 8, 12, 16, 21, 15, 7, 9)，和需求量為：b = (9, 7, 15, 10, 13, 16, 7, 10, 11)。算例擁有兩個(gè)成本矩陣，如下：
算法中的參數(shù)設(shè)置：pop_size=50，max_gen=10000，run=5。
上圖是上面相同參數(shù)下三種算法的結(jié)果比較。”圓點(diǎn)”代表st-GA，即基于Pruefer樹的遺傳算法，該算法是采用貪婪法的運(yùn)輸分配方案。”矩形點(diǎn)”代表Fuzzy-GA，是在st-GA的基礎(chǔ)上采用fuzzy規(guī)則來(lái)對(duì)運(yùn)輸量進(jìn)行模糊分配。”菱形點(diǎn)”代表本文 Lam-GA算法結(jié)果，得到了更好的結(jié)果。如：(207,207)。而且明顯看出取得了很好的Pareto前沿面。
4.2 算例二
算例二的規(guī)模較大，設(shè)有18家工廠，19家倉(cāng)庫(kù)，工廠供應(yīng)量為a=(27, 38, 35, 24, 12, 29, 37, 42, 56, 36, 42, 40, 60, 22, 19, 38, 66, 48)，倉(cāng)庫(kù)的需求量為b=(42, 30, 37, 19, 36, 46, 45, 37, 24, 46, 38, 23, 29, 45, 62, 18, 30, 28, 36)。該算例的成本矩陣如下：
算法中的參數(shù)設(shè)置：pop_size=120,max_gen=5000,run=5次。
上圖和前面算例一樣。”圓點(diǎn)”代表st-GA，即基于Pruefer樹的遺傳算法，該算法是采用貪婪法運(yùn)
輸分配方案。”矩形點(diǎn)”代表Fuzzy-GA，是在st-GA的基礎(chǔ)上采用fuzzy規(guī)則來(lái)對(duì)運(yùn)輸量進(jìn)行模糊分配。”菱形點(diǎn)”代表本文Lam-GA算法結(jié)果。從圖可以明顯看出，對(duì)于大規(guī)模算例，本文中的算法取得了很好的Pareto前沿面和Pareto解。
本文提出的新的Lam-GA算法，采用了新的可行性判斷方法，具有更快的收斂速度和更強(qiáng)的收斂性，在保持供應(yīng)平衡的基礎(chǔ)上對(duì)運(yùn)輸量進(jìn)行局部變異，提高了解的精度。通過(guò)加入免疫思想中抗體濃度控制，使得Pareto解的分布性更加均勻。
References (參考文獻(xiàn))
[1] Zou Shurong and Zhong Hongwei, Fuzzy-GA and Multi-Objective Transportation ptimization, IEEE International Conference cis-ram .270-273，9，2008
[2] Michalewicz. Z, Genetic Algorithm + Data Structure = Evolution Programs,3rd. edition, Springer-Verlag, New York, 1996
[3] Michalewicz. Z, G. A. Vignaux and M. Hobbs, A non-standard genetic algorithm for the nonlinear transportation problems, ORSA Journal of computing, vol. 3, no.4, 307-316, 1991
[4] Gen,M. and Y. Li,Spanning tree-based genetic algorithm for bicriteria fixed charge transportation problem, in proceeding of the Congress on Evolutionary Computation, PP.2265-2271 Washington, DC,1999
[5] Gen,M. and R. Cheng, Genetic Algorithm and Engineering Optimization, J Wiley&Sons, Inc, 20004
[6] 多目標(biāo)進(jìn)化算法及其應(yīng)用[M] 鄭金華 科學(xué)出版社 2007
[7] 自然計(jì)算、機(jī)器學(xué)習(xí)與圖像理解前沿[M] 焦李成 公茂果等 西安電子科技出版社 2008
[8]Feng Zhongtian and Zou Shurong , Improvement of the Algorithm to Determine the Feasibility of the Prüfer Number, IEEE International Conference on Natural Computation(2009)
[9] J. Jang, C. Sun and E. Mizutani, Neuro-Fuzzy and Soft Computation, Prentice Hall, 1997
[10] Das Indraned etal, A Closer look at Drawbacks of Minimizing Weighted Sums of Objectives for Pareto Set Generation in Multicriteria Optimization Problems, Structural Optimization, 14(1),63-69, 1997
[11] 人工免疫系統(tǒng)[M] 莫宏偉 左興權(quán) 科學(xué)出版社 2009
[12] 免疫進(jìn)化理論與應(yīng)用[M] 楊孔雨 社會(huì)科學(xué)文獻(xiàn)出版社 2008
