我正在使用遗传算法 (GA) 来优化旅行商问题 (TSP)。我的问题是我如何计算个人的适应度。显然，具有较短路线的解决方案更合适，但是我如何在不知道最短可能路线和最长可能路线是什么的情况下准确分配适应度值来确定我的解决方案适合该范围的位置？
问问题
2816 次
3 回答
5
适应度等于路径长度很好。请记住，在遗传算法中，适应度仅用于选择个体：因此对于通常的选择程序，规模并不重要，只有等级重要。
实施示例：
- http://www.codeproject.com/Articles/1403/Genetic-Algorithms-and-the-Traveling-Salesman-Prob
- http://khayyam.developpez.com/articles/algo/voyageur-de-commerce/genetique/（使用谷歌翻译）
- http://www.lalena.com/ai/tsp/
- http://www.mathworks.com/matlabcentral/fileexchange/13680
更多细节（2001 - Swarm Intelligence - Kennedy & Eberhart - 第 249 页）：
Pablo Moscato 是一位南美研究员，他率先研究了模因算法（例如，Moscato，1989）。他和现在在苏格兰爱丁堡大学工作的迈克尔·诺曼（Michael Norman）于 1980 年代开始在加州理工学院合作。在最近的一篇论文中，他们描述了使用模因算法优化旅行商问题 (TSP) (Moscato and Norman, 1992)。回想一下，TSP 需要找到穿过多个城市的最短路径，每个城市只经过一次。这个问题在应用数学中有着悠久的历史，因为它很难解决，尤其是在城市数量很大的情况下。TSP 是一个 NP-hard 问题，这表明如果找到解决它的方法，那么大量其他问题也将得到解决。
一群人——这些研究人员通常使用 16 人的人口规模——搜索由城市排列定义的问题空间，称为“旅游”。种群被概念化为一个环，每个个体都连接到它的两个紧邻的邻居，并在搜索中与之竞争；个人还与环另一端的其他人有联系，他们与之合作。人口中的每个人都包括城市之旅。竞争被视为个体之间的“挑战”和“战斗”，其中比较个体与其邻居的旅行长度，并根据差异设置概率阈值。行程长度之间的差异会影响 S 形曲线的陡度；当差异较小或温度较低时，
合作被用来让更成功的人彼此“交配”，而不是与人群中不适合的成员“交配”。用于决定竞争性互动的相同规则用于评估合作伙伴对交叉的渴望，这与在 GA 中一样实施。一个人向另一个人“提议”，如果提议被接受，也就是说，如果随机决策有利于他们的交互，则实施交叉算子。这样就产生了下一代。
于 2012-07-31T20:35:16.490 回答
2
您可以对所有候选解决方案进行规范化，以使您迄今为止看到的最短路径的适应度得分为 1.0（或 10、42 或 3.14 ......随您喜欢），然后将所有路径缩放得比这相对更长。与最长路径相同 - 您观察到的最长路径被认为是最差的分数。
当你找到一条更短的路径时，诀窍就在于你所做的事情（假设你为一些更长的路径分配了最高可能的分数，例如 1.0）——然后你必须提高标准化函数的上限。例如，开始分配适应度 2.0（或 1.1，或其他任意更大的适应度分数）。
于 2012-07-31T20:08:04.337 回答
0
如果您的程序正在最大化适应度值，您可能希望最大化适应度函数
f = - 行程长度
已编辑：我在健身中添加了 1000000000000，一个任意数字，以使健身变得积极，在阅读了一些评论后，我意识到这没有必要。
如果您的程序正在最小化适应度值，您可能希望最小化适应度函数
f = 巡回赛长度
于 2012-07-31T21:41:38.123 回答