24
3.8053
A7
29
8.0155
A12
12
0
A8
30
3.0608
A13
23
0.5
A14
21
3.265
A16
14
6.7417
A15
28
4.7518
四、案例应用
建模案例：交巡警服务平台的设置与调度
源代码说明如下： 主程序为：fengsuo.m； 新编写初始种群的生成算子（crt_zp）； 将交叉算子（recombin）、变异算子（mut）、重插
本题模型可以描述为：
min
Max
1im
ti
,
zi
,
m
min ti,zi i 1
s.t.
1
zi
zi
z
m
j
1i m i j
四、案例应用
建模案例：交巡警服务平台的设置与调度
为了简化这么一个从 m 个交巡警服务平台中挑选出 n 个来的过程，可以虚拟出 m n 待封锁的路口，所有平
入算子（reins）重新编写有序交叉算子 （order_crossover）、变异算子（mute_yth）、重插入 算子（reins_yth）。
一、遗传算法基本理论
生物进化
遗传算法
环境
适应值函数
适者生存，优胜 劣汰
适应值函数越大的解被保留的概率越大
个体
问题的一个可行解
染色体
可行解的编码
基因
编码的元素
群体
被选定的一组可行解
种群
根据适应值函数选择的一组可行解
交叉
以交叉方式由双亲产生后代的过程
变异
编码的某些分量发生变化的过程
一、遗传算法基本理论
交叉算子
例如: 对两条全1和全零的12位染色体，假如产生的 交叉点位置为4，则执行的交叉操作如下图所示：
变异算子
遗传变异操作首先在种群中随机选择一个个体，对该 个体以一定的概率（称为变异概率 pm ，一般地， pm 介于 1/ 种群规模与 1/染色体长度之间，平均约为 0.0001～0.1。）
二、遗传算法工具箱
四、案例应用
建模案例：交巡警服务平台的设置与调度
使用一个数字（例如1,2,……,20）代表一个城市，通过对 这20个数字排序构造路径，选择合适的遗传算子产生路径。 有序交叉（Order Crossover）算子（ Davis（1985）提出）
首先，随机产生交叉点： p1(238|7154|69) p2(947|1856|32)
15
16
17
18
19
二进制码 01111 01000 10000 11000 10001 11001 10010 11011 10011 11010
原始值
20
21
22
23
24
二进制码 10100 11110 10101 11111 10110 11101 10111 11100 11000 10100
二、遗传算法工具箱
交叉算子
子种群的支持 实用函数
函数 recdis recint reclint recmut recombin xovdp xovdprs xovmp xovsh xovshrs xovsp xovsprs migrate bs2rv
功能 离散重组 中间重组 线性重组 具有变异特征的线性重组 高级重组算子 两点交叉算子 减少代理的两点交叉 通常多点交叉 洗牌交叉 减少代理的洗牌交叉 单点交叉 减少代理的单点交叉 在子种群间交换个体 二进制串到实值的转换
三、遗传算法应用
一元函数的优化问题
例：利用遗传算法计算函数 f (x) x cos(5 x) 3.5在区间[1,2.5]上的最值
最大值运行结果：
源代码请见本目录：exp12_1_1.m
三、遗传算法应用
一元函数的优化问题
例：利用遗传算法计算函数 f (x) x cos(5 x) 3.5在区间[1,2.5]上的最值
12
10
8
6
0
50
100
150
200
250
300
350
400
450
500
迭代次数
四、案例应用
建模案例：交巡警服务平台的设置与调度
封锁调度方案
封锁平台 封锁路口 封锁时间 封锁平台 封锁路口 封锁时间
A2
38
3.9822
A9
16
1.5325
A4
62
0.35
A10
22
7.7079
A5
48
2.4758
A11
其中， Cmin 为目标函数 f (x) 的最小估计值。
针对目标函数最大化问题，则令
Fitness(
f
(x))

Cmax
0
f
(x)
Cmax f (x) others
其中， Cmax 为目标函数 f (x) 的最大估计值。
选择算子
遗传算法的本质就是模拟了“物竞天择”的自然选择学说，选择 提供了遗传算法的驱动力。选择的思想就是适应值越高的染色体获得 选择（复制）的机会越大。关于选择方式，Holland 提出对轮盘赌选 择是最经典的。
最小值运行结果：
源代码请见本目录：exp12_1_1.m
三、遗传算法应用
多元函数的优化问题
例：利用遗传算法求解多峰的 Shubert 函数 f (x, y) 在区域[10,10][10,10] 上的最
5
5
其中 f (x, y) k cos k 1 x k g k cos k 1 y k 。
采用格雷编码（Gray Encoding）可以避免这一缺陷。 格雷码的特点是任意两个连续的两个整数的编码值之间 只有一个位是不同的，其他位都完全相同。
格雷编码
格雷编码是一种基于二进制编码的循环码，它需要对 普通的二进制编码从最右一位起，依次将每一位与其左边 一位作异或运算，作为对应格雷编码在该位的值，最左边 一位保持不变。
创建种群 适应度计算
选择函数 变异算子
函数 crtbase crtbp crtrp ranking scaling reins
rws select
sus mut mutlate mutbga
功能 创建基向量 创建任意离散随机种群 创建实值初始种群 基于秩的适应度计算 基于比率的适应度计算 一致随机和基于适应度的重插入 轮盘选择 高级选择例程 随机遍列采样 离散变异 高级变异函数 实值变异
染色体编码（chromosome coding）与解码（decode）
二进制编码:是最简单也最常用的编码方式，它 采用一个二进制字符串来表征解。
例如：在区间[a,b] 内根据解的精度进行长度为n的二进制编码：
0000……000＝0
┆
┆┆
1111……111＝ 2n -1
则编码 b1b2
bn
解码后对应值为：
数学建模与数学实验
遗传算法
后勤工程学院数学教研室
实验目的
学习遗传算法的基本原理与方法。
实验内容
1、遗传算法基本理论 2、遗传算法工具箱 3、遗传算法应用 4、案例应用
遗传算法（Genetic Algorithm 简称GA）起源于对 生物系统所进行的计算机模拟研究，是由一种基于生 物遗传和进化机制的适合于复杂系统优化的自适应概 率优化算法。 特点：
k 1
k 1
三、遗传算法应用
最大值运行结果：
源代码请见本目： exp12_1_2.m
三、遗传算法应用
最小值运行结果：
源代码请见本目： exp12_1_2.m
四、案例应用
建模案例：交巡警服务平台的设置与调度
对于重大突发事件，需要调度全区20个交巡警服务 平台的警力资源，对进出该区的13条交通要道实现快速 全封锁。实际中一个平台的警力最多封锁一个路口，请 给出该区交巡警服务平台警力合理的调度方案。
最后，交叉划分点之间的部分 c1(329|7154|86) c2(923|1856|74)
然后，双亲中划分点中间的 部分复制到后代中： c1(×××|7154|××) c2(×××|1856|××)
四、案例应用
建模案例：交巡警服务平台的设置与调度
各子代种群最优解
交通要道封锁调度优化过程
18
16
14
x

a

ba 2n 1
n k 1
bk
2k 1
精度为： b a
染色体编码（chromosome coding）与解码（decode）
普通的二进制编码方式可能具有较大的汉明 （Hamming）距离，也称作汉明悬崖。
例如：当原始值x为15和16时，它的5位二进制表示为01111 和10000，此时改变了二进制编码的所有位。
原始值
5
6
7
8
9
二进制码 00101 00111 00110 00101 00111 00100 01000 01100 01001 01101
原始值
10
11
12
13
14
二进制码 01010 01111 01011 01110 01100 01010 01101 01011 01110 01001
原始值
四、案例应用
建模案例：交巡警服务平台的设置与调度
假设已知 m 个交巡警服务平台到 n 个待封锁路口的时间为
T tij mn ，若安排第 i 个平台去封锁第 zi 个路口，则将其顺序排列
为分配方案：F z1z2 L zm ，其中1 zi m ，且 i j 有 zi z j 。