張紅

基于自適應遺傳算法的模糊伙伴選擇

張紅

福建船政交通職業(yè)學院，福建福州350004

在模糊環(huán)境下，引入模糊理論，以具有時序關系的任務時間的最大平均滿意度為優(yōu)化目標，建立項目伙伴選擇的數(shù)學模型更符合生產(chǎn)實際情況。而利用自適應遺傳算法求解可改進基本遺傳算法收斂慢的缺點，通過驗證這種算法能以更快的速度收斂，達到全局最優(yōu)值。

伙伴選擇；模糊數(shù)；自適應遺傳算法

一、模糊伙伴選擇的提出

在以往的虛擬企業(yè)合作伙伴的研究中，大多數(shù)學者所考慮的都是在條件精確的下進行的。然而，事實上由于各種不確定因素的存在，如合作伙伴的加工進度的不確定，加工過程中機器的故障，操作工人的熟練程度，因故缺席等，以及運輸過程中的不確定因素，這些都造成了開工時間和交貨期不能精確，合作伙伴只能夠提供一個大概的數(shù)據(jù)以及數(shù)據(jù)的范圍。因此，我們研究在模糊環(huán)境下虛擬企業(yè)伙伴選擇的問題，引入模糊數(shù)學理論來描述候選伙伴的開工時間和交貨期的不確定性，研究的模型更接近于實際情況，符合生產(chǎn)要求，更容易被用戶接受。

近年來，隨著模糊數(shù)學的發(fā)展，應用模糊數(shù)學解決不確定參數(shù)問題引起了廣泛的關注，有很好的優(yōu)越性和發(fā)展前景。把模糊數(shù)學運用到合作伙伴的選擇當中，把任務的開工時間和交貨期按模糊數(shù)學處理更符合實際生產(chǎn)情況，已成為非確定性合作伙伴研究的一個分支。所以，關于模糊開工時間和模糊交貨期的研究有重要的意義。

二、模型的建立

在模糊的開工時間、完工時間及交貨期下，以極大化平均客戶滿意度（每一個組合滿意度的平均值mean（AI））為目標的虛擬企業(yè)合作伙伴選擇問題可以描述為如下模型：

約束條件：

式（3—1）表示極大化平均客戶滿意度的目標函數(shù)；式（3—2）表示每個任務必須從候選伙伴集中選擇一個候選伙伴完成，且只能由一個候選伙伴來完成；式（3—3）保證任務的最早允許開工期約束；式（3—4）保證任務的開工期約束；式（3—5）保證項目的成本約束。

在對合作伙伴選擇的模型建立后，要構造相應的算法對問題進行優(yōu)化求解。

三、自適應遺傳算法

遺傳算法（Genetic Algorithm）是J.Holland在1975年提出的，是基于對自然界中生物遺傳與進化理論的仿真，模仿生物進化過程中的“物競天擇，適者生存”的原理，在一定程度上解決了傳統(tǒng)的基于符號處理機制的人工智能方法在知識表示、信息處理和解決組合爆炸等方面所遇到的困難，其自組織、自適應、自學習和群體進化能力使其適合于大規(guī)模復雜優(yōu)化問題。遺傳算法作為一種實用、高效、魯棒性強的算法、適用于并行分布處理以及應用范圍廣的特點。經(jīng)過20多年的發(fā)展，遺傳算法已經(jīng)在函數(shù)優(yōu)化、組合優(yōu)化、數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、機器學習、圖像處理等領域得到成功應用。

基本遺傳算法容易出現(xiàn)早熟收斂、易陷入局部極值點的問題，即算法收斂于一個非全局最優(yōu)點，出現(xiàn)這種問題是一種被稱為“頂端優(yōu)勢”的現(xiàn)象存在，即當算法進行到某一代時，在種群中某個個體的適應度值遠遠大于其他個體的適應度。因為大多數(shù)選擇策略采用繁殖機會與適應值成比例的方法，這樣就會使子代中許多個體來自同一祖先。一旦出現(xiàn)過早收斂，遺傳算法中的交叉操作就會失效。從理論上來講，遺傳算法中的變異操作可以使算法跳出局部最優(yōu)，但是為了保證算法的穩(wěn)定性，變異操作的變異概率通常取值較?。ɡ?.01），算法一旦出現(xiàn)過早收斂，靠傳統(tǒng)的變異操作需要許多代才能變異出一個不同于其他個體的新個體，因此，本文采用自適應遺傳算法，能夠有效防止這種問題的出現(xiàn)。

遺傳算法的交叉概率和變異概率的選擇是影響遺傳算法行為和性能的關鍵參數(shù)，直接影響算法的收斂性。在一般的遺傳算法中，對所有個體的交叉概率和變異概率選用固定參數(shù)，并在遺傳過程中保持不變。本文提出了交叉和變異概率的自適應調(diào)整規(guī)則，使得每個個體按其適應度大小選擇不同的交叉概率和變異概率。而且，在遺傳過程中根據(jù)適應度的變化自動調(diào)節(jié)這兩個控制參數(shù)。這樣，群體中每個個體對環(huán)境的變化就具有了自適應調(diào)節(jié)能力。

自適應交叉概率設計為：

自適應變異概率設計為：

式中：pc0、pc1分別表示最大的交叉概率和最小的交叉概率；pm0、pm1分別表示最大的變異概率和最小的變異概率；fmax是群體中最大的適應度值；favg是每代群體的平均適應度值；f是要交叉的兩個個體中較大的適應度值；f′是要變異個體的適應度值。

四、約束處理

常用的約束處理方法有：搜索空間限定法、可行解變化法、簡化約束條件法、懲罰函數(shù)法。

懲罰函數(shù)因為執(zhí)行簡單而被廣泛的應用，它的基本原理是將約束問題中的不等式和等式約束函數(shù)經(jīng)過加權后，和原目標函數(shù)結合成新的目標函數(shù)，將約束問題轉(zhuǎn)化為無約束問題。

在新目標函數(shù)中，r1和r2是懲罰因子，項，障礙項的作用是當?shù)c在可行區(qū)域內(nèi)時，在迭代的過程中阻止迭代點越出可行域，懲罰項的作用是當?shù)c在非可行域或不滿足約束條件時，在迭代過程中將迫使迭代點逼近約束邊界或等式約束曲面。

但是使用懲罰函數(shù)處理約束，會產(chǎn)生以下問題：（1）懲罰因子難以確定，解決問題的好壞取決于選擇懲罰因子的好壞；（2）問題的可行域較小，個體跳出可行域的機會較大。

為了更好的處理約束問題，Jimenez和Verdegay提出了一種聯(lián)賽選擇算法，并采用以下比較準則進行比較：

1．當兩個個體都是可行解時，目標函數(shù)值較小的占優(yōu)；

2．當兩個個體，一個是可行解，另外一個是不可行解，可行解總是優(yōu)于不可行解；

3．當兩個個體都是不可行解時，則違反約束較小的總是占優(yōu)。

基于以上3個原則，蘇平（2006）構造了一種不需要設置懲罰因子的約束處理方法，取得了較好的效果。該方法的思想用于遺傳算法中處理約束，定義滿足所有約束條件的粒子為可行粒子，否則稱之為不可行粒子，一旦違背了約束條件，可行粒子變?yōu)椴豢尚辛Ｗ印?/p>

根據(jù)本實例的特點，目標函數(shù)是平均值的最大值，根據(jù)約束條件判斷粒子是否是可行解，當粒子滿足所有約束條件時，粒子的適應度不變，保留較好粒子個體，粒子逐漸靠近最優(yōu)解。當粒子沒有滿足所有的約束，粒子的適應度增加懲罰約束函數(shù)P（x），P（x）為足夠大負值，使得粒子的適應度比滿足所有約束條件的粒子要小，這樣使這些粒子保留下來的概率較小。采用以下式子計算適應度：

其中，fmin（x）為最差可行解適應度，即最小適應度，P（x）為懲罰函數(shù)。

五、實例應用

以模具制造為例，一個模具制造企業(yè)需完成一個大型注塑模的項目，由于該企業(yè)不具備完成這個項目的所有資源，故需要組織虛擬企業(yè)來完成。該項目分解成下列制造任務：

任務1：產(chǎn)品的三維造型、模具設計，包括型腔、型芯和電極的設計，需要有經(jīng)驗的模具設計人員和相關的CAD軟件包。

任務2：模架的設計、模架制造工藝設計、模架加工制造以及在模架上進行相關加工，需要大型銑床和磨床。

任務3：型腔和型芯的工藝設計、NC編程及鑲塊的粗加工，需要數(shù)控機床。

任務4：電極的工藝設計、NC編程和加工，需要精密數(shù)控機床。

任務5：鑲塊的電火花加工，需要電火花機床。

任務6：其他零部件的設計和制造、模具裝配，需要有經(jīng)驗的模具工人。

任務7：試模，需要大型注塑機。

任務8：根據(jù)試模結果進行修模，需要有經(jīng)驗的模具工人。

任務之間的先后次序關系如圖所示。企業(yè)決定任務1由自己完成，其他的任務由合作伙伴來完成。經(jīng)過初選，任務2～7有3個候選伙伴，任務8有2個候選伙伴。根據(jù)各候選伙伴的地理位置關系、需要運送的材料和運輸工具，可以估算出其費用和時間。需要項目的成本預算是70w，模糊交貨期為（39，39.5，41.5，42）。

圖3-1任務的先后順序關系

表3-1候選伙伴費用數(shù)據(jù)表

候選伙伴費用數(shù)據(jù)如表3-1所示：

候選伙伴的時間數(shù)據(jù)如表3-2所示：

遺傳算法的參數(shù)為：種群大小N＝200，交叉概率pc＝0.7，變異概率pm＝0.1，最大進化代數(shù)T＝50。

自適應遺傳算法的參數(shù)設置：種群大小N＝200，交叉概率：最大交叉概率pc0=0.9，最小交叉概率pc1=0.6，變異概率：最大變異概率pm0=0.1，最小變異概率pm1=0.001，最大進化代數(shù)T=50。

分別采用遺傳算法和自適應遺傳算法搜索結果，Matlab仿真結果為：

圖3-2遺傳算法搜索結果

利用基本遺傳算法仿真，求得極大化平均客戶滿意度的解為[1 1 2 3 1 3 3 1]，即合作伙伴的最優(yōu)組合為：{p11，p21，p32，p43，p51，p63，p73，p81}，交貨期的滿意度為100%，極大化平均客戶滿意度為：85.5%，所需要的成本為：67.4w。

采用遺傳算法進行優(yōu)化得到的任務對的滿意度如下表3-3所示：

利用自適應遺傳算法仿真，求得極大化平均客戶滿意度的解為[1 1 2 3 1 3 3 1]，即合作伙伴的最優(yōu)組合為：{p11，p21，p32，p43，p51，p63，p73，p81}，交貨期的滿意度為100%，極大化平均客戶滿意度為：85.5%，所需要的成本為：67.4w。

表3-3任務對的滿意度

采用自適應遺傳算法優(yōu)化得到的任務對的滿意度如下表3-4所示：

表3-4任務對的滿意度

從搜索結果可以得出：

1．遺傳算法和自適應遺傳算法都能達到全局最優(yōu)值。

2．在搜索速度方面，自適應遺傳算法能夠以更快的速度收斂，達到全局最優(yōu)值。

[1]MaCahon C,S,Lee.E.S.Fuzzy Job Sequencing for Flow Ship[J].European Journal of Operational Research,1992，62：294-301.

[2]Fortemps.P.Job Shop Scheduling with Impecise Durations:A Fuzzy Approach[J].IEE-E Trans on Fuzzy Systems,1997，5（4）：557-569.

[3]王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學出版社，2003：146-153.

[4]袁曉輝，王乘，張勇傳，等.水電系統(tǒng)短期經(jīng)濟運行的新方法[J].水力發(fā)電學報，2006（4）：1-5.

[5]蘇平，伍乃騏，于兆勤，等.改進遺傳算法在虛擬企業(yè)伙伴選擇與優(yōu)化中的應用[J].系統(tǒng)工程理論與實踐，2006（12）：85-92.

責任編輯：陳卓陳巖

Fuzzy Partner Selection Based on Adaptive Genetic Algorithm

ZHANG Hong
（Fujian Chuanzheng Communications College,Fuzhou Fujian 350004）

The fuzzy theory is introduced in an obscure environment.The maximum average satisfaction of the task with a sequential relationship is taken as the optimization goal.The mathematic model of project partner selection is more in line with the actual production situation.The adaptive genetic algorithm(GA)is used to improve the convergence speed of the basic genetic algorithm,thus, the global optimal value and a faster convergence speed can be obtained by verifying the algorithm.

partner selection;fuzzy number;adaptive genetic algorithm

TP18

A

2095－5537（2016）06－00073－05

2016-09-30

張紅（1969—），女，漢族，湖南省湘潭人，福建船政交通職業(yè)學院高級實驗師。研究方向：計算機應用技術、電教。