一種基于改進遺傳算法的煙廠卷包排產方法

向偉康，殷軍普

（上海威士頓信息技術股份有限公司，上海 200000）

0 引言

遺傳算法作為最優化領域中的一個熱點得到了廣泛應用，但由于其存在算法早期收斂、耗時長、局部搜索能力差等缺陷，在實際應用中一般會基于求解問題進行針對性優化。例如，文獻［2］設計了一種改進的遺傳算法解決旅行商問題，引入貪婪算法初始化種群并自適應調節交叉與變異；提出了一種基于二代非劣前沿排序遺傳算法的城市物流設施選址方法；基于新的編碼方式提出了一種基于改進遺傳算法的微小圖像邊緣特征快速識別方法；提出了一種改進的相對快速收斂的遺傳算法，并應用到網格任務調度管理，其增加了對染色體的分割與重組[1]。本文則提出了一種基于改進遺傳算法的煙廠卷包排產方法，針對煙廠卷包排產問題，采用特殊編碼方式、刪除了交叉算子、改進了初始化與變異算子并選擇精英保留策略，以提高遺傳算法的收斂速度。

1 煙廠卷包排產問題描述

煙廠卷包排產是以月為周期，當月要制定下月的生產計劃。已知下月的基礎數據為n臺設備和m個訂單。

設備屬性：設備號（設備的編號）、可生產牌號（設備能生產的煙支編號）、各牌號生產速度（設備單位時間內生產指定牌號的數量）、換牌時間（從一個牌號切換生產另一個牌號時，停止生產的時間）、工班制度（設備可使用的時間段）。

訂單屬性：訂單號（訂單的編號）、需求牌號（訂單所需煙支編號）、需求量（訂單所需煙支數量）、需求時間點（訂單需在該時間點前完成生產）。存在不同訂單，需求牌號相同但需求時間點不同的情況。

排產要求：訂單不拆分（每一個訂單只能由一臺設備連續生產）。

排產優先級：訂單延期量最少、設備最晚結束時間最小、設備均衡性好。訂單延期量為在需求時間點后生產該訂單的數量；設備最晚結束時間為所有設備結束時間中最晚的時間點；設備均衡性是指已開啟設備結束時間的均方差，值越小則設備均衡性越好[2]。

現在煙廠卷包排產需要解決的問題為：在滿足排產要求的前提下，如何將m個訂單按序分配給n臺設備，使得制定的生產計劃最佳。

2 遺傳算法求解煙廠卷包排產問題

傳統遺傳算法求解煙廠卷包排產問題步驟如下：

（1）以訂單為基礎對生產順序和生產設備進行編碼。生產順序編碼為可由訂單亂序后生成，si表示第i個訂單亂序后的位置，排產時訂單按編碼從小到大的順序進行生產；生產設備編碼可從生產該訂單的設備集合中隨機選取一個，排產時訂單按編碼指定設備進行生產。現總共有m個訂單，第i個訂單Oi的編碼對應si，c i。因此，一個個體的編碼為設置種群規模為N，進行種群初始化。隨機生成N個個體，種群的編碼集合，每一個代表一個個體。

（2）計算種群中各個個體的適應度。首先，基于各個體編碼生成排產計劃；其次，根據當前的排產計劃計算訂單延期量v1、設備最晚結束時間v2、設備均衡性v3；再次，基于整個種群的數據分布分別對v1，v2，v3作最大最小歸一化處理；最后計算適應度，ki代表vi所占適應度的比重，建議

（3）輪盤選擇法選擇N個個體作為新種群。已知現有種群適應度列表，v i表示第i個個體的適應度。首先，計算各個個體被隨機選中的概率得到種群中個體的概率分布；然后，按序統計各個個體所代表被選中的區域其中；最后，進行N次輪盤選擇，每次隨機獲取0到1范圍內一個數r，找到所屬區域即表示本次選擇第i個個體。

（4）兩兩交叉得到新的N個個體作為新種群。首先，將現有種群中個體亂序并兩兩分為一組；然后，以組為單位從m個訂單中隨機選擇一個本組的目標訂單；最后，將組內兩個個體中目標訂單的生產設備編碼互換。

（5）種群中N個個體進行變異。設置生產順序編碼變異概率和生產設備編碼變異概率。先判斷是否進行生產順序編碼變異，如需變異則對生產順序編碼亂序改變訂單生產順序；后判斷每個訂單是否進行生產設備編碼變異，如需變異則獲取除所選生產設備編碼外的其它可生產該訂單的設備集合，當集合為空則不變異，否則從中隨機選擇一個作為該訂單新的生產設備編碼。跳轉到（2）。

（2）-（5）步驟不停循環選出最優個體并安排詳細的生產計劃。

3 改進遺傳算法求解煙廠卷包排產問題

本文第2章遺傳算法求解煙廠卷包排產問題時存在兩個缺點：一是，隨機性太大，導致求解速度慢且不易找到最優解。二是，交叉變異操作可能會使種群中個體往差的方向變化，導致算法不收斂。

因此，本章針對這些缺點做了一些改進：一是，在遺傳算法初始化與變異過程中利用排產經驗指導個體去接近最優解，以提高搜索速度。生產順序編碼時，讓要貨期早的訂單優先生產，使訂單延期量盡量少。生產設備編碼時，讓設備生產的訂單量大致相同，使設備最晚結束時間早且設備均衡性好。相比于變異算子，利用排產經驗指導交叉算子操作的步驟繁瑣且耗時，而直接進行交叉有較大概率導致種群往差的方向變化，故刪除交叉算子。二是，種群中個體在變異前保留一半較優的個體，可以防止算法不收斂[3]。

改進遺傳算法求解煙廠卷包排產問題步驟如下：

（1）確定煙廠卷包排產的編碼方式并初始化種群。改進遺傳算法的編碼方式與第2章編碼方式一致，但初始化種群個體會稍有區別。首先，訂單按其要貨期從早到晚排序；然后，在要貨期相同的訂單之間進行亂序，生成生產順序編碼，其與第2章的生產順序編碼相比多添加了一個條件：當o i的要貨期

（2）精英保留。計算N個個體的適應度并排序，復制并保存一半較優的個體。

（3）優化變異算子。設置生產順序編碼變異概率、生產設備編碼變異概率和全局搜索概率，對N個個體分別進行變異。先進行生產順序編碼變異，基于生產順序編碼變異概率判斷生產順序是否變異，基于全局搜索概率來判斷變異方式。如需變異且不為全局搜索，則只將要貨期相同的訂單進行內部亂序；如需變異且為全局搜索，則所有訂單亂序。后進行生產設備編碼變異，基于生產設備編碼變異概率判斷生產設備是否變異，基于全局搜索概率來判斷變異方式。如需變異且不為全局搜索，則獲取當前訂單的所有可生產設備，統計可生產設備已被其它訂單選擇的次數，未被選擇為0次，被目標訂單選擇的設備加0.5次（次數相同時，生產設備編碼變化優先），從被選次數最少的設備中隨機選擇一個設備作為該訂單新的生產設備編碼；如需變異且為全局搜索，則獲取當前訂單除已選設備外的其它可生產設備集合，當集合為空則不變異，否則從中隨機選擇一個作為該訂單新的生產設備編碼[4]。

（4）將b中精英個體合并入c中的新種群，計算適應度并排序，選出靠前的N個個體作為新種群。

（2）-（3）-（4）步驟不停循環選出最優個體并安排詳細的生產計劃。

本文以解決煙廠的卷包排產問題為出發點，采用傳統遺傳算法來尋找最佳的卷包排產生產計劃。但是，由于遺傳算法求解速度慢、穩定性差、不易收斂等缺點導致其實用性很差。為了找到產生這些缺點的原因，通過分析遺傳算法求解卷包排產生產計劃的過程，發現其在選擇、交叉、變異等操作過程中種群及個體變好變壞是隨機的，例如選擇操作在小概率情況下可能拋棄當前的最優個體，交叉變異操作的隨機性可能導致個體變壞。為了解決傳統遺傳算法在實際使用中帶來的這些問題，將卷包排產經驗與遺傳算法相結合，例如為了訂單不延期則要貨期早的訂單肯定優先生產，為了設備均衡性好則讓設備生產的訂單量大致相同。遺傳算法在種群初始化過程中通過卷包排產經驗引導種群個體盡量靠近最優解，而在種群迭代過程中通過卷包排產經驗引導種群及個體向好的方向隨機變化，這樣不僅可以大大提高求解速度、而且提高了算法的穩定性。同時，采用精英保留策略可以進一步提高遺傳算法的求解速度。最終，形成了針對卷包排產問題的改進遺傳算法[5]。

4 結語

本文設計了一種改進遺傳算法來解決煙廠卷包排產問題，其核心是基于排產經驗對遺傳算法初始化與變異步驟進行改進以提高算法的求解速度，同時引入了精英保留策略確保算法收斂。該方法能在較少的迭代次數內，得到較優的排產結果。