Holland为解释基于二进制编码的基本遗传算法建立了模式 定理和隐含并行性定理 模式定理的含义：在SGA中，阶次低、定义长度短且适配 值超过平均适配值的模式在种群中的数目的期望值以指数 级递增（遗传算法存在找到全局最优解的可能性） 隐含并行性定理：遗传算法所处理的有效模式的总数约与 群体规模的三次方成正比
2015-4-20
北京交通大学计算机与信息技术学院
8
主要内容

智能优化算法简介
问题的NP-完全特性 常用的智能优化算法

遗传算法-Genetic Algorithm
群智能优化算法
蚁群优化算法-Ant
Colony Optimization Swarm Optimization
粒子群优化算法-Particle …
遗传算法与群智能优 化算法简介
主要内容

智能优化算法简介
问题的NP-完全特性 常用的智能优化算法

遗传算法-Genetic Algorithm
群智能优化算法
蚁群优化算法-Ant
Colony Optimization Swarm Optimization
粒子群优化算法-Particle ...
0.492 0.055 0.309 1.000
根据遗传操作生成下一代种群

假设选择的两对父代个体分别为1和2，2和4
2015-4-20
北京交通大学计算机与信息技术学院
21

交叉过程（假设使用单点交叉，交叉概率pc = 0.95） 位串1、2： 0 1 1 | 0 1 110|00 位串2、4： 1 1 0 | 0 0 100|11 011|00 110|01 110|11 100|00
北京交通大学计算机与信息技术学院
7
智能优化算法简介 -常用的智能优化算法

遗传算法（Genetic Algorithm，GA）
演化规划（Evolutionary Programming，EP）
蚁群优化算法（Ant Colony Optimization，ACO） 粒子群优化算法（Particle Swarm Optimization，PSO） 模拟退火算法（Simulated Annealing，SA） 禁忌搜索算法（Tabu Search，TS） 人工神经网络（Artificial Neural Network，ANN） …
p2' = [5 7 1 6 2 8 9 3 4]
Non-ABEL群置换操作产生后代方式简单，过分打乱了父串，不利 于保留有效模式

次序交叉（OX）

首先随机确定两个交叉位置，并交换交叉点之间的片段，并从第2 交叉位置起在原先父代个体中删除将从另一父代个体交换过来的 基因，然后从第2交叉位置后开始填入剩余基因。 p1' = [4 3 5 | 1 8 7 6 | 9 2] p = [2 6 4 | 7 3 5 8 | 9 1]
15
2015-4-20
北京交通大学计算机与信息技术学院
遗传算法-交叉（续）

Non-ABEL交叉：p1'[i] = p1[p2[i]], p2'[i] = p2[p1[i]]
p1 = [2 6 4 7 3 5 8 9 1]
p2 = [4 5 2 1 8 7 6 9 3]

p1' = [7 3 6 2 9 8 5 1 4]



将问题求解表示为“染色体”，通过选择（selection）、 交叉（crossover）和变异（mutation）操作的迭代，实现 种群的演化，最后终收敛到“最适应环境”的个体，从而 求得问题的最优解（满意解）
北京交通大学计算机与信息技术学院 10
2015-4-20
遗传算法-简单遗传算法

简单遗传算法（Simple Genetic Algorithms，SGA），又称 基本遗传算法、标准遗传算法 基于二进制编码，是最基本的遗传算法，其遗传进化操作 过程简单、容易理解，是其他遗传算法的雏形和基础
1
p2 = [4 5 2 | 1 8 7 6 | 9 3]
2015-4-20
p2' = [2 1 6 | 7 3 5 8 | 9 4]
16
北京交通大学计算机与信息技术学院
遗传算法-交叉（续）

单位置次序交叉（C1）

类似于OX。选择一个交叉位置，保留父代个体p1交叉位置前的基 因，并在另一父代个体p2中删除p1中保留的基因，将剩余基因填入 p1的交叉位置后来产生后代个体p1'。如父代个体同前，交叉位置 为4，则后代个体为p1' =[2 6 4 7 | 5 1 8 9 3]，p2' =[4 5 2 1 | 6 7 3 8 9]
2015-4-20
北京交通大学计算机与信息技术学院
2
智能优化算法简介

20世纪80年代以来，一些优化算法得到发展

GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等

基本思想：模拟或揭示某些自然现象或过程 为用传统的优化方法难以解决的NP-完全问题提供了有效 的解决途径 由于算法构造的直观性与自然机理，因而通常被称作智能 优化算法（intelligent optimization algorithms），或现代启 发式算法（meta-heuristic algorithms） [智能优化算法及其应用，王凌，清华大学出版社，2001]
2015-4-20
北京交通大学计算机与信息技术学院
9
遗传算法(Genetic Algorithm)

1975年，Holland出版了著名的《Adaptation in Natural and Artificial Systems》，标志着遗传算法的诞生。 在一定程度上解决了传统的基于符号处理机制的人工智能 方法在知识表示、信息处理和解决组合爆炸等方面所遇到 的困难 基于“适者生存”原则，是并行优化算法，其自组织、自 适应、自学习及群体进化的能力适合大规模复杂优化问题
19
遗传算法-函数优化示例

求整数函数f(x) = x2在区间[0, 31]上取最大值的点
用基本遗传算法பைடு நூலகம்解

问题是求最大值点，目标函数可取为x2。 用5位的二进制位串表示个体，对应区间[0, 31]上的32个整数。随 机地选取4个位串作为初始种群，位串与对应的整数如下： 01101 11000 01000 10011 13 24 8 19
f (x )
j
i
p p 锦标赛选择：在父代个体随机选k个，然后选最好的。
j 1 j j 1 j
每一个体分配选择概率（线性、非线性等方式，要求 [0,1] 产生随机数： 好的个体被选择的概率大，所有个体所分配的概率之 选择满足下式的第i个 i 个体：i 1 和为1）


2015-4-20
北京交通大学计算机与信息技术学院
3
智能优化算法简介 - 问题的NP-完全特性

求解n个城市的TSP问题。

典型的组合优化问题，是NP-完全的
要准确求解该问题只能用枚举类的办法 要枚举的解的个数为(n - 1)!
例：n = 24，则要枚举的解的个数为：
23!=25,852,016,738,884,976,640,000
n 24
25
26
27
28
29
30
31
时 间 1s 24s 10m 4.3h 4.9d 136.5d 10.8y 325y
2015-4-20
北京交通大学计算机与信息技术学院
4
2015-4-20
北京交通大学计算机与信息技术学院
5
2015-4-20
北京交通大学计算机与信息技术学院
6
2015-4-20


三种基本操作

选择：通常用比例选择，即选择概率正比于个体的适配值，使适 配值高的个体在下一代中被选中的概率大，提高种群平均适配值

交叉：交换两父代个体的部分信息构成后代个体，使得后代继承 父代的有效模式，有助于产生优良个体
变异：随机改变个体中的某些基因，有助于增加种群多样性，避 免早熟收敛
北京交通大学计算机与信息技术学院 11


循环交叉（CX）
2015-4-20
北京交通大学计算机与信息技术学院
18
遗传算法-变异

二进制或十进制

用另一种基因替换某一位置或某些位置上的基因

实数编码

采用扰动的方式：x‘ = x + ηξ，其中η为扰动幅度，ξ为扰动变量

组合优化

互换、逆序、插入等
2015-4-20
北京交通大学计算机与信息技术学院

变异过程（假设变异概率pm = 0.05，且此处无变异） 编号 1 2 3 4 总计 位串 01100 11001 11011 10000 参数值 12 25 27 16 目标函数值 144 625 729 256 1754
北京交通大学计算机与信息技术学院 22

评价第二代种群
2015-4-20
遗传算法-数学解释
多点交叉：随机选择多个位置，然后对换相应子串。两点交叉：
1 0 0 0
1 1 0 1 0 1
2015-4-20
北京交通大学计算机与信息技术学院
14
遗传算法-交叉（续）

实数编码的GA通常采用算术交叉：

双个体算术交叉：x1、x2为父代个体，α ∈(0, 1)为随机数
x1' = αx1 + (1 - α)x2 x2' = αx2 + (1 - α)x1 多个体算术交叉： x1, …, x2为父代个体; αi ∈(0, 1)且∑αi = 1