人工智能中的八皇后问题

八皇后问题是人工智能和组合优化中的一个经典谜题。它指的是在 8x8 英寸的棋盘上放置八个皇后，使得任意两个皇后都不能互相攻击。也就是说，任意两个皇后不能在同一行、同一列或同一对角线上。

问题陈述

给定一个 8x8 英寸的棋盘，目标是在棋盘上放置 8 个皇后，使得：

• 任意两个皇后不在同一行。
• 任意两个皇后不在同一列。
• 任意两个皇后不在同一对角线上。
• 主对角线和副对角线都被考虑在内。
• 将此问题推广为 N 皇后问题，并在 NxN 的棋盘上放置 N 个皇后。

为此，有许多方法，例如约束满足问题 (CSP) 和回溯法，但我们将采用遗传算法。

遗传算法

遗传算法是一类优化算法，其起源可以追溯到自然进化过程，如突变、交叉和选择。这类算法通过模拟进化，可以比标准方法更有效地解决问题。它们将可能的解决方案表示为种群中的个体，并携带其各自的遗传信息。将计算解决方案的适应度，该适应度表示效率，适应度越高，解决方案越好。经过多代，最适应的个体进行交配以产生新的解决方案，最终朝着最优解决方案进化。

遗传算法的实现方式有多种，因为交叉和突变等机制是可选的，具体取决于问题。正是这种灵活性使得设计出的算法能够收敛到一些最佳解决方案，而不会陷入局部最优解。最终的解决方案仅继承了前几代中最佳特征，并通过平衡随机性和选择来优化这些特征。因此，战略决策在很大程度上影响算法的性能。

递归亚当和夏娃

这是一种遗传算法策略，在该策略中，每一代只保留两个最适应的个体——亚当和夏娃。这两个个体通过繁殖来产生一个全新的、在结构上与旧一代等效的新一代。也就是说，如果亚当和夏娃幸存下来，那么他们可能拥有更好的基因。他们很可能拥有属于最优解决方案的共同部分，因此可以使算法快速收敛到好的解决方案。另一方面，这是一种非常具探索性的方法，快速收敛通常能得到一个好的解决方案，但可能不是完美的。与突变率相关的这种中断可以略微提高，以纠正这一点并使探索更可能发生。突变中的探索性非常高，这增加了其发生的概率，因此保持了高探索性和低概率开发之间的平衡，避免了过早收敛并增加了找到最优解决方案的机会。

杀死一半的种群

执行遗传算法的另一种方法是递归亚当和夏娃的弱化版本，其中我们允许种群中的一半——即最佳的一半——生存并繁殖，而不是淘汰除两个个体之外的所有个体。也就是说，通过移除适应度最低的个体，我们确保通过交叉来专注于培育最佳解决方案，从而改进使它们成功的性状。这将增加遗传多样性，允许更多个体进行交配，并减少陷入局部最优（即好但不完美的解决方案）的可能性。现在，如何将这些幸存者配对进行繁殖成为下一个决定。

有随机配对（互斥）的方法，其中每对只交配一次；有具有相似适应度的个体配对以进行受控近亲繁殖；以及具有多样化适应度的个体配对以增强遗传变异。在我们的方法中，我们采用随机配对（互斥），这允许轻松预测未来种群的大小，并避免了“相似的适应度意味着相似的个体”之类的假设。该策略的目的是在关注提高每一代的整体适应度的同时，保持种群多样性。

伟大的比赛

这是对遗传算法中应用的普通（即标准）锦标赛选择方法的一种非常新颖的变体。锦标赛的基本思想是随机选择一组个体，然后让他们进行“战斗”，即胜者——通常基于其适应度——幸存下来进行繁殖。但另一种方法是定义一个胜率，该胜率偏向于更适应的个体，而不总是让其稳操胜券；这样会更具探索性。例如，随机选择 10 个人，然后他们进行比赛，胜者将进入约会池进行繁殖。这个过程重复进行，直到从这些冠军中形成一个新一代。

这些变化可能包括调整锦标赛规模或让失败者有机会再次竞争。此类变化会显著影响算法性能；大型锦标赛具有很高的选择压力并促进精英主义。在这项工作中，锦标赛只使用了 2 个对手，并且无论适应度差距多大，都给予适应度更高的个体 85% 的获胜机会。

这个方案的一个奇怪之处在于为失败者提供了“救赎”。如果弱的竞争者赢得了比赛，他们不会幸存下来；相反，他们会与对手交配，而他们的后代将被送到约会池。这确保了较弱的竞争者的遗传物质只有在与更适应的对手互动时才会传递下去。这通过使用小规模的锦标赛和减少较弱个体的遗传影响来平衡探索和开发。

性能

遗传算法的性能可以定义为它们达到最优解决方案的速度。通常，效率等同于速度。由于这些算法是用相对低效的语言实现的，因此实际的计算时间会比使用 C 或 Fortran 等语言编写的可比程序更长。因此，测得的性能应该可以转移到其他语言，甚至更好地用于更高效的实现。

为了对遗传算法的性能进行基准测试，我们将针对不同数量的皇后和突变概率运行模型，并尽可能多次重复实验。记录运行中的数据并保存以供分析。由于这可能需要很长时间来计算，因此最好将这些实验安排在夜间运行。

首先将收集信息，然后进行清理和准备以进行可视化。初步分析仅仅是对数据的查看，而不会区分不同的模型。

输出

我们发现，在问题中增加皇后的数量会导致计算量增加，结果的变异性也会随之增加。也就是说，解决问题需要更多的时间，并且所需的时间由于结果的分散程度更大而无法像以前那样容易地估算。这对进一步的洞察很有帮助：可以查看实验期间使用的每个模型区分开的结果。

输出

该图显示，伟大的比赛模型是测试模型中最混乱的模型。对于皇后数量少于 10 个的问题，半数模型和递归亚当和夏娃模型能更快地找到最优解决方案。然而，随着皇后数量的增加，结果变得不可预测且更加混乱。

下一步需要进行的分析是性能如何随突变概率的变化而变化。为了对抗模型的精英主义倾向，已经包含了一个突变概率的案例，这方面的研究可以为结果提供有价值的见解。

输出

现在我们已经考虑了上述图表，我们可以看到模型之间的关键差异以及它们如何利用突变概率。我们看到 allbut2 模型是最具影响力的。事实上，较小的突变概率，如 0.01 甚至 0.05，由于即使是最小的问题使用此模型计算也需要过长的时间才能收集到相关数据，因此无法纳入分析。这同时也说明了突变在创建高度开发性模型方面是多么重要。人们可能会注意到，当该概率增加时，实际性能会更高，在 p = 0.5 左右会达到一个“甜蜜点”。

结论

杀死一半的种群和递归亚当和夏娃模型比伟大的比赛模型表现更好，随机选择有时比所有这些模型都好。对于超过 10 个皇后的数量，结果变得更加不可预测，因此我们无法真正判断定制模型是否比随机试错更好；然而，整体适应度的逐渐提高表明它们在更多的皇后数量上可能会获胜。

对于递归亚当和夏娃模型，突变概率很重要，但对于其他模型则不然。性能对突变概率的依赖性不是很明确，模型中应用的“交叉”方法的有效性也不清楚。换句话说，突变的概率可以决定交叉是否发生，从而影响未来几代特征的产生方式。另一方面，递归亚当和夏娃模型由于突变概率非常低而陷入了局部最小值。尽管如此，递归亚当和夏娃模型的适度突变概率 0:25 < p < 0:75 有时仍能返回更好的解决方案，这表明尽管该模型是精英主义的且收敛速度很快，但有时它比其他模型更快地收敛到最优解决方案。