遗传算法与群智能优 化算法简介
主要内容
智能优化算法简介
问题的NP-完全特性 常用的智能优化算法
遗传算法-Genetic Algorithm 群智能优化算法
蚁群优化算法-Ant Colony Optimization 粒子群优化算法-Particle Swarm Optimization ...
2020/5/14
北京交通大学计算机与信息技术学院
9
遗传算法(Genetic Algorithm)
1975年，Holland出版了著名的《Adaptation in Natural and Artificial Systems》，标志着遗传算法的诞生。
在一定程度上解决了传统的基于符号处理机制的人工智能 方法在知识表示、信息处理和解决组合爆炸等方面所遇到 的困难
2020/5/14
北京交通大学计算机与信息技术学院
2
智能优化算法简介
20世纪80年代以来，一些优化算法得到发展
GA、EP、ACO、PSO、SA、TS、ANN及混合的优化策略等
基本思想：模拟或揭示某些自然现象或过程 为用传统的优化方法难以解决的NP-完全问题提供了有效
的解决途径 由于算法构造的直观性与自然机理，因而通常被称作智能
时 间 1s 24s 10m 4.3h 4.9d 136.5d 10.8y 325y
2020/5/14
北京交通大学计算机与信息技术学院

2020/5/14
北京交通大学计算机与信息技术学院
5
2020/5/14
北京交通大学计算机与信息技术学院
6
2020/5/14
北京交通大学计算机与信息技术学院
7
智能优化算法简介 -常用的智能优化算法
2020/5/14
北京交通大学计算机与信息技术学院
8
主要内容
智能优化算法简介
问题的NP-完全特性 常用的智能优化算法
遗传算法-Genetic Algorithm 群智能优化算法
蚁群优化算法-Ant Colony Optimization 粒子群优化算法-Particle Swarm Optimization …
2020/5/14
北京交通大学计算机与信息技术学院
10
遗传算法-简单遗传算法
简单遗传算法（Simple Genetic Algorithms，SGA），又称 基本遗传算法、标准遗传算法
基于二进制编码，是最基本的遗传算法，其遗传进化操作 过程简单、容易理解，是其他遗传算法的雏形和基础
三种基本操作
选择：通常用比例选择，即选择概率正比于个体的适配值，使适 配值高的个体在下一代中被选中的概率大，提高种群平均适配值
交叉：交换两父代个体的部分信息构成后代个体，使得后代继承 父代的有效模式，有助于产生优良个体
变异：随机改变个体中的某些基因，有助于增加种群多样性，避 免早熟收敛
2020/5/14
北京交通大学计算机与信息技术学院
优化算法（intelligent optimization algorithms），或现代启 发式算法（meta-heuristic algorithms） [智能优化算法及其应用，王凌，清华大学出版社，2001]
2020/5/14
北京交通大学计算机与信息技术学院
3
智能优化算法简介 - 问题的NP-完全特性
基于“适者生存”原则，是并行优化算法，其自组织、自 适应、自学习及群体进化的能力适合大规模复杂优化问题
将问题求解表示为“染色体”，通过选择（selection）、 交叉（crossover）和变异（mutation）操作的迭代，实现 种群的演化，最后终收敛到“最适应环境”的个体，从而 求得问题的最优解（满意解）
求解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
11
随机产生N个个体构成初始种群P(0), 令k=0
对种群P(k)中各个体进行评价
终止？ y n
令m=0
输出优化结果
n
y
m<N？
从种群中选择两个体
rand()>pc
y
n
将所选个体作为临时个体
对选中个体执行 交叉操作生成两 个临时个体
对临时个体以概率pm执行变异操作，产生 两个新个体并放入P(k+1)中，令m=m+2
2020/5/14
北京交通大学计算机与信息技术学院
12
遗传算法-选择
适者生存：适应值高的个体的生存概率大，即被选中用来
繁殖下一代的概率大。
适应值： f (xi )
第i个个体的选择概率：
常用的选择方法有： 比例选择（轮盘选择）
pi
f (xi ) f (xj)
基于排名的选择：由好到坏排序，然后以j 一定方式给
二进制编码的GA通常采用单点交叉和多点交叉。
单点交叉：随机选定一个交叉位置，然后对换交叉点后的子串。
1011 001
0010 110
多点交叉：随机选择多个位置，然后对换相应子串。两点交叉：
10 110 01 00 101 10
2020/5/14
北京交通大学计算机与信息技术学院
每一个体分配选择概率（线性、产非生线随性机等数方：式，[要0,求1]
好的个体被选择的概率大，所有选个择体满所足分下配式的的概第率i个之
和锦为标1赛）选择：在父代个体随机个选体k个：，ij11然p后j 选最好ji 1的p。j
2020/5/14
北京交通大学计算机与信息技术学院
13
遗传算法-交叉
用于组合出新的个体，在解空间中进行有效搜索，同时降 低对有效模式的破坏概率
遗传算法（Genetic Algorithm，GA） 演化规划（Evolutionary Programming，EP） 蚁群优化算法（Ant Colony Optimization，ACO） 粒子群优化算法（Particle Swarm Optimization，PSO） 模拟退火算法（Simulated Annealing，SA） 禁忌搜索算法（Tabu Search，TS） 人工神经网络（Artificial Neural Network，ANN） …