鄭光勇，徐雨明，余 瑩

（衡陽師范學(xué)院 計算機科學(xué)系，湖南 衡陽 421002）

0 引 言

N皇后問題是一個經(jīng)典的NP難問題，求解這一問題的算法很多，過去一般用窮舉法、回溯法求解，由于其時間復(fù)雜度為O（n！）（n為皇后數(shù)），所以是一個NP難問題。本文采用的化學(xué)反應(yīng)優(yōu)化（CRO）方法是解決NP難問題一個較好方法，對它的應(yīng)用已有較多的研究。文獻［1－3］中就提出了用CRO來解決異構(gòu)環(huán)境下任務(wù)調(diào)度問題。在文獻［4－5］中分別提出了用CRO解決0－1背包問題和網(wǎng)絡(luò)編碼優(yōu)化問題。在文獻［6］中還提出了CRO優(yōu)化感知無線電頻譜分配問題。而在文獻［7］中從理論上探討了CRO算法的全局收斂性，并證明收斂性較好。

1 問題描述

八皇后問題是著名的數(shù)學(xué)家Gauss于1850年提出的，在一個8×8格的國際象棋盤上放置8個皇后，要求皇后不能互相攻擊，即任意兩個皇后都不處于同一行、同一列或同一斜線方向上（與兩個主對角線平行）。問題也可以推廣到N個皇后，即N個皇后放置在一個N×N的棋盤上且使得沒有兩個皇后可以互相攻擊［8］。

2 化學(xué)反應(yīng)優(yōu)化（CRO）元啟發(fā)式方法

化學(xué)反應(yīng)優(yōu)化（Chemical Reaction Optimization，CRO），是通過模擬化學(xué)反應(yīng)中分子運動這種自然現(xiàn)象，得到的一種元啟發(fā)式方法。其通過捕獲勢能（Potential Energy，PE）較低的分子，得到較優(yōu)的解決方案。對于一些常見的優(yōu)化問題，CRO提供了一種全新的解決辦法［9］。

化學(xué)反應(yīng)現(xiàn)象都遵循一個規(guī)則：每個化學(xué)反應(yīng)系統(tǒng)的最終目標是停止在一個能量最小的狀態(tài)。即化學(xué)反應(yīng)實際上是一個釋放能量的過程，開始，分子運動較為激烈，具有較高的能量，經(jīng)過一系列的反應(yīng)后，分子穩(wěn)定下來，得到能量最低的狀態(tài)，物質(zhì)的能量越低，它就更穩(wěn)定。而優(yōu)化問題和化學(xué)反應(yīng)之間存在著一定的內(nèi)在聯(lián)系。它們都是尋找最小值，并且都是一個階梯式的演變過程。通過模擬化學(xué)反應(yīng)分子的運動，并尋找能量較低的分子，得到了一種啟發(fā)式方法。

2.1 分子屬性

定義的分子須要有一些屬性，基本的有：

（a）分子結(jié)構(gòu) （b）勢能PE

（c）動能KE（kinetic energy）（d）碰撞數(shù)Numhit（Number of hits）

（e）MinHit（the minimumhit number）

（f）MinPE（the minimum PE）

2.2 四個基本反應(yīng)

化學(xué)反應(yīng)過程中，分子間會發(fā)生一系列的碰撞。分子通過與分子相撞，或者與容器的壁相撞，不同沖撞程度下會產(chǎn)生不同的基本反應(yīng)，可以由分子的數(shù)量或分子的結(jié)構(gòu)變化大小分類?；瘜W(xué)反應(yīng)由分子的4類基本反應(yīng)組成：單分子碰撞（Onwall－Collision）、單分子的分解（Decomposition）、分子間的碰撞（IntermolecularCollision）以及分子的合成（Synthesis）?；瘜W(xué)反應(yīng)的最終結(jié)果是化學(xué)反應(yīng)產(chǎn)物?；瘜W(xué)反應(yīng)產(chǎn)物形成的變化情況用反應(yīng)系統(tǒng)的勢能變化來表示［10］。整個化學(xué)反應(yīng)過程是勢能逐漸減小的過程，反應(yīng)過程結(jié)束，系統(tǒng)勢能達到最小，狀態(tài)趨于穩(wěn)定。

至于分子發(fā)生什么類型的反應(yīng)，由算法所設(shè)定的條件決定。

2.3 算法求解過程

求解過程分為以下三個階段：

2.3.1 初始化階段

初始化階段，需要定義解空間以及一些算法函數(shù)，如分解函數(shù)、合成函數(shù)等，并且為一些變量和控制參數(shù)賦值。

在定義了分子結(jié)構(gòu)（即所求問題的解形式）和解空間（所求問題的解的范圍）的同時，還要定義相關(guān)的函數(shù)和參數(shù)，并給出初始值，具體如表1所示［11］：

表1 CRO算法的函數(shù)和參數(shù)

續(xù)表

2.3.2 迭代階段

迭代階段，執(zhí)行一定次數(shù)的迭代。每次迭代過程中都執(zhí)行一個基本反應(yīng)。主要流程如下：

（1）確定反應(yīng)的類型。確定是單分子還是多分子，根據(jù)隨機產(chǎn)生的一個 a∈［0，1］，如果a＞MoleColl（分子反應(yīng)類型的決定因子），則執(zhí)行單分子反應(yīng)過程，否則，執(zhí)行多分子反應(yīng)過程。當只有一個分子時，執(zhí)行單分子反應(yīng)。

（2）根據(jù)第（1）步判斷的反應(yīng)類型，隨機地從反應(yīng)群體Pop中選出相應(yīng)數(shù)目的分子。

（3）對于單分子反應(yīng)，如滿足NumHit－ Min－Hit＞α，則執(zhí)行分解反應(yīng)，否則執(zhí)行碰撞反應(yīng)。

對于多分子反應(yīng)，如滿足KE≤β，則執(zhí)行合成反應(yīng)，否則執(zhí)行分子間碰撞反應(yīng)。

（4）如果反應(yīng)停止條件沒有滿足，則轉(zhuǎn)到（1）。反應(yīng)停止條件可由使用者根據(jù)具體需求確定，如迭代次數(shù)達到預(yù)先設(shè)定的值、執(zhí)行時間達到最大值等。

2.3.3 最終確認

經(jīng)過CRO迭代后，輸出整個算法最小的PE值以及其對應(yīng)的分子。

2.4 算法描述

根據(jù)上述過程，算法用偽代碼描述如下［12］：

3 CRO方法求解八皇后問題算法

3.1 編碼

對于八皇后問題，有些算法采用傳統(tǒng)的二進制編碼，也有些采用多值編碼，如定義一個向量a＝（a1，a2，a3，a4，a5，a6，a7，a8），ai∈［0，7］，其中，ai為整數(shù)，表示第i個皇后在棋盤的第i列第ai行位置上［12］。為了加快化學(xué)反應(yīng)優(yōu)化效率，本文采用帶沖突統(tǒng)計數(shù)的多值編碼方法，用一個二維向量表示，如：

定義a＝［a（c0，0），a（c1，1），a（c2，2），a（c3，3），a（c4，4），a（c5，5），a（c6，6），a（c7，7）］，其中a（ci，i）∈N，表示第i個皇后與其它皇后的沖突數(shù)；ci∈｛0，1，2，3，4，5，6，7｝且，即取值不能相同，它表示第i個皇在棋盤的第i列，第ci行位置上。該二維向量表示及說明如下：

第三，當前我國處于社會矛盾凸顯期，刑事犯罪始終居高不下，而相對于刑事案件高發(fā)的現(xiàn)實，偵查人員則數(shù)量不足。在偵查實踐中，偵查人員手中的案件往往都不止一個，基本上都是多個案件同時開展偵查，加之案件偵查必須在法律規(guī)定的訴訟時限內(nèi)完成，這就形成了偵查決策時的時間壓力。

向量元素值 a（c0，0）a（c1，1）a（c2，2）a（c3，3）a（c4，4）a（c5，5）a（c6，6）a（c7，7）棋盤行 c0 c1 c2 c3 c4 c5 c6 c 7棋盤列0 1 2 3 4 5 6 7

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

算法偽代碼如下：

3.2 解空間及目標函數(shù)

根據(jù)八皇后問題棋盤格局，每一列有8個位置可以選擇。由此看到，八皇后問題的解搜索空間為88。

八皇后問題中皇后不能處于同一行同一列，意味著向量各元素ci的取值不能重復(fù)出現(xiàn)。另外，考慮不在同一斜線上的情況，當兩個皇后的行數(shù)差與列數(shù)差比值的絕對值為1的時候，兩皇后在同一斜線上（在兩條主對角線上或與主對角線平行），表示有沖突，表達式表示如式（1）：

3.3 算子

3.3.1 單分子碰撞

單分子撞墻反應(yīng)中，分子結(jié)構(gòu)變化非常小，它以一個現(xiàn)有分子a為輸入，輸出一個新的分子a′這個算子的主要設(shè)計目的是在勢能面上小范圍的細致探索，因此它應(yīng)該在小范圍內(nèi)改變分子解結(jié)構(gòu)。本研究中，我們通過選擇交換向量a中的兩個特定元素來產(chǎn)生撞墻后的分子。規(guī)則是：把向量a中沖突數(shù)最大的和次大的兩個元素的行號值ci?cj進行交換，如下所示：

a（c0，0）a（c1，1）a（c2，2）a（c3，3）a（c4，4）a（c5，5）a（c6，6）a（c7，7）

碰撞后的分子a′：

a（c0，0）a（c1，1）a（c5，2）a（c3，3）a（c4，4）a（c2，5）a（c6，6）a（c7，7）

重新計算向量a′中各皇后的沖突數(shù)，得到新向量的元素值，完成過程。

3.3.2 單分子的分解

這個算子利用現(xiàn)有的分子a來產(chǎn)生兩個新的分子a1和a2。具體方法是：隨機選取向量a中的一個元素，作為分解點，將a分成兩部分，每部分成為2個新分子的固定部分，他們空余的部分元素的行號從現(xiàn)有元素行號集與集合｛0，1，2，3，4，5，6，7｝的差集中隨機選取不同的值填上。過程如下所示：

第一步：隨機分解

第二步：空余部分分別隨機選取不同行號，得到：

分子a1：

a（2，0）a（1，1）a（5，2）a（7，3）a（6，4）a（4，5）a（0，6）a（3，7）

分子a2：

a（1，0）a（5，1）a（2，2）a（4，3）a（3，4）a（7，5）a（6，6）a（0，7）

第三步：計算各皇后的沖突數(shù)，得到2個新向量的元素值，完成分解過程。

3.3.3 分子間的碰撞

在發(fā)生碰撞時隨機改變兩個已有分子a和b以產(chǎn)生新分子a′和b′。由于分子這個反應(yīng)中，分子結(jié)構(gòu)變化較小，故在本研究中，我們參照單分子無效碰撞隨機交換a和b中的兩個元素的行號而得到a′和b′，具體過程與單分子碰撞相同。

3.3.4 分子的合成

在這反應(yīng)中，分子a和b相撞，由于撞擊力度較大，合成為一個新的分子x。分子在合成的過程中，新分子x結(jié)構(gòu)與原分子a和b結(jié)構(gòu)相差較大。我們采用隨機選擇方式合成新分子x。選擇參加反應(yīng)的分子時，選擇有元素值為0分子，具體方法如下：

第一步：把分子a中a（ci，i）＝0的元素保留，其它元素行號值cj按向量b中的元素行號順序選擇（若a中某行號已保留，則忽略，繼續(xù)選擇下一行號），得到a′，計算分子a′中各皇后的沖突數(shù)，得到新元素值。

第二步；把分子b中b（ci，i）＝0的元素保留，其它元素行號值cj按向量a中的元素行號順序選擇（若b中某行號已保留，則忽略，繼續(xù)選擇下一行號），得到b′，計算分子b′中各皇后的沖突數(shù)，得到新元素值。

舉例說明如下：

設(shè)分子a為：

元素 a（6，0）＝0 a（2，1）a（3，2）a（7，3）a（0，4）a（4，5）a（1，6）a（5，7）＝1＝1＝0＝0＝1＝0＝0

設(shè)分子b為：

元素 b（5，0）＝0 b（3，1）b（4，2）b（6，3）b（0，4）b（2，5）b（1，6）b（7，7）＝2＝1＝0＝1＝1＝1＝0

第一步：分子a和b合成，得到a′過程如下：

第二步：分子a和b合成，得到b′過程如下：

第三步：計算f（a′）＝9，f（b′）＝6，故取x＝b′。

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

（1）在Visaul studio 2010集成開發(fā)環(huán)境平臺上，采用面向?qū)ο蟮腃＃語言實現(xiàn)CRO求解八皇后問題算法。

在CRO中算法的基本單元是分子，同時還有4種基本反應(yīng)過程，其操作對象為分子?？梢酝ㄟ^面向?qū)ο蟮腃＃語言定義一個分子類及4種反應(yīng)過程。分子的定義如下：

4.2 實驗結(jié)果

程序運行所得結(jié)果如下圖1：

圖1 程序運行結(jié)果圖

由運行結(jié)果圖知，運用CRO方法當MinPE＝0時獲得八皇后問題的一個解a為：

（5，0）（2，1）（4，2）（7，3）（0，4）（3，5）（1，6）（6，7）

其中，（i，j）表示棋盤上皇后的行標i和列標j。如果改進算法，可以得到N皇后問題的較優(yōu)解。

5 結(jié)束語

本文詳細介紹了使用元啟發(fā)式方法——化學(xué)反應(yīng)優(yōu)化（CRO）算法求解八皇后問題的求解過程，并用C＃語言編程實現(xiàn)。在應(yīng)用化學(xué)反應(yīng)優(yōu)化方法過程中，使用碰撞、分解和合成的操作設(shè)計方法只是其中一種，還有許多其他的方法可以研究。對于化學(xué)反應(yīng)優(yōu)化方法應(yīng)用于求解N皇后問題，其算法性能有待進一步討論，同時還值得與其它算法進行比較研究，進而挖掘出CRO方法的具大優(yōu)勢。

［1］Kenli Li，Zhimin Zhang，Yuming Xu，et，al.Chemical Reaction Optimization for Heterogeneous Computing Environments［C］.Parallel and Distributed Processing with Applications （ISPA），2012IEEE 10th International Symposium，2012.

［2］Yuming Xu，Kenli Li，Ligang He，et，al.Scheduling scheme on heterogeneous computing systems using double molecular structure：based chemical reaction optimization［J］.Journal of Parallel and Distributed Computing，2013，73（9）：1306－1322.

［3］Jin Xu，Lam，A.Y.S.，Li，V.O.K.Chemical reaction optimization for task scheduling in grid computing［J］.Parallel and Distributed Systems，IEEE Transactions on，2011，22（10）：1624－1631.

［4］Tung Khac Truong，Kenli Li，Yuming Xu.Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem ［J］.Applied Soft Computing，2013，13（4）：1774－1780.

［5］Bo Pan，Lam，A.Y.S.，Li，V.O.－K..Network coding optimization based on chemical reaction optimization［C］.Global Telecommunications Conference（GLOBECOM 2011），2011IEEE.

［6］Lam，Albert Y.S.，Li，Victor O.K.，Yu，James J.Q.，Power－Controlled Cognitive Radio Spectrum Allocation with Chemical Reaction Optimization［J］.Wireless Communications，IEEE Transactions on.2013，12（7）：3180－3190.

［7］Lam，A.；Li，V.；Xu，J.，On the Convergence of Chemical Reaction Optimization for Combinatorial Optimization［J］.Evolutionary Computation，IEEE Transactions on，2003，7（9）：1－10.

［8］王振義.遺傳算法求解N皇后問題的優(yōu)化［J］.山西大同大學(xué)學(xué)報：自然科學(xué)版，2010，26（2）：13－14.

［9］Lam A，Li V.Chemical－reaction－inspired meta－h(huán)euristic for optimization［J］.Evolutionary Computation，IEEE Transactions on，2010，14（3）：381－399.

［10］張智民.基于化學(xué)反應(yīng)優(yōu)化的網(wǎng)格任務(wù)調(diào)度研究［D］.長沙：湖南大學(xué)，2012.5.

［11］Albert Y.S.Lam· Victor O.K.Li.Chemical Reaction Optimization：a tutorial［J］.Memetic Computing，2012，4（1）：3－17.

［12］Lam，A.Y.S.，Li，V.O.－K.，Yu，J.J.Q.，Real－Coded Chemical Reaction Optimization［J］.Evolutionary Computation，IEEE Transactions on，2012，16（3）：339－353.