GA2-遗传算法实例

遗传算法 (II)

Genetic Algorithm，GA

by 谢广明 ， 2005~2006学年度第一学期

1

内

应用实例1： TSP 应用实例2：函数优化 策略设计 算法改进

容

by 谢广明 ， 2005~2006学年度第一学期

2

应用实例1：TSP

问题回顾

– 给定n个城市以及两两城市之间的距离，求解 一条从某个城市出发、不重复地遍历所有其它 城市并最终又回到起始城市的最短路径。

数学描述

– 给定图G=(V,E), V为顶点集, E为边集，确定 一条长度最短的Hamilton回路

by 谢广明 ， 2005~2006学年度第一学期

3

应用实例1：TSP

编码方案

– 路径表达：对一个旅行最自然的表达 – 一个旅行 5—>1—>7—>8—>9—>4—>6—>2—>3 的编码就是（5 1 7 8 9 4 6 2 3） – 编码空间和解空间一一对应，总量为n! 个？ – 其实一些解是相同的，因为

（5

1 7 8 9 | 4 6 2 3）= （4 6 2 3 | 5 1 7 8 9） 二者是同一个解 (n -1)!/2

by 谢广明 ， 2005~2006学年度第一学期

4

应用实例1：TSP

适应度函数

– 就取为目标函数的倒数，即路径总长度的倒数

初始种群

– 随机生成40个

终止条件

– 2000次迭代

参数设置

– 自定

5

by 谢广明 ， 2005~2006学年度第一学期

应用实例1：TSP

选择操作算子: 轮盘式选择 首先计算每个个体 i 被选中 f (i) 的概率 p

i

f ( j)

j 1

n

.

r

.

pi

.

p1

然后根据概率的大小将将圆 盘分为 n个扇形，每个扇形 的大小为 2 pi 。选择时转 动轮盘，参考点r落到扇形i则 选择个体i 。

by 谢广明 ， 2005~2006学年度第一学期

.. .

p2

6

应用实例1：TSP

交叉操作算子

– Davis提出OX算子：通过从一个亲体中挑选一个子序列旅行 并保存另一个亲体的城市相对次序来构造后代 – 例如： p1=（1 2 3 | 4 5 6 7 | 8 9） p2=（4 5 2 | 1 8 7 6 | 9 3） 首先保持中间部分 o1=（X X X | 4 5 6 7 | X X ） o2=（X X X | 1 8 7 6 | X X ）

by 谢广明 ， 2005~2006学年度第一学期

7

应用实例1：TSP

交叉操作算子

然后移走p2中已在o1中的城市4、5、6和7后，得到 2—1—8—9—3 该序列顺次放在o1中： o1=（2 1 8 | 4 5 6 7 | 9 3） 类似地，可以得到另一个后代： o2=（2 3 4 | 1 8 7 6 | 5 9）

by 谢广明 ， 2005~2006学年度第一学期

8

应用实例1：TSP

变异操作算子

– 采用倒置变异：在染色体上随机地选择两点，将两 点间的子串反转 – 例如 原个体：（1 2 3 4 5 6 7 8 9） 随机选择两点：（1 2 | 3 4 5 6 | 7 8 9） 倒置后的个体：（1 2 | 6 5 4 3 | 7 8 9）

by 谢广明 ， 2005~2006学年度第一学期

9

应 用 实 例 1： T S P

by 谢广明 ， 2005~2006学年度第一学期

10

应用实例1：TSP

中国城市TSP的一个参考解

by 谢广明 ， 2005~2006学年度第一学期

11

应用