求解二次分配問題的預處理快速螞蟻系統

吳果林， 李學遷

（1.桂林航天工業學院理學部，桂林 541004；2.上海理工大學管理學院，上海 200093）

二次分配問題（quadratic assignment problem，QAP）是由Koopmans等［1］在1957年提出的組合優化問題.該問題可描述為給定n個設施和n個節點，兩個n×n的矩陣D＝（drs）和F＝（fij）.其中drs是節點r和s之間的距離，而fij是設施i和j之間的流量.QAP是尋找一個分配方案，使得每一個設施分配一個節點.由于設施的數量等于節點的數量，故每一個分配方案相當于整數集｛1，2，…，n｝中的一個排列.QAP的目標是尋找整數集｛1，2，…，n｝中的一個排列，最小化目標函數

其中，Φ為整數集｛1，2，…，n｝所有排列的集合，φ為Φ中的一個排列（或問題的一個解），φi給出了設施i在當前解φ上的節點.

Sahni等［2］于1976年證明QAP是一個NP－難的優化問題，因此當問題的規模超過30時，尋找問題的最優解就變得不切實際，一個切實可行的辦法是使用元啟發式算法以便在合理的時間內找到高質量的解.當前用于求解QAP的元啟發式算法有遺傳算法［3］、模擬退火算法［4］、禁忌搜索算法［5－6］、蟻群優化算法［7－13］和迭代局部搜索算法［14－15］等.

在過去的近20年里，蟻群優化算法被用于求解許多組合優化問題［16］.事實上，對于二次分配問題中結構化的、現實生活例子，蟻群優化算法是已知的求解QAP的最好算法之一.本文調查分析了快速螞蟻系統（fast ant system，FANT）［10－11］，給出了預處理快速螞蟻系統（preprocessing fast ant system，PFANT）.該算法在構建問題的解時預先進行了搜索，挑選那些質量較優的解參與局部搜索，并設置動態的算法參數，防止算法陷入局部最優解，出現停滯.這種對FANT算法的改進既保持了其運行前期收斂速度快的優點［11］，拓寬了算法的搜索范圍，又改進了解的質量.數值實驗進一步表明，預處理快速螞蟻系統在求解結構化的、現實生活的例子保持蟻群優化算法的優越性；在求解隨機產生無結構、網格距離例子時，其性能與求解這兩類例子的最好算法——禁忌搜索算法（robust taboo search，RTS）［6］不相上下.

1 快速螞蟻系統

受螞蟻系統算法的啟發，Taillard開發了求解QAP的蟻群優化算法，稱為快速螞蟻系統［10－11］.在FANT算法中，解的構建是由人工螞蟻通過隨機地選擇還沒有分配的設施i，利用概率選擇規則將其分配到空閑的節點j上，即

式中，τij為分配設施i到節點j上的權重；Ni為設施i可分配的節點.

FANT算法不同于其它蟻群優化算法的地方主要是人工螞蟻的數量和信息素更新管理.FANT算法僅使用一個人工螞蟻，單個人工螞蟻導致該算法快速尋找到一個質量較好的解歸咎于局部搜索算法的引入和相當特殊的參數設置.另一個不同于其它蟻群優化算法，是信息素更新管理，FANT算法不使用信息素蒸發.初始所有的信息素都設置為1，每一次迭代后信息素更新方式為

式中，Jφ為當前解φ的目標函數值；Jφib為迭代最優解φib的目標函數值；r和R為兩個參數.r的值在算法運行過程中可以發生改變，初始值設為1，而R為固定常數.除按式（2）的更新規則更新信息素之外，信息素與參數r還將在兩種情況下發生改變：a.如果迭代最優解φib發生改變，則參數與所有的信息素全都重新設置為1；b.當人工螞蟻構建的解與迭代最優解φib相同時，參數將增加1個單位且所有的信息素設為r.

設信息素矩陣為Γ＝（τij）n×n，初始，令r＝1，τij＝r（i，j＝1，2，…，n），迭代最優解為φib，則FANT重復執行如下步驟（算法1）：

步驟1 利用式（1）構建問題的當前解φ；

步驟2 利用局部搜索技術改進當前解φ，為方便計仍記為φ；

步驟3 如果Z（φ）＜Z（φib），則φib＝φ，并設r＝1，τij＝r（i，j＝1，2，…，n）；

步驟4 按式（2）的更新方式更新信息素矩陣Γ.

2 預處理快速螞蟻系統

從前面的敘述可以看出，FANT試圖設計一種能夠整合重點搜索迭代最優解和解構建時探索性的算法.也就是說，一方面通過信息素更新，FANT不斷地增加迭代最優解的權重，使得算法在迭代最優解鄰域選擇問題的解；另一方面，當算法出現停滯時（FANT以構建解等于迭代最優解作為判斷標準），重新設置信息素，并令r＝r＋1，降低迭代最優解與算法構建解所對應節點信息素增加的比重，減少迭代最優解所對應節點的權重，拓寬解的搜索范圍，增加算法構建解的探索性.然而，從實驗的結果來看，FANT算法解的質量并沒有達到預期效果，只是在算法運行的初期，FANT總體上比其它算法要好一些，在算法運行的后期，其解的質量比其它算法要劣［11］.即FANT算法初期收斂速度快，后期易出現停滯.出現這種現象，與FANT算法信息素更新策略有關.由于FANT算法在每次出現新的迭代最優解時，信息素重新設置為1，迭代最優解對應的節點信息素設為R，算法始終在迭代最優解鄰域尋找問題的解，故算法運行初期收斂速度快.易見，這樣處理的結果是算法容易陷于局部最優解，產生停滯.盡管FANT算法設計了跳出局部最優解的策略（當人工螞蟻構建的解與迭代最優解φib相同時，參數將增加1個單位且所有的信息素設為r），但這種方式所需迭代次數太多，代價太高.關于這一點，可從下面的分析看出.

設FANT在t次迭代產生的迭代最優解φib，信息素矩陣為Γ＝（τij）n×n，τij＝r且r＝1，進一步假設此解φib為局部最優解，算法出現停滯.下面計算FANT算法跳出局部最優解所需迭代的次數.由于FANT算法采用當迭代產生的解與迭代最優解φib相同時，重新設置信息素r，降低迭代最優解權重的方法，改變停滯現象.為此，先計算第一次當前解與迭代最優解φib相同（即第t＋k1次迭代產生的解等于迭代最優解φib）時，FANT算法所需迭代次數，記為k1.根據FANT算法，每次迭代時，當前解對應節點的信息素增加1；迭代最優解φib對應節點的信息素增加R.故第t＋k1次迭代時，信息素矩陣Γ每一行元素和都為n＋k1（R＋1），迭代最優解φib對應的每一個節點的信息素應小于等于k1（R＋1）＋1（此值為每次迭代時當前解等于迭代最優解時信息素的值）.設在第t＋k1次迭代時，迭代最優解作為當前解的概率P，由概率乘法公式

則P應滿足

表1給出了QAP規模為25，50，100，選擇概率為0.1，0.5，0.9，重新設置信息素為1，2，…，6時，FANT算法所需迭代的次數，R的取值均為6.

表1 跳出局部最優解的迭代次數Tab.1 Iterations times of jumping out of local optimal solution

從表1可以看出，要以較高的概率跳出局部最優解，算法所需的迭代次數非常多.以QAP規模50為例，若以0.9的概率取得局部最優解，算法至少需要迭代1 656次.由于算法每次迭代所需的時間為O（503），故算法跳出局部最優解的時間花費至少為1 656×O（503），這個數值已經超過RTS［6］算法求解QAP規模為50的迭代1 000×50次所需的時間（RTS每次迭代所需的時間為O（502）），而RTS算法迭代1 000×50次得到問題的解常常作為其它算法求QAP時比較的參照文獻［8，14－15］.也就是說，對于規模為50的QAP實例而言，FANT算法以0.9的概率跳出局部最優解的時間大于RTS算法1 000×50次迭代的時間.由表1不難得出，QAP其它規模的例子同樣也有類似的結果.綜上所述，FANT算法設計跳出局部最優解的策略所需迭代次數太多，算法后期很少改進算法解的質量.

盡管有上述不足，但FANT算法仍然是求解QAP的非常有競爭力的算法，文獻［12－13］給出了兩種改進的FANT算法.事實上，仔細分析算法1的流程不難發現，步驟2是對步驟1產生的解利用局部搜索進行改進，而改進后解質量的好壞很大程度取決于步驟1產生解的質量.因此，可以對步驟1進行改進，如對步驟1產生的解進行預處理，以便較高質量的解參與步驟2的搜索改進.由于步驟1構建解是不斷通過隨機選擇一個設施由概率選擇式（1）分配一個節點得到，故對于每一個設施i分配的節點φi，可以比較與前次迭代產生的解所對應的設施i的節點φ′i是否相同.若φi≠φ′i，將前次迭代解對應的兩個節點φi，φ′i的位置進行交換，再比較交換后解的質量；若質量優于交換前的，則設施i分配節點φi，否則設施i還是分配原來的節點φ′i.上述方法通過不斷地重復，最終得到改進的迭代解.易見，改進后的迭代解剔除了那些迭代過程中產生的質量較劣的解，使得每次迭代產生的解始終以較好的解參與步驟2的局部搜索，減少一些無為的迭代與局部搜索，保證更好質量的解產生.當然，上述改進也易使算法快速陷入局部最優解，產生停滯.為防止或減少該現象的發生，在算法每次得到一個新的迭代最優解時重新設置一個新的r值，記為r（t），區別于原算法每次重新設置r都等于1.

另一方面，由算法1可知，FANT算法采用固定參數R的策略，這種固定參數的策略對于規模較小的QAP例子容易過早陷入局部最優解.而對于規模較大的QAP例子由于迭代最優解的權重較輕，算法收斂速度較慢.為此，文獻［13］給出了一種變參數的FANT算法，實驗證明，改進了的算法求解QAP的質量有較大的提高.借鑒文獻［13］的思想，為進一步簡化運算，針對不同規模QAP采用不同的參數R的策略，記為R（n）.因此，改進后的算法信息素更新方式為

綜上所述，可以對FANT算法作如下兩點改進：其一，在FANT算法解的構建步，對每一個設施分配的節點進行預處理，判斷該分配是否改進上一次迭代解的質量，若改善，則分配該節點，否則，保留原迭代解分配的節點；其二，在FANT算法信息素更新步，由式（3）取代式（2）作為算法的信息素更新策略.改進后的FANT算法稱為預處理快速螞蟻系統（PFANT），其算法流程為：

設信息素矩陣為Γ＝（τij）n×n，初始令r（0）＝1，τij＝r（0）（i，j＝1，2，…，n），初始解為φ，迭代最優解為φib，則PFANT重復執行步驟（算法2）為：

步驟1 考查由式（1）分配的每一個節點的能否改進上一次迭代解φ的質量.若改善，則分配該節點；否則，保留原迭代解分配的節點.為方便計構建后的解記為φ；

步驟2 利用局部搜索技術改進當前解φ，仍記為φ；

步驟3 如果Z（φ）＜Z（φib），則φib＝φ，重新設置信息素τij＝r（t）（i，j＝1，2，…，n，t＝1，2，…）；

步驟4 按式（3）的更新方式更新信息素矩陣Γ.

3 數值實驗

這一部分選擇QAPLIB中的例子運行PFANT和FANT算法.實驗的硬件環境為Pentium（R）4 2.5GHz處理器，80GB硬盤，256MB內存，Microsoft Windows SP3操作系統，開發工具為VC＋＋6.0.對于FANT算法，參數R＝6；PFANT算法參數R＝［2n］，其中［］為取整運算，參數r隨著迭代最優解φib的改變在1與2之間不斷地取值.實驗以RTS算法迭代1 000n次所需的時間作為迭代終止條件.實驗采用QAPLIB中的例子按文獻［17］分為4類.第一類，隨機產生無結構問題，這類問題是根據均勻分布隨機產生距離流量矩陣的問題.第二類，隨機產生網格距離問題，這類問題的距離來源于一個網格，節點與節點的距離定義為網格上節點之間的曼哈頓距離.第三類，現實問題，這類問題是從實際問題抽象出來的.第四類，模擬現實問題，因為第三類現實問題規模較小，所以這類問題是根據現實問題的特點隨機產生的較大規模的問題.另外，考慮到規模小于20的問題容易求解，這里只測試規模大于等于20的問題，數值實驗結果見表2.表中給出的結果是超出已知最優解的百分比，最好的結果用斜粗體表示.

表2 PFANT算法的測試結果Tab.2 Testing result of the PFANT algorithm

盡管算法解的質量很大程度依賴所求例子［17］，但從表2仍然不難發現，PFANT算法解的質量較FANT算法有較大幅度的提升，總體上要優于FANT算法，例外的只有Tai 35a，Tai 80a，Tai 50b，Tai 80b.對比RTS算法，在RTS算法求解有較大優勢的隨機產生無結構與網格距離例子中，PFANT算法總體上質量也稍優于RTS算法；至于現實問題及模擬現實問題，PFANT算法全面優于RTS算法，例外的只有Tai 50b，Tai 80b.相對MMAS［8］，ILS［14］，HILS［15］算法在現實問題及模擬現實問題優于RTS算法，在隨機產生無結構及網格距離問題遜于RTS算法而言，PFANT算法求解QAP上有較大提高.

其次，考察FANT與PFANT算法跳出局部最優解時重新設置信息素的次數，表3（見下頁）給出了兩算法求解上述4類問題的結果.從表3明顯可以看出，上述4類問題的每一個例子，PFANT算法重新設置的次數都小于或等于FANT算法.出現這種情況的原因是由于PFANT算法在每次迭代構建問題的解時都預先進行了搜索，剔除了那些質量較劣的解參與局部搜索.在相同的迭代時間內，算法能在局部最優解更廣的鄰域內搜索，增加發現更優的局部最優解的機會，減少了重新設置信息素的次數.

表3 FANT與PFANT算法重新設置信息素的次數Tab.3 The times of resetting pheromone in the FANT and PFANT algorithm

4 結 論

盡管FANT算法在信息素更新管理與解的構建方面較其它蟻群優化算法作了較大的改進，為求解不規則QAP例子最有競爭性的算法之一［9］，但也有明顯的缺點（如算法前期收斂速度較快，后期速度較慢，易發生停滯現象等）.通過分析FANT算法跳出迭代最優解的策略，指出算法易發生停滯現象的原因，并提出了改進的方法，得到一種求解QAP的新算法——預處理快速螞蟻系統（PFANT）.理論與實驗分析表明，PFANT算法較大程度地改進FANT算法的缺點，拓寬了算法迭代最優解鄰域的搜索范圍，減少了重新設置信息素的次數，改善了QAP解的質量.

［1］ Koopmans T C，Berkmann M J.Assignment problems and the location of economic activities［J］.Econometrica，1957，25（1）：53－76.

［2］ Sahni S，Gonzalez T.P－Complete approximation problems［J］.Journal of the Association of Computing Machinery，1976，23（3）：555－565.

［3］ Ahuja R K，Orlin J B，Tiwari A.A greedy genetic algorithm for the quadratic assignment problem［J］.Computers and Operations Research，2000，27（10）：917－934.

［4］ Connolly D T.An improved annealing scheme for the QAP［J］.European Journal of Operational Research，1990，46（1）：93－100.

［5］ Skorin－Kapov J.Tabu search applied to the quadratic assignment problem［J］.ORSA Journal on Computing，1990，2（1）：33－45.

［6］ Taillard E D.Robust taboo search for the quadratic assignment problem［J］.Parallel Computing，1991，17（4／5）：443－455.

［7］ Maniezzo V，Colorni A.The ant system applied to the quadratic assignment problem［J］.IEEE Transactions on Knowledge and Data Engineering，1999，11（5）：769－778.

［8］ Stützle T，Hoos H H.MAX－MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889－914.

［9］ Gambardella L M，Taillard E D，Dorigo M.Ant colonies for the quadratic assignment problem［J］.Journal of the Operational Research Society，1999，50（2）：167－176.

［10］ Taillard E D.FANT：fast ant system.Technical report IDSIA－46－98［R］.Lugano：IDSIA，1998.

［11］ Taillard E D，Gambardella L M.Adaptive memories for the quadratic assignment problems.Technical ReportIDSIA－87－97［R］.Lugano：IDSIA，1997.

［12］ 吳果林，劉登峰.改進的快速蟻群系統求解二次分配問題［J］.桂林航天工業學院學報，2012，17（4）：424－427.

［13］ 吳果林.變參數的快速螞蟻系統求解二次分配問題［J］.科學技術與工程，2013，13（7）：324－328.

［14］ Stützle T.Iterated local search for the quadratic assignment problem［J］.European Journal of Operational Research，2006，174（3）：1519－1539.

［15］ Hussin M S，Stützle T.Hierarchical iterated local search for the quadratic assignment problem［J］.Lecture Notes in Computer Science，2009，5818：115－129.

［16］ 馬良，項培軍.螞蟻算法在組合優化中的應用［J］.管理科學學報，2004，4（2）：32－37.

［17］ Taillard E D.Comparison of iterative searches for the quadratic assignment problem［J］.Location Science，1995，3（2）：87－105.