目 录
引言............................................................................................................................................1
1 遗传算法概论.........................................................................................................................1
1．1 遗传算法的历史和研究现状 1
1．2 遗传算法的基本原理 3
1．2．1 遗传算法基本概念...........................................................................................................................3
1．2．2 遗传算法基本原理...........................................................................................................................3
1．2．3 遗传算法的特点...............................................................................................................................3
2 普通遗传算法.........................................................................................................................4
2．1 普通遗传遗传算法思想 4
2．2 普通遗传算法的遗传操作 4
2．2．1 选择（selection）操作.....................................................................................................................4
2．2．2 交叉(crossover)操作.........................................................................................................................4
2．2．3 变异(mutation)操作...........................................................................................................................6
4 遗传算法在 TSP 问题上的应用............................................................................................6
4．1 TSP 问题概述 6
TSP 问题就是已知个城市各城市间的距离，一旅行商从某一城市出发访问每个城市一次且仅一次 ，
最后回到出发城市，如何安排才能使其所走路程最短？...........................................................................6
问 题 的 数 学 模 型 可 以 描 述 为 ： 对 于 n 个 城 市 V={v
1
,v
2
,…,v
n
} 的 一 访 问 次 序 为 T=(t
1
,t
2
,…,t
n
),
t
i
V
i
（i=1，2,…，n）,t
n+1
= t
1,
则问题即要求 min，其中表示城市 i 与城市 i+1 之间的距离。.................6
对于 TSP 这样的一个典型的组合优化问题，最为普通的一种解决办法就是穷举出所有可能的合法
序列，然后比较距离函数，得出最优的城市序列。这就是穷举搜索法的思想，理论上它可以解决任
何组合优化问题，但是对于 n 个城市的 TSP 问题来说，可能的合法回路有条,计算每一条路径需求 n
个距离之和，因此计算量正比于。即使使用运算速度为 10
5
亿次每秒的巨型计算机按穷举搜索法计
算 100 个城市的 TSP 问题也需要 1.4810
136
年的时间，在这里还没有考虑算法所需的巨大的存储空间，
由此可见 TSP 问题的时空复杂度之高，这就为遗传算法的应用提供了机会，下面我们就来看一求解
TSP 问题的遗传算法。....................................................................................................................................6
4．2 遗传算法求解 TSP 问题 6
4．2．1 编码与解码........................................................................................................................................6
在遗传算法中每一个个体表示成一个染色体，每一个染色体又是由一个个基因位所构成的。这样
每一个个体对象相当于生物体的表现型，而染色体就相当于生物体的基因型，从表现型到基因型的
映射称为编码。在遗传算法中最初使用的编码方法是二进制编码：每个染色体使用固定长度的
0，1 字符串表示，如：...................................................................................................................................6
4．2．2 初始化种群........................................................................................................................................7
4．2．3 适应度函数........................................................................................................................................7
4．2．4 选择算子............................................................................................................................................8
4．2．5 交叉算子............................................................................................................................................8
4．2．6 变异算子..........................................................................................................................................13
变异算子的 JAVA 实现：..............................................................................................................................13
}......................................................................................................................................................................13
4．2．7 停止准则..........................................................................................................................................13
遗传算法中的停止准则一般是设定最大代数的方式，最大代数常设为 popsize，本文采用，最大代
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
评论0