歐陽浩 廣西科技大學計通學院

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

歐陽浩 廣西科技大學計通學院

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

1 引言

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

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

2 遺傳算法與禁忌算法

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

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

圖2 禁忌算法計算過程

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

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

3.1 倉庫選址的數(shù)學模型

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

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

圖3 倉庫選址的模型

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

在遺傳算法的編碼過程中用Xi來表示第i個候選地點是否被選中。fij表示第i個候選地點到達地第j個需求地的貨物量，rij表示第i個候選地點到達地第j個需求地的距離。

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

3.3 遺傳算法的各個算子

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

4 小結(jié)

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

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

[2]趙振亞,霍國先.基于模擬退火算法的應急物流倉庫選址優(yōu)化[J].大連交通大學學報,2010,31(3):102-106.

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