求解選址問(wèn)題遺傳算法的適應(yīng)度函數(shù)選擇

孫 濤

(1.中國(guó)石油大學(xué)勝利學(xué)院基礎(chǔ)科學(xué)學(xué)院，山東 東營(yíng) 257000;2.中國(guó)石油大學(xué)儲(chǔ)運(yùn)與建筑工程學(xué)院，山東 青島 266580)

配送中心選址問(wèn)題是指在一個(gè)固定連續(xù)區(qū)域內(nèi)分布著一些需求點(diǎn)，要求在此區(qū)域建立配送中心，在滿足一定約束的前提下，確定配送中心的位置和需求點(diǎn)的分配方案，使得配送距離最短或配送費(fèi)用最低。由于問(wèn)題的復(fù)雜性，傳統(tǒng)優(yōu)化方法很難取得好的效果，而以遺傳算法為代表的智能算法能夠更加有效地求解此類問(wèn)題。遺傳算法是一種高效的全局優(yōu)化技術(shù)，在優(yōu)化運(yùn)算、機(jī)器學(xué)習(xí)、智能控制等許多領(lǐng)域都得到了成功的運(yùn)用［1-3］，目前已有眾多研究將遺傳算法應(yīng)用于配送中心選址問(wèn)題［4-6］上，本文在使用遺傳算法時(shí)，將配送中心的位置坐標(biāo)進(jìn)行編碼，使用貪心算法給出近似最優(yōu)分配方案并計(jì)算適應(yīng)度函數(shù)，通過(guò)遺傳進(jìn)化，得出最終的配送中心位置坐標(biāo)與需求點(diǎn)的分配方案，并通過(guò)實(shí)例將算法與使用分枝定界法進(jìn)行比較。

1 配送中心選址問(wèn)題的數(shù)學(xué)模型

假設(shè)在一連續(xù)的平面區(qū)域D內(nèi)分布著n個(gè)需求點(diǎn)，需求點(diǎn)的位置坐標(biāo)(aj，bj)，j=1，2，…，n，要求在區(qū)域D內(nèi)建立p個(gè)配送中心，給出配送距離最短或配送費(fèi)用最低的配送中心位置及需求點(diǎn)的分配方案，其優(yōu)化問(wèn)題的數(shù)學(xué)模型

其中，cij為連接的權(quán)重，(xi，yi)為配送中心的位置坐標(biāo)，i=1，2，…，p，j=1，2，…，n。約束(1)表明一個(gè)需求點(diǎn)只能連接到一個(gè)配送中心;約束(2)為配送中心連接需求點(diǎn)不能超過(guò)k;約束(3)為配送中心位置坐標(biāo)的幾何約束。

2 遺傳算法的實(shí)現(xiàn)

2.1 編碼方案

遺傳算法的編碼是對(duì)問(wèn)題的可行解進(jìn)行某種編碼，將問(wèn)題的解空間轉(zhuǎn)化為編碼空間，每一個(gè)可行解對(duì)應(yīng)一個(gè)編碼，稱為個(gè)體或染色體，常用的編碼有二進(jìn)制編碼、實(shí)數(shù)編碼等。由于模型中既含有連續(xù)變量，又含有離散變量，為簡(jiǎn)化運(yùn)算，本文采用實(shí)數(shù)編碼，將p個(gè)配送中心的位置坐標(biāo)按順序?qū)懗梢粋€(gè)2p維的實(shí)數(shù)向量，每個(gè)實(shí)數(shù)向量即為一個(gè)個(gè)體。

2.2 確定適應(yīng)度函數(shù)

適應(yīng)度是衡量個(gè)體優(yōu)劣的指標(biāo)，它直接決定每個(gè)個(gè)體的存活概率，而適應(yīng)度函數(shù)的構(gòu)造一般是對(duì)目標(biāo)函數(shù)值進(jìn)行改造，這時(shí)需要計(jì)算每個(gè)個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值，對(duì)于每個(gè)個(gè)體，由于配送中心位置坐標(biāo)已經(jīng)確定，模型就簡(jiǎn)化成了一個(gè)0－1規(guī)劃模型，通過(guò)求解這一簡(jiǎn)化模型可得到每個(gè)個(gè)體對(duì)應(yīng)的分配方案和目標(biāo)函數(shù)值，從而得到每個(gè)個(gè)體對(duì)應(yīng)的可行解與適應(yīng)度函數(shù)。

在此并不求解最優(yōu)的分配方案，而是選用貪心算法給出一個(gè)近似最優(yōu)分配方案，具體做法如下:

(1)按需求點(diǎn)到配送中心的距離由小到大排列;

(2)將距離最小的需求點(diǎn)與配送中心選出，將此需求點(diǎn)歸入這一配送中心;

(3)刪除這一需求點(diǎn)對(duì)應(yīng)的所有距離值;

(4)檢驗(yàn)配送中心是否已達(dá)到最大連接數(shù)，如果已達(dá)最大連接數(shù)，則刪除配送中心對(duì)應(yīng)的所有距離值。

(5)返回步驟(1)，直到所有需求點(diǎn)分配完成。

2.3 遺傳算子的確定

(1)選擇算子模擬的是“物競(jìng)天擇，適者生存”的自然進(jìn)化原理，是從當(dāng)前種群中以一定概率選取個(gè)體用作父本去繁殖后代，個(gè)體被選中的概率與適應(yīng)度值有關(guān)。常用的選擇方法有比例選擇、排序選擇等，本文使用的是比例選擇。

(2)交叉算子模擬生物進(jìn)化中的有性繁殖，是從種群中選擇兩個(gè)父本個(gè)體，通過(guò)兩交換組合產(chǎn)生兩個(gè)新個(gè)體。常用的交叉方案有單點(diǎn)交叉、雙點(diǎn)交叉、均勻交叉等，本文采用單點(diǎn)交叉。

(3)變異算子選擇。對(duì)交叉后的染色體進(jìn)行變異是為了防止算法陷入局部搜索，提高算法達(dá)到全局最優(yōu)解的機(jī)會(huì)，變異操作采用均勻變異，即隨機(jī)選取父染色體的一個(gè)基因，然后用在可行域內(nèi)區(qū)間中均勻分布的一個(gè)隨機(jī)數(shù)代替［2］。

2.4 保優(yōu)與終止進(jìn)化準(zhǔn)則

在算法中，記錄每次迭代的最優(yōu)染色體，每次迭代都將記錄的上一代的最優(yōu)染色體取代新種群中適應(yīng)度最差的染色體，以保證優(yōu)良基因的延續(xù)。遺傳算法的終止準(zhǔn)則常常是根據(jù)計(jì)算代價(jià)與計(jì)算結(jié)果的權(quán)衡，本文采用預(yù)先設(shè)定進(jìn)行時(shí)限的終止準(zhǔn)則。

3 算例分析

在一矩形區(qū)域，隨機(jī)分布44個(gè)需求點(diǎn)，其坐標(biāo)見(jiàn)表1，現(xiàn)要求在上述區(qū)域設(shè)置6個(gè)地址建立配送中心，使得需求度到配送中心的總路程最短，其中每個(gè)需求點(diǎn)只能連接到一個(gè)配送中心，而每個(gè)配送中心的最大連接數(shù)為8。使用遺傳算法運(yùn)算，種群規(guī)模為40，進(jìn)化600代。分別使用貪心算法和分枝定界法計(jì)算適應(yīng)度，其中分枝定界法求解使用MATLAB函數(shù)bintprog實(shí)現(xiàn)。

表1 區(qū)域站點(diǎn)原始數(shù)據(jù)

遺傳算法的迭代過(guò)程比較見(jiàn)圖1，從圖1中可知雖然貪心算法只給出了近似最優(yōu)的分配方案，但經(jīng)過(guò)遺傳算法的進(jìn)化，算法仍然能夠收斂到全局最優(yōu)解。

圖1 算法優(yōu)化過(guò)程圖

兩種算法的主要優(yōu)化結(jié)果見(jiàn)表2，雖然所得到的中心位置各異，但最終的目標(biāo)函數(shù)值相差不大，在計(jì)算時(shí)間上，由于使用貪心算法在每次迭代中不用求解最優(yōu)，與使用分枝定界法相比，計(jì)算效率高出兩個(gè)數(shù)量級(jí)。

表2 主要優(yōu)化結(jié)果對(duì)比

4 結(jié)束語(yǔ)

使用遺傳算法求解配送中心選址問(wèn)題，將配送中心的位置坐標(biāo)和需求點(diǎn)的分配方案分開(kāi)，將位置坐標(biāo)進(jìn)行實(shí)數(shù)編碼，在計(jì)算適應(yīng)度函數(shù)時(shí)，采用貪心算法給出分配方案，從而得到適應(yīng)度函數(shù)。與使用分枝定界法比較，雖然貪心算法只給出了近似最優(yōu)的分配方案，但由于遺傳算法的全局尋優(yōu)能力，算法仍然能夠收斂到全局最優(yōu)解，而且由于貪心算法方法簡(jiǎn)單、計(jì)算量小，在計(jì)算時(shí)間上，較使用分枝定界法有明顯的優(yōu)勢(shì)，實(shí)際的算例也驗(yàn)證了算法的收斂性和有效性。

［1］阮曉青，周義倉(cāng).數(shù)學(xué)建模引論［M］.北京:高等教育出版社，2006:116-188.

［2］史峰，王輝，郁磊，等.MATLAB智能算法30個(gè)案例分析［M］.北京:北京航空航天大學(xué)出版社，2011:17-26.

［3］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002:1-50.

［4］吳堅(jiān)，史忠科.基于遺傳算法的配送中心選址問(wèn)題［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2004.6，32(6):71-74.

［5］劉揚(yáng)，鞠志忠，鮑云波.一類多級(jí)星式網(wǎng)絡(luò)的拓?fù)鋬?yōu)化設(shè)計(jì)方法［J］.大慶石油學(xué)院學(xué)報(bào)，2009，33(2):68-73.

［6］姜大立，楊西龍.易腐物品配送中心連續(xù)選址模型及其遺傳算法［J］.系統(tǒng)工程理論與實(shí)踐，2003(2):62-67.