向偉康，殷軍普

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

0 引言

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

1 煙廠卷包排產(chǎn)問題描述

煙廠卷包排產(chǎn)是以月為周期，當(dāng)月要制定下月的生產(chǎn)計劃。已知下月的基礎(chǔ)數(shù)據(jù)為n臺設(shè)備和m個訂單。

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

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

排產(chǎn)要求：訂單不拆分（每一個訂單只能由一臺設(shè)備連續(xù)生產(chǎn)）。

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

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

2 遺傳算法求解煙廠卷包排產(chǎn)問題

傳統(tǒng)遺傳算法求解煙廠卷包排產(chǎn)問題步驟如下：

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

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

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

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

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

（2）-（5）步驟不停循環(huán)選出最優(yōu)個體并安排詳細的生產(chǎn)計劃。

3 改進遺傳算法求解煙廠卷包排產(chǎn)問題

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

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

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

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

（2）精英保留。計算N個個體的適應(yīng)度并排序，復(fù)制并保存一半較優(yōu)的個體。

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

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

（2）-（3）-（4）步驟不停循環(huán)選出最優(yōu)個體并安排詳細的生產(chǎn)計劃。

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

4 結(jié)語

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