基于自適應(yīng)遺傳算法的模糊伙伴選擇

張紅

基于自適應(yīng)遺傳算法的模糊伙伴選擇

張紅

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

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

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

一、模糊伙伴選擇的提出

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

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

二、模型的建立

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

約束條件：

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

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

三、自適應(yīng)遺傳算法

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

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

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

自適應(yīng)交叉概率設(shè)計(jì)為：

自適應(yīng)變異概率設(shè)計(jì)為：

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

四、約束處理

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

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

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

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

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

1．當(dāng)兩個(gè)個(gè)體都是可行解時(shí)，目標(biāo)函數(shù)值較小的占優(yōu)；

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

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

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

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

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

五、實(shí)例應(yīng)用

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

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

任務(wù)2：模架的設(shè)計(jì)、模架制造工藝設(shè)計(jì)、模架加工制造以及在模架上進(jìn)行相關(guān)加工，需要大型銑床和磨床。

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

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

任務(wù)5：鑲塊的電火花加工，需要電火花機(jī)床。

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

任務(wù)7：試模，需要大型注塑機(jī)。

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

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

圖3-1任務(wù)的先后順序關(guān)系

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

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

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

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

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

分別采用遺傳算法和自適應(yīng)遺傳算法搜索結(jié)果，Matlab仿真結(jié)果為：

圖3-2遺傳算法搜索結(jié)果

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

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

利用自適應(yīng)遺傳算法仿真，求得極大化平均客戶滿意度的解為[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任務(wù)對(duì)的滿意度

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

表3-4任務(wù)對(duì)的滿意度

從搜索結(jié)果可以得出：

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

2．在搜索速度方面，自適應(yīng)遺傳算法能夠以更快的速度收斂，達(dá)到全局最優(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].北京：清華大學(xué)出版社，2003：146-153.

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

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

責(zé)任編輯：陳卓陳巖

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è)學(xué)院高級(jí)實(shí)驗(yàn)師。研究方向：計(jì)算機(jī)應(yīng)用技術(shù)、電教。