基于化學(xué)反應(yīng)優(yōu)化 （CRO）求解八皇后問題

鄭光勇，徐雨明，余 瑩

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

0 引 言

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

1 問題描述

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

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

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

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

2.1 分子屬性

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

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

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

（e）MinHit（the minimumhit number）

（f）MinPE（the minimum PE）

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

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

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

2.3 算法求解過程

求解過程分為以下三個(gè)階段：

2.3.1 初始化階段

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

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

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

續(xù)表

2.3.2 迭代階段

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

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

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

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

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

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

2.3.3 最終確認(rèn)

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

2.4 算法描述

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

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

3.1 編碼

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

定義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個(gè)皇后與其它皇后的沖突數(shù)；ci∈｛0，1，2，3，4，5，6，7｝且，即取值不能相同，它表示第i個(gè)皇在棋盤的第i列，第ci行位置上。該二維向量表示及說明如下：

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

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

算法偽代碼如下：

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

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

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

3.3 算子

3.3.1 單分子碰撞

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

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）

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

3.3.2 單分子的分解

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

第一步：隨機(jī)分解

第二步：空余部分分別隨機(jī)選取不同行號(hào)，得到：

分子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）

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

3.3.3 分子間的碰撞

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

3.3.4 分子的合成

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

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

第二步；把分子b中b（ci，i）＝0的元素保留，其它元素行號(hào)值cj按向量a中的元素行號(hào)順序選擇（若b中某行號(hào)已保留，則忽略，繼續(xù)選擇下一行號(hào)），得到b′，計(jì)算分子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′過程如下：

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

由運(yùn)行結(jié)果圖知，運(yùn)用CRO方法當(dāng)MinPE＝0時(shí)獲得八皇后問題的一個(gè)解a為：

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

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

5 結(jié)束語

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

［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é)報(bào)：自然科學(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.