退火单亲遗传算法求解旅行商问题及MATLAB实现

被引：10

作者：

吴值民 ^{[1
]}

吴凤丽 ^{[2
]}

邹赟波 ^{[1
]}

李宏伟 ^{[1
]}

卢厚清 ^{[1
]}

机构：

[1] 解放军理工大学工程兵工程学院

[2] 解放军理工大学气象学院

来源：

解放军理工大学学报(自然科学版) | 2007年 / 01期

关键词：

旅行商问题; 单亲遗传; 模拟退火;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

为了提高遗传算法求解较大规模旅行商问题的能力,在单亲遗传算法中引入两代竞争模拟退火选择操作,与倒位算子和插入算子相结合,同时加入保优操作,使遗传搜索效率、收敛速度都得到大幅提高,所花费时间、收敛迭代次数、最后结果明显优于一般遗传算法和单亲遗传算法。给出了用MATLAB实现算法的一些重要步骤和函数,并进行了简要说明。在仿真实例中,用一般遗传、单亲、退火单亲遗传算法对75个城市的TSP问题进行了求解,退火单亲遗传算法对280、535个城市TSP问题进行了求解。结果表明,退火单亲遗传算法最终所得结果最好,但收敛所花时间约为一般遗传的2.5%,单亲遗传的20%,迭代次数为一般遗传的20%,单亲遗传的25%。

引用

页码：44 / 48

页数：5

共 9 条

[1] 一种求解TSP问题的单亲遗传算法 [J].