林巨廣，榮海龍，汪 洋

(合肥工業大學 機械與汽車工程學院，合肥 230009)

?

基于COIN算法的工藝原則布置優化

林巨廣，榮海龍，汪 洋

(合肥工業大學 機械與汽車工程學院，合肥 230009)

為了解決焊裝工廠的工藝原則布置問題,文章運用COIN算法(Coincidence Algorithm)，用聯合概率矩陣模型代替傳統遺傳算法的交叉和變異，來更新產生新的子代種群，并在學習和優化過程中利用負相關學習與傳統的正相關學習相結合的方法，保持了種群的多樣性，提高了算法的收斂速度。最后通過運用該算法解決焊裝工廠的工藝原則布置問題，并以遺傳算法做對比，驗證了COIN算法的有效性。

COIN算法；遺傳算法；工藝原則布置

0 引言

工藝原則布置對各類企業的生產成本和利潤有很大的影響，湯普金斯[1]的研究表明：企業的物料運輸成本約占總成本的20%～50%，通過合理的布置設計，物流分析、規劃，可以有效降低15%～30%，極大的提高了生產效率。工藝原則布置屬于組合優化問題，目前實際生產中，最常用的解決方法是啟發式方法：直接放置，然后兩兩調換，檢驗，修改，如此反復，直到滿足條件。這種方法在求解規模比較小(N值較小)的布置問題時比較有效，隨著規模不斷增大，解空間呈指數增長，出現組合爆炸現象，求解困難。隨著智能算法和計算機技術的發展，為解決組合優化問題產生了多種有效的算法，如遺傳算法[2-5]、分布估計式算法[6-8]、COIN算法[9-12]等，智能算法通過隨機抽取部分解，利用適應度函數進行分析，估計全局解的分布情況，進而進行全局搜索，在符合實際精度的條件下，快速、有效的得出最優解。

1 COIN算法

1.1 COIN算法概述

COIN算法以傳統的遺傳算法(Genetic Algorithm:GA)和統計學為基礎，并吸收了MIMIC(Mutual Information Maximization for Input Clustering)算法的長處。遺傳算法是由美國Michigan大學的Holland教授于1969年提出，后經DeJong Goldberg等人歸納總結，形成的一類模擬進化算法。這種算法是模擬生物進化過程中優勝劣汰規則與群體內部染色體交叉、變異重組操作來處理復雜優化問題的啟發式優化算法，在許多領域得到廣泛的應用。但同樣存在許多不足：易陷入局部最優、未成熟收斂、收斂性能差導致的耗費時間長。針對上述不足，文中提出的COIN算法避免了交叉、變異的重組操作，而是根據種群中優勢群體的有效信息構造聯合概率矩陣，通過聯合概率矩陣來產生下一代種群，同時在更新聯合概率矩陣過程中，將負相關與傳統的正相關學習相結合，保持了物種的多樣性，一定程度上避免了局部最優解的產生，加速了算法的收斂速度，有利于通過聯合概率矩陣更有效的體現種群進化的方向。最后將該算法應用于解決焊裝工廠的工藝原則布置問題，與遺傳算法做對比，驗證了該算法的有效性。COIN算法的流程圖如圖1所示。

圖1 COIN算法流程圖

1.2 COIN算法基本步驟

步驟1：COIN算法的聯合概率矩陣是一個n×n的方形矩陣，n為單個個體中需排序的工作單元數目，首先要獲得一個矩陣C：

其中的Cij表示兩個工作單元相鄰，第i個工作單元后面出現j單元的次數。因為當i=j時，同一個工作單元不存在相鄰情況，故Cij=0(當i=j)，初始化的過程中，為了避免矩陣C中元素出現過多的0元素(初始化過程中，第i個工作單元后的每一個j不一定都會出現，故存在Cij=0(當i≠j))，種群數值M要選的適當大一些，選出優秀個體M個，對矩陣C進行初始化訓練，以便獲得良好的初始狀態：

Xij=Cij/M

得到矩陣A：

步驟3：適應度評價，檢驗個體是否符合進化結束條件。根據實際問題，確定優化方向，對于單目標組合優化問題，按單一目標適應度值大小直接排序。對于多目標組合優化問題，按帕累托分級[7](pareto ranking),確定優勢群體。

步驟4：COIN算法的特別之處在于在學習和優化的過程中，引入正相關學習優化的同時加入負相關學習的方法，以下是根據最優和最差的兩組種群來更新聯合概率矩陣。

最優種群的更新方式：

最差種群的更新方式：

其中：Xij表示聯合概率矩陣中(i,j)代表的元素，k為進化系數，t為進化代數，Rij表示最優種群的個體中(i,j)出現的次數，Pij表示最差種群的個體中(i,j)出現的次數。

步驟5：重復步驟2～4，直到最優個體符合最終條件。

2 實例模型

2.1 工藝原則布置數學模型

焊裝工廠的工藝原則布置問題是一個復雜的組合優化問題，n個工作地是確定的且相互之間的距離是已知的，工藝原則布置問題就是將n個工作單元分配到n個工作地固定的位置上，并使得總的物流量最小：

其中：Wij為n個工作單元兩兩之間的物料搬運量，Dij為n個工作地兩兩之間的距離。

2.2 模型編碼與具體數據

編碼工作不僅影響COIN算法中更新聯合概率矩陣方式的設計，最重要的是它還決定了從搜索空間的基因型到解空間的表現型之間的對應和轉換關系，好的編碼方式可以使進化操作簡單的實現和執行，減少無效解的產生，極大的提高求解速度。設求解的模型是n維向量X=(X1,X2,X3,…,Xn),在每個固定位置上，X1,X2,X3,…,Xn都是等可能占據，代表對應的個體編號。例如n=8時，取X=(8,4,5,2,1,6,3,7)表示種群中的一個個體，對應一組工作單元序列號，最終所求解的最優結果將得到類似的工作單元序列號。利用遺傳算法和COIN算法分別對焊裝工廠的工藝原則布置問題進行求解，以Mi(i=1,2,3,…,n)表示可進行獨立生產零部件的工作單元i,n個工作地位置固定且相互之間的距離是已知的，這時，布置問題實際上轉換成了工作單元的排序問題，以n=8為例，8個工作單元用M1M2…M8表示，則M2M4M3M7M6M8M1M5即(2,4,3,7,6,8,1,5)表示：M2在工作地A，M4在工作地B，M3在工作地C，M7在作地D，M6在工作地E，M8在工作地F，M1在工作地G，M5在工作地H。以物料搬運量最小為目標函數，不同的工作單元的排序，為單目標組合優化問題。具體數據如表1、表2所示，表1中工作單元M1到工作單元M2的值175表示：從工作單元M1到工作單元M2運輸175車次，A到B的值1表示：從工作地A到工作地B的距離為1個單位，后面以此類推。

表1 8個工作單元之間物料搬運量(車次)

表2 8個工作地之間的距離

2.3 模型求解

2.3.1 遺傳算法求解

最初的解決辦法是根據現場工程師的經驗，對各工作單元進行排序，然后反復調整，直到盡量滿足現場輸出需求，缺乏理論基礎，且所得結果與最優值相差較大，不利于形成穩定的結果輸出。智能算法的發展使問題得到更加有效的解決。下面利用plant simulation建立焊裝工廠工藝原則布置2D仿真模型[14]，如圖2所示。

圖2 Plant simulation 2D仿真模型

在利用plant simulation提供的遺傳算法求解工具GAwizard的過程中，設置適當的進化代數和種群大小12和50，利用plant simulation軟件中的GAwizard工具進行數值計算，得到如圖3所示的結果。最優個體為：(5,8,7,3,6,1,4,2)，最佳適應度為3815。

圖3 遺傳算法實驗結果性能圖

2.3.2 COIN算法求解

遺傳算法存在易陷入局部最優、未成熟收斂、收斂性能差導致的耗費時間長等不足，COIN算法的特別之處在于在學習和優化的過程中，在正相關學習優化的同時引入負相關學習的方法，保持了種群的多樣性，加速了算法的收斂速度。利用MATLAB進行編程，通過數值計算來更新聯合概率矩陣，參數的設置[13]如表3所示。

表3 COIN算法中參數設置

得到的首工作單元概率向量P=(0.22，0.12，0.06，0.3，0.06，0.1，0.08，0.02)，得到的聯合概率矩陣:

根據首工作單元概率向量和聯合概率矩陣，得到的最優序列為(4,2,6,1,7,3,5,8)，最佳適應度值為3815，最佳代數出現在第二代。設置相同的種群大小M為50，以COIN算法和遺傳算法的進化代數和收斂速度做對比，結果如圖4所示。

圖4 COIN算法與遺傳算法進化對比圖

以COIN算法和遺傳算法的耗時作對比，結果如圖5所示。

圖5 COIN算法與遺傳算法耗時對比圖

由圖4可以看出：COIN算法的進化收斂速度要快于遺傳算法，最佳代數出現在第二代，COIN算法較快的收斂速度得益于負相關學習的引入和優勢種群初始化。

由圖5可以看出：隨著進化代數的增加直到達到最優解時，遺傳算法的耗時要多于COIN算法，最初COIN算法耗時多的原因在于初始化時處理計算較多的個體。

3 結束語

文中在利用COIN算法求解工藝原則布置問題時，通過選取優秀種群對聯合概率矩陣進行初始化，提高了算法的收斂速度。在種群的更新進化過程中，采取了精英保留策略，大大縮短了進化代數，有利于保證種群的進化方向。最后通過與遺傳算法做對比表明：COIN算法在進化代數、全局搜索能力、耗時方面優于遺傳算法，可以廣泛的應用于解決焊裝工廠工藝原則布置問題等相關的單目標組合優化問題。復雜程度更高的多目標組合優化問題是下一步的研究方向。

[1] 湯普金斯.設施規劃[M].伊俊敏,袁海波,譯. 3版.北京：機械工業出版社,2007.

[2] 王萬良,姚明海.基于遺傳算法的混合Flow-shop調度方法[J].系統仿真學報,2012,14(7):863-869.

[3] 馮林,李聰,沈莉.基于鄰域粗糙集和量子遺傳算法的人臉表情特征選擇方法[J].合肥工業大學學報(自然科學版),2013,36(1):39-42.

[4] 李慧,丁萬寧,周明姬,等.基于改進遺傳算法框架結構損傷識別[J].合肥工業大學學報(自然科學版),2015,38(7):973-977.

[5] 藍會立,高遠,范建文,等.基于遺傳算法的車輛4自由度主動懸架最優控制研究[J].合肥工業大學學報(自然科學版),2014,37(11):1304-1310.

[6] 劉明芳.基于分布估計算法的整數規劃研究[D].武漢：武漢理大學，2008.

[7] 郝承偉,高慧敏.求解TSP問題的一種改進的十進制MIMIC算法[J].計算機科學與技術，2012,39(8):233-236.

[8] 程玉虎,王雪松,郝明林.一種多樣性保持的分布估計算法[J].電子學報,2010,38(3):591-597.

[9] 陳淑玲,李鐵克,王雷.求解組合優化問題的耦合算法綜述[J].中國管理信息化,2013,16(4):57-61.

[10] Chutima Parames ,Kampirom Noppon.A Multi-Objective Coincidence Memetic Algorithm for a mixed model U-line Sequencing problem[J].InternationalJournal of Advanced Operations Management,2010,2(3-4),201-248.

[11] Wattanapornprom Warin,Olanviwitchai Panuwat,Chutima Parames,Multi-objective Combinatorial Optimisation with Coincidence Algorithm [C]//IEEE Congress on Evolutionary Computation,2009,1675-1682.

[12] Sirovetnukul R, Chutima Parames. Multi-objective Particle Swarm Optimization with Negative Knowledge for U-shaped Assembly Line Worker Allocation Problems[C]//IEEE Proceedings of the 2010 IEEE IEEM,2010,2033-2038.

[13] 黃寶珠.改進的MIMIC算法求解旅行商問題[J].計算機工程與設計,2010,31(16):3650-3653.

[14] 周金平,汪銳.生產系統仿真-plant simulation應用教程[M].北京：電子工業出版社，2011.

(編輯 李秀敏)

Optimization of Process Principle Arrangement Based on Coincidence Algorithm

LIN Ju-guang，RONG Hai-long，WANG Yang

(School of Machinery and Automobile Engineering, Hefei University of Technology, Hefei 230009, China)

To solve the problem of process principle arrangement,the Coincidence Algorithm which replaces the traditional genetic algorithm crossover and mutation with the joint probability matrix model uses both good and not-good solutions that is defined by fitness to generate the population in this paper.It maintains the diversity of the population and improves the convergence rate.Finally,using the Coincidence Algorithm to solve the problem of process principle arrangement,it verifies the validity of Coincidence Algorithm compared with Genetic Algorithms.

coincidence algorithm;genetic algorithms;process principle arrangement

1001-2265(2016)11-0138-03

10.13462/j.cnki.mmtamt.2016.11.037

2015-11-27

國家支撐項目:多平臺高節拍汽車車身柔性焊裝自動化生產線(2012BAF06B01);國家智能制造裝備發展專項項目(發改辦高科[2011]2548號)

林巨廣(1963—)，男，安徽霍邱人，合肥工業大學教授，博士生導師，博士，研究方向為汽車試驗設備，智能制造，新能源汽車等領域研究；通訊作者：榮海龍(1990—)，男，安徽阜陽人，合肥工業大學碩士研究生，研究方向為計算機集成制造、智能制造，(E-mail)1062570304@qq.com。

TH162;TG506

A