基于混合化学反应优化算法的N 皇后问题研究

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时,则两皇后在同一斜线上(在两条主对角线上或与主对角线平行),表示有冲突。

3.3 四种化学反应算子

3.3.1 反应的初始化群体

随机选取M个不同的分子作为反应的初始群体(M可大于N的10倍以上)。

3.3.2 分子的碰撞

由于单分子之间结构较小,单分子在进行碰撞时反应的状态变化不大,反应中主要的研究是对势能小范围的搜索,贪心算法单分子碰撞可以改变分子结构。

3.3.3 分子的分解

这个化学反应的目的就是让两个分子之间发生碰撞,让分子的结构发生变化,产生裂变,从而提供一个新的搜索。

表1 CRO与回溯法运行时间对比表(单位：秒)皇后数 8 10 15 25 40 80 180 H C R O 算法 0 0.02 0.024 0.3 1.54 6.15 21.12 回溯法 0 0.47 578.04

3.3.4 分子之间的碰撞

在发生碰撞时改变两个现有分子b3和b4,以产生新分子b5和b6。参照单分子碰撞的过程,分别对向量b3和b4进行单分子碰撞,直到出现较优解或测试顶点达到顶点数的一半为止。

3.4 HCRO算法描述

HCRO算法基本思想：在利用化学反应优化算法可以在分子间进行最优解决方式的搜索,利用贪心算法可以找到最优解,最终提高解题效率。

文章来源：《分子科学学报》 网址: http://www.fzkxxbzz.cn/qikandaodu/2020/1222/470.html