林巨廣，榮海龍，汪 洋

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

?

基于COIN算法的工藝原則布置優(yōu)化

林巨廣，榮海龍，汪 洋

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

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

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

0 引言

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

1 COIN算法

1.1 COIN算法概述

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

圖1 COIN算法流程圖

1.2 COIN算法基本步驟

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

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

Xij=Cij/M

得到矩陣A：

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

步驟4：COIN算法的特別之處在于在學(xué)習和優(yōu)化的過程中，引入正相關(guān)學(xué)習優(yōu)化的同時加入負相關(guān)學(xué)習的方法，以下是根據(jù)最優(yōu)和最差的兩組種群來更新聯(lián)合概率矩陣。

最優(yōu)種群的更新方式：

最差種群的更新方式：

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

步驟5：重復(fù)步驟2～4，直到最優(yōu)個體符合最終條件。

2 實例模型

2.1 工藝原則布置數(shù)學(xué)模型

焊裝工廠的工藝原則布置問題是一個復(fù)雜的組合優(yōu)化問題，n個工作地是確定的且相互之間的距離是已知的，工藝原則布置問題就是將n個工作單元分配到n個工作地固定的位置上，并使得總的物流量最?。?/p>

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

2.2 模型編碼與具體數(shù)據(jù)

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

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

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

2.3 模型求解

2.3.1 遺傳算法求解

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

圖2 Plant simulation 2D仿真模型

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

圖3 遺傳算法實驗結(jié)果性能圖

2.3.2 COIN算法求解

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

表3 COIN算法中參數(shù)設(shè)置

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

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

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

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

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

由圖4可以看出：COIN算法的進化收斂速度要快于遺傳算法，最佳代數(shù)出現(xiàn)在第二代，COIN算法較快的收斂速度得益于負相關(guān)學(xué)習的引入和優(yōu)勢種群初始化。

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

3 結(jié)束語

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

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

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

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

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

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

[6] 劉明芳.基于分布估計算法的整數(shù)規(guī)劃研究[D].武漢：武漢理大學(xué)，2008.

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

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

[9] 陳淑玲,李鐵克,王雷.求解組合優(yōu)化問題的耦合算法綜述[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].計算機工程與設(shè)計,2010,31(16):3650-3653.

[14] 周金平,汪銳.生產(chǎn)系統(tǒng)仿真-plant simulation應(yīng)用教程[M].北京：電子工業(yè)出版社，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

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

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

TH162;TG506

A