版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 一直对遗传算法非常好奇,它是对自然界生物进化机制的计算机模拟。可以用于对NP问题的最优化求解。 在生活中,可以被用于排班、排课、路径优化,甚至可以被用于歌曲自动编写。 2. 问题分析 遗传算法的一个典型案例是针对旅行商问题。 旅行商问题,一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 我们从一个最简单的情况来说明这个问题。 例1:假定有A、B、C、D四个地点,坐标如上图 假定出发点是A点,那么所有的可能的路径是 ABCDA ABDCA ACBDA ACDBA ADBCA ADCBA 由于起点和终点都是A,是完全确定的;所以所有可能的路径就是B、C、D的全排列 共有n!中情况,此处n为3,共有6种情况 我们实际是在解空间中寻找最优解。 当n=20时 20!= 2,432,902,008,176,640,000 当n=21时,解空间的大小已经溢出了int64所能存储的空间 解空间相当大,以至于遍历一遍几乎是不大可能的 3. 遗传算法如何寻找最优解 事实上,遗传算法得到有可能得到最优解,也有可能得到次优解。 下面是遗传算法的完整过程 3.1 编码 让我们再回到例1,由于只有6种情况,那么解空间的取值范围就是 [0, 5] 假定如下的对应关系 BCD — 0 — 000 BDC… 继续阅读 使用遗传算法来解决旅行商问题