求解組合優(yōu)化法問題的偶合算法綜述

[摘要] 偶合算法（Coincidence Algorithm，COIN）是演化算法中最先進(jìn)的一種。它主要用來解決組合問題。偶合算法屬演化算法的一個(gè)分支，其主要功能是運(yùn)用概率模式代替?zhèn)鹘y(tǒng)突變和交叉算子來解決問題。偶合算法模式是一個(gè)相鄰事件（最初稱符合）的聯(lián)合概率表，它來源于許多備選的解決辦法。偶合算法的獨(dú)特之處是在學(xué)習(xí)和優(yōu)化過程中它運(yùn)用負(fù)相關(guān)學(xué)習(xí)（Negative Correlation Learning，NCL）和傳統(tǒng)的正相關(guān)學(xué)習(xí)（Positive Correlation Learning，PCL）相結(jié)合的方法。偶合算法在解決組合優(yōu)化方法中非常有效。它的解釋力和與現(xiàn)代其他算法的比較也顯而易見。據(jù)此，本文旨在介紹偶合算法在解決一些工程問題如貨郎擔(dān)問題、生產(chǎn)線平衡問題、配線排序問題和工人配置問題的實(shí)際應(yīng)用。

[關(guān)鍵詞] 組合優(yōu)化；偶合算法；綜述

[中圖分類號(hào)] TP301.6；F272 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 1673 - 0194（2013）04- 0057- 05

1 引 言

組合優(yōu)化放法（Combinatorial Optimization，CO），可行性領(lǐng)域分散的優(yōu)化方法在工程領(lǐng)域有許多對(duì)可操作研究的運(yùn)用。這個(gè)領(lǐng)域的實(shí)例主要有生成樹、最短路徑、最小費(fèi)用流、權(quán)匹配、背包問題、箱柜包裝、貨郎擔(dān)問題、設(shè)施選址問題等等。對(duì)于一個(gè)精確問題做詳盡的探究是不可能的，任何探究順序的方法不能確保找到一個(gè)最佳結(jié)果。

現(xiàn)今，解決大型重要的組合優(yōu)化方法問題的能力在這10年間有很大的提高。可靠的軟件、便宜且運(yùn)行速度快的硬件、高級(jí)語言的有效性使得解決復(fù)雜問題的建模更加快捷，這也對(duì)優(yōu)化工具的提出了更大要求。這主要?dú)w因于科技和工業(yè)專業(yè)組合優(yōu)化方法問題的重要性。這篇論文是基于過去兩年泰國的研究團(tuán)隊(duì)對(duì)組合優(yōu)化方法問題提出的解決辦法的一篇研究論文。其中包括最新的關(guān)于偶合算法的結(jié)論、演化算法中的在優(yōu)化過程中混入負(fù)相關(guān)學(xué)習(xí)的算法。論文還詳細(xì)介紹了在單一和多重目標(biāo)問題中偶合算法的基準(zhǔn)。

2 偶合算法

偶合算法屬演化算法的一個(gè)分支，其主要功能是運(yùn)用概率模式代替?zhèn)鹘y(tǒng)突變和交叉算子來解決問題。這種算法叫做分布估算法（Estimation of Distribution Algorithms，EDA）。它強(qiáng)調(diào)運(yùn)用一些模型的形式作為一個(gè)庫存或從之前備選的解決辦法中萃取出的知識(shí)。從當(dāng)下的解決方法中創(chuàng)造出下一代的備選解決辦法來代替遺傳算子。EDA直接從模式中例舉了新的備選，因此消除了在設(shè)計(jì)和執(zhí)行這些遺傳算子的過程中所出現(xiàn)的困難和阻礙。

通常，演化算法運(yùn)用從優(yōu)選的人群中選取的知識(shí)。我們忽略不在最差人群中選取的原因。偶合算法的獨(dú)特性是它把匿藏在最差人群中的負(fù)相關(guān)學(xué)習(xí)與集合了最佳人群知識(shí)的傳統(tǒng)的正相關(guān)學(xué)習(xí)一并運(yùn)用。負(fù)相關(guān)學(xué)習(xí)已經(jīng)被運(yùn)用在許多學(xué)習(xí)技巧中，其中包括強(qiáng)化學(xué)習(xí)算法、人工神經(jīng)網(wǎng)、決策樹。負(fù)相關(guān)學(xué)習(xí)不僅防止了算法過早的集中，而且在備選解決方法中保持了多樣性。

偶合算法模式是一個(gè)聯(lián)合概率矩陣H。這個(gè)矩陣來源于馬爾可夫鏈。在Hxy上的條目是從狀態(tài)X到狀態(tài)Y轉(zhuǎn)變的概率。我們