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

林巨廣，榮海龍，汪 洋

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

?

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

林巨廣，榮海龍，汪 洋

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

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

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

0 引言

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

1 COIN算法

1.1 COIN算法概述

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

圖1 COIN算法流程圖

1.2 COIN算法基本步驟

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

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

Xij=Cij/M

得到矩陣A：

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

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

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

最差種群的更新方式：

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

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

2 實(shí)例模型

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

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

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

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

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

表1 8個(gè)工作單元之間物料搬運(yùn)量(車(chē)次)

表2 8個(gè)工作地之間的距離

2.3 模型求解

2.3.1 遺傳算法求解

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

圖2 Plant simulation 2D仿真模型

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

圖3 遺傳算法實(shí)驗(yàn)結(jié)果性能圖

2.3.2 COIN算法求解

遺傳算法存在易陷入局部最優(yōu)、未成熟收斂、收斂性能差導(dǎo)致的耗費(fèi)時(shí)間長(zhǎng)等不足，COIN算法的特別之處在于在學(xué)習(xí)和優(yōu)化的過(guò)程中，在正相關(guān)學(xué)習(xí)優(yōu)化的同時(shí)引入負(fù)相關(guān)學(xué)習(xí)的方法，保持了種群的多樣性，加速了算法的收斂速度。利用MATLAB進(jìn)行編程，通過(guò)數(shù)值計(jì)算來(lái)更新聯(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算法和遺傳算法的進(jìn)化代數(shù)和收斂速度做對(duì)比，結(jié)果如圖4所示。

圖4 COIN算法與遺傳算法進(jìn)化對(duì)比圖

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

圖5 COIN算法與遺傳算法耗時(shí)對(duì)比圖

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

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

3 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

[9] 陳淑玲,李鐵克,王雷.求解組合優(yōu)化問(wèn)題的耦合算法綜述[J].中國(guó)管理信息化,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] 黃寶珠.改進(jìn)的MIMIC算法求解旅行商問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì),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

國(guó)家支撐項(xiàng)目:多平臺(tái)高節(jié)拍汽車(chē)車(chē)身柔性焊裝自動(dòng)化生產(chǎn)線(2012BAF06B01);國(guó)家智能制造裝備發(fā)展專(zhuān)項(xiàng)項(xiàng)目(發(fā)改辦高科[2011]2548號(hào))

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

TH162;TG506

A