矩陣式編碼智能算法在生產批量計劃中的應用

（中國計量大學 質量與安全工程學院，杭州 310018）

生產批量計劃問題是確定最優(yōu)的生產批量計劃，使得生產、生產準備和庫存費用綜合指標最小或利潤最大[1-2]。受到資源約束的情況下，為消除各種資源間的沖突，需要同時對項目、時間和數(shù)量這三維變量進行調整[3-4]，隨著求解問題規(guī)模的增大，精確解的計算量也增大。

遺傳算法在求解大規(guī)模問題時易陷入局部最優(yōu)解中，從而難以得到符合預期的解[5-7]。在研究生產批量計劃問題時，也有學者將粒子群算法和遺傳算法相結合，一定程度上彌補了GA局部搜索能力弱的缺陷，但可能以損失種群多樣性為代價降低算法搜索效率，最終搜索得到的解不易滿足預期要求。利用蟻群算法求解生產批量問題的相關研究較少，少數(shù)學者進行了一些研究，并將研究成果應用在固定的模型與生產實例中[8]。

本文對求解算法進行創(chuàng)新性的改進以提升算法性能。通過矩陣式編碼的智能算法尋到近似最優(yōu)的生產批量計劃并將所求的結果與基本遺傳算法和遺傳粒子群算法進行對比，以證明改進算法提升了算法性能。

1 生產批量計劃問題的數(shù)學模型

本文所考慮有能力約束的多級生產批量CMLLS（constrained multilevel lot-sizing）問題，問題描述為在給定的計劃時間范圍內，確定全部項目在不同時間段上的生產數(shù)量，使得總費用之和最小。CMLLS問題與實際生產計劃更加貼近，是生產批量問題研究的重點。本文采用的數(shù)學模型為[9-10]

式（1）為總費用，包括生產準備費用及庫存費用；式（2）為物流守衡方程；式（3）為需求公式，如果物料i是最終項目，則需求為外部需求，否則需求由當前物料i的所有后繼物料的生產量決定；式（4）為資源約束條件；式（5）為只有在生產數(shù)量大于0時才能進行生產調整；式（6）為二進制決策變量，1表示生產，0表示不生產；式（7）為生產量和庫存量不能為負數(shù)。

2 遺傳算法的改進策略

2.1 改進方法

遺傳算法求解過程本質上是隨機尋優(yōu)過程，但是遺傳算法是按照概率隨機進行的尋優(yōu)操作，在大多數(shù)情況下只能得到全局范圍的次優(yōu)解，不易獲得最優(yōu)解，這是因為它的搜索是隨機的，帶有一定的盲目性[12]。

粒子群算法對自身參數(shù)的依賴很大，且初始粒子群是隨機生成的，通常具有收斂速度慢、易陷入局部收斂等方面的缺陷[13]。

蟻群算法雖然通用性、魯棒性較好，以及在各個領域的廣泛應用近些年來受到越來越多的關注，但是把傳統(tǒng)蟻群算法應用于求解涂料生產調度時，難以滿足所有的約束條件[14]。

鑒于遺傳算法、蟻群算法和粒子群算法存在一定的不足，本文將遺傳算法、蟻群算法和粒子群算法融合以便于生產批量計劃的求解，具體的計算步驟為

步驟1隨機生成粒子位置，并按照上述算法得到初始種群（粒子群）。初始化全局極值和個體極值為第一個個體（粒子）的適應度函數(shù)值；

步驟2對當前種群（粒子群）的各個個體（粒子）描述求解適應度函數(shù)值；

步驟3按照適應度函數(shù)值對當前種群 （粒子群）進行排序，找出個體極值和全局極值；

步驟4選擇：用5個隨機的新個體替換種群（粒子群）中適應度函數(shù)值較差的5個個體（粒子）；

步驟5交叉：以輪盤賭博方式，改變種群（粒子群）中的部分個體（粒子）的特性；

步驟6變異：采用粒子群算法的更新規(guī)則對種群（粒子群）中的所有個體（粒子）進行更新；

步驟7變異：采用蟻群算法的信息素全局更新規(guī)則中的所有個體（粒子）進行更新；

步驟8變異：采用蟻群算法的信息素局部更新規(guī)則中的所有個體（粒子）進行更新；

步驟9查看是否達到最大迭代次數(shù)，如果是則轉步驟8，否則轉步驟2；

步驟10仿真結束。

具體的改進結合蟻群算法的遺傳粒子群算法的計算流程如圖1所示。

2.2 編碼方式

為使用本文提出的粒子群、蟻群和遺傳算法結合的智能算法，我們將生產批量進行編碼作為個體（粒子），其目的是讓計算機能夠利用矩陣計算以大幅提高計算效率。個體（粒子）選擇1～2048之間的隨機整數(shù)。具體的某粒子矩陣式編碼表如表1所示。

為了使用粒子群算法的位置和速度更新公式，需要對粒子速度進行編碼。具體的某粒子速度矩陣式編碼表如表2所示。其中，粒子速度選擇-128～128之間的隨機整數(shù)。

定義粒子在粒子群算法中的更新算法。更新的粒子位置矩陣由舊的粒子位置矩陣和粒子速度矩陣相加，當新的粒子編碼矩陣中的元素越界時，越界元素由新的1～2048之間的隨機整數(shù)進行替換。

圖1 改進的智能算法流程Fig.1 Flow chart of improved intelligent algorithm

表1 某粒子矩陣式編碼表Tab.1 A particle matrix encoding table

表2 某粒子速度矩陣式編碼表Tab.2 A particle velocity matrix encoding table

本文在計算過程中采用矩陣計算。顯然，相較于簡單的數(shù)字計算，矩陣計算具有計算速度敏捷的優(yōu)點。

3 實例測試

3.1 仿真實例

小型機是一種輕量型的計算機。本文收集到某計算機生產廠家接到一批2016年度的小型機訂單，該訂單要在一年內交付897臺小型機，各月至少需要的交付數(shù)量為 51、8、45、98、86、57、6、181、139、57、27、142。生產1件小型機需要事先生產得到7個小型機箱體A和9件小型機外包裝。由于電子器件壽命、員工工資變化、生產和裝配造成的機器耗損和廠房維修等各種因素每月各異，小型機處理器、箱體和外包裝的生產費用、裝配費用、庫存費用每月各異，具體如表3～表5所示。

表3 小型機單件生產費用月度表（單位：元，每月平均值）Tab.3 Minicomputer piece production cost monthly report（Unit：Yuan，monthly average）

表4 小型機裝配費用月度表（單位：元，每月平均值）Tab.4 Minicomputer assembly cost monthly report（Unit：Yuan，monthly average）

表5 小型機單件庫存費用月度表（單位：元，每月平均值）Tab.5 Minicomputer piece inventory cost monthly report（Unit：Yuan，monthly average）

裝配和生產小型機需要對小型機處理器、箱體和外包裝的外側噴塑（一層輕薄的塑料薄膜，生產和裝配前貼住，生產和裝配完成時揭下）以形成保護層，防止小型機處理器、箱體和外包裝意外受損。由于溫度、濕度等各種因素每月各異，每件部件的噴塑損失每月各異，具體如表6～表7所示。

表6 小型機裝配過程噴塑損失月度表（單位：cm3/件，每月平均值）Tab.6 Minicomputer spraying plastics losses monthly report in the assembling process（Unit：cm3/piece，monthly average）

表7 小型機庫存過程噴塑損失月度表（單位：cm3/件，每月平均值）Tab.7 Minicomputer spraying plastics losses monthly report in the inventory process（Unit：cm3/piece，monthly average）

廠家根據(jù)環(huán)境保障局的相關規(guī)定，計劃生產該批次小型機造成的噴塑損失不超過645000 cm3。

廠家希望結合生產需求給出較為合理的生產批量計劃以盡可能小的成本生產該批量897臺小型機，即在上述條件下，尋求每個月的生產小型機的數(shù)量以使生產費用、裝配費用和庫存費用的綜合成本費用盡可能的省。

3.2 仿真結果

對于上述實際應用算例，采用矩陣式編碼的遺傳算法、蟻群算法和粒子群算法結合的智能算法連續(xù)仿真20次可以得到下述仿真結果。具體的20次仿真過程中最優(yōu)結果的當前代最優(yōu)解與進化代數(shù)的關系曲線如圖2所示。

圖2 當前代最優(yōu)解與進化代數(shù)的關系Fig.2 Relation curve between the optimal solution of current generation and the evolutionary algebra

具體的20次仿真過程中最優(yōu)解函數(shù)值和收斂代數(shù)與進化代數(shù)的關系曲線如圖3所示。

圖3 最優(yōu)解函數(shù)值和收斂代數(shù)與進化代數(shù)的關系Fig.3 Relation curve between the optimal solution and the convergence algebra of current generation and the evolutionary algebra

由圖3可知，20次仿真過程中每一次計算得到的最優(yōu)解函數(shù)值Y∈（2.2×106，2.3×106）元，收斂代數(shù)小于200代。證明了本文提出的智能算法具有良好的收斂性能，適于解決多級有資源約束生產批量計劃問題。

本文基于上述實際應用算例對提出的矩陣式編碼的智能算法和普通粒子群（PSO）算法和遺傳算法進行對比測試。具體的測試結果如圖4所示。

圖4 實際應用算例的數(shù)學模型的測試結果Fig.4 Results of mathematical model of practical application example

由圖4可知，本文提出的矩陣式編碼的智能算法較優(yōu)，得到的最優(yōu)解更接近于實際最優(yōu)解且收斂速度更快。最優(yōu)解函數(shù)值Y＜2.25×106元。

為了驗證本文提出的智能算法相比于基本粒子群算法收斂性更好，采用相同算例，多次試驗仿真結果如表8所示。

表8 改進的算法與粒子群算法的結果比較Tab.8 Comparison of the results of improved algorithm and particle swarm optimization algorithm

由表8可知，改進后的算法相比于基本粒子群算法，計算時間減少了一半左右，計算結果的適應度值也有明顯改善。

4 結語

如何實現(xiàn)生產費用、生產準備費用和庫存費用綜合指標最小或利潤最大，是關系企業(yè)生存與發(fā)展的重要課題。本文提出的一種新型的矩陣式編碼的蟻群算法、遺傳算法和粒子群算法相結合的智能算法有高速的計算性能、便于搜索近似最優(yōu)解，可以得到比傳統(tǒng)算法更好的計算效果，能滿足當代企業(yè)對生產批量精確的要求。

[1]梁海峰.基于仿真的柔性自動化鋼料加工車間規(guī)劃設計研究[D].大連：大連理工大學，2005.

[2]屈國強.求解流水車間調度問題的瓶頸指向啟發(fā)式算法[J].計算機集成制造系統(tǒng)，2012，18（2）：356-363.

[3]Ruiz R，V-R J A.The hybrid flowshop scheduling problem[J]. European Journal of Operational Research，2010，205（1）：1-18.

[4]周輝仁，唐萬生，魏穎輝.柔性Flow-Shop調度的遺傳算法優(yōu)化[J].計算機工程與應用，2009，45（30）：224-226.

[5]唐海波，葉春明，劉長平，等.基于知識進化粒子群算法的模糊交貨期流水車間調度問題[J].計算機集成制造系統(tǒng)，2012，18（4）：807-812.

[6]王圣堯，王凌，許燁，等.求解混合流水車間調度問題的分布估計算法[J].自動化學報，2012，38（3）：437-443.

[7]M N，Hansen P.Variable neighborhood search[J].Computers&Operations Research，1997，24（11）：145-184.

[8]李英俊，陳志祥.蟻群算法在單級多時段多資源約束的生產批量問題的應用研究[J].中國機械工程，2012，23（19）：2326-2330.

[9]Pan Q K，Ruiz R.An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J].Omega，2012，40（2）：166-180.

[10]周云鵬，題正義.遺傳算法在組合優(yōu)化中的應用[J].遼寧工程技術大學學報：自然科學版，2005，24（z1）：283-285.

[11]Xu Y，Wang L，Zhou G，et al.An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem[C]// Proceedings of the International Conference on intelligent Computing，Zhengzhou，China：Springer，2011.

[12]唐立新，楊自厚，王夢光，等.CIMS中帶多資源的CLMS問題的遺傳啟發(fā)式算法[J].系統(tǒng)工程理論與實踐，1997，17（4）：39-44.

[13]馬慧民，柳毅，葉春明.基于粒子群算法求解單級多資源約束生產批量計劃問題[J].工業(yè)工程與管理，2005，10（6）：66-70.

[14]馬艷，黃玲，蘇受寶.含再制造的受限批量問題求解的蟻群算法[J].計算機應用與軟件，2011，28（2）：96-99.