我构建了一个GA算法来解决TSP问题。
这是Norvig书中（AIAMA）的一个练习。他建议我们阅读Larrañaga对问题表示等方面的看法。我在那里学习了一些交叉操作符和变异，并尝试了一些，看看哪一种更适合我。我还根据每条路径的成本制定了适应度函数。
尽管如此，我对我的算法设计有一个问题，我之前从未接触过AI，所以我不知道我的方法是否是GA的有效方法。
这是我所做的：
我采用了一组路径向量（我的初始种群）
然后在每个循环中，我按成本递增顺序组织这个向量，并从中选取最好的X条路径，删除其他路径。
然后我以一定的速率应用交叉和变异操作，并将它们放置在向量中旧的被删除值的位置上。
然后我重复同样的操作（排序向量 – 提取最佳路径等）
并一直进行直到结果稳定下来。
这是一个好的方法吗？如果不是，请给我一些建议。因为当我选择最好的路径但不保留它们（只是通过交叉和变异从中创建一个全新的种群）时，我没有得到好的结果。用这种方法（保留最好的路径 – 在一些实验中我只保留了最好的那一个）我有更好的结果，而且结果总是快速收敛的
状态表示：对于状态表示，我选择使用路径表示法（我从一开始就使用它，并且在阅读了Larrañaga等人的文章后决定继续使用），如下所示：如果我们有5个城市，首先访问第一个城市，然后是第二个，然后是第三个……我们的路径表示将是（1, 2, 3, 4, 5）
初始种群生成：实际上，我是生成随机点来表示城市（这是书中要求我做的，在一个封闭的正方形中生成随机点） – 但为了比较，我生成了一个种群并在比较结果时坚持使用它 – 我认为如果我不坚持使用一个特定的种群，我将无法了解我的改进情况
最佳适应个体：最佳适应个体是那些具有最佳旅行成本的个体。（我不知道在这个问题中是否应该使用其他参数
交叉：我尝试了一些交叉操作符，并将我的结果与书中呈现的结果进行了比较，最终使用了Larrañaga等人（1999年）提出的顺序交叉之一：这种交叉从两个父路径中随机选择两个切割点（形成一个子路径），然后从另一个父路径中复制路径的其余部分（子路径内尚未访问的城市，从第二个切割点开始，而不是从位置’0’开始） – 按它们在另一个父路径中出现的顺序添加城市。
示例：路径（1 2 3 4 5）（3 4 2 1 5）选择子路径（234）和（421），我们将得到的后代是（5 |2 3 4| 1）（5 |4 2 1| 3）<- | | 内的部分来自一个父路径，其余部分来自另一个父路径
变异：对于变异，我选择了IVM（倒置变异）方法。它从原始路径中取出一个子路径，并将其（倒置后）插入到一个随机点上。
示例：路径（1 2 3 4 5）子路径（2 3 4）并在5之后随机插入
生成：（1 5 |4 3 2）
回答：
首先，避免使用所有这些缩写（GA, TSP, XOver）。这很难读懂，有些人可能不知道你在说什么。遗传算法的第一个问题是如何选择初始种群，如何执行交叉，如何执行变异。第二个问题是，对描述的简单理解可能是一个糟糕的理解。
对你来说，最佳适应个体是那些已经有更好成本的个体。你可以争辩说，选择最具多样性的个体，即那些更有可能探索问题空间不同部分的个体会更好。描述你是如何进行以下操作的：
- 状态表示：只是为了确保
- 初始种群生成：非常重要。可能有可用的材料用于这一步骤，因为这在局部搜索算法中很常见。
- 最佳适应个体：我建议你在这里尝试更多的方法。尝试不同的策略。你寻找的是最适合繁殖的个体，而不是问题的整体解决方案。
- 交叉：你是如何做的？
- 变异：变异的目的是逃离当前的问题空间区域，你可以创建一个成本非常高的个体。用你当前的算法，在下一步排序时他会被淘汰
你还需要评估你的解决方案随运行时间的改进情况。例如，与n次迭代相比，你提供100n次迭代，解决方案是否变得更好，改善了多少？当算法停止时，最后一代个体的相似度如何，等等。
另一个问题，你是尝试解决固定拓扑结构还是可变拓扑结构？
编辑：你使用的是已发表的算法，所以问题似乎不在于特定的操作。对于适应度，你是对的，坚持使用路径成本。你说
因为当我选择最好的路径但不保留它们（只是通过交叉和变异从中创建一个全新的种群）时，我没有得到好的结果。用这种方法（保留最好的路径 – 在一些实验中我只保留了最好的那一个）我有更好的结果，而且结果总是快速收敛的。
你应该保留最佳适应个体及其后代。这遵循自然界的一个邪恶原则，只有最好的个体才有繁殖的权利。需要被替换的是最不适应的个体。
有三个参数你可以调整：有后代的最佳适应个体的比例（同时也是将被淘汰的个体的数量），变异概率，以及运行次数。
为了测试你的算法的表现，你可以按迭代采样最佳解决方案，即每t次迭代你保存最低成本。一旦绘制出来，它应该看起来像：
