基于混合化學反應優化算法的N皇后問題研究

鄭光勇 徐雨明 羅振庭

摘要：N皇后問題是個經典的NP難問題，有較多的求解方法，本文提出用一種混合化學反應優化算法來求解N皇后問題。

關鍵詞：N皇后;混合;化學反應優化（CRO）;分子

中圖分類號：TP301 文獻標識碼：A 文章編號：1007-9416（2019）09-0116-01

1 N皇后問題描述

N皇后問題是著名的數學家Gauss于1850年提出的，在一個N×N格的國際象棋盤上放置N個皇后，要求皇后不能互相攻擊，即任意兩個皇后都不處于同一行、同一列或同一斜線方向上（與兩個主對角線平行）。

2 混合化學反應優化（CRO）算法思想

2.1 思想描述

對N皇后的問題研究通過模擬一種化學現象來解說一種現象，通過化學反應優化（Chemical Reaction Optimization，CRO）提高人們對一種現象的理解。在此過程中，得到啟發，得到最優的解決方案。

化學反應中，主要是分子做不規則的運動，單分子進行運動，在運動過程中進行碰撞，隨后發生分解。分子間進行碰撞，最終形成新的物質。化學反應是將不同的物質相互之間發生變化最終產生一種新的物質的過程。化學反應是通過分子的性質決定的，分子的勢能變化表示反應的程度，反應勢能減小，反應過程就結束，當勢能最小時，反應狀態就趨于穩定。

2.2 算法求解過程

CRO算法的求解過程分為以下三個階段：（1）初始化階段：定義空間中的分解，利用算法函數進行求解，例如：目標函數，分解函數，合唱函數等。算法的執行設置控制參數，同時設定初步參與反應的分子群體。（2）迭代階段：當算法執行時，通過多次的迭代不斷重復化學反應，每次迭代都是執行一個基本反應。主要步驟是：第一根據隨機產生的參數值確定反應類型;第二是根據反應類型，隨機選取相應數目的分子;第三是根據分子反應情況，如果沒有滿足反應停止的條件，則再轉到第一步。如果達到設定的停止條件（如設定的迭代次數等），則執行后面的程序。

2.3 與貪心算法融合

貪心算法簡單描述為：在進行計算前，對數據進行分析，保證整個解決過程中可以找到最優解，對此在進行處理，以找到最優值作為目標，不斷重復，直到符合條件的最優值出現或問題處理步驟完成。總的來說，貪心算法就是在解題的每個環節中都選擇最優的解決辦法，得到最好的結果。

3 混合化學反應優化（HCRO）算法求解N皇后問題

本算法是結合貪心算法與化學反應優化算法的優勢，以加快最優解的搜索速度，而形成的一種混合化學反應優化算法（HCRO）。

3.1 分子編碼

解決N皇后問題，不同的人利用不同的算法，有些算法利用二進制進行計算，有些則采用編碼的形式。下面以N=9為例介紹分子編碼，采用帶沖突統計數的多值編碼方法，N皇后問題分子用一個二維向量b表示：定義b=[b（c1，1），b（c2，2），b（c3，3），b（c4，4），b（c5，5）， b（c6，6），b（c7，7），b（c8，8），b（c9，9）]，其中b（ci，i）是自然數，表示第i個皇后與其它皇后的沖突數;ci∈{1，2，3，4，5，6，7，8，9}即取值不能相同，它表示第i個皇后在棋盤的第ci行、第i列位置上。

各元素沖突數計算方法：各向量元素b（ci，i）的初始值為0，第1列皇后與第2-9列皇后進行沖突比較，每出現1次沖突，b（c1，1）的值增加1;第2列皇后與第1，3-9列皇后進行沖突比較，每出現1次沖突，b（c2，2）的值增加1;依此類推，計算得到各向量元素的值。

3.2 目標函數

N皇后問題中對皇后的位置有明確的規定，由此就需要讓每個元素不可以重復出現。當皇后不在同一斜線上時，兩個皇后之間的行數差與列數差比值的絕對值為1時（|（cj-ci）/（j-i）|=1），則兩皇后在同一斜線上（在兩條主對角線上或與主對角線平行），表示有沖突。

3.3 四種化學反應算子

3.3.1 反應的初始化群體

隨機選取M個不同的分子作為反應的初始群體（M可大于N的10倍以上）。

3.3.2 分子的碰撞

由于單分子之間結構較小，單分子在進行碰撞時反應的狀態變化不大，反應中主要的研究是對勢能小范圍的搜索，貪心算法單分子碰撞可以改變分子結構。

3.3.3 分子的分解

這個化學反應的目的就是讓兩個分子之間發生碰撞，讓分子的結構發生變化，產生裂變，從而提供一個新的搜索。

3.3.4 分子之間的碰撞

在發生碰撞時改變兩個現有分子b3和b4，以產生新分子b5和b6。參照單分子碰撞的過程，分別對向量b3和b4進行單分子碰撞，直到出現較優解或測試頂點達到頂點數的一半為止。

3.4 HCRO算法描述

HCRO算法基本思想：在利用化學反應優化算法可以在分子間進行最優解決方式的搜索，利用貪心算法可以找到最優解，最終提高解題效率。

4 模擬實驗結果及分析

4.1 實驗結果

程序運行后獲得最優解，但由于啟發式算法具有一定的隨機性，每次運行所需時間都不一樣，因此運行時間取3次的平均值。算法的終止條件為找到最優解或者迭代數達到設定的值。皇后數N=9時程序運行所得問題的一個解為a=[（1，1），（4，2），（6，3），（8，4），（2，5），（5，6），（3，7），（0，8），（7，9），（8，9）]。

4.2 實驗結果分析

本算法與回溯法的求解運行時間對比如表1所示。

5 結語

本文闡述了使用混合化學反應優化（HCRO）算法求解N皇后問題的基本思想與過程，用C#語言編程實現，并取得了較好的模擬實驗效果。在應用混合化學反應優化算法時，實驗結果也許因為參與反應的分子群不一樣，結果會略有不同，但總體來說，對于求解N皇后問題有所改善。

參考文獻

[1] 王振義.遺傳算法求解N皇后問題的優化[J].山西大同大學學報：自然科學版，2010，26（2）：13-14.

[2] Lam A，Li V. Chemical-reaction-inspired meta-heuristic for optimization[J]. Evolutionary Computation，IEEE Transactions on，2010，14（3）：381-399.

Abstract：The N queen problem is a classic NP hard problem， and there are many solving methods. This paper proposes a hybrid chemical reaction optimization algorithm to solve the N queen problem.

Key words：N queen; mixing; chemical reaction optimization （CRO）; molecule