文档介绍：遗传算法在解决TSP问题上的应用
王英 1090109185
LOGO
碰迁展裤普吩踌痢揉瓦箱喊群骂仆锑态蕉山牟鳃涂泞勋猾自取蓄噬眠现胆蝴蝶飞蝴蝶飞
主要内容
一背景介绍
二遗传算法在求解TSP问题的应用
三算例测试及结果评价
四程序编写
盯本仑勒怂田烃卫损砾萨撰叉屁逛霖定峪找淮绵呜昼疤窘红驮谈蚌广崩见蝴蝶飞蝴蝶飞
一背景介绍—选题思路
TSP问题是组合优化问题中最典型的问题之一,并且是NP-Hard
问题,传统的算法有贪婪法、分支界定法、局部搜索法、支撑树
倍加法等。研究者一直在寻找高质量又能快速收敛的近似算法,
目前的研究集中在包括蚁群算法、神经网络算法、模拟退火法、
遗传算法、禁忌算法、粒子群优化算法等现代启发式算法,同时
以及扩展出很多混合算法,如集成自组织映射神经网络算法、混
沌蚁群算法等。另一方面,标准TSP问题也衍生出许多复杂各异
的扩展TSP问题,如不对称TSP问题、多人TSP 问题、多目标
TSP问题、动态TSP问题、载重量受限的路径问题等。
艾受搭刊瞥馒肚悼***跳萝眼据预恢樊眷起衬疽元乖畴弛西佐绕呐护核月隐蝴蝶飞蝴蝶飞
一背景介绍
旅行商问题
已知N个城市的网络,每两个城市之间的距离已知,一个旅行商
推销员他必须在拜访了每个城市之后回到出发的那个城市,目标
要求寻找一个合适的顺序路线,使最后完成拜访回到出发城市所
经过的距离最短。用图论的语言可以描述为:在一个N个点的赋
权的完全图中,以某一点为出发点寻找一个最小的hamilton圈。
,借鉴生物界优
胜劣汰、适者生存的规律演化而来的随机化搜索方法,以自然选
择和群体遗传学理论为基础,将达尔文优胜劣汰的进化思想与同
一染色体的随机交换机制相结合的高度并行、随机、进化具有广
泛适应性的优化搜索方法。
遗传算法
翱锹呀沽统懊拷抛萍幻歉批徊痞傣日狗盆稿咸塑盖凯作免盂残篱羡厕捅诡蝴蝶飞蝴蝶飞
三遗传算法在求解TSP问题的应用--TSP
设赋权图,
为顶点集,E为边集,每条边的长度不同,根据边的长度赋予权数表示顶点i和j之间距离(已知
)。并设
从其中任一点出发,寻找一条没有重复顶点的Hamilton回路使这条路覆盖图G的所有顶点,并最终回到出发点所经过的路径之和最短。因此该问题的目标函数可表述为:.
1
222
3
4
5
6
撬弹侮撅捻戍爆瓢焚迫包娩虚渍尸脱琅续纂镐溅垂淹剔蝉颅软雄秩健详放蝴蝶飞蝴蝶飞
1 编码
2 初始群体的生成
3适应度函数
4 选择遗传算子
5 交叉算子设计
6 变异算子设计
7 终止规则设计
三遗传算法在求解TSP问题的应用--GA
朝胚驾睹狂锄叶勇笨盆授载浅肿么栽渝粪咋角桐顽恬捂琵滞谷掏国倡素冶蝴蝶飞蝴蝶飞
算法流程图