基于化学反应优化 （CRO）求解八皇后问题

郑光勇，徐雨明，余 莹

（衡阳师范学院 计算机科学系，湖南 衡阳 421002）

0 引 言

N皇后问题是一个经典的NP难问题，求解这一问题的算法很多，过去一般用穷举法、回溯法求解，由于其时间复杂度为O（n！）（n为皇后数），所以是一个NP难问题。本文采用的化学反应优化（CRO）方法是解决NP难问题一个较好方法，对它的应用已有较多的研究。文献［1－3］中就提出了用CRO来解决异构环境下任务调度问题。在文献［4－5］中分别提出了用CRO解决0－1背包问题和网络编码优化问题。在文献［6］中还提出了CRO优化感知无线电频谱分配问题。而在文献［7］中从理论上探讨了CRO算法的全局收敛性，并证明收敛性较好。

1 问题描述

八皇后问题是著名的数学家Gauss于1850年提出的，在一个8×8格的国际象棋盘上放置8个皇后，要求皇后不能互相攻击，即任意两个皇后都不处于同一行、同一列或同一斜线方向上（与两个主对角线平行）。问题也可以推广到N个皇后，即N个皇后放置在一个N×N的棋盘上且使得没有两个皇后可以互相攻击［8］。

2 化学反应优化（CRO）元启发式方法

化学反应优化（Chemical Reaction Optimization，CRO），是通过模拟化学反应中分子运动这种自然现象，得到的一种元启发式方法。其通过捕获势能（Potential Energy，PE）较低的分子，得到较优的解决方案。对于一些常见的优化问题，CRO提供了一种全新的解决办法［9］。

化学反应现象都遵循一个规则：每个化学反应系统的最终目标是停止在一个能量最小的状态。即化学反应实际上是一个释放能量的过程，开始，分子运动较为激烈，具有较高的能量，经过一系列的反应后，分子稳定下来，得到能量最低的状态，物质的能量越低，它就更稳定。而优化问题和化学反应之间存在着一定的内在联系。它们都是寻找最小值，并且都是一个阶梯式的演变过程。通过模拟化学反应分子的运动，并寻找能量较低的分子，得到了一种启发式方法。

2.1 分子属性

定义的分子须要有一些属性，基本的有：

（a）分子结构 （b）势能PE

（c）动能KE（kinetic energy）（d）碰撞数Numhit（Number of hits）

（e）MinHit（the minimumhit number）

（f）MinPE（the minimum PE）

2.2 四个基本反应

化学反应过程中，分子间会发生一系列的碰撞。分子通过与分子相撞，或者与容器的壁相撞，不同冲撞程度下会产生不同的基本反应，可以由分子的数量或分子的结构变化大小分类。化学反应由分子的4类基本反应组成：单分子碰撞（Onwall－Collision）、单分子的分解（Decomposition）、分子间的碰撞（IntermolecularCollision）以及分子的合成（Synthesis）。化学反应的最终结果是化学反应产物。化学反应产物形成的变化情况用反应系统的势能变化来表示［10］。整个化学反应过程是势能逐渐减小的过程，反应过程结束，系统势能达到最小，状态趋于稳定。

至于分子发生什么类型的反应，由算法所设定的条件决定。

2.3 算法求解过程

求解过程分为以下三个阶段：

2.3.1 初始化阶段

初始化阶段，需要定义解空间以及一些算法函数，如分解函数、合成函数等，并且为一些变量和控制参数赋值。

在定义了分子结构（即所求问题的解形式）和解空间（所求问题的解的范围）的同时，还要定义相关的函数和参数，并给出初始值，具体如表1所示［11］：

表1 CRO算法的函数和参数

续表

2.3.2 迭代阶段

迭代阶段，执行一定次数的迭代。每次迭代过程中都执行一个基本反应。主要流程如下：

（1）确定反应的类型。确定是单分子还是多分子，根据随机产生的一个 a∈［0，1］，如果a＞MoleColl（分子反应类型的决定因子），则执行单分子反应过程，否则，执行多分子反应过程。当只有一个分子时，执行单分子反应。

（2）根据第（1）步判断的反应类型，随机地从反应群体Pop中选出相应数目的分子。

（3）对于单分子反应，如满足NumHit－ Min－Hit＞α，则执行分解反应，否则执行碰撞反应。

对于多分子反应，如满足KE≤β，则执行合成反应，否则执行分子间碰撞反应。

（4）如果反应停止条件没有满足，则转到（1）。反应停止条件可由使用者根据具体需求确定，如迭代次数达到预先设定的值、执行时间达到最大值等。

2.3.3 最终确认

经过CRO迭代后，输出整个算法最小的PE值以及其对应的分子。

2.4 算法描述

根据上述过程，算法用伪代码描述如下［12］：

3 CRO方法求解八皇后问题算法

3.1 编码

对于八皇后问题，有些算法采用传统的二进制编码，也有些采用多值编码，如定义一个向量a＝（a1，a2，a3，a4，a5，a6，a7，a8），ai∈［0，7］，其中，ai为整数，表示第i个皇后在棋盘的第i列第ai行位置上［12］。为了加快化学反应优化效率，本文采用带冲突统计数的多值编码方法，用一个二维向量表示，如：

定义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个皇后与其它皇后的冲突数；ci∈｛0，1，2，3，4，5，6，7｝且，即取值不能相同，它表示第i个皇在棋盘的第i列，第ci行位置上。该二维向量表示及说明如下：

第三，当前我国处于社会矛盾凸显期，刑事犯罪始终居高不下，而相对于刑事案件高发的现实，侦查人员则数量不足。在侦查实践中，侦查人员手中的案件往往都不止一个，基本上都是多个案件同时开展侦查，加之案件侦查必须在法律规定的诉讼时限内完成，这就形成了侦查决策时的时间压力。

向量元素值 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

向量中各元素的冲突数计算方法：各向量元素a（ci，i）的初始值为0，第0列皇后与第1－7列皇后进行冲突比较，每出现1次冲突，a（c0，0））的值增加1；第1列皇后与第0，2－7列皇后进行冲突比较，每出现1次冲突，a（c1，1））的值增加1；依此类推，计算得到各向量元素的值。

算法伪代码如下：

3.2 解空间及目标函数

根据八皇后问题棋盘格局，每一列有8个位置可以选择。由此看到，八皇后问题的解搜索空间为88。

八皇后问题中皇后不能处于同一行同一列，意味着向量各元素ci的取值不能重复出现。另外，考虑不在同一斜线上的情况，当两个皇后的行数差与列数差比值的绝对值为1的时候，两皇后在同一斜线上（在两条主对角线上或与主对角线平行），表示有冲突，表达式表示如式（1）：

3.3 算子

3.3.1 单分子碰撞

单分子撞墙反应中，分子结构变化非常小，它以一个现有分子a为输入，输出一个新的分子a′这个算子的主要设计目的是在势能面上小范围的细致探索，因此它应该在小范围内改变分子解结构。本研究中，我们通过选择交换向量a中的两个特定元素来产生撞墙后的分子。规则是：把向量a中冲突数最大的和次大的两个元素的行号值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′中各皇后的冲突数，得到新向量的元素值，完成过程。

3.3.2 单分子的分解

这个算子利用现有的分子a来产生两个新的分子a1和a2。具体方法是：随机选取向量a中的一个元素，作为分解点，将a分成两部分，每部分成为2个新分子的固定部分，他们空余的部分元素的行号从现有元素行号集与集合｛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）

第三步：计算各皇后的冲突数，得到2个新向量的元素值，完成分解过程。

3.3.3 分子间的碰撞

在发生碰撞时随机改变两个已有分子a和b以产生新分子a′和b′。由于分子这个反应中，分子结构变化较小，故在本研究中，我们参照单分子无效碰撞随机交换a和b中的两个元素的行号而得到a′和b′，具体过程与单分子碰撞相同。

3.3.4 分子的合成

在这反应中，分子a和b相撞，由于撞击力度较大，合成为一个新的分子x。分子在合成的过程中，新分子x结构与原分子a和b结构相差较大。我们采用随机选择方式合成新分子x。选择参加反应的分子时，选择有元素值为0分子，具体方法如下：

第一步：把分子a中a（ci，i）＝0的元素保留，其它元素行号值cj按向量b中的元素行号顺序选择（若a中某行号已保留，则忽略，继续选择下一行号），得到a′，计算分子a′中各皇后的冲突数，得到新元素值。

第二步；把分子b中b（ci，i）＝0的元素保留，其它元素行号值cj按向量a中的元素行号顺序选择（若b中某行号已保留，则忽略，继续选择下一行号），得到b′，计算分子b′中各皇后的冲突数，得到新元素值。

举例说明如下：

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

设分子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 实验结果与分析

4.1 实验环境

（1）在Visaul studio 2010集成开发环境平台上，采用面向对象的C＃语言实现CRO求解八皇后问题算法。

在CRO中算法的基本单元是分子，同时还有4种基本反应过程，其操作对象为分子。可以通过面向对象的C＃语言定义一个分子类及4种反应过程。分子的定义如下：

4.2 实验结果

程序运行所得结果如下图1：

图1 程序运行结果图

由运行结果图知，运用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皇后问题的较优解。

5 结束语

本文详细介绍了使用元启发式方法——化学反应优化（CRO）算法求解八皇后问题的求解过程，并用C＃语言编程实现。在应用化学反应优化方法过程中，使用碰撞、分解和合成的操作设计方法只是其中一种，还有许多其他的方法可以研究。对于化学反应优化方法应用于求解N皇后问题，其算法性能有待进一步讨论，同时还值得与其它算法进行比较研究，进而挖掘出CRO方法的具大优势。

［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皇后问题的优化［J］.山西大同大学学报：自然科学版，2010，26（2）：13－14.

［9］Lam A，Li V.Chemical－reaction－inspired meta－heuristic for optimization［J］.Evolutionary Computation，IEEE Transactions on，2010，14（3）：381－399.

［10］张智民.基于化学反应优化的网格任务调度研究［D］.长沙：湖南大学，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.