第 4 章 基于遗传算法的TSP算法

1、案例背景

TSP (旅行商问题—Traveling Salesman Problem)，是典型的NP完全问题，即其最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能。

2、案例目录：

第4章 基于遗传算法的TSP算法 4.1 理论基础 4.1.1 遗传算法概述 4.1.2 TSP问题介绍 4.2 案例背景 4.2.1 问题描述 4.2.2解决思路及步骤 4.2.2.1 算法流程 4.2.2.2 遗传算法实现 1. 编码 2. 种群初始化 3. 适应度函数 4. 选择操作 5. 交叉操作