基于遺傳禁忌算法的倉(cāng)庫(kù)選址優(yōu)化

歐陽(yáng)浩 廣西科技大學(xué)計(jì)通學(xué)院

基于遺傳禁忌算法的倉(cāng)庫(kù)選址優(yōu)化

歐陽(yáng)浩 廣西科技大學(xué)計(jì)通學(xué)院

針對(duì)物流行業(yè)的倉(cāng)庫(kù)選址問(wèn)題，本文提出了一種基于遺傳禁忌算法的解決方法。在算法的計(jì)算過(guò)程中，先對(duì)選址問(wèn)題進(jìn)行有效的編碼，然后對(duì)編碼后的染色體進(jìn)行選擇，交叉以及變異。而其中的變異計(jì)算采用的是禁忌算法，可以有效避免遺傳算法的過(guò)早收斂，從而獲得更優(yōu)的值。

1 引言

如何優(yōu)化倉(cāng)庫(kù)的選址一直是物流行業(yè)中的一個(gè)重要問(wèn)題，優(yōu)化后的選址可以大大降低物流中的運(yùn)營(yíng)成本。因此，該問(wèn)題實(shí)質(zhì)上是如何對(duì)一個(gè)最優(yōu)化問(wèn)題的求解。遺傳算法在求解最優(yōu)化問(wèn)題中得到了普遍的運(yùn)用，其實(shí)現(xiàn)起來(lái)簡(jiǎn)單，可以在較短的時(shí)間里獲得一個(gè)比較理想的結(jié)果，但傳統(tǒng)的遺傳算法也有著一定的局限性，當(dāng)其進(jìn)化到一定程度，算法將將陷入到某個(gè)局部最優(yōu)解中，從而無(wú)法再進(jìn)化下去。

本文將根據(jù)遺傳算法的特點(diǎn)，在此基礎(chǔ)上引入禁忌算法，將禁忌算法作為遺傳算法的變異算子，從而使得計(jì)算可以跳出局部最優(yōu)解，最終獲得全局上的優(yōu)化結(jié)果。

2 遺傳算法與禁忌算法

遺傳算法是一種模擬大自然中“適者生存”法則的智能進(jìn)化算法，模擬過(guò)程中，包括種群的“選擇”，“交叉”以及“變異”計(jì)算。從而不斷地迭代和進(jìn)化，使得計(jì)算結(jié)果逐漸優(yōu)化。

禁忌算法是在計(jì)算過(guò)程中使用一張禁忌表，禁忌表中將記錄最近計(jì)算得到的值，在今后的一段時(shí)間內(nèi)，表中的值禁忌出現(xiàn)。為了提升算法的求解能力，若計(jì)算獲得的新值優(yōu)于此前設(shè)定的某個(gè)閾值時(shí)，這個(gè)新的值不管是否在禁忌表中，都能被接受，此過(guò)程稱(chēng)為“破禁”。算法的計(jì)算過(guò)程如圖2所示。計(jì)算中，迭代次數(shù)記為NG，適應(yīng)度的計(jì)算公式為C(X)，禁忌表為T(mén)。

圖2 禁忌算法計(jì)算過(guò)程

3 基于遺傳禁忌算法的倉(cāng)庫(kù)選址優(yōu)化

由于遺傳算法容易陷入到“局部最優(yōu)”中，從而使得進(jìn)化過(guò)程將停滯不前，因此，改變遺傳算法中傳統(tǒng)的“變異”算子，使用禁忌算法作為遺傳算法的“變異”算子，將大大提升遺傳算法的進(jìn)化能力。完成新算法中，需要考慮的問(wèn)題還包括問(wèn)題的編碼，適應(yīng)度函數(shù)的確定，“選擇”和“交叉”算子的設(shè)計(jì)。

3.1 倉(cāng)庫(kù)選址的數(shù)學(xué)模型

為了解決倉(cāng)庫(kù)選址問(wèn)題，首先需要將該區(qū)域劃分為多個(gè)方格，方格中包括了貨物的需求地點(diǎn)以及倉(cāng)庫(kù)候選地點(diǎn)，從而構(gòu)成選址問(wèn)題的數(shù)據(jù)模型，此模型的示意圖見(jiàn)圖3。

設(shè)數(shù)學(xué)模型中包括n個(gè)貨物需求地點(diǎn)，m個(gè)倉(cāng)庫(kù)候選地點(diǎn)，由此，倉(cāng)庫(kù)選址問(wèn)題就演變成了如何從m個(gè)候選地點(diǎn)中選出K個(gè)確定的地點(diǎn)。此問(wèn)題若采用傳統(tǒng)的窮舉法，計(jì)算量會(huì)隨著m的增大而成指數(shù)上升。由此，采用智能計(jì)算方式有利于計(jì)算此類(lèi)問(wèn)題。

圖3 倉(cāng)庫(kù)選址的模型

3.2 遺傳算法的編碼和適應(yīng)度函數(shù)

在遺傳算法的編碼過(guò)程中用Xi來(lái)表示第i個(gè)候選地點(diǎn)是否被選中。fij表示第i個(gè)候選地點(diǎn)到達(dá)地第j個(gè)需求地的貨物量，rij表示第i個(gè)候選地點(diǎn)到達(dá)地第j個(gè)需求地的距離。

這樣，倉(cāng)庫(kù)選址實(shí)際上就是去求得下面G(X)公式的最優(yōu)值。適應(yīng)度函數(shù)可以取1/G(X)。

3.3 遺傳算法的各個(gè)算子

在采用遺傳算法解決倉(cāng)庫(kù)的選址問(wèn)題中，為了簡(jiǎn)化問(wèn)題，“選擇”算子采用由概率計(jì)算的輪盤(pán)賭算法，使得適應(yīng)度高的染色體優(yōu)選被選中，同時(shí)，適應(yīng)度低的染色體也有被選中的可能，這樣既可以保證種群的優(yōu)越性，也能保證其多樣性。“交叉”算子采用部分映射交叉的方式，可以保證每次生成的子代染色體都是有效的解?！白儺悺彼阕硬捎们懊嫠龅慕伤惴ǎ梢员苊馑惴ㄟ^(guò)早的收斂，而導(dǎo)致無(wú)法找到全局的最優(yōu)解。

4 小結(jié)

本文介紹了一種基于遺傳禁忌的算法來(lái)解決倉(cāng)庫(kù)選址的優(yōu)化問(wèn)題，相對(duì)傳統(tǒng)的遺傳算法而言，本文提出的算法可以更好地獲得全局最優(yōu)解。當(dāng)然，本文提出的數(shù)學(xué)模型未能考慮選址中是否存在限定條件等因素，在今后的研究中，需要進(jìn)一步研究和改進(jìn)。

[1]歐陽(yáng)浩,王萌,黃鎮(zhèn)謹(jǐn)?shù)?用遺傳算法解決物流中的倉(cāng)庫(kù)選址問(wèn)題[J].制造業(yè)自動(dòng)化,2014,36(1):51-52,64.

[2]趙振亞,霍國(guó)先.基于模擬退火算法的應(yīng)急物流倉(cāng)庫(kù)選址優(yōu)化[J].大連交通大學(xué)學(xué)報(bào),2010,31(3):102-106.

本文由廣西科技大學(xué)?？谱訬o.174523資助。