基于遺傳禁忌算法的倉庫選址優化

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

基于遺傳禁忌算法的倉庫選址優化

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

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

1 引言

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

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

2 遺傳算法與禁忌算法

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

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

圖2 禁忌算法計算過程

3 基于遺傳禁忌算法的倉庫選址優化

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

3.1 倉庫選址的數學模型

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

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

圖3 倉庫選址的模型

3.2 遺傳算法的編碼和適應度函數

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

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

3.3 遺傳算法的各個算子

在采用遺傳算法解決倉庫的選址問題中，為了簡化問題，“選擇”算子采用由概率計算的輪盤賭算法，使得適應度高的染色體優選被選中，同時，適應度低的染色體也有被選中的可能，這樣既可以保證種群的優越性，也能保證其多樣性?！敖徊妗彼阕硬捎貌糠钟成浣徊娴姆绞剑梢员ＷC每次生成的子代染色體都是有效的解?！白儺悺彼阕硬捎们懊嫠龅慕伤惴?，可以避免算法過早的收斂，而導致無法找到全局的最優解。

4 小結

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

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

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

本文由廣西科技大學校科自No.174523資助。