求解約束滿足問題的改進蟻群優(yōu)化算法

張永剛 ，張思博 ，薛秋實

（1. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；2. 符號計算與知識工程教育部重點實驗室，吉林 長春 130012）

1 引言

在人工智能領(lǐng)域中，約束滿足問題(CSP， constraint satisfaction problems)[1]是其重要組成部分，現(xiàn)今也被廣泛應(yīng)用于各領(lǐng)域的實際問題，如工作調(diào)度、資源配置、模式識別和機器視覺等。對約束滿足問題進行求解主要包含：推理和搜索。推理技術(shù)以約束傳播[1]為核心，目的是通過對某些特征節(jié)點進行傳播來壓縮搜索空間，從而提高搜索效率；搜索技術(shù)以回溯[2]為核心，在理論上回溯方法是一種完備算法，它能夠求解所有約束滿足問題。當(dāng)求解實際問題時，如果CSP實例困難性較高，規(guī)模較大時，使用回溯方法求解的效率就會明顯降低，出現(xiàn)難以在合理的時間內(nèi)求解的情況。為了解決這一問題，人們提出了許多改進方法。這些方法力求在提高求解效率和降低求解成本之間得到較好權(quán)衡。希望不但可以實現(xiàn)最小的執(zhí)行代價和最少的使用空間，又能達到提高效率的效果。本文進行的研究主要基于蟻群優(yōu)化元啟發(fā)式[3]的約束求解算法展開。蟻群優(yōu)化算法是一種搜索算法，根據(jù)完備性可將其定義為不完備搜索算法，即無法判定該類問題是否存在最優(yōu)解。它的優(yōu)點是能快速求出近似最優(yōu)解（通常也能求出最優(yōu)解），在實際應(yīng)用中非常有效。另外，蟻群優(yōu)化元啟發(fā)式的效率不依賴于具體問題，所以有很強的通用性，稱它為問題獨立的啟發(fā)式。蟻群算法通常在某個問題上求解效率可能不如專用的算法，但是在多種問題的平均求解效率上有很大優(yōu)勢。這一特點在事先不知道問題特性或不知道應(yīng)該選擇哪種專用算法時非常有意義，并且實現(xiàn)簡單，在復(fù)雜的實際應(yīng)用環(huán)境下可以極大地節(jié)省成本。

蟻群算法的約束求解器(ant-solver)[4]對于靜態(tài)的組合優(yōu)化問題沿用了經(jīng)典蟻群優(yōu)化算法。每一次循環(huán)構(gòu)建一個完備的分配后將信息素進行更新。當(dāng)已經(jīng)找到了一種解決方案，或者當(dāng)已經(jīng)執(zhí)行到最大循環(huán)次數(shù)時該迭代算法停止。通過信息素引導(dǎo)整個搜索過程，作為一種啟發(fā)式引導(dǎo)變量選擇值進行初始化。其中，通過設(shè)置信息素的上界和下界來盡量避免信息素表示大小和搜索空間實際大小之間的過度差異，從而試圖使用較低的花銷盡量搜索到最大的搜索空間。一個約束滿足問題CSP(X，D，C)，其中，X為變量的集合，設(shè)X中變量數(shù)量是n，關(guān)系圖中頂點數(shù)為q，則

當(dāng)構(gòu)建一個完整的分配，所有轉(zhuǎn)移概率的信息素值計算需要O(nq)次操作。在每一次循環(huán)結(jié)束后，信息素的更新需要O(n2)次添加已訪問節(jié)點的信息素濃度和O(q2)次揮發(fā)。對于其他不涉及到信息素的操作，如變量的選擇、啟發(fā)式因子的計算，時間復(fù)雜度主要根據(jù)約束是全局約束或者二元約束等有所不同。實驗證明，這種不完備的仿生隨機算法，在大規(guī)模實例的情況下，雖然無法保證最優(yōu)解，但是比確定的算法更有效，可以在極短的時間內(nèi)求出近似最優(yōu)解，實際應(yīng)用中更有意義。

本文在約束求解器Ant-Solver的基礎(chǔ)上提出了改進：第一點改進是在整個搜索過程執(zhí)行之前用弧相容檢查[1]進行一次預(yù)處理；第二點改進是提出了一種新的蟻群優(yōu)化算法參數(shù)調(diào)節(jié)方案?；∠嗳蓊A(yù)處理可以刪除搜索空間中的冗余節(jié)點，一方面可以在保持問題語義的同時降低搜索難度，另一方面可以減小啟發(fā)式陷入局部最優(yōu)的可能性；參數(shù)對蟻群算法的效率有關(guān)鍵性地影響，合理的參數(shù)設(shè)置是高效求解問題的必要條件，通過分析各參數(shù)在算法運行過程中所起到的作用，設(shè)計了一套參數(shù)的在線調(diào)解方案—預(yù)定參數(shù)調(diào)節(jié)。最后，將得出的算法應(yīng)用于實際問題，將通過優(yōu)化改進的 AC-AS(基于弧相容的蟻群算法約束求解器)算法應(yīng)用于組合優(yōu)化問題，并且與Ant-Solver算法進行了比較，通過實驗得出結(jié)果：AC-AS算法在收斂速度、穩(wěn)定性及最優(yōu)解的質(zhì)量方面明顯優(yōu)于Ant-Solver。

完備性算法[5]理論上可以完美求解所有組合優(yōu)化問題，在存在最優(yōu)解的情況下，一定可以求出有解，在無解的情況下可以證明無解。但是在實際應(yīng)用中，很多大規(guī)模的復(fù)雜問題，用完備算法的求解代價很高，甚至不能在合理的時間內(nèi)完成。因此，不完備算法被提出來。由于實際應(yīng)用中，最優(yōu)解并不是必須的，在短時間內(nèi)求出近似最優(yōu)解更有實際意義，這就體現(xiàn)出不完備算法的實用性。大量實驗表明，蟻群算法是一種優(yōu)秀的不完備算法，不僅具有求解速度快準(zhǔn)確率高的優(yōu)點，而且可以在較短時間內(nèi)求出符合精度要求的近似最優(yōu)解。本文是在蟻群算法上做出改進，進一步提升了算法的求解速度和準(zhǔn)確性。

2 AC-AS算法

AC-AS算法是基于 Ant-Solver而來的改進算法，主要加入了弧相容預(yù)處理和預(yù)定參數(shù)調(diào)節(jié)，并重新設(shè)計了數(shù)據(jù)結(jié)構(gòu)。Solnon在蟻群優(yōu)化元啟發(fā)式的基礎(chǔ)上結(jié)合最大最小螞蟻系統(tǒng)和局部搜索等技術(shù)設(shè)計了 CSP求解器 Ant-Solver。Solnon將 CSP抽象為一個無向約束圖，在抽象得到的約束圖中：每一個頂點代表一個變量-值對，2個頂點之間的連線（邊）代表這2個頂點所代表的變量之間的約束關(guān)系。在約束圖中對所有變量進行一次遍歷的路徑與CSP的候選解路徑一一對應(yīng)，這與使用蟻群算法求解最短路徑的思路相吻合，因此可以利用這種思路，求出所有在約束圖中的約束所滿足的解路徑，該解路徑就是最終所求CSP的解。Ant-Solver的優(yōu)點是數(shù)據(jù)結(jié)構(gòu)簡單，容易實現(xiàn)且易于理解，求解效率較高；缺點是擴展性不足，所采用的不是Benchmarks[1]中的數(shù)據(jù)結(jié)構(gòu)，并且只能求解文獻[4]中給出的實例或者自行設(shè)計測試用例，非常麻煩。本文重寫了算法的數(shù)據(jù)結(jié)構(gòu)，一方面使算法可以直接讀取 Benchmarks中的實例，方便測試和交流；另一方面也為加入弧相容預(yù)處理打下了基礎(chǔ)。

Ant-Solver中信息素因子代表評價某個賦值的“經(jīng)驗”偏好，啟發(fā)式因子代表局部評價賦值的效果。Ant-Solver通過對信息素因子和啟發(fā)式因子之間相關(guān)概率的隨機賦值，為求解CSP提供了對索引進行引導(dǎo)的一個可通用的啟發(fā)式?，F(xiàn)在假設(shè)一只螞蟻已經(jīng)訪問過的節(jié)點的集合為A，下一個將被賦值的變量為xj。這只螞蟻按照一定概率隨機選擇下一個節(jié)點，其中，節(jié)點稱為目標(biāo)節(jié)點，目標(biāo)節(jié)點對其中所有候選節(jié)點吸引力的比例即為轉(zhuǎn)移概率[4]

下面討論AC-AS算法對Ant-Solver的第一個主要改進：預(yù)定參數(shù)調(diào)節(jié)。從式(1)可以看出，參數(shù)，α β對算法有直接影響，以下2個指標(biāo)：成功率和運行時間，其中，成功率代表算法成功求解的問題占所有問題的百分比，運行時間代表算法從執(zhí)行開始到執(zhí)行終止所用的時間。當(dāng)對這2個指標(biāo)進行考察時，其中有5個參數(shù)α、β、ρ、nbAnts、q0起到?jīng)Q定性作用。對參數(shù)進行設(shè)置也一直是蟻群算法研究中的核心問題。參數(shù)問題在方法上大致可以分為2種方法：離線調(diào)節(jié)方法和在線調(diào)節(jié)[6]方法。離線調(diào)節(jié)希望可以在算法還未真正開始工作以前找到一個針對于該問題較為適合的設(shè)置參數(shù)方案。這一過程相對較為耗時，且需要人為干預(yù)，整個算法主要依賴于開發(fā)人員的直覺和經(jīng)驗，容易出錯，且難以通用和復(fù)用。比離線調(diào)節(jié)更有前景的另一個替代方案稱為在線調(diào)節(jié)方法，該方法通常在問題實例的求解過程中持續(xù)不斷地修正對參數(shù)的設(shè)置。在線調(diào)節(jié)的優(yōu)點一是可以適應(yīng)不均衡的實例，二是可以依據(jù)搜索的階段特征來改變參數(shù)設(shè)置方案。本文提出的預(yù)定參數(shù)調(diào)節(jié)即是一種在線調(diào)節(jié)方案。方案的設(shè)計思路來自于對每個參數(shù)的具體作用分析。首先看α，假設(shè)對解圖的搜索進行到了圖中的某一節(jié)點vi處，即已對vi代表的變量進行了隨機賦值操作，從vi出發(fā)的候選節(jié)點集合（假設(shè)vi的候選節(jié)點集合中元素不少于2個）中候選節(jié)點被選中的概率滿足式(1)，繼而得出任意 2個節(jié)點vi和vk被選中的概率比為

同理可得β對算法的影響，式(6)明顯可以看出在搜索過程中，啟發(fā)式η所起的作用隨著參數(shù)β的增大而變大。由于啟發(fā)式與“經(jīng)驗”無關(guān)，僅代表vi附近的局部信息，所以針對局部信息的依賴性可得出在算法中隨著啟發(fā)式所起作用的增大對局部信息的依賴增強，同時算法快速的收斂于局部最優(yōu)組成的路徑。閾值q0滿足 0 ＜q0＜1，為當(dāng)前節(jié)點選擇后繼節(jié)點時算法就會隨機生成一個值q～U( 0，1)，當(dāng)生成值q低于閾值q0時算法就會直接將轉(zhuǎn)移概率最大的節(jié)點取出，而當(dāng)所選擇的值高于q0時算法則按照轉(zhuǎn)移概率隨機選取節(jié)點。閾值q0的大小也影響著算法，算法在為當(dāng)前節(jié)點選擇后繼節(jié)點時，q0越大，選取最大轉(zhuǎn)移概率節(jié)點的可能性就越大。相對于采用轉(zhuǎn)移概率隨機選取的方法而言，該方法依賴過去的“經(jīng)驗”較多，而隨機性較少。相對于參數(shù)α與β的設(shè)定，調(diào)節(jié)q0屬于對算法進行微調(diào)，原因是閾值q0減小，過往解路徑的子路徑組合會受到影響，即閾值q0越小就會使不同的經(jīng)驗解路徑的交叉變得越頻繁，同時也影響了算法的經(jīng)驗路徑和探索路徑，使得探索路徑在經(jīng)驗路徑附近加大了擺動振幅。

其中參數(shù)ρ用來對信息素的“揮發(fā)”速率進行控制，ρ所起的作用隨著自身值的增大而變小，即ρ越大，信息素就揮發(fā)得越快，那么它起到的作用就越小。由于調(diào)節(jié)ρ實際上是對信息素積累速度的調(diào)節(jié)，所以這也屬于對算法的微調(diào)，間接影響信息素的引導(dǎo)作用。事實上，由于相對問題而言信息素是完全獨立的，所以一般情況下不需對ρ進行調(diào)節(jié)，只要設(shè)定一個較為合理的初始值即可。參數(shù)nbAnts的作用是對信息素更新的頻率進行控制，它決定了算法的循環(huán)周期和信息素在更新時所采用樣本的解集，同時影響著收斂速度和探索寬度。當(dāng)nbAnts變大，信息素的更新就會越慢，信息素所起到的作用就越?。O端情況下，nbAnts→∞，代表信息素永遠不進行更新，算法變成完全的隨機探查）。由此可見，nbAnts也是間接影響信息素的引導(dǎo)作用，屬于對算法的微調(diào)。特別地，在多次循環(huán)以后nbAnts的調(diào)節(jié)能力就會逐漸變小。由于信息素不斷積累，在每一次循環(huán)中會得到解路徑的樣本集合，該樣本集合和經(jīng)驗路徑的相似度之間進行匹配，得出的相似度越高通過調(diào)節(jié)nbAnts產(chǎn)生的影響就越小。通常只在包含重置信息素的算法步驟時，對nbAnts調(diào)節(jié)才起作用。

在以上分析的基礎(chǔ)上，通過反復(fù)實驗給出了預(yù)定參數(shù)調(diào)節(jié)方案。參數(shù)α，nbAnts，ρ通常情況下是與問題無關(guān)的，對于不同的問題可以使用同種調(diào)節(jié)方案。而參數(shù)β通常情況下則依賴于問題特征，原因是不同問題中的啟發(fā)式因子不同，選擇參數(shù)β的最優(yōu)調(diào)節(jié)方案就不同。參數(shù)α，β共同決定著轉(zhuǎn)移概率中信息素和啟發(fā)式的權(quán)重，事實上對2個參數(shù)的調(diào)節(jié)是可以做到等效的，所以在參數(shù)α，β中，只需選擇一個參數(shù)即可，而究竟選擇哪個參數(shù)比較適合則要看兩者的調(diào)節(jié)效率。通常人們更喜歡選擇β，因為實際應(yīng)用中α遠小于β，做同樣幅度的調(diào)節(jié)時，β增加1，而α可能只減少了零點幾，所以出于方便簡潔考慮，通常會選擇β。而對參數(shù)nbAnts和ρ只需要在開始的時候給出較為合理的初始值即可，所以也不予選擇。綜上，當(dāng)β很大時，算法會迅速收斂于信息素濃度高的路徑，反之，則會迅速收斂于局部最優(yōu)解路徑。從搜索的全局過程分析，初期要采用充分大的β值，這樣用很小的計算量就可以迅速排除很多不可能的解；隨著搜索的深入，減小β值，避免算法迅速收斂于次優(yōu)解。同理，參數(shù)q0在搜索初期應(yīng)該充分大以提高搜索速度，隨著搜索的深入逐漸減小，使搜索寬度增加來避免算法陷入局部最優(yōu)。

AC-AS算法對Ant-Solver的另一個主要改進是加入了弧相容預(yù)處理?；∠嗳輽z查是經(jīng)典的約束傳播技術(shù)，在用回溯搜索算法求解CSP時通常要結(jié)合約束傳播對搜索空間進行壓縮來簡化問題。受這一思想的啟發(fā)，本文在蟻群算法搜索之前采用弧相容檢查對問題實例進行預(yù)處理。這樣做有兩點好處，第一是簡化了問題，使蟻群算法能夠更快地求解，第二是修剪掉了搜索空間中的許多無效值，減小了算法收斂于局部最優(yōu)（這是啟發(fā)式算法的通病）的可能性。顯然，如果預(yù)處理過程的開銷小于該過程為所有蟻群算法節(jié)省的開銷，那么總體的效率就能得到提升。因此，在搜索權(quán)重和約束傳播之間做較好的權(quán)衡即可得出較優(yōu)的求解效率。如果在進行完相容性檢測以后就得到了最優(yōu)解那么算法就等同于約束傳播算法，這種極端情況是存在的。

圖1列出了幾種主要約束傳播技術(shù)的強弱關(guān)系[1]，越強的技術(shù)刪除無效值的能力越強，相應(yīng)的開銷也越大。本文選擇了刪除能力最弱的弧相容檢查用作預(yù)處理，這是為了避免在預(yù)處理階段消耗過多的時間。實際上，對不同問題應(yīng)該采用不同強度的約束傳播技術(shù)，如何能讓算法自適應(yīng)地選擇合適的約束傳播技術(shù)，是值得進一步研究的課題。至此，給出了AC-AS算法的主要思想，AC-AS算法的具體描述如下。

圖1 域過濾相容性檢查的強弱關(guān)系

算法中的第1)步進行了預(yù)處理操作，通過預(yù)處理減掉空間中的無效值，簡化了問題，確保求解效率。實驗中應(yīng)用的是面向弧的粗粒度傳播方法，主要使用其中的AC3，因此在預(yù)處理階段時間復(fù)雜度是O(ed3)，空間復(fù)雜度是O(e)，其中，有e個約束d是論域的大小。第2)步構(gòu)建一個完整的分配，所有轉(zhuǎn)移概率的信息素值計算需要O(nq)次操作。在每一次循環(huán)結(jié)束后，信息素的更新需要O(n2)次添加已訪問節(jié)點的信息素濃度和O(q2)次揮發(fā)。其后通過合理調(diào)節(jié)參數(shù)進一步提升了算法的求解速度和準(zhǔn)確性。

3 AC-AS算法在隨機問題中的應(yīng)用

在日常生活中所遇到的問題都是具有結(jié)構(gòu)特點的，通過對不同結(jié)構(gòu)問題的研究可以設(shè)計出針對不同結(jié)構(gòu)的高效算法。當(dāng)然有時針對某一問題結(jié)構(gòu)設(shè)計的算法實際求解效率可能并不能達到預(yù)期效果。這一點不利人們設(shè)計出通用的求解算法。那么對無結(jié)構(gòu)的隨機CSP進行研究就顯得尤為必要，并且隨機 CSP測試用例在評估求解器效能時更具說服力。

下面給出生成隨機約束問題實例的經(jīng)典模型[7]。

RB模型是在B模型的基礎(chǔ)上得來的，它不同于B模型的區(qū)別主要有2點：首先變量之間允許存在多個約束關(guān)系，即約束可以共享作用域；其次，RB模型中每個變量的論域大小是隨著變量多項式增長的，各自并不相同。本文中所使用的測試用例均來自相變區(qū)，因為該區(qū)域的問題難度相對較高，具有一定說服力與代表性。關(guān)于相變區(qū)在文獻[8]中指出，欠約束區(qū)域與過約束區(qū)域之間稱作相變區(qū)域，相變區(qū)域是最難求解的隨機實例出現(xiàn)的區(qū)域。其中欠約束區(qū)域是指在該區(qū)域中的所有實例幾乎都是可滿足的，而過約束區(qū)域中實例則幾乎都是不可滿足問題。

除了上面所介紹的隨機模型，還有包含少量結(jié)構(gòu)的準(zhǔn)隨機問題，常用的有 Ehi、Geometric、Composed 3種問題，實驗所測問題來自于文獻[1]中的Benchmarks。以下所有的實驗全部都在同一臺 PC上操作完成的，操作系統(tǒng)為 Microsoft Windows XP Professional Service Pack 3，處理器為Intel E7500雙核CPU，主頻為2.93 GHz，內(nèi)存為2 GB。

Ant-Solver作為實驗的參照組，AC-AS是本文改進后的最終算法。從表1和表2中可以清楚地看到，AC-AS算法在隨機實例上的表現(xiàn)明顯優(yōu)于Ant-Solver算法。

表1 B模型隨機CSP實例100-8-14-p2

表2 RB模型隨機CSP實例frb

表3 準(zhǔn)隨機CSP實例

以表1～表3作為實例，表1統(tǒng)計了AC-AS和Ant-Solver求解 B(2， 100， 8， 0.14，p2)的實驗數(shù)據(jù)，p2=0.19～0.28；表2統(tǒng)計了求解模型RB隨機CSP實例的實驗數(shù)據(jù)；表3統(tǒng)計了求解隨機CSP實例geom-50-20-d4-75、composed-25-10-20和ehi的實驗數(shù)據(jù)；從表1可以清楚看出，在實例 B(2，100， 8，0.14，p2)中 AC-AS比 Ant-Solver表現(xiàn)更好，只有B(2， 100， 8， 0.14， 0.23)和 B(2， 100， 8， 0.14， 0.26)例外。后3個實例沒有求出解，它們的沖突數(shù)在2種方案下對問題的無解猜測做出了進一步印證，但是仍然無法確定有無解。表2中實例的情況稍復(fù)雜，有一半的AC-AS比Ant-Solver結(jié)果要好，其中有些Ant-Solver明顯好于AC-AS，這說明AC-AS算法存在不足，在某些問題中需要進行微調(diào)。表 3可以看出AC-AS表現(xiàn)普遍較好，但是ehi-85中不帶AC預(yù)處理參數(shù)調(diào)節(jié)的AC-AS的時間為1.500，低于 AC-AS的 1.704。說明在極少數(shù)情況下預(yù)處理中刪除的無效值可能會降低與它相關(guān)的一些解路徑的轉(zhuǎn)移概率。表中有些問題本身并不可滿足，本文認為沖突數(shù)較多的問題從循環(huán)次數(shù)上推斷（表中未列出）很有可能已得出了最優(yōu)解。另外，認為結(jié)果中沖突數(shù)優(yōu)先級高于求解時間，即沖突數(shù)少的解更優(yōu)，在沖突數(shù)相同的情況下再比較求解時間。

4 AC-AS算法在組合優(yōu)化問題中的應(yīng)用

組合優(yōu)化問題中的應(yīng)用比較廣泛，例如工程、建筑、計算機科學(xué)、音樂、理財以及其他許多領(lǐng)域。例如，人們?nèi)粘Ｉ钪兴褂玫碾娫挘谄鋵崿F(xiàn)的過程中就要求通過成本低、路徑堵塞小和智能化等系列優(yōu)化問題來最終實現(xiàn)較高效能；汽車制造也有很多的優(yōu)化目標(biāo)：減小風(fēng)阻、提高安全系數(shù)、人性化舒適體驗等。組合優(yōu)化問題可以用 CSP來表示，因此可以用 AC-AS來求解組合優(yōu)化問題。另外，由于組合優(yōu)化問題來自于現(xiàn)實中的應(yīng)用，通常都帶有一定的結(jié)構(gòu)特點，求解組合優(yōu)化問題可以考察 AC-AS求解結(jié)構(gòu)化問題的性能。以下實驗均在同一臺 PC上完成：處理器為Intel E7500雙核CPU、主頻為2.93 GHz、內(nèi)存為 2 GB、操作系統(tǒng)為 Microsoft Windows XP Professional Service Pack 3。

表4中全部實例取自文獻[1]中的Benchmarks，包括 QCP[9]、RLFAP[10]、JSSP[11]、BH[12]等，顯然AC-AS算法的表現(xiàn)明顯優(yōu)于Ant-Solver，僅在bqwh問題上Ant-Solver有微弱的優(yōu)勢?？梢姡珹C-AS算法對Ant-Solver的改進是非常顯著的。可以預(yù)期，未來可以進一步改進算法，使算法能夠更加自適應(yīng)地選擇合適的約束傳播技術(shù)和參數(shù)調(diào)節(jié)方案，繼續(xù)提高AC-AS算法的效率。

表4 組合優(yōu)化問題實例

5 結(jié)束語

本文工作主要體現(xiàn)在以下幾個方面：①重新設(shè)計并實現(xiàn)了Ant-Solver的數(shù)據(jù)結(jié)構(gòu)和接口，使得算法可以加入弧相容預(yù)處理，并可以處理所有Benchmarks中的問題實例；②提出了一種在線參數(shù)調(diào)節(jié)方案——預(yù)定參數(shù)調(diào)節(jié)，大幅提高了算法的性能并提升了算法的求解成功率；③為Ant-Solver算法加入了弧相容預(yù)處理步驟，進一步提高了算法的性能，最終得到了高效的AC-AS算法；④將此算法用于求解隨機約束滿足問題和組合優(yōu)化問題，并與Ant-Solver進行了實驗對比，驗證了算法的有效性。

[1] LECOUTRE C. Constraint Networks： Techniques and Algorithms[M].London： John Wiley & Sons， Inc， 2009.

[2] GOLOMB S W， BAUMERT L D. Backtrack programming[J]. Journal of the ACM， 1965，(12)： 51-524.

[3] DORIGO M. Optimization， Learning and Natural Algorithms[D].Politecnico di Milano， 1992.

[4] SOLNON C. Ants can solve constraint satisfaction problems[J]. IEEE Transactions on Evolutionary Computation， 2002，6(4)：347-357.

[5] CORMEN T H，et al. Introduction to Algorithms[M]. Cambridge MIT Press， 2001.840-890.

[6] EIBEN A E， MICHALEWICZ Z， SCHOENAUER M，et al. Parameter Control in Evolutionary Algorithms[M]. Springer Berlin Heidelberg，2007.

[7] SMITH B， DYER M. Locating the phase transition in binary constraint satisfaction problems[J]. Artificial Intelligence， 1996， 81(1)：155-181.

[8] CHEESEMAN P， KANEFSKY B， TAYLOR. Where the really hard problems are[A]. Proceedings of IJCAI[C]. 1991. 331-337.

[9] GOMES C， SHMOYS D. Completing quasigroups or latin squares： a structured graph coloring problem[A]. Proceedings of Computational Symposium on Graph Coloring and Generalization[C]. 2002. 22-39.

[10] CARBON B，et al. Radio link frequency assignment[J]. Constraints，1999， (4)： 79-89.

[11] SADEH N， FOX M S. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem[J]. Artificial Intelligence， 1996， 86(1)：1-41.

[12] PARLETT P. The Penguin Book of Patience[M]. Penguin Press， 1996.