一種基于改進(jìn)遺傳算法的煙廠卷包排產(chǎn)方法

向偉康，殷軍普

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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