论文部分内容阅读
为解决NP完全的旅行商问题，提出一种四点三线遗传算法。该算法特色在两阶段策略，第一阶段是变异算子优化，将汉密尔顿环中所有大于两点的内部路径倒置，并用新极值代替原极值。第二阶段是四点三线优化，将汉密尔顿环分为n个四点三线局部路径并将每个局部路径转化为最优局部路径，将所有局部路径长度求和除以1/3。交叉算子结束后，如子代含有重复位点，将未交叉部分重复位点与交叉部分重复位点对应的父代等位点交换。通过将该算法与传统遗传算法及只进行第一步优化的遗传算法进行比较，采用TSPLIB数据库实例数据，证明该算法有更高的执行