求解約束滿足問題的改進蟻群優化算法

張永剛 ，張思博 ，薛秋實

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

1 引言

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

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

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

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

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

2 AC-AS算法

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

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

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

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

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

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

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

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

圖1 域過濾相容性檢查的強弱關系

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

3 AC-AS算法在隨機問題中的應用

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

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

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

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

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

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

表2 RB模型隨機CSP實例frb

表3 準隨機CSP實例

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

4 AC-AS算法在組合優化問題中的應用

組合優化問題中的應用比較廣泛，例如工程、建筑、計算機科學、音樂、理財以及其他許多領域。例如，人們日常生活中所使用的電話，在其實現的過程中就要求通過成本低、路徑堵塞小和智能化等系列優化問題來最終實現較高效能；汽車制造也有很多的優化目標：減小風阻、提高安全系數、人性化舒適體驗等。組合優化問題可以用 CSP來表示，因此可以用 AC-AS來求解組合優化問題。另外，由于組合優化問題來自于現實中的應用，通常都帶有一定的結構特點，求解組合優化問題可以考察 AC-AS求解結構化問題的性能。以下實驗均在同一臺 PC上完成：處理器為Intel E7500雙核CPU、主頻為2.93 GHz、內存為 2 GB、操作系統為 Microsoft Windows XP Professional Service Pack 3。

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

表4 組合優化問題實例

5 結束語

本文工作主要體現在以下幾個方面：①重新設計并實現了Ant-Solver的數據結構和接口，使得算法可以加入弧相容預處理，并可以處理所有Benchmarks中的問題實例；②提出了一種在線參數調節方案——預定參數調節，大幅提高了算法的性能并提升了算法的求解成功率；③為Ant-Solver算法加入了弧相容預處理步驟，進一步提高了算法的性能，最終得到了高效的AC-AS算法；④將此算法用于求解隨機約束滿足問題和組合優化問題，并與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.