关键词：局部搜索方法，启示式搜索

1. 局部搜索方法比拟与剖析

局部搜索方法是对一个或多个状态进行评价和修正，而不是系统地从初始状态开始的路径，这些算法适用于关注那些关注解状态而不是路径代价的问题[1]。
本节我们以八数码问题和八皇后问题为例，分别采取爬山法、随机重启爬山法、仿照退火算法和遗传算法进行实验设计，从而比拟各算法的搜索性能。

1.1 实验设计方法

1.1.1 八皇后问题描述

八皇后问题，一个古老而著名的问题，是回溯算法的范例案例。
该问题由国际泰西棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法[2]，描述如图1-1所示。

图1-1 八皇后问题

1.1.2 八数码问题描述

八数码问题是指将分别标有数字1，2，3，4，5，6，7，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上[3]。
放牌时哀求不能重叠。
于是多出来的一个空格。
按照每次只能将与空格相邻的数码牌与空格交流的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。
空格方块在中间位置时有上、下、左、右四个方向可移动，在四个角落上有两个方向可移动，在其他位置上有三个方向可移动，描述如图1-2所示。

图1-2 八数码问题实行过程

1.1.3 爬山法求解八皇后和八数码设计

爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。
如果当前节点是最大的，那么返回当前节点，作为最大值，即山峰最高点；反之就用最高的邻居节点来，更换当前节点，从而实现向山峰的高处攀爬的目的[4]。
如此循环直到达到最高点。
我们采取爬山法分别对八皇后和八数码进行算法设计，个中在爬山法求解八数码的问题中，我们采取曼哈顿间隔作为启示式函数进行打算。
设计流程图见图1-3和图1-4所示。

图1-3 爬山法解八皇后流程图

图1-4 爬山法解八数码流程图

1.1.4 随机重启爬山法求解八皇后和八数码设计

随机重启爬山法的思想是通过随机天生初始状态来导引爬山法搜索，直到找到目标状态[5]。
对付八皇后问题来说是通情达理的，由于八皇后问题目标便是找到终极状态，所有初始状态随机改变是可以许可的。
但是对付八数码问题不合理，由于八数码问题的目标便是给定初始状态，从而找达到到终极状态的路线，初始状态是不能随意改变的，如果利用了随机重启算法，则违反了规则。
因此，此处不采取随机重启法对八数码问题进行设计和求解。
随机重启爬山法算法设计流程图见图1-5所示。

图1-5 随机重启爬山法求解八皇后流程图

1.1.5仿照退火算法求解八皇后和八数码设计

仿照退火实在也是一种贪心算法，但是它的搜索过程引入了随机成分[6]。
在迭代更新可行解时，以一定的概率来接管一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。
由Kirkpatrick等人在1983年提出。
我们采取仿照退火算法分别对八皇后和八数码进行算法设计，设计流程图见图1-6和图1-7所示。

图1-6 仿照退火解八皇后流程图

图1-7 仿照退火解八数码流程图

1.1.6 遗传算法求解八皇后和八数码设计

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它仿照自然选择和自然遗传过程中发生的繁殖、交叉和基因突变征象，在每次迭代中都保留一组候选解，并按指标从解群中选取较优的个体，保留一组候选解，并按指标从解群中选取较优的个体，利用遗传算子对这些个体进行组合，产生新一代的候选解群，重复此过程，直到知足收敛指标[7]。
我们采取遗传算法分别对八皇后和八数码进行算法设计，设计流程图见图1-8和图1-9所示。

图1-8 遗传算法解八皇后流程图

图1-9 遗传算法解八数码流程图

1.1.7 实验设计依据及目的

为了比拟爬山法、随机重启爬山法、仿照退火算法和遗传算法的搜索性能，我们分别以八皇后和八数码为例对各算法进行了实验算法设计，所有算法的详细流程图1-3至图1-9所示。
在八皇后问题中，采取相同个数的测试数据，分别打算每种算法的求解的成功率、失落败率、成功求解的均匀步数、失落败的均匀步数以及每种算法在进行所有测试数据所花费的韶光，然后进行比拟试验，剖析各算法的搜索性能。
同理，在八数码问题求解中，由于随机重启爬山法，当其搜索不到目标状态时，则会重新初始化新的初始状态，而八数码的问题是给定初始状态求解到达目标状态的过程，以是随机重启爬山法不适宜运用于求解八数码的问题，因此，在求解八数码的问题中，我们没有对随机重启爬山法进行实验。
分别采取爬山法、仿照退火算法和遗传算法进行比拟试验。
所设计的比拟参数同八皇后问题中的比拟参数。
统计测试结果，进一步剖析各算法的搜索性能。

我们之以是采取求解成功率、失落败率、成功求解均匀路径长度、失落败的均匀步数以及求解所需的韶光作为各算法的比拟参数。
由于通过这些参数我们可以剖析出各算法的最优性、收敛性和韶光繁芜度等，进而达到剖析各算法综合的搜索性能的实验目的。

1.2 实验数据及实验结果

为了担保实验结果不受外界成分影响，我们利用配置相同的一台电脑，所有算法均采取同一种措辞python，版本为python3.6下，序运行环境为windows 10，所用编译器为PyCharm进行实验。
在八皇后问题中，我们分别随机初始化1000个样本作为实验测试数据，每个样本分别采取爬山法、随机重启爬山法、仿照退火算法和遗传算法进行测试，末了打算出1000个样本在每个算法中成功求解的个数、失落败的个数、成功求解均匀路径长度、失落败的均匀步数以及求解所花费的总韶光。
同理，在八数码问题中，随机初始化1000个初始样本，设定1000个样本的目标状态一样，然后分别采取爬山法、仿照退火算法和遗传算法进行测试。
各算法在八皇后下的测尝尝验结果见表1所示。
个中我们在随机重启算法中我们分别设定不同的随机重启上限次数进行测试，在其它参数相同的情形下，在仿照退火算法中，分别设定不同的退火速率进行实验；在遗传算法中我们设定不同的繁衍代数进行实验，测试参数对实验结果的影响。
同理，各算法在八数码问题下的测尝尝验结果见表2所示。
实验测试代码附件1。

表1 各算法在求解八皇后问题实验结果

表2 各算法在求解八数码问题实验结果

1.3 实验结论

通过1.2节的实验测试，我们可以从表1中明显的看到爬山法在求解八皇后问和八数码问题中求解率都不是很空想，在八皇后问题中成功求解率仅为14.2%，在八数码问题中，成功求解率仅仅占了0.002%，但其求解韶光短。
成功解的均匀步数收敛到4.01，解释爬山法均匀走了更短的路径到达全局最优解。
从表1可得随机重启爬山法比较爬山法的成功率大大提高，当设定随机重启次数上限参数为5，在求解八皇后问题中成功率达到了60.1%，当设定随机重启次数上限参数为50时，求解成功率达到100%，这解释随机重启爬山法的成功率随随机重启次数上限参数的增加而上升。
当重启次数较低时，成功率、解长度、解耗时也相对较低。
随着重启次数增加，成功率也大大上升，当重启次数达到一定值时，随机重启爬山法成功求解率靠近于1，由于只要随机重启的次数上限足够大，那么终极我们能够随机重启天生一个目标状态作为初始状态。
在求解八皇后问题时，我们创造随机重启次数为50时，就可以达到100%的求解率。
但是，其有个不敷之处，随着重启次数增加，相应地，解长度和解耗散也大大增加。
由于随机重启爬山法不适宜求解八数码问题，因此此处不做剖析。
在采取仿照退火算法求解八皇后问题中，当初始温度设定为5，退火速率设定为0.99时，我们创造并不总能成功找到解，成功的概率是77.8%。
比较爬山法，可以明显看出仿照退火算法的成功均匀步数发生了巨大的递增。
反响了爬山法韶光效率很高，这是优点也是缺陷。
同时，我们通过设定不同的退火速率进行比拟试验，可得，在不同的退火速率下，其求解成功率、解长度、解耗时也随之发生变革，退火越缓慢，仿照退火成功求解八皇后问题的概率就越高，但随着成功求解概率的提高，成功均匀步数也明显提高。
仿照退火算法在八数码问题和八皇后问题的表现类似。
都随着初始温度的上升而上升，同时解长度和解花费韶光急剧增大。
从表2中可以看出仿照退火算法的求解成功率远大于爬山法的成功求解率，达到52.1%，但是其所花费的韶光大打折扣。
从上面对比我们可以看出，仿照退火算的效率和其参数有很大的关系，如果参数设置得当，仿照退火算法搜索效率比穷举法要高很多。
在遗传算法求解八皇后问题中，有表1可得在不同的参数情形下其求解的效率不同，所需的韶光也不同，解释它求解问题的快慢与其初始种群有着很大的关系.从表1可以看出，对付同一个问题，由于初始种群不同，相应求解问题所需的代数相差好多倍。
因此可以用启示式算法使其得到一个较好的初始化种群，以加快收敛速率。
通过对各个算法在八皇后和八数码问题的求解中，我们可得，在搜索代价方面， 爬山法移动步数较少，在较短的步数之内就能很快求出解，性能很高，但成功求解率不堪入目。
随机重启爬山法随设定其重启次数增大，成功求解率也随之上升，但韶光本钱随之增大。
仿照退火搜索算法和遗传算法虽然成功率高，但是移动步数却非常多，查找韶光也比较长，代价也因此大了很多。
其次，仿照退火算法和遗传算法易受其参数的影响。

2、启示式搜索方法比拟与剖析

启示式搜索便是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
这样可以省略大量无谓的搜索路径，提高了效率[8]。
本节分别采取曼哈顿间隔和错位棋子数为启示式函数对八数码问题进行实验设计(八数码问题详细描述见1.1.2节)，根据实验结果剖析利用不同的启示式函数，算法在各方面具有不同的性能，并剖析产生这些不同的紧张缘故原由。

2.1 实验设计方法

2.1.1 错位棋子数作为启示式函数办理八数码设计

本节我们采取错位棋子方法作为启示式函数进行实验设计，首先，我们定义估价函数如下：

f(n) =g(n)+w(n) (1)

个中f(n) 是从初始状态经由状态n到目标状态的代价估计，称作估计函数;g(n) 是在状态空间从初始状态到状态n的实际代价，称作节点深度；w(n) 从状态n到目标状态的的估计代价，称作启示函数，此处w(n)指结点n的数据库中错放的棋子个数。

由于我们利用启示式搜索里的A算法进行了实验设计，因此，首先须要验证设计是否知足A算法的条件，判断该设计是否知足A算法须要知足两个条件，第一，我们所设计的估价函数里的w(n)应知足w(n)>w'(n),w'(n)为从当前节点到目标点的实际的最优代价值。
第二，每次扩展的节点的f值大于即是父节点的f值。
从设计的估价函数可以直不雅观得出条件一符合，因此，我们只需证明条件二是否知足。
由于所定义的估价函数中g(n)表示节点的深度，因此每次都会较父节点增加1。
相对付w(n)而言，数字每移动一次，最多使得一个数字回归，或者说不在位减一个。
w(n)最多减小1，g(n)而表示深度，每次会增加1。
以是f(n)=g(n)+w'(n)为非递减，因此，条件二得以证明，即知足A算法的所有条件[9]。
基于A和错位棋子数方法办理八数码问题设计流程图2-1所示：

图2-1 基于错位棋子数法办理八数码问题设计流程图

2.1.2 曼哈顿间隔作为启示式函数办理八数码设计

本节我们采取曼哈顿间隔方法[10]作为启示式函数进行实验设计，首先，我们定义估价函数如下：

f(n)=g(n)+p(n) (2)

个中f(n)是从初始状态经由状态n到目标状态的代价估计，称作估计函数;g(n)是在状态空间从初始状态到状态n的实际代价，称作节点深度；p(n)是从状态n到目标状态的的估计代价，称作启示函数，此处p(n)指将所有数字归位到目标状态须要的最少移动次数总和。

同理我们须要验证其是否知足A算法的两个条件。
此方法将所有数字归位须要的最少移动次数总和。
作为启示函数，第一个条件自然知足。
对付第二个，由于每交流一次，它至多向目标提高1，而g(n)作为深度每次是增加1，因此，g(n)+p(n)至少和原来相等，即第二个条件也知足。
因此A算法可用。
基于A和曼哈顿间隔方法办理八数码问题设计流程图2-2所示。

2.1.3 实验设计依据及目的

为了比拟采取错位棋子数作为启示式函数和采取曼哈顿间隔作为启示式函数对算法的性能造身分歧的影响。
首先我们利用了相同的编程措辞和相同的硬件设备进行实验，在确保这些外在环境对实验不造成影响的情形下，其次我们分别利用两种不同启示式函数，在同一初始状态，同一目标状态下，打算它们在办理八数码问题中所花费的韶光和找到目标状态所移动步数进行比拟试验，以此比拟采取两种不同的启示式函数对算法的性能好坏并进一步剖析造身分歧的影响缘故原由。

2.2 实验数据及实验结果

图2-2 基于曼哈顿间隔办理八数码问题设计流程图

我们随机采取10组不同的初始状态数据，分别采取错位棋子数作为启示式函数和采取曼哈顿间隔作为启示式函数进行比拟实验，10组初始状态数据如下：

初始状态1： {8,2,5,1,0,3,4,7,6}

初始状态2： {3,1,4,0,6,7,5,2,8}

初始状态3： {1,5,7,4,8,2,3,6,0}

初始状态4： {5,3,1,7,4,0,8,2,6}

初始状态5： {5,4,7,8,6,0,2,3,1}

初始状态6： {4,0,8,2,5,1,7,3,6}

初始状态7： {0,2,7,3,8,6,1,4,5}

初始状态8： {5,4,2,7,3,1,6,8,0}

初始状态9： {2,4,8,6,3,1,5,0,7}

初始状态10：{8,2,6,7,3,0,4,1,5}

10组数据的目标状态均为{1,2,3,4,5,6,7,8,0}。
为了避免实验环境的影响，我们采取相同的措辞在一台windows 10，jdk为1.8.0的电脑上进行实验，编码见附件2。
实验结果如表2-1所示，个中difference表示错位棋子数作为启示式函数，manhattan表示哈顿间隔作为启示式函数实验结果。

表2-1 采取错位棋子数和曼哈顿间隔作为启示式函数实验结果

2.3 实验结论

启示式搜索有很多种方法，如局部择优搜索法，最好优先搜索法等等，包括了 A算法，这些算法都利用了启示函数，但在详细的选取最佳搜索节点时的策略不同。
本章节我们分别采取分别采取错位棋子数作为启示式函数和采取曼哈顿间隔作为启示式函数进行设计和比拟实验，从实验结果可得，采取错位棋子数作为启示式函数所花费的韶光远大于采取曼哈顿间隔作为启示式函数，解释启示式函数选择会对算法的性能造成影响，选择得当的启示式函数，能够极大地提高算法的性能。
通过实验结果我们可以得出，利用启示式搜索方法，要懂得构建估价函数，不同的估计函数对实验结果影响很大。
比如该实验，对付我们定义的估价函数f(n)的考虑第一种方法将错位棋子数作为启示式函数，比较每个状态与目标状态比较错位的个数。
这种启示如果其他条件相同，那么错位的牌数最少的状态可能最靠近目标状态。
然而这种启示没有利用从棋盘格局中可以得到的所有信息，由于它没有把牌必要的移动间隔纳入考虑。
并且从实验结果可以明显的看出这种方法所花费的韶光很多，第二种是采取曼哈顿间隔作为启示式函数，对错位的数字必须要移动的间隔求和，为了达到这个目的，每个数字必须要移动的每个方格算为一个间隔单位，这种方法优于第一种。
其次，从实验结果可以看出，两种不同的启示函数也均存在不敷之处，比如当搜索的深度比很大时，第二种方法同样很耗时。
当启示式函数选择不恰当时，算法的性能就会大打折扣。
因此，应该还有很多优化的地方，如迭代加深的A搜索等。

3. 总结

本文以八数码问题和八皇后问题为例，比拟爬山法，随机重启爬山法，仿照退火算法，遗传算法的搜索性能。
以八数码问题为例，分别采取曼哈顿间隔和错位棋子数为启示式函数，设计实验，剖析启示式搜索方法。
如爬山法在求解问题中花费的韶光少，但是随意马虎陷入局部最优解。
随机重启爬山法随重启次数增大，成功求解率上升，但其所花费的韶光本钱也随之增大等。
启示式搜索采取不同的启示式函数时，性能各不相同。

参考文献

[1] 张立毅等著．神经网络盲均衡理论、算法与运用：清华大学出版社，2013.12

[2] Olson, Alton T. The Eight Queens Problem.[J].journal of computers in mathematics & science teaching, 1993, 12(10):93-102.

[3] Lin-Yan O . Searching Algorithms Comparison of the Eight Digital Problem[J].journal of luoyang normal university, 2011.

[4] 汪西原,汪西莉. 启示式搜索策略(爬山法)的改进与实现[J].陕西师大学报:自然科学版(1期):58-58.

[5] 蔡自兴, 徐光祐.人工智能及其运用(第三版)(本科生用书)[M].清华大学出版社,2004.

[6] Dimitris Bertsimas, John Tsitsiklis. Simulated Annealing[C]//1993.

[7] Shaefer, Craig G. Genetic algorithm: Springer New York 1993.

[8] 李俊青. 关于启示式搜索算法的改进策略剖析[J]. 打算机光盘软件与运用, 2012, 000(005):36-36.

[9] 阿凡卢 八数码问题及 A算法. 2012 年

[10] 付宏杰, 王雪莹, 周健,等. 八数码问题解法效率比较及改进研究[J].软件导刊, 2016, 015(009):41-45.

文章对应的实验代码见我的github：

https://github.com/luhongchun/Eight-Numbers_and_Eight-Queens