一種改進的多種群遺傳算法在車間布局的應用

摘要：針對基本遺傳算法中存在早熟的問題，本文設計出一種新的多種群遺傳算法選擇與協作方式，合理設計出種群內與種群間的協作關系，采用一種新的選擇、交叉與變異方式。實驗證明，本算法能夠有效地解決早熟問題，而且能夠達到快速的收斂。與基本遺傳算法相比較，在應用車間設施布局問題方面不但能夠快速地收斂，而且減少了物流成本費用。

Abstract： Aiming at the problem of premature maturity in basic genetic algorithm， this paper designs a new multi-group genetic algorithm to select and cooperate， and rationally design the cooperative relationship between population and population， adopting a new way of choice， cross and mutation. Experiments show that the algorithm can effectively solve the premature problem and achieve rapid convergence. Compared with the basic genetic algorithm， it can not only quickly converge on the application floor layout problem， but also reduce the logistics cost.

關鍵詞：多種群遺傳算法;設施布局;精英保留

Key words： multi-population genetic algorithm;facility layout;elite retention

中圖分類號：TH181? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）17-0206-03

0? 引言

遺傳算法是模擬生物繁殖生存演化過程，基于自然生存法則淘汰機制的一種搜索算法，能夠并行、高效、速地解決各類復雜的工程問題。最先由美國學者Holland教授[1]在1975年提出的優化算法，許多實驗都能夠證明此算法有著良好地解決全局最優化問題。雖然遺傳算法有著很強的全局搜索能力，但是許多學者驗證了算法存在著局部搜索能力差和早熟收斂等問題[2]。針對遺傳算法中的缺點，涌現了許多種有關遺傳算法操作的改進方法，如Srinivas M等人提出的自適應遺傳算法[3]、陳輝等人提出的改進的混沌量子遺傳算法[4]、李軍華等人提出的改進雙種群遺傳算法[5]、呂卉等人提出的一種多種群遺傳算法[6]，也有諸多學者嘗試與其它智能優化算法相結合等方法。本文在遺傳算法的基礎上提出一種新的多種群間協同合作方法與各種群內選擇交叉與變異方式，把此改進算法應用到車間設施布局設計之中，提高了遺傳算法的性能。

1? 模型建立

在設計車間設施布中，廠房的面積大小，選址等工作，車間的布局方式均確定的情況下，已知所有設施的大小尺寸，車間的占地面積，設施之間物流量大小與其搬運費用，建立以最小費用為目標的數學模型。模型如圖1所示。

在圖1中mk，mi，mj為設施的名稱，hj0為設施j到邊界最小的間距要求，hki為設施k和i設施之間的最小距離要求，？駐j為設施j到邊界或者與設施j-1的凈距離，s為設施擺設的行間距，s0為第一行或最后一行設備到邊界的距離。車間的多行設施布局目標是設施之間的物料搬運費用最低，建立目標函數為：C

其中：Pij為設施和設施j之間的每單位距離物料的搬運費用，Qij為設施i和設施j之間的搬運物流量，Dij為設施i和設施j之間的搬運距離。

在實際車間設施布局中，不僅要余留設施之間的最小間距，也要存在設施之間的凈距離？駐，在模型中凈距離值設為[0-1]m之間的隨機數。模型的約束條件主要包括以下幾點：

①確保同一行設備不重疊，即：

2? 算法簡介

2.1 多種群遺傳算法簡介

多種群遺傳算法是在遺傳算法的基礎上經過改進引入多種群概念而產生的：

①把單個種群改變為多個種群，每個種群都有著可控制的參數，例如交叉，變異概率，給予不同的數值能夠產生不同的搜索目的。

②通過特定的操作因子來控制各種群之間的聯系與協同進化，例如設定移民算子，可以得出所有種群最優的進化結果。

③多種群的收斂條件可以根據每個種群進化的最優個體的數量來測定，各個種群中的最優個體可以增加人工選擇算子來進行保留。

多種群遺傳算法有以下幾種優點：

各個種群不同參數的設定，例如交叉概率與變異概率的設定，可以使各個種群向著不同方向進行進化，這樣全面增強搜索能力。

各個種群之間的交流是經過特定的操作因子進行實現了，通過設定移民算子，即種群中最優個體，把最優個體引入到其他種群之中，實現各個種群之間的信息交流。

判斷整個遺傳操作過程是否收斂，設定精華種群，在精華種群中，每個個體均不參加遺傳操作，這樣每代的最佳個體均能得到保護，也可以根據精華個體的數量作為終止條件。

多種群遺傳算法流程圖如圖2所示。

2.2 多種群遺傳算法改進

本文在多種群遺傳算法的改進點是通過對選擇、交叉、變異等過程進行改進，各種群之間的協作是根據精華個體之間的遺傳操作進行的。針對每個種群中，選擇出每個種群中的最優個體，作為本種群的一個基礎遺傳操作個體，然后選擇種群中其他的個體與本群落中最優個體進行遺傳操作，且在進行交叉與變異操作過程中，最優個體是不發生改變。遺傳操作過程如圖3所示。

多種群之間的信息交流方式是通過每個種群的最優個體進行交流，對這些種群內的最優個體與所有群落中最優的一個個體進行遺傳交叉與變異操作，只改變種群內的最優個體，全局最優個體不發生基因的改變。整個多種群算法流程如圖4所示。

對于多種群遺傳算法的參數控制，交叉概率Pc與變異概率Pm采用不同的控制參數，這樣能夠保持種群的差異化，交叉概率Pc與變異概率Pm的值能夠決定算法全局搜索和局部搜索能力的均衡，交叉概率Pc的值一般保持在[0.7，0.9]區間內，變異概率Pm的值一般保持在[0.05，0.1]區間內。交叉概率Pc與變異概率Pm可采用公式（4）進行計算。

其中Pc0為交叉概率，Pm0為變異概率;單個種群的總數目為G;c是交叉概率的變化區間長度，m是變異概率的變化區間長度;frand是產生特定區間的隨機函數。

適應度函數設計：由于當占地面積有限，設施布局有可能會走出廠區的面積，在此設計出適應度函數，保證在布局的時候不會超過車間的范圍。適應度函數如公式（5）所示。

其中ck為物流成本，T為超過車間范圍的懲罰值，此處設為1000。

本文設計的多種群遺傳算法終止條件根據最大進化次數進行決定的，設置最大迭代值為gMax=500。

3? 算例分析

實驗數據來源于文獻[7]，各個設施尺寸如表1所示。車間的總面積為10m×8m。各設施之間的搬運費用如表2所示。設施之間最小間距如表3所示。

本文使用matlab2015進行仿真，整個多種群遺傳算法的程序參數設置如下：種群的數量設置為10，種群的規模設置為50，交叉概率在區間，變異概率在區間。

本文使用改進的多種群遺傳算法與遺傳算法相比較，每種算法實驗10次，實驗結果如表4所示。

本文改進的多種群遺傳算法與基本遺傳算法收斂性能如圖5所示。

由表4與圖5可得，本文改進的多種群遺傳算法相比遺傳算法有以下優勢：由于設施布局問題屬于NP-hard問題，算法只能得出近似最優解，本文改進的多種群遺傳算法最優值為1734，而基本遺傳算法得出的最優結果為1825，設施布局成本費用降低了約5%;相比基本遺傳算法，本文設計的算法在100代左右達到收斂，而基本遺傳算法在260代左右才達到收斂;本文改進的算法實驗結果標準差為46.8569，均值為1794，而基本遺傳算法標準差為128.8436，均值為1939，兩者相比本文改進的算法穩定性較好，得出的近似最優解比基本遺傳算法更優。

4? 結論

針對基本遺傳算法的早熟與局部搜索能力較弱問題，本文提出的一種改進多種群遺傳算法，能夠很好地解決這類問題，能夠達到更快的收斂與更優的結果。本文提出的多種群遺傳算法在種群間和種群內均能夠達到很好的協調，提出的新的交叉與變異方式，使得本算法有著一定的獨特性。本算法應用實例是車間設施布局問題，也可以把本算法應用到其他的領域進行更深地研究。

參考文獻：

[1]Holland， John Henry. Adaptation in natural and artificial systems： an introductory analysis with applications to biology， control， and artificial intelligence. MIT press， 1992.

[2]Jong K A D. An Analysis of the Behavior of a Class of Genetic Algorithm Adaptive System[D]. Ann Arbor， USA： University of Michigan， 1975.

[3]Srinivas M， Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems， Man， and Cybernetics， 1994， 24（4）： 656-667.

[4]陳輝，張家樹，張超.實數編碼混沌量子遺傳算法[J].控制與決策，2005，20（11）：1300-1303.

[5]李軍華，黎明，袁麗華.一種改進的雙種群遺傳算法[J].小型微型計算機系統，2008（11）：2099-2102.

[6]呂卉，周聰，鄒娟，鄭金華.基于多種群進化的遺傳算法[J].計算機工程與應用，2010，46（28）：57-60.

[7]汪一筇，米智偉.SLP和遺傳算法結合在車間設備布局中的應用[J].計算機工程與應用，2010，46（05）：211-213.

作者簡介：陸慶偉（1972-），男，上海人，畢業于上海電機技術高等專科學校，機械制造，工程師。