基于混合化學反應優(yōu)化算法的N皇后問題研究

鄭光勇 徐雨明 羅振庭

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

關(guān)鍵詞：N皇后;混合;化學反應優(yōu)化（CRO）;分子

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

1 N皇后問題描述

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

2 混合化學反應優(yōu)化（CRO）算法思想

2.1 思想描述

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

化學反應中，主要是分子做不規(guī)則的運動，單分子進行運動，在運動過程中進行碰撞，隨后發(fā)生分解。分子間進行碰撞，最終形成新的物質(zhì)?；瘜W反應是將不同的物質(zhì)相互之間發(fā)生變化最終產(chǎn)生一種新的物質(zhì)的過程。化學反應是通過分子的性質(zhì)決定的，分子的勢能變化表示反應的程度，反應勢能減小，反應過程就結(jié)束，當勢能最小時，反應狀態(tài)就趨于穩(wěn)定。

2.2 算法求解過程

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

2.3 與貪心算法融合

貪心算法簡單描述為：在進行計算前，對數(shù)據(jù)進行分析，保證整個解決過程中可以找到最優(yōu)解，對此在進行處理，以找到最優(yōu)值作為目標，不斷重復，直到符合條件的最優(yōu)值出現(xiàn)或問題處理步驟完成?？偟膩碚f，貪心算法就是在解題的每個環(huán)節(jié)中都選擇最優(yōu)的解決辦法，得到最好的結(jié)果。

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

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

3.1 分子編碼

解決N皇后問題，不同的人利用不同的算法，有些算法利用二進制進行計算，有些則采用編碼的形式。下面以N=9為例介紹分子編碼，采用帶沖突統(tǒng)計數(shù)的多值編碼方法，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）是自然數(shù)，表示第i個皇后與其它皇后的沖突數(shù);ci∈{1，2，3，4，5，6，7，8，9}即取值不能相同，它表示第i個皇后在棋盤的第ci行、第i列位置上。

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

3.2 目標函數(shù)

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

3.3 四種化學反應算子

3.3.1 反應的初始化群體

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

3.3.2 分子的碰撞

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

3.3.3 分子的分解

這個化學反應的目的就是讓兩個分子之間發(fā)生碰撞，讓分子的結(jié)構(gòu)發(fā)生變化，產(chǎn)生裂變，從而提供一個新的搜索。

3.3.4 分子之間的碰撞

在發(fā)生碰撞時改變兩個現(xiàn)有分子b3和b4，以產(chǎn)生新分子b5和b6。參照單分子碰撞的過程，分別對向量b3和b4進行單分子碰撞，直到出現(xiàn)較優(yōu)解或測試頂點達到頂點數(shù)的一半為止。

3.4 HCRO算法描述

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

4 模擬實驗結(jié)果及分析

4.1 實驗結(jié)果

程序運行后獲得最優(yōu)解，但由于啟發(fā)式算法具有一定的隨機性，每次運行所需時間都不一樣，因此運行時間取3次的平均值。算法的終止條件為找到最優(yōu)解或者迭代數(shù)達到設(shè)定的值?；屎髷?shù)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 實驗結(jié)果分析

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

5 結(jié)語

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

參考文獻

[1] 王振義.遺傳算法求解N皇后問題的優(yōu)化[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