贪婪算法

null基于贪婪思想的TSP问题GA算法基于贪婪思想的TSP问题GA算法TSP下的贪婪思想TSP下的贪婪思想TSP的目标是要求路径总和最小 贪婪的思想就是在以与已知末节点最近为标准来选择下个点，直到路径包含了所有点。编码编码采用实数编码 如：1-2-5-3-6-4 表示从1点出发，依次经过2、5、3、6、4再回到节点1。交叉交叉选取父辈 随机产生第一个点位置利用贪婪思想选取后续节点产生一个新个体结束循环，产生另一个体利用贪婪思想选取后续节点利用贪婪思想选取后续节点将随机产生第1节点 记入子代 ，并作为当前点比较父辈两个体中当前点 与后续节点的距离选取距离小的后续节点， 记入子代删除父辈个体中当前点以刚才记入子代的 点定为当前点判断是否结束结束注：若当前点为某个父辈中个体中的末节点，则距离为该点与个体的第1节点的距离示例数据示例数据利用贪婪思想选取后续节点利用贪婪思想选取后续节点P1: 5-1-6-3-2-4 P2: 2-1-5-3-6-4D63 VS D64D(6-3)：5 D(6-4)：3随机产生第1节点：6 记作当前节点6 4 * * * *删除节点6， 记4为当前节点P1: 5-1-3-2-4 P2: 2-1-5-3-4D(4-5)：5 D(4-2)：5删除节点6， 记4为当前节点D45 VS D426 4 5 * * *比较距离利用贪婪思想选取后续节点利用贪婪思想选取后续节点P1: 5-1-3-2-4 P2: 2-1-5-3-4D(4-5)：5 D(4-2)：5D45 VS D426 4 5 * * *比较距离删除节点4， 记5为当前节点P1: 5-1-3-2 P2: 2-1-5-3……最终可以产生：6-4-5-1-3-2 再重新随机产生第1节点，循环一次产生第2个子代变异变异可直接通过随机产生交换位置，交换变异 如： 6-4-5-1-3-2 随机产生交换位置3、5，则交换5、3产生变异后个体6-4-3-1-5-2其它设置其它设置群体大小：根据节点数目设置，一般10个节点可设置100个 变异概率：贪婪算法下可设置稍大，如0.3 循环迭代次数：10个节点可设500代左右谢谢！谢谢！