約束可滿足性中求解RB模型實例的算法綜述

摘 要：約束滿足問題是人工智能領域中最基本的NP完全問題之一。多年來，隨著約束滿足問題的深入研究，國內外學者提出多種實例模型。其中，RB模型是一種能生成具有精確相變的增長域約束滿足問題實例，其求解難度極具挑戰性。為了尋找其求解的新型高效算法，促進約束可滿足問題的RB模型求解算法領域的研究，首先從約束滿足問題的模型發展、求解技術進行分析；其次，對各類求解RB模型實例算法進行梳理，將求解的算法文獻劃分為回溯啟發式類、信息傳播類和元啟發式類相關改進算法，從算法原理、改進策略、收斂性和精確度等方面進行對比綜述；最后給出求解RB模型實例算法的研究趨勢和發展方向。

關鍵詞：約束滿足問題； RB模型； 回溯啟發式算法； 信息傳播算法； 元啟發式算法

中圖分類號：TP18

文獻標志碼：A

文章編號：1001-3695（2023）07-002-1929-08

doi： 10.19734/j.issn.1001-3695.2022.11.0567

Summary of algorithms for solving RB model instances in constraint satisfiability

Yang Yi^a， Wang Xiaofeng^a，b?， Mo Chunhui^a， Pang Lichao^a， Yang Lan^a， Zhao Xingyu^a

（a.School of Computer Science amp; Engineering， b.Key Laboratory of Images amp; Graphics Intelligent Processing of State Ethnic Affairs Commission， North Minzu University， Yinchuan 750021， China）

Abstract：Constraint satisfaction problem is one of the most basic NP-complete problems in artificial intelligence. Over the years， with the in-depth study of constraint satisfaction problem， scholars at home and abroad have proposed a variety of case models. RB model is an example of growth domain constraint satisfaction problem with precise phase transition， which is very challenging to solve. In order to find a new efficient algorithm and promote the research of RB model algorithm for constraint satisfiability problem， firstly， this paper analyzed the model development and solving techniques of constraint satisfaction problem. Secondly， it sorted out various examples of RB model solving algorithms， and divided the solving algorithm literature into backtracking heuristic， information propagation and meta-heuristic related improved algorithms. This paper compared and summarized the algorithm principles， improved strategies， convergence and accuracy. Finally， it gave the research trend and development direction of solving RB model example algorithm.

Key words：constraint satisfaction problem; RB model; backtracking heuristic algorithm; information dissemination algorithm; meta heuristic algorithm

0 引言

人工智能科學領域中約束可滿足問題（constraint satisfiability problem，CSP）是一個重要的研究方向。CSP是可滿足性（SAT）問題的推廣，可以通過直接編碼、支持編碼和日志編碼等不同的編碼方式轉換為SAT問題。許多實際的優化問題都可以建模轉換為CSP，這使得CSP通過不同編碼方式的SAT公式相較于隨機SAT公式更加天然地擬合了現實問題中的約束關系^［1］。通過約束編程成功應用的實例有機器設計^［2］、電路設計^［3］、汽車變速器設計^［4］、調度與規劃^［5］，還有經典的TSP和皇后問題都屬于CSP。因此，對CSP的研究探索就顯得極其有意義。隨著CSP的發展，在CSP生成模型、相變現象和求解算法等方面的研究取得了不錯的成果。RB（revised B）模型^［6］是近年來所有模型中最為經典的一種具有大值域CSP隨機實例模型，由于RB模型具有精確相變，并且能簡單方便地生成隨機CSP實例，目前是該領域研究人員最常用的實例模型。本文將近年來以RB模型生成CSP大值域實例的求解算法分為基于回溯啟發式、信息傳播類、元啟發式相關改進算法進行分析綜述。這三類算法在求解RB模型實例時都有各自的不足之處：a）回溯（backtracking，BT）啟發式類，雖然求解精度可以保證，但隨著RB模型的變量規模和約束緊密度的增加，算法的時間復雜度呈指數增長；b）信息傳播算法類，該算法較BT算法的啟發式在時間效率上有一定優勢，但算法的收斂性很大程度受限于因子圖中環路數目的影響，由于信息可能會在因子圖環路中出現循環傳遞，算法無法收斂到一個固定的信息，導致求解失敗；c）元啟發式算法類，在求解RB模型的實例時，主要集中在進化類算法上，在大規模實例求解時間上效果優越，但算法極其不穩定，收斂性差，易陷入局部解，需要針對RB模型實例的特點對算法的步驟、搜索特征、算法參數、迭代公式方面都要進行離散化的改進，尋找全局和局部搜索的均衡點是元啟發式算法的一個關鍵。

本文將分別從CSP模型的發展、求解技術、RB模型的基本原理和以RB模型生成的大值域CSP實例的求解算法進行相關概括，從改進思路和相關改進算法的優缺點來對三類算法進行綜述，最后分析以RB模型生成的CSP實例求解算法的改進方向和后續算法的研究趨勢。

1 背景介紹

1.1 CSP模型發展

在最初的理論和算法研究中，針對CSP分別提出了四種“標準”模型（A、B、C、D）來產生隨機的二元標準^［7］CSP實例。但Achlioptas等人^［8］發現這些模型都有致命缺陷，隨著變量數的增加，傳統隨機模型產生的問題實例幾乎都包含缺陷變量，在其大部分參數空間上沒有漸近相變，即平凡漸近不可滿足性。隨后為解決最初提出傳統模型的缺陷，相繼提出E模型^［8］和廣義模型^［9］，E模型不能調整實例的密度，而廣義模型則需利用概率分布而變得復雜。Xu等人^［6］在2000年提出了一種新隨機CSP模型，稱為RB模型，RB模型是一種具有精確相變的增長域實例模型；2006年他們嚴格證明當變量數趨近無窮大時，RB模型確實存在可滿足性相變現象，可以精確地定位閾值點，即具有指數樹解析復雜性^［10］； 2007年Xu等人^［11］從理論和實驗上給出了RB模型容易生成任何數量的隨機實例，并證明在相變的閾值點附近， 求解RB模型隨機實例的難度隨著問題規模的增加呈指數增長，RB模型的提出完美地彌補了上述幾個模型的缺陷。Fan等人在RB模型的基礎上提出了兩個改進模型k-CSP^［12］和d-k-CSP^［13］，k-CSP模型在較小的域和約束長度范圍內能簡單自然地生成漸近非平凡的CSP實例；d-k-CSP模型包括k-CSP和RB模型的特殊極端情況，即域大小和約束范圍是固定的，因此d-k-CSP模型是一種具有小值域非平凡的CSP實例。趙春艷等人^［14］在2020年提出p-RB模型，該模型是RB模型約束緊度的一種改進，具有可變取值域，且在不同的約束緊度能生成具有精確相變點的CSP實例。基于上述RB模型的優點，其生成的基準已廣泛用于各種算法大賽，在統計物理學相關方面進行的研究也頗有成果^［15］，尋找實例解的高效算法便成為研究人員感興趣且具有挑戰性的一個方向。

1.2 RB模型

定義1 RB模型的一類隨機CSP實例表示為P∈RB（k，n，α，r，p），其中對于每個實例的符號定義^［11］如表1所示。

RB模型是從著名的CSP模型B改進而來，由表1定義可以看出隨著RB模型變量數xn的增長，取值域d_N規模呈多項式級增長。生成一個實例P∈RB（k，n，α，r，p），具體步驟如下：a）設置模型RB的主要參數n、p、α和r，其中n是變量數量，p是約束緊度，r和α是兩個自定義的常數；b）重復隨機選擇m個約束條件，每個約束都是通過從n個變量中獨立隨機地選擇k個變量形成；c）對于每個約束C，從完整的d^k_N個賦值中隨機選取pd^k_N種不同的K元賦值形成一個不相容賦值的集合Q_a，當約束C的變量取值不屬于這些不相容賦值集合Q_a時該約束滿足。在文獻［11］中給出存在控制參數p、臨界值p_cr，可確定RB模型的可滿足性相變現象，并給出以下定理：

定理1 設p_cr=1-e^-αr，若α＞1/k，r＞0為兩個常數，且k、α和r滿足不等式ke^-αr≥1，則RB模型有解的概率Pr（Sat）可表示為

利用上述定理公式，根據RB模型的參數取值可確定出相變點p_cr，更準確地說，變量數接近無窮時，若p＜p_cr，RB模型生成的隨機CSP實例以高概率接近于1可解；若p＞p_cr，則CSP實例高概率接近0無解。

二元RB模型實例可用二分無向圖來表示，將RB模型的組成元素劃分為子句節點集合A={a，b，c，…}和變元節點集合B={i，j，k，…}，圖1中分別用方塊和圓圈表示。在RB模型的因子圖中，變量節點的平均度m/n=r ln n，隨著變量數n增加，環的長度呈對數增長，因此RB模型的因子圖是帶有許多環結構的稠密圖而不是稀疏的，但當n增長到充分大時，RB模型的因子圖成局部樹狀結構，這也是RB模型實例能夠使用信息傳播算法高效求解的原因。

2 約束滿足問題求解技術分析

2.1 回溯機制

回溯算法是最先求解CSP的最基本方式，標準回溯在求解時并不理想，其只回溯到搜索樹中最近實例化的變量，導致死胡同的原因可能是在搜索樹的許多層次上。主要有兩個缺點，一個是顛簸，另一個是在搜索的后期才發現死胡同。以回溯算法的改進稱為回溯方案，即向后檢查。如2018年，Udovi?i?等人^［16］利用沖突導向后跳回溯算法解決約束滿足時間表問題；Nadel等人^［17］提出了將時間回溯算法集成在SAT求解器中，提升了求解器的性能。這類回溯方案主要是通過檢查當前變量和先前實例化的變量來發現沖突進行改進，回溯機制的精確求解在小規模實例集上是首選方案，但回溯機制和約束傳播并沒有良好的兼容性，因此改進對于較大規模實例并沒有明顯提升。

2.2 約束傳播

約束傳播也稱為相容性技術，目的是在回溯搜索之前或過程中利用變量和約束的相互關系刪除那些非解變量，縮小搜索空間提高算法效率^［18］，如弧相容（arc consistency，AC）^［19］、廣義弧相容（generalized arc consistency，GAC）^［20］、單弧相容（singleton arc consistency，SAC）^［21］和強局部相容（strong local consistencies，SLC）^［22］等。GAC主要集中在非二進制CSP上；SAC主要是在有限域CSP上；SLC主要體現在規范的二進制或表約束上。由于弧相容在求解約束滿足問題中的高效性和普遍適應性，這些相容技術中AC技術求解CSP的應用問題最為成功。在搜索中，保持弧度一致性（maintaining arc consistency，MAC）算法^［23］是求解CSP的常用方式。它與回溯機制的向后檢查相反，主要針對到連接當前變量的未來變量執行檢查，前向檢查有助于防止未來的沖突。如2021年，Habet等人^［24］提出將沖突歷史搜索集成到基于MAC保持弧一致性和回溯與樹分解（backtracking with tree decomposition，BTD）的求解器中，與最先進的啟發式相比，獲得了具有競爭力的結果和改進。2022年，Kalandaragh^［25］提出在AC-3算法的基礎上引入弧一致性和源節點系數兩個輔助因子，首先嘗試基于弧一致性因子對約束圖中的弧進行排序，如果兩個弧相等，則使用源節點系數輔助因子標準來比較源節點的臨界性，從根本上提升AC-3算法時間復雜度。2019年，Zouita等人^［26］提出在遺傳算法上集成弧相容，其目標是利用弧相容AC算法在遺傳算法的初始種群中從每個域中消除違反其變量的特定約束并使CSP不一致的值，縮小解空間再進行搜索，利用約束傳播與啟發式結合也是一種新思路。

2.3 變量排序和值啟發式

在回溯搜索空間樹中，優秀的剪枝策略能夠在搜索前期高效剪枝，減少回溯次數，是提高求解效率的關鍵^［27］。對變量賦值順序決策和選擇一個合適值賦值直接影響著搜索解的效率，當CSP的約束變量為n時，賦值變量的順序便有n！種^［28］。嘗試實例化最大限度約束其余搜索空間的變量，通常選擇最多約束的變量，對于這種選擇變量實例化的決策稱為變量排序啟發式^［29］。變量排序啟發式又分為靜態變量排序（static variable ordering，SVO）和動態變量排序（dynamic variable ordering，DVO）。由于SVO啟發式是使用約束網絡的初始結構，搜索前確定好排序策略，搜索過程中保持排序不變^［30］。使用這種方式最壞情況的算法復雜度并沒有改變，在SVO和DVO啟發式中，學者們更傾向于探討DVO啟發式。DVO啟發式是指在搜索過程中，根據搜索的當前狀態來決定下一個需要賦值的變量。2016年，Li等人^［31］在值域與加權度比值dom/wdeg^［32］的基礎上提出了值域與動態度結合的約束緊密度dow/Tdeg和值域與動態度結合的加權約束緊密度dom/WTdeg。DVO啟發式都是基于一種失敗優先原則的評估方式^［33］。2018年，Yong等人^［34］提出動態變量排序啟發式算法，使用加權度啟發式算法來確定下一個要選擇的變量，在加權度啟發式算法中，基于加權啟發式算法給每個約束賦予一個權重，然后使用約束權重確定變量的順序。2019年，Wattez等人^［35］對值域和動態度權重比值進行更細致的劃分提出dom/wdeg^ca，cd；2021年，Stergiou^［36］在各類CSP實例集上對主流的啟發式排序策略做了完整的實驗，實驗結果表明，在保持dom/ddeg排序策略下，結合面向變量或面向賦值的AC技術要比結合面向節點的算法策略更加有效，而保持dom/wdeg排序策略在與面向節點相結合的情況下要比結合面向變量或面向賦值的算法策略效率更佳。這兩種排序策略算法與其他一些新型排序啟發式算法相比，適用性和算法效率的表現依然可觀。

2.4 元啟發式

隨著問題規模增大，上述算法復雜度并沒有減少，無法在可接受的時間效率內完成搜索。近年來，元啟發式算法與局部啟發式策略結合提供了新思路，雖然這種近似算法并不能保證找到一致的解決方案，但求解速率在大規模實例集下遠高于普通的完備性算法。與變量排序啟發式相比，面對日益復雜的一些NP完全問題，元啟發式算法往往不需要精確的數學模型，并具有智能性、非線性、通用性、全局性和并行性等優點，一些元啟發式算法在解決CSP時已經取得成功。如：2018年，Dali等人^［37］提出了改進的并行遺傳算法；2019年，Bidar等人^［38］對粒子群算法從算法步驟、迭代公式、參數取值進行離散化改進，提出離散粒子群算法；2021年，Guan等人^［39］提出自適應蟻群算法引入了自動更新機制，在不放棄賦值的優秀變量值對的條件下優化當前最佳賦值，利用該機制保證了解的質量，提高了所提算法的收斂速度和穩定性；2022年，Korani等人^［40］提出離散群智能算法離散母樹優化，記錄收集違反約束并利用母樹優化拓撲結構進行求解。值得一提的是，由于CSP的復雜性和離散性，并非所有的元啟發式算法都適合用來求解，CSP的求解僅局限在個別進化類算法上，算法離散化的適應程度對求解效果有著巨大影響，對元啟發式算法的離散化是算法改進求解的難點。

2.5 其他方式

除上述主流方法處，針對CSP，近些年也提出了各種新型方式。如Cooper等人^［41］給出兩種保持約束滿足的變量的消去規則DE-snake和BT-degree，是一種新型約束傳播技術；Segundo等人^［42］提出一種基于底層微觀結構圖上的問題簡化為k-CLP求解二進制CSP的精確算法；還有利用神經網絡^{［43，44］}、強化學習^{［45～47］}等進行學習變量排序或者賦值順序，然后再利用精確啟發式算法搜索。這些新型技術確實提供了不少新思路，但由于CSP的復雜性，這些算法文獻中的實驗數據都集中在小規模易解區域實例集上，適用性和求解效率還需進一步探索。

3 各種求解算法對比分析

本章主要分析對比近年來以RB模型生成的各類大值域CSP實例算法的求解，將眾多求解中的相關算法再細致化地分為回溯及相關改進算法、信息傳播及其相關改進算法和其他元啟發改進算法三類。這三類算法在求解中各有所長，具體的劃分如圖2所示。

3.1 基于回溯啟發式的改進算法

2021年，范如夢等人^［48］在基于經典的回溯算法上提出基于度啟發式和最少約束值啟發式策略（heuristic backtracking algorithm，HBT）相結合的求解算法，在約束圖中按變量的度降序排列變量，其目的是優先挑選剩余變量和已挑選變量存在約束關系且最大度的變量，再計算出優先挑選出的每個變量的AC支持個數總和num，最后利用最少約束值啟發賦值給num改進求解。2022年，張學才等人^［49］提出基于回溯兩種動態度啟發式算法：一種是ddeg-MAC算法，在回溯算法初始時，根據ddeg啟發式對變量根據動態度進行遞減排序，挑選最大變量賦值，結合MAC技術來求解；另一種是dom/ddeg-MAC算法，根據值域與動態度的比值的最小值來賦值，并結合MAC技術回溯。結果表明，引入值域與度的比值后，在RB模型較小維度上的求解概率和時間效率極其優異，并且在接近相變區域也取得了較好的效果，同組算法中該算法在RB模型求解中的效果最優。該文獻實驗數據表明，dom/ddeg-MAC改進算法是回溯改進啟發式中效果最好的，具體的回溯相關改進算法分析對比如表2所示。

3.2 信息傳播算法及相關改進算法

信息傳播算法^［49］是統計物理分析中提出的計算因子圖上邊緣概率分布的一類近似算法，經典的傳播算法有警示傳播算法（warning propagation，WP）、置信傳播算法（belief propagation，BP）和調查傳播算法（survey propagation，SP）等。信息傳播算法在求解可滿足性問題時取得了不錯的效果^［51］，但問題規模增大時，其樹狀因子圖會變得復雜，影響算法的收斂性能，近年來吸引了不少的國內外學者對其進行收斂性和有效性的研究^{［51～54］}。在針對具有增長域的RB模型求解中，WP和BP的相關改進算法都展現出了其優秀的算法效率。

3.2.1 警示傳播

WP算法是一種逐步迭代的概率算法，算法思想是在因子圖上將子句a傳遞到變量節點i的基本信息記為一個布爾值，表示為u_a→i∈{0，1}。WP算法信息u_a→i的迭代方程為

定義2 因子圖G=（V，E），V表示節點集，E表示邊集合，其中（a，i）∈E，a表示子句，i表示變量節點。集合V（a）表示所有收到的子句a的信息集合；集合C（i）表示變元x_i子句的集合，其中C₊（i）∪C_-（i）=C（i），集合C₊（i）表示變元x_i以正文字出現的子句集合，集合C_-（i）表示變元x_i以負文字出現的子句集合；集合V（a）＼i=V（a）-{i}表示子句a中剔除變元節點i剩余變元節點的信息集合，其中i∈V（a），a∈C（i）。

式（2）中，I^j_a表示若x_i變元正文字出現在子句a中，則I^j_a=-1，若x_i變元以負文字出現在子句a中，則I^j_a=1；t為迭代次數;截尾函數θ（x）為

由式（2）可以得出u_a→i=1表示子句a的滿足性完全取決于變元x_i；u_a→i=0表示a的滿足性并非完全取決于變元x_i；其他變元的取值也有可能使子句a可滿足，對于每個變元x_i，可計算其局部腔域H_i和沖突域C（i）∈{0，1}為

當C_i=1，（∑b∈C₊（i）u^*_b→i）（∑b∈C_-（i）u^*_b→i）＞0表示變元x_i的正文字和負文字出現在兩個子句a、b中，變元x_i的取值在兩子句中不一致，即有a∈C₊（i），u^*_a→i=1，b∈C_-（i），u^*_b→i=1；子句a滿足，變元x_i=1，而子句b滿足，則要變元x_i=0，因而出現矛盾。當C_i=0，變元x_i的取值沒有發生矛盾，則x_i的取值是通過局部腔域H_i來確定的：

當H_i＞0，若WP算法收斂，可以通過高概率確定部分變量取值，即x_i=1；當H_i=0，變元x_i可隨機取值{0，1}；當H_i＜0，變元x_i=0。

算法1 WP算法

輸入：因子圖G=（V，E），最大迭代次數t_max。

輸出：是否收斂，輸出警示信息u^*_a→i。

初始化，迭代次數t=0，對圖G=（V，E）中所有的邊a→i，以0.5的概率從{0，1}中賦值，即初始化警示信息u_a→i（t=0）∈{0，1}；

for t=1 to t_max

通過隨機掃描對每個均勻分布隨機生成排列的邊緣集合，利用式（3）更新所有的邊，即u_a→i（t-1）=u_a→i（t）；

如果對所有的邊存在u_a→i（t）=u_a→i（t-1），則算法已收斂，且u^*_a→i=u_a→i（t）；

若t=t_max，return未收斂；若t＞t_max，return u^*_a→i=u_a→i（t）。

3.2.2 置信傳播

BP算法是一種高效邊緣概率計算的近似算法，其基本思想是基于因子圖以子句a向變元節點i傳遞一個概率值{0，1}，記為u_a→i（x_i）∈{0，1}。置信傳播的數學符號定義如下：

定義3 因子圖G=（V，E），其中（a，i）∈E，a表示子句，i表示變量節點；u_a→i表示子句約束a發送到變量節點i的置信信息；u_i→a表示變量節點i發送給子句約束a的置信信息；u_a→i（x_i）表示在給定x_i概率下，沒有子句a的約束下，滿足子句a的概率；u_i→a（x_i）表示在沒有子句a的約束下，取值為x_i的概率；V（a）表示所有與子句a相連的變量的節點集合；V（i）表示所有與變量節點i相連的子句集合；V（a）＼i=V（a）-{i}表示子句a中剔除變元節點i剩余變量節點的信息集合。

根據以上定義和物理統計中的方法，可以得出BP的迭代方程為

其中：C_i→a和C_a→i是歸一化因子；f_a（X）是一個特征函數，如果X={x_i}滿足子句a，則取值1，否則取值0。

如果BP算法收斂，則收斂唯一的固定信息集δ^*_a→i（x_i）。利用固定信息集可得每個變元節點i邊際概率為u_i。

為了更好地確定變元的賦值順序，定義變量i取值為x_i的分量熵為

S_i（x_i）=-u_i×ln（u_i）（10）

算法2 BP算法

輸入：因子圖G=（V，E），最大迭代次數 t_max，精度ε。

輸出：是否收斂，若收斂，返回定點信息集δ^*_a→i。

初始化，迭代次數t=0，對圖G=（V，E）中所有的邊（a，i）隨機賦值初始化，即u_a→i（x_i）∈{0，1}；

for t=1 to t_max

隨機掃描邊集，并對（a，i）利用迭代方程更新信息，生成δ_a→i（t）；

如果對所有的邊存在δ_a→i（t）-δ_a→i（t-1）＜ε，存在某一時刻t0＜t_max，則算法已收斂，且δ^*_a→i=δ_a→i（t）；

若t=t_max，return未收斂；若t＜t_max，return定點信息集δ^*_a→i。

3.2.3 相關改進算法

由于WP算法在RB模型產生的強迫性可滿足實例集上無法收斂，秦永彬等人^［55］在WP算法的基礎上提出了兩種改進方法，分別是基于WP算法隨機賦值改進和啟發式極性決策算法（heuristic polarity decision making，HPD）。基于WP算法的隨機賦值是指在上述WP算法的第一步初始化時，當t=0 時，有V（a）＼i=?，則取u_a→i=1；對b∈V（i）＼a，若J^a_jJ^b_j＞0，取u_b→i=1，對所有的j∈V（b）＼i，取u_b→i=0，若J^a_jJ^b_j＜0，取u_b→i=0。其余算法步驟不變，這種改進方法是由于固定取值的變元x_i對其子句的滿足性影響不大，所以簡化變元x_i與其子句之間的滿足性關系，起到對WP算法快速收斂的作用。HPD是將WP和DPLL相結合的啟發式極性決策算法，重新定義迭代距離公式為

啟發式極性決策是取某次迭代的警示信息u_a→i（t）的最小值，利用局部腔域H_i得到部分變元進行賦值，剩下的變元隨機賦值。在WP算法不收斂時，將上述得到的這組近似賦值作為DPLL 極性決策變量的賦值來調用DPLL算法，達到快速收斂效果。然而HPD算法在個別實例上會無法搜索到解，其原因是啟發極性策略是建立在WP算法取得一組優秀的警示信息的基礎上，隨著RB模型實例約束緊度P的增大，WP算法的本身性能就會受到影響，并影響整體算法效率。

BP算法在樹狀圖上是精確的^［56］，因為它計算精確的邊際概率u_i，而WP概率的確定完全受約束的變量影響。王曉峰等人^［53］從理論和實驗證明了BP算法在二元CSP實例RB模型上高概率收斂。Zhao等人^［57］提出一種基于變量熵S_i（x_i）挑選變量來固定值的賦值策略，利用邊際概率u_i計算出變量熵S_i（x_i），在S_i（x_i）中挑選出最小的值，賦值給概率最小邊際概率的分量上，循環其過程進而消去所有的變量。隨后趙春艷等人^［58］對文獻［57］進行了改進，每次將最小熵固定賦值在最大邊際概率分量上，提高原基礎算法的效率，但隨著模型實例變得復雜，變量的賦值會被固定在特別少的邊際概率分量上，使算法陷入局部解。吳撥榮等人^［59］提出了置信傳播與模擬退火相結合的方法，在文獻［57，58］最大概率賦值和最小熵策略基礎上得到的賦值作為局部啟發式搜索的初始賦值求解，但其沒有充分考慮變量之間的相互約束關系，使在可滿足性相變發生前該算法失效。任雪亮^［60］對BP算法的迭代方程進行了改進，在其子句a到變量節點i過程中加入懲罰函數P_i（x），具體的計算公式如下：

P_i（x）=exp（δV_i（x））（12）

其實質是將子句對變量的取值約束減弱，懲罰函數中浮點常數δ直接決定了改進置信傳播算法的效率，當改進的置信傳播算法無法收斂時，加入隨機游走算法提高收斂效率。但該算法也存在著明顯的缺陷，即懲罰函數好壞和函數中的浮點常數的取值會直接影響其求解性能。上述改進算法具體的分析對比如表3所示。

3.3 元啟發式及相關改進算法

原志強等人^［61］提出兩種基于模擬退火算法的改進來求解RB模型實例，其改進的第一種算法是在傳統的模擬退火中加入策略性擾動，稱為RSA算法。對傳統退火算法在實例求解上無法利用最優初始賦值做改進，在算法前期采用隨機擾動策略；在算法后期直接找到最佳賦值記為當前賦值，再進行擾動策略。RSA并沒有考慮到對于傳統模擬退火的初始賦值隨機性的改進，于是提出了另一種改進算法GAS，將上述模擬退火的擾動策略應用于遺傳算法的變異操作，利用改進的遺傳算法得到初始賦值，再利用RSA算法尋優。李飛龍等人^［62］提出了一種禁忌搜索和模擬退火相結合的算法，稱為TS-SA，首先利用禁忌算法得到一組初始賦值，利用改進的RSA退火算法求解，通過禁忌算法增強了全局搜索能力，提高了RSA算法對初始賦值的依賴性。Jashmi等人^［63］針對CSP提出的兩種啟發式遺傳算子——無性算子和多親算子進行改進，在基本的遺傳算法中用無性算子來代替交叉算子提出了HGA1、將多重啟發算子應用在隨機突變的遺傳算法中提出了HGA2、提出的HGA3是HGA1與HGA2相結合的啟發式算法。結果表明，無論是算法HGA1還是HGA2和HGA3并沒有提升原遺傳算法的性能。隨后微遺傳迭代下降算法（micro genetic iterative descent algorithm，MGID）通過改變搜索過程中計算適應度的方式來指導搜索；另外在遺傳算法中加入一種逐步調整權重（stepwise adaption of weights，SAW）^［64］的啟發式。SAW啟發的基本思想是，在經過一定的算法步驟后，不滿足的約束或導致違反約束的變量是困難的，所以給其較多的權重懲罰，促使算法達到快速收斂。結果表明，Swing-GA更適合解決較難的問題，在低密度問題上Swing-GA算法效率反而變慢。在簡單問題上來看，MGID算法似乎是相當優秀的，在算法能夠達到解的情況下，MGID算法在成功率和平均最佳適應度方面是最有效的。Abbasian等人^［65］提出了一種改進的遺傳算法，利用主從式結構MSPGA設計了一種新體系結構HPGA（hierarchical PGA），提出了一種專門為CSP設計的新交叉算子稱為父母成功交叉（parental success crossover，PSC），加入額外操作步驟基因改造（genetic modification，GM），并結合一種可變排序啟發式策略^［66］。具體流程是，可變排序將作為每個PGA的一部分運行，在每次迭代結束時，搜索選擇從搜索過程找到最佳的解決方案，并計算約束的新權重進行排序，將得到最大的排序賦值給GM，然后GM使用這個新排序來創建新的個體，結合HPGA算法進行求解。上述改進都是基于GA提出的一些改進，遺傳算法通常用于處理離散化問題，更容易應用于CSP。Bidar等人^［67］提出的FA求解RB模型實例，首先要解決的問題是將FA進行離散化處理，重新定義FA算法的步驟和特征，并考慮三種隨機突變算子來處理局部最優陷阱。隨后又提出了將FGOA離散化，稱為DFGOA來求解RB模型產生的CSP實例^［68］。同樣，重新定義算法步驟，通過改進影響因子函數使FGOA避免早期收斂，引入監控函數來防止FGOA避免陷入局部最優。上述改進在文獻中提出的相變區域0.05～0.6都表現非常優異，但并未給出RB模型的具體參數，因此無法評估其算法的具體性能。上述改進算法的分析對比如表4所示。

3.4 各算法效率統計分析

對于以上各種算法，本文取上述對比算法的各文獻中使用同種RB模型設置參數進行統計對比分析。表5分別統計了各類算法在變量n取［20∶20∶100］，約束密度P在［0.00， 0.23］五組實例上的求解概率范圍。評價指標為在以1概率可解p和算法最大失效p值下，p值越大算法的求解能力越高效。

可以看出以回溯為核心完備性求解的三種算法中，在各組維度上dom/ddeg-MAC算法最優，在變量n=20時，基本在可滿足相變點0.2處依然概率1可解；但在變量逐漸增大后，時間復雜度呈指數增長，求解能力也隨之下降。在不完備算法中，BP-RSA、TS-SA和GSA較優，整體求解范圍性能相差不大，雖然與dom/ddeg-MAC相比還有一定差距，但整體算法時間效率是可觀的。由于完備性算法是精確類算法，只取不完備性算法進行精確度對比。圖3是統計文獻［59］中部分不完備性算法在變量n取［20∶20∶100］、在接近可滿足相變P取［0.17，0.20］的平均不可滿足約束數的對比圖，可以清晰地看出隨著約束密度的增長，算法的平均不可滿足數也在增加，在各算法對比中TS-SA求解精度最好，RSA效果最差。

表6是取文獻［63］統計分析遺傳啟發式等在變量n取80、約束密度P取［0.05，0.16，0.24］上的對比分析統計，其中SR代表算法的求解成功率，Bfit表示算法的求解最佳適應度值。由表6中可以看出，MGID算法在P=0.05和P=0.16時求解效率最優，而Sawing GA雖然在P=0.16時求解失敗，但在復雜難解的P=0.24實例集上依然有概率求解。

表7統計了文獻［67］中各算法在變量n取100、在約束密度P取［0.1∶0.05∶0.6］的求解對比，SR為求解概率，NVC為最佳不可滿足約束。由于RB模型參數的取值影響實例的復雜程度，該實驗中DFA與DFGOA在該模型上都取得了較優秀的效果，求解概率SR都為100%，而HPGA+GM+PSC算法在P=0.6時，79%概率可解。

4 求解RB模型的研究趨勢

針對上述文獻的各類算法在求解RB模型實例中的分析對比，本文給出以下幾個求解改進方向：

a）基于回溯的啟發式改進算法從上述算法對比可以看出，回溯法在變量排序啟發式策略和MAC相結合時有著相當不錯的效果，在中小規模對精度有要求的求解上，完備性算法依然是首選。之后算法的求解中，主要還是在變量排序的啟發式策略上進行改進，或者從另一種思路改進，如利用神經網絡或強化學習來進行學習變量排序賦值順序，提高算法效率。

b）信息傳播算法求解RB模型實例時還是存在一些問題，收斂性會隨著問題規模和求解的復雜度增大，其RB模型因子圖的結構變得復雜；當因子圖存在多個環形結構，信息傳播算法往往存在著難以收斂的情況。在后續的信息傳播算法中改進信息傳播算法的迭代方程，提高信息傳播算法的收斂性和精確度，在難以收斂的情況下引入如隨機游走最小沖突啟發式算法（min-conflicts heuristic with random walk，WMCH）^［69］等局部搜索啟發式再進行優化。

c）完備性策略算法不適用于大規模具有增長域RB模型求解，信息傳播算法又受限于RB模型因子圖環狀個數的收斂條件。綜上所述，基于元啟發式求解似乎是一種理想的求解方式，但根據目前文獻檢索，除蟻群、遺傳、局部搜索等個別算法并沒有其他智能優化算法應用于RB模型的大實例集求解（只局限于小規模的易解區域）上。分析智能優化算法難以應用于RB模型有以下難點：（a）一般啟發式優化算法大多用于連續型問題，首要解決的是將初始解空間進行離散化；（b）元啟發式優化搜索對于RB模型是一種并不適用的無規則擾動，要用于求解，需要對算法的步驟、搜索特征、算法參數、迭代公式方法進行離散化改進；（c）對于智能優化算法求解精度不高的缺陷，可以設計一種高效的局部啟發式，在智能優化給出的優化賦值上進行局部搜索，提高算法的精確度；（d）由于RB算法實例集龐大復雜，具有精確相變點，算法需要考慮每組變量維度和相變區域，需要大量實驗仔細設置算法中的各種參數值，找到全局各組變量實例集的一個均衡、最佳的參數值。

分析以上四個難點，希望有針對性地提出一種適用性廣、穩定性好且兼容RB模型實例各個變量維度和約束緊密度離散版本的改進的元啟發式并結合局部啟發式技術的高效算法。

5 結束語

CSP是人工領域的重要分支之一，RB模型作為一種經典且具有挑戰性的CSP實例，尋找其高效的求解算法是極其有意義的。求解RB模型的研究算法已受到學術界的廣泛關注，梳理CSP的模型發展、對經典求解技術進行概述，分析近年求解RB模型上的多種算法文獻，從各類算法的原理、有效性等基礎對比，希望能為求解CSP方向的研究人員整理出新的探究思路，尋找更優秀、高效的求解算法。

參考文獻：

［1］Cook S A. The complexity of theorem-proving procedures［C］//Proc of the 3rd Annual ACM Symposium on Theory of Computing. New York： ACM Press， 1971：151-158.

［2］Frayman F， Mittal S. COSSACK： a constraint-based expert system for configuration tasks［C］//Proc of Knowledge-Based Expert Systems in Engineering： Planning and Design. Cambridge： Cambridge University Press， 1987：143-166.

［3］De Kleer J， Sussman G J. Propagation of constraints applied to circuit synthesis［J］. International Journal of Circuit Theory and Applications， 1980，8（2）： 127-144.

［4］Nadel B A， Lin J. Automobile transmission design as a constraint sa-tisfaction problem： modelling the kinematic level［J］. AI EDAM， 1991，5（3）： 137-171.

［5］Mackworth A K. On seeing things， again［C］//Proc of the 8th International Joint Conference on Artificial Intelligence. 1983： 1187-1191.

［6］Xu Ke， Li Wei. Exact phase transitions in random constraint satisfaction problems［J］. Journal of Artificial Intelligence Research， 2000，12（1）： 93-103.

［7］Gent I P， MacIntyre E， Prosser P， et al. Random constraint satisfaction： flaws and structure［J］. Constraints， 2001，6（4）： 345-372.

［8］Achlioptas D， Molloy M S O， Kirousis L M， et al. Random constraint satisfaction： a more accurate picture［J］. Constraints， 2001，6（4）： 329-344.

［9］Molloy M. Models and thresholds for random constraint satisfaction problems［C］//Proc of the 34th Annual ACM Symposium on Theory of Computing. New York： ACM Press， 2002： 209-217.

［10］Xu Ke， Li Wei. Many hard examples in exact phase transitions［J］. Theoretical Computer Science， 2006，355（3）： 291-302.

［11］Xu Ke， Boussemart F， Hemery F， et al. Random constraint satisfaction： easy generation of hard （satisfiable） instances［J］. Artificial Intelligence， 2007，171（8-9）：514-534.

［12］Fan Yun， Shen Jing. On the phase transitions of random k-constraint satisfaction problems［J］. Artificial Intelligence， 2011，175（3-4）：914-927.

［13］Fan Yun， Shen Jing， Xu Ke. A general model and thresholds for random constraint satisfaction problems［J］. Artificial Intelligence， 2012，193（12）： 1-17.

［14］趙春艷， 范如夢， 劉雅楠. 不同緊度下約束滿足問題的相變現象［J］. 計算機應用研究， 2020，37（9）： 2739-2743. （Zhao Chunyan， Fan Rumeng， Liu Yanan. Phase transitions in random constraint satisfaction problem with various constraint tightness［J］. Application Research of Computers， 2020，37（9）： 2739-2743.）

［15］Zhou Guangyan， Xu Wei. Super solutions of the model RB［J］. Frontiers of Computer Science， 2022，16（6）： article No.166406.

［16］Udovi?i? M， Hafizovi?" N. Constraint satisfaction problem：generating a schedule for a company excursion［C］//Proc of International Symposium on Innovative and Interdisciplinary Applications of Advanced Technologies. Cham： Springer， 2018： 430-438.

［17］Nadel A， Ryvchin V. Chronological backtracking［C］//Proc of the 21st International Conference on Theory and Applications of Satisfiability Testing. Cham： Springer， 2018： 111-121.

［18］Barták R. Theory and practice of constraint propagation［C］//Proc of the 3rd Workshop on Constraint Programming in Decision and Control. 2001.

［19］Guo Jinsong， Li Zhanshan， Li Hongbo. Partial max-restricted path consistency［C］//Proc of the 24th International Conference on Tools with Artificial Intelligence. Washington DC： IEEE Computer Society， 2012： 186-190.

［20］Zhang Xizhe， Gao Jian， Lyu Yizhi， et al. Early and efficient identification of useless constraint propagation for all different constraints［C］//Proc of the 29th International Joint Conferences on Artificial Intelligence. 2021： 1126-1133.

［21］Bessiere C， Cardon S， Debruyne R， et al. Efficient algorithms for singleton arc consistency［J］.Constraints， 2011，16（1）： 25-53.

［22］Paparrizou A. Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems［J］. Constraints， 2015，20（10）： 484-485.

［23］Wang Ruiwei， Yap R H C. Arc consistency revisited［C］//Proc of the 16th International Conference on Integration of Constraint Programming，Artificial Intelligence， and Operations Research.Cham： Springer， 2019： 599-615.

［24］Habet D， Terrioux C. Conflict history based heuristic for constraint satisfaction problem solving［J］. Journal of Heuristics， 2021，27（6）： 951-990.

［25］Kalandaragh Y S. Speeding up the arc consistency algorithm in constraint satisfaction problems： a new modification of AC-3［J］. Journal of Algorithms and Computation， 2022，54（1）： 125-138.

［26］Zouita M，Bouamama S，Barkaoui K. Improving genetic algorithm using arc consistency technic［J］. Procedia Computer Science， 2019，159： 1387-1396.

［27］Balafoutis T， Stergiou K. Evaluating and improving modern variable and revision ordering strategies in CSPs［J］. Fundamenta Informaticae， 2010，102（3-4）： 229-261.

［28］Gent I P， MacIntyre E， Presser P， et al. An empirical study of dynamic variable ordering heuristics for the constraint satisfaction pro-blem［C］//Proc of the 2nd International Conference on Principles and Practice of Constraint Programming. Berlin： Springer-Verlag ， 1996： 179-193.

［29］Stone H S， Stone J M. Efficient search techniques： an empirical study of the N-Queens problem［J］. IBM Journal of Research and Deve-lopment， 1987，31（4）： 464-474.

［30］Mohamed A， Yusoff M， Mohtar I A， et al. Constraint satisfaction problem using modified branch and bound algorithm［J］. WSEAS Trans on Computers， 2008，7（1）： 1-7.

［31］Li Hongbo， Liang Yanchun， Zhang Ning， et al. Improving degree-based variable ordering heuristics for solving constraint satisfaction problems［J］. Journal of Heuristics， 2016，22（2）： 125-145.

［32］Balafoutis T， Stergiou K. Adaptive branching for constraint satisfaction problems［C］//Proc of the 19th European Conference on Artificial Intelligence. Amsterdam： IOS Press， 2010： 855-860.

［33］Crawford B， Castro C， Monfroy ， et al. Dynamic selection of enumeration strategies for solving constraint satisfaction problems［J］. Romanian Journal of Information Science and Technology， 2012，15（2）： 106-128.

［34］Yong K W， Mouhoub M. Using conflict and support counts for variable and value ordering in CSPs［J］. Applied Intelligence， 2018，48（8）： 2487-2500.

［35］Wattez H， Lecoutre C， Paparrizou A， et al. Refining constraint weighting［C］//Proc of the 31st IEEE International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE Press， 2019： 71-77.

［36］Stergiou K. Adaptive constraint propagation in constraint satisfaction： review and evaluation［J］. Artificial Intelligence Review， 2021，54（7）： 5055-5093.

［37］Dali N， Bouamama S. New parallel genetic algorithms on GPU for solving max-CSPs［C］//Proc of the 14th IEEE International Confe-rence on Intelligent Computer Communication and Processing. Pisca-taway， NJ： IEEE Press， 2018： 119-126.

［38］Bidar M， Mouhoub M. Discrete particle swarm optimization algorithm for dynamic constraint satisfaction with minimal perturbation［C］//Proc of IEEE International Conference on Systems， Man and Cybernetics. Piscataway， NJ： IEEE Press， 2019： 4353-4360.

［39］Guan Boxin， Zhao Yuhai， Li Yuan. An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems［J］. Expert Systems with Applications， 2021，164（2）： 114021.

［40］Korani W， Mouhoub M. Discrete mother tree optimization and swarm intelligence for constraint satisfaction problems［C］//Proc of the 14th International Conference on Agents and Artificial Intelligence. Berlin： Springer-Verlag， 2022： 234-241.

［41］Cooper M C， El Mouelhi A， Terrioux C. Variable elimination in binary CSPs［C］//Proc of the 29th International Joint Conference on Artificial Intelligence. 2021： 5035-5039.

［42］Segundo P S， Furini F， León R. A new branch-and-filter exact algorithm for binary constraint satisfaction problems［J］. European Journal of Operational Research， 2022，299（2）： 448-467.

［43］Tnshoff J， Ritzert M， Wolf H， et al. Graph neural networks for maximum constraint satisfaction［J］. Frontiers in Artificial Intelligence， 2020，3：580607.

［44］Pedretti G， Mannocci P， Hashemkhani S， et al. A spiking recurrent neural network with phase-change memory neurons and synapses for the accelerated solution of constraint satisfaction problems［J］. IEEE Journal on Exploratory Solid-State Computational Devices and Circuits， 2020，6（1）： 89-97.

［45］Wattez H， Koriche F， Lecoutre C， et al. Learning variable ordering heuristics with multi-armed bandits and restarts［C］//Proc of the 24th European Conference on Artificial Intelligence. Amsterdam：IOS Press， 2020： 371-378.

［46］Balafrej A， Bessiere C， Paparrizou A. Multi-armed bandits for adaptive constraint propagation［C］//Proc of the 24th International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2015： 290-296.

［47］Xia Wei， Yap R H C. Learning robust search strategies using a bandit-based approach［C］//Proc of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2018： 6657-6664.

［48］范如夢， 趙春艷， 李飛龍. 啟發式回溯算法求解約束滿足問題［J］. 計算機應用研究， 2021，38（5）： 1438-1442. （Fan Rumeng， Zhao Chunyan， Li Feilong. Heuristic backtracking algorithm to solve constraint satisfaction problems［J］. Application Research of Computers， 2021，38（5）： 1438-1442.）

［49］張學才， 趙春艷. 基于動態度的回溯算法求解大值域約束滿足問題［J］. 計算機應用研究， 2022，39（5）：1427-1431. （Zhang Xuecai， Zhao Chunyan. Dynamic degree based backtracking algorithm to solve constraint satisfaction problems with large domains［J］. Application Research of Computers， 2022，39（5）： 1427-1431.）

［50］Braunstein A， Mézard M， Zecchina R. Survey propagation： an algorithm for satisfiability［J］. Random Structures amp; Algorithms， 2005，27（2）： 201-226.

［51］Maneva E， Mossel E， Wainwright M J. A new look at survey propagation and its generalizations［J］. Journal of the ACM， 2007，54（4）： article No.17.

［52］王曉峰， 許道云， 姜久雷， 等. 調查傳播算法收斂的一個充分條件［J］. 中國科學： 信息科學， 2017，47（12）： 1646-1661. （Wang Xiaofeng， Xu Daoyun， Jiang Jiulei， et al. A sufficient condition for convergence of survey propagation algorithm［J］. Science in China： Information Sciences， 2017，47（12）： 1646-1661.）

［53］王曉峰， 許道云. RB模型實例集上置信傳播算法的收斂性［J］. 軟件學報， 2016，27（11）： 2712-2724. （Wang Xiaofeng， Xu Daoyun. Convergence of the belief propagation algorithm for RB model instances［J］. Journal of Software， 2016，27（11）： 2712-2724.）

［54］Koehler F. Fast convergence of belief propagation to global optima： beyond correlation decay［C］//Proc of the 33rd Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2019： 8331-8341.

［55］秦永彬， 許道云， 王曉峰. 基于警示傳播與 DPLL 算法的啟發式極性決策算法［J］. 計算機科學， 2010，37（12）： 178-181，185. （Qin Yongbin， Xu Daoyun， Wang Xiaofeng. Heuristic polarity decision making algorithm based on warning propagation and DPLL algorithm［J］. Computer Science， 2010，37（12）： 178-181，185.）

［56］王曉峰， 李強， 丁紅勝. 規則實例集上警示傳播算法的收斂性［J］. 計算機科學， 2015，42（1）： 279-284. （Wang Xiaofeng， Li Qiang， Ding Hongsheng. Convergence of warning propagation algorithm for regular structure instances［J］. Computer Science， 2015，42（1）： 279-284.）

［57］Zhao Chunyan， Zhou Haijun， Zheng Zhiming， et al. A message-passing approach to random constraint satisfaction problems with growing domains［J］. Journal of Statistical Mechanics： Theory and Experiment， 2011，2011（2）： P02019.

［58］趙春艷， 鄭志明. 一種基于變量熵求解約束滿足問題的置信傳播算法［J］. 中國科學： 信息科學， 2012，42（9）： 1170-1180. （Zhao Chunyan， Zheng Zhiming. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems［J］. Science in China： Information Sciences， 2012，42（9）： 1170-1180.）

［59］吳撥榮， 趙春艷， 原志強. 置信傳播和模擬退火相結合求解約束滿足問題［J］. 計算機應用研究， 2019，36（5）： 1297-1301. （Wu Borong， Zhao Chunyan， Yuan Zhiqiang. Combining belief propagation and simulated annealing to solve random satisfaction problems［J］. Application Research of Computers， 2019，36（5）： 1297-1301.）

［60］任雪亮. 改進的置信傳播算法在求解最大約束滿足問題的應用［D］. 長春： 東北師范大學， 2015. （Ren Xueliang. Application of improved belief propagation algorithm in solving the maximum constraint satisfaction problem［D］. Changchun： Northeast Normal University， 2015.）

［61］原志強， 趙春艷. 兩種改進的模擬退火算法求解大值域約束滿足問題［J］. 計算機應用研究， 2017，34（12）： 3611-3616. （Yuan Zhiqiang， Zhao Chunyan. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains［J］. Application Research of Computers， 2017，34（12）： 3611-3616.）

［62］李飛龍， 趙春艷， 范如夢. 基于禁忌搜索算法求解隨機約束滿足問題［J］. 計算機應用， 2019，39（12）： 3584-3589. （Li Feilong， Zhao Chunyan， Fan Rumeng. Solving random constraint satisfaction problems based on tabu search algorithm［J］. Journal of Computer Applications， 2019，39（12）： 3584-3589.）

［63］Jashmi B J， Mouhoub M. Solving temporal constraint satisfaction problems with heuristic based evolutionary algorithms［C］//Proc of the 20th IEEE International Conference on Tools with Artificial Intelligence. Piscataway， NJ： IEEE Press， 2008： 525-529.

［64］Fredericks E M. An empirical analysis of the mutation operator for run-time adaptive testing in self-adaptive systems［C］//Proc of the 11th International Workshop on Search-based Software Testing. New York： ACM Press， 2018： 59-66.

［65］Abbasian R， Mouhoub M. A new crossover for solving constraint sa-tisfaction problems［C］//Proc of the 13th European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin：Springer-Verlag， 2013： 37-48.

［66］Mouhoub M，Jafari B. Heuristic techniques for variable and value ordering in CSPs［C］//Proc of the 13th Annual Conference on Genetic and Evolutionary Computation. New York：ACM Press， 2011：457-464.

［67］Bidar M， Mouhoub M， Sadaoui S. Discrete firefly algorithm： a new metaheuristic approach for solving constraint satisfaction problems［C］//Proc of IEEE Congress on Evolutionary Computation. Pisca-taway， NJ： IEEE Press， 2018： 1-8.

［68］Bidar M， Mouhoub M， Sadaoui S. Discrete focus group optimization algorithm for solving constraint satisfaction problems［C］//Proc of the 12th International Conference on Agents and Artificial Intelligence. Cham： Springer， 2020： 322-330.

［69］Xu Wei， Gong Fuzhou. Performances of pure random walk algorithms on constraint satisfaction problems with growing domains［J］. Journal of Combinatorial Optimization， 2016，32（1）： 51-66.