遗传chu-beasley算法在解决棋马旅行中的应用

国际象棋骑马之旅是一个已经由国际象棋玩家和数学家研究了数百年的问题。提出了具有特征性跳跃的马的路线，以使其覆盖板上的所有方格（64个方格，8×8），每个方格仅接触一次。

关于此问题的第一笔数据是在840年的阿拉伯手稿中找到的（Murray，1913年），其中详细列出了两条路线。第一次数学分析是由莱昂哈德·欧拉（Leonhard Euler）在柏林（1759年）提出的，处理该问题的其他知名数学家是泰勒（Taylor），德·莫夫（de Moivre）和拉格朗日（Lagrange）。

骑士之旅

接近我们的时代，McKay和Mordecki使用功能强大的大型机在8×8板上寻找最可能的路线。麦凯计算了闭合路线的总数（当马完成赛道时，下一跳将他带到起跑区）

13,267,364,410,532，而Mordecki发现

1,305×10 ^35条开放路线。

至于搜索系统，它们的范围包括纯粹的启发式系统（Warnsdorff 1823），深度优先搜索/回溯，神经网络，遗传算法，蚁群算法等。

为了解决这项工作，我们采用了一种基于

朱比斯利

遗传算法

遗传算法（AG）是用于解决搜索和优化问题的方法。它们基于自然选择的种群，并遵循自然选择和适者生存的原则，查尔斯·达尔文（Charles Darwin，1859年）提出了这一原则。

通过模仿这些自适应过程，AG能够为现实生活中的问题生成解决方案。通过适当地编码初始GA种群并正确实施进化方法，可以获得最佳解决方案。

遗传算法的基本原理是由荷兰在1975年确立的，但是该技术直到1980年代中期才流行起来，特别是通过戈德堡（1989）的工作。

在自然界中，个人争夺生存资源以及繁殖。那些拥有最佳生存条件并吸引其伴侣的人是最有机会产生后代的人。相反，天赋最小的人几乎没有繁殖的机会。适应能力最强的孩子的子女继承了遗传，这些孩子从父母那里获得了最佳基因的组合，因此得以进化，从而实现了对他们所处环境的更大适应。

股份公司的工作方式类似于自然系统。他们有很多个人，每个人都是解决特定问题的潜在方法。这些人中的每个人将具有与他们距离实现这一解决方案有多远或多远相关的才能或适应价值。

与自然相似，这些人将能够杂交并产生后代，这些后代将得到他们最好的祖先，因此，随着世代的流逝，他们将朝着解决该问题的最佳方式收敛。

典型的GA采用简化的选择，交叉，变异和优胜劣汰的概念，因此即使对解决问题的方法了解得很少，您也可以找到解决方案。

在针对特定解决方案存在特定技术的领域中，它们始终会比AG更好地工作。使用这些算法的想法是在没有定界解决方案的情况下搜索字段，或者如果存在该解决方案，则可以通过将其与AG结合使用加以改进。

AG被广泛应用于各个领域，例如：数值和组合优化，机器学习，自动编程，经济学，免疫系统，生态学，进化与学习，社会系统等。

遗传算法的结构和功能

一个简单的AG（类似于Holland创建的AG，也是最常用的AG之一）由一群个体组成，也称为染色体。每个染色体代表对提出的问题的可能解决方案，并且由一系列值组成，这些值可以是{0,1}，整数，实数等。这些值与构成染色体的每个基因相对应。可能的图形表示如下：

AG还拥有遗传操作员，他们负责选择，杂交和突变过程。由于这三个运营商是最常见和最基本的运营商，因此一些专门的AG合并了可行性改进，最优性改进等运营商。

Chu-Beasley遗传算法

如上所述，Chu-Beasley GA用于这项工作。简单AG的最重要区别是：

种群中不能有相等的染色体。在简单的GA中，每一代都将替换全部或几乎全部人口。在朱比斯利（Chu-Beasley），只有一个人被替换，只要新人具有所需的多样性，可行性等特征即可。它合并了一个优化性改进运算符。

遗传算法对国际象棋马问题的适应

根据其所在的广场，马匹可以有2到8个合法动作，可以用各种方式编码。在这项工作中，解决了整数编码问题：

因此，可以用类似于以下内容的整数条表示部分跑动：

4-6-0-0-2-4…

如果我们以e4（板的中心）为起点，并以代数表示法表示该路径，则将有：

（e4）-f6-h5-g3-f1-d2-e4

请注意，最后一步将我们带到先前访问的空间（e4），这条路线是非法的。因此，可以说这条路线的有效长度为五跳。跳数就是我们所说的个人健身功能。对于此问题，合法的63次跳跃的适应度函数是有效的解决方案。回到与自然的相似性，一个个体或一条染色体或多或少地取决于其适应功能的数目是多还是少。智能功能越大，您就越能解决问题：完成马在棋盘周围的旅程。

遗传算法的实现

决定创建一个由64个个体或染色体组成的初始种群（随后的测试确认这是最合适的数目）。这些染色体上的每个基因均以0到7之间的随机数完成。是从x平方的跳跃并没有使这匹马脱离董事会。

创建初始种群后，一个周期或世代开始，可以简化如下：

祖细胞的选择祖细胞的杂交和子代的产生

选择父母

有几种方法可以选择将生成种群后代的父母。最常用的是：

精英轮盘或蒙特卡洛锦标赛排名

在这项工作中，对Torneo，Elitista和Montecarlo的选择进行了试验，后者是产生最佳结果的选择，稍后将看到。

比赛选择

从种群中随机选择两对候选祖细胞（染色体）。从每对中选择具有最佳适应性功能的染色体，并从所选择的两个中产生杂交。

精英选择

最好的两条染色体总是从种群中提取的，并且它们之间发生杂交以产生孩子。

蒙特卡洛或轮盘赌选择

用这种方法，一个人必须繁殖的概率与他的才能和他的竞争者之间的差异成正比。这可以表示为轮盘游戏，其中每个人都获得轮盘的一部分或一部分，但适者获得的部分大于最不适合的部分。然后旋转轮盘（随机选择一个数字），每次选择具有轮盘停止位置的个人。

通过执行轮盘两次，选择了两个要交配的父母。

父母穿越

两条选定的染色体发生了基因交换，其中将产生两个孩子。这些孩子中只有最适者才能进入人群。

正如有多种选择方法一样，交叉也会发生这种情况。在这项工作中，测试了一个点和两个点的交叉操作员，从而使交叉点最成功。其实现如下：

一旦选择了两个亲本，它们的染色体就会在一个随机选择的点被切割。这样，每个染色体中会产生两个不同的片段：头和尾。然后，在每个人之间交换尾巴的基因，这样就创建了两个继承父母双方特征的孩子。最后，只有具有最佳才能功能的孩子才有可能进入人群。

儿子的变异

儿子的突变导致他的某些基因（通常只有一个）随机改变其值。这样，自然发生的行为就被模仿了，因为当产生后代时，通常在遗传负荷从父母传给孩子时会发生某种类型的错误，通常没有重大意义。通常，突变的可能性非常低，小于1％。但是，这项工作中的测试结果更好，突变率接近85％。

最常用的遗传突变算子是染色体的两个基因的随机替换和交换。

在目前的工作中，有可能将两个算子中的任何一个应用于突变。

改善儿童适应能力

这一点在AG中比其他重要。由几位作者（以及目前的工作）使用简单的GA进行的测试未能为国际象棋马寻找有效的路线。为了改善AG的功能，已采用了各种方法来部分专门化该过程。惠特利（1994）探索了这种适应性的想法

Gordon和Slocum（2004）介绍了修复技术，下面将对此进行说明。另一个专业是Al-Gharaibeh，Qqwagneh和Al-zahawi（2007），他们通过启发式方法提高了后代的适应能力。

Gordon和Slocum的想法如下：对于种群中的每个染色体，在跳跃无效的点（即，将马从板上移开或移至先前访问的广场）将进行修复。将检查此举动，并尝试用允许行程继续的另一有效举动替换它。如果没有有效的跳跃，则终止对该染色体的评估。如果存在有效的跳转，则无效的基因会被该跳转修改，然后传递到右边的基因。持续进行直到没有任何跳跃的正方形重新出现或达到马的路径的解。与其他技术一样，没有应用启发式或回溯。

在上述示例中，当马跳回到方框e4时，对染色体的评估结束了。也就是说，基因链：

4-6-0-0-2-4…

（e4）-f6-h5-g3-f1-d2-e4，其中最后一个值（4）无效。

修复过程试图为该基因找到正确的值，比如说值7，这会使我们无所适从。然后我们搜索另一个值，例如3，它将带我们到c4，这是一个尚未访问的框。然后基因链将被留下

4-6-0-02-3…

（e4）-f6-h5-g3-f1-d2-c4

我们将以同样的方式处理链右边的下一个基因。

当前工作与Gordon和Slocum的工作之间的区别在于，他们对整个人口适用赔偿，而在我们的Chu-Beasley AG中，我们仅处理新创建的儿子。

将儿子纳入人口

一旦获得并改善了孩子，就可以计算出他的能力函数，即他的基因链具有多少个有效跳跃。将此功能与当前人口的每个成员进行比较。如果适应功能比人口中最差的那个人好，则此人将被淘汰，并由当前孩子代替。始终尊重多样性：孩子不等于人口中的任何成员。

如果种群中已经存在与当前子代具有相同基因的染色体，或者如果这个子代比最差的个体更好，则将其丢弃，并假定这一代没有后代。

获得的结果

对于这项工作，C#语言与A-Forge.Net框架一起使用，A-Forge.Net框架是一款出色的免费开放源代码产品，面向人工智能，可加快开发速度。

我们尝试执行类似于先前调查的测试过程，但是由于Chu-Beasley是不同的AG，因此无法使用相同的参数。最后，创建了64条染色体的初始种群，并为板上的每个正方形进行了1,000,000代的遗传。对每个方框重复此过程五次，以获得与其他建议相当的平均值。结果可以在下表中看到：

三种选择方法允许至少一次找到第一代旅行。这要归功于修复机制。

值得注意的是，尽管Gordon和Slocum的AG在一个单独的正方形中发现了最高的运行次数（642对529），但我们的AG却认为板上几乎每个正方形的平均值都更高。

另一方面，没有测试给出否定的结果，也就是说，GA总是在每个测试中都找到有效的路由。

五个测试的旅行平均值。

参考文献：

Murray HJR（1913）国际象棋BD McKay的历史，“骑士的8×8棋盘之旅”，博士学位。学位，澳大利亚国立大学计算机科学系，1997年。Mordecki，“论骑士之旅的次数”，载于2001/57年在乌拉圭共和国的共和大学，2001年。57.BEASLEY，JE E CHU，PC A广义分配问题的遗传算法。 Computers Operations Research，24（1），第17-23页，1997年。Holland，J。，《自然和人工系统的适应》，第一版，密歇根大学，1975年。第二版。麻省理工学院出版社，1992年，戈德堡，1992年，搜索，优化和机器学习中的遗传算法。 Addison-Wesley，1989年。Whitley，D.，Gordon，VS和Mathias，K。，“ Lamarckian进化，鲍德温效应和功能优化”，《平行概率》，《自然》第3期，以色列，第6-15页，1994年。