Und*_*ned 4 artificial-intelligence traveling-salesman genetic-algorithm
我正在使用遗传算法(GA)来优化旅行商问题(TSP).我的问题是我如何计算个人的健康状况.显然,具有较短路线的解决方案更适合但是我如何在不知道最短路径和最长可能路线确定我的解决方案在该范围内的位置的情况下分配适合度值？
健身等于路径长度是好的.请记住,在遗传算法中,适应度仅用于选择个体:因此,通过常规选择程序,量表无关紧要,只有等级才有效.
实施例子:
更微妙(2001 - Swarm Intelligence - Kennedy&Eberhart - 第249页):
Pablo Moscato是南美研究员,他开创了模因算法研究的先驱(例如,Moscato,1989).现在在爱丁堡大学苏格兰的他和迈克尔·诺曼在20世纪80年代开始在加州理工学院合作.在最近的一篇论文中,他们描述了使用模因算法来优化旅行商问题(TSP)(Moscato和Norman,1992).回想一下,TSP需要找到通过一些城市的最短路径,只通过一个城市.这个问题在应用数学方面有着悠久的历史,因为它很难解决,特别是当城市数量很大时.TSP是一个NP难问题,它表明如果找到一种方法来解决它,那么大量其他问题也将得到解决.Moscato和Norman使用一种算法,在群体中的代理之间进行协作和竞争,并为局部搜索实现模拟退火的混合版本.
一群人 - 这些研究人员通常使用16人口搜索问题空间,这是由城市的排列定义的,称为"旅游".人口被概念化为一个环,每个人都附着在其两个人身上.紧邻邻居,与之竞争; 个人也与戒指远端的其他人联系,他们与之合作.人口中的每个人都参观了城市.竞争被视为成对个体之间的"挑战"和"战斗",其中比较个体及其邻居的巡回长度并且基于该差异设置概率阈值.游览长度之间的差异会影响s形曲线的陡度; 当差异很小或温度很冷时,概率分布几乎变得均匀,并且当两个游览之间的长度差异很大时,概率增加,游览1将被删除并替换为游览0的副本.
合作被用来让更多成功的人彼此"交配",而不是与不太适合的人口成员交配.用于决定竞争性互动的相同规则用于评估合作伙伴进行交叉的可取性,这与GA一样实施.一个人向另一个人"提出",如果命题被接受,也就是说,如果随机决策有利于他们的相互作用,则实施交叉算子.因此创造了下一代.