旅行推销员 - 进化算法
Travelling Sales Person - Evolutionary Algorithm
我了解进化算法的工作原理。我已经写了一个找到 n 维方程的最大值 space.
我可以看到一个问题使用相同的设计来解决 TSM 问题。
当我使用交叉甚至突变时，我可能会创建一个去同一个城市两次的个体，或者不会访问每个城市。
我可以采取哪些措施来确保人口中的每个人只访问每个城市一次？也就是说，每个人都是有效答案。
解决这个问题的一个常用技术是施加一个"penalty"，其中，任何具有任何未访问过的城市的染色体都会被添加惩罚。例如，如果一条染色体有五个未访问过的城市，则将 5 倍的惩罚加到染色体适应度分数上。在这种情况下，任何没有访问过城市的染色体，逐渐从种群中移除，并允许其他（零个没有访问过的城市）个体保留在种群中。
您不能使用用于查找方程最大值的相同设计模式并将其应用于 TSP 问题。原因是两个问题之间的染色体编码/解码不同。
对于数值方程问题，根据问题的类型，大部分染色体可以解码为 "real value" / "binary value"。但是，对于 TSP 问题，我们必须使用 "permutation" 编码。这种排列编码主要用于"Combinatorial optimization"(https://en.wikipedia.org/wiki/Combinatorial_optimization)
下面是一个很好的 GA 编码技术参考站点：
http://www.obitko.com/tutorials/genetic-algorithms/encoding.php
这个"permutation encoding/decoding"背后的想法是：给定一个包含n个城市的列表，表示为c1，c2，...，cn；染色体将被编码为旅行推销员旅行过的这些城市的顺序（例如染色体= c1, c2, ..., cn）。通过对该染色体应用排列，您可以为种群生成不同的染色体，GA 算子将从这里开始。把染色体编码成这样可以避免一个城市被多次访问的问题！
由于你没有提到任何数据结构或首选编程语言，所以我不能post这里的源代码。如果您仍然想要一些工作版本的示例，可以通过电子邮件与我联系。
一种方法是使用双点有序交叉。这种类型的交叉从单个 parent 创建一个 child。选择了两个parent，并选择了染色体上的两个随机点。点之间的基因传递给child。其余基因从同一个 parent 中转移，但按照它们在第二个 parent 中出现的顺序。结果是 child 包含来自单个 parent 的所有值，但包括来自两个 parent 的排序和特征。
此处显示了使用此类运算符求解 TSP 的两个示例；
http://johnnewcombe.net/blog/gaf-part-4/
http://johnnewcombe.net/blog/gaf-part-7/
这些示例中的第一个使用整数来引用城市，第二个示例通过使用基于 object 的基因将城市存储在染色体中来简化这一点。
我了解进化算法的工作原理。我已经写了一个找到 n 维方程的最大值 space.
我可以看到一个问题使用相同的设计来解决 TSM 问题。 当我使用交叉甚至突变时，我可能会创建一个去同一个城市两次的个体，或者不会访问每个城市。
我可以采取哪些措施来确保人口中的每个人只访问每个城市一次？也就是说，每个人都是有效答案。
解决这个问题的一个常用技术是施加一个"penalty"，其中，任何具有任何未访问过的城市的染色体都会被添加惩罚。例如，如果一条染色体有五个未访问过的城市，则将 5 倍的惩罚加到染色体适应度分数上。在这种情况下，任何没有访问过城市的染色体，逐渐从种群中移除，并允许其他（零个没有访问过的城市）个体保留在种群中。
您不能使用用于查找方程最大值的相同设计模式并将其应用于 TSP 问题。原因是两个问题之间的染色体编码/解码不同。 对于数值方程问题，根据问题的类型，大部分染色体可以解码为 "real value" / "binary value"。但是，对于 TSP 问题，我们必须使用 "permutation" 编码。这种排列编码主要用于"Combinatorial optimization"(https://en.wikipedia.org/wiki/Combinatorial_optimization)
下面是一个很好的 GA 编码技术参考站点： http://www.obitko.com/tutorials/genetic-algorithms/encoding.php
这个"permutation encoding/decoding"背后的想法是：给定一个包含n个城市的列表，表示为c1，c2，...，cn；染色体将被编码为旅行推销员旅行过的这些城市的顺序（例如染色体= c1, c2, ..., cn）。通过对该染色体应用排列，您可以为种群生成不同的染色体，GA 算子将从这里开始。把染色体编码成这样可以避免一个城市被多次访问的问题！
由于你没有提到任何数据结构或首选编程语言，所以我不能post这里的源代码。如果您仍然想要一些工作版本的示例，可以通过电子邮件与我联系。
一种方法是使用双点有序交叉。这种类型的交叉从单个 parent 创建一个 child。选择了两个parent，并选择了染色体上的两个随机点。点之间的基因传递给child。其余基因从同一个 parent 中转移，但按照它们在第二个 parent 中出现的顺序。结果是 child 包含来自单个 parent 的所有值，但包括来自两个 parent 的排序和特征。
此处显示了使用此类运算符求解 TSP 的两个示例；
http://johnnewcombe.net/blog/gaf-part-4/
http://johnnewcombe.net/blog/gaf-part-7/
这些示例中的第一个使用整数来引用城市，第二个示例通过使用基于 object 的基因将城市存储在染色体中来简化这一点。