11
搜索示例：TSP问题
典型问题——旅行商问题（Traveling salesman
problem, TSP）
12
给定个城市和两两
1
2
城市之间的距离，要
求确定一条经过各城 1
8
3
市当且仅当一次的最
短路线。
3
10
2 4
12
TSP的搜索的困难
典型问题——旅行商问题（Traveling salesman problem, TSP） 计算复杂度：指数灾难
3
现代优化算法的特点
它们的共同特点：都是从任一解出发，按照 某种机制，以一定的概率在整个求解空间中探索 最优解。由于它们可以把搜索空间扩展到整个问 题空间，因而具有全局优化性能。
4
现代优化算法的特点
1)不依赖于初始条件； 2)不与求解空间有紧密关系,对解域无可微或连续的要求;
容易实现，求解稳健。 3)但收敛速度慢,能获得全局最优;适合于求解空间不知
城市 24 25 26 27 28
29
30 31
数
计算 1 24 10 4.3 4.9 136.5 10.8 325 时间 sec sec min hour day day year year
13
遗传算法(Genetic Algorithm) 进化算法(Evolutionary Algorithm)
33
二进制编码与解码
假设某一参数取值范围是[A, B]。我们用长度为 L的二进制编码串来表示该参数，将[A, B]等分成(2L-1) 个子部分，记每一个等分的长度为δ，则它能够产生 (2l)种不同的编码，
参数编码对应关系如下：δ = (B－A)／(2L－1)
00000000 … 00000000 = 0
28
生物进化理论和遗传学的基本知识
遗传学基本概念与术语 变异（mutation）：在细胞进行复制时可能以很小的
概率产生某些复制差错，从而使DNA发生某种变异， 产生出新的染色体，这些新的染色体表现出新的性状; 编码（coding）：表现型到基因型的映射； 解码（decoding）：从基因型到表现型的映射。
第8讲 MATLAB遗传算法工具箱
现代优化算法
现代优化算法 禁忌搜索算法 模拟退火算法 遗传算法 人工神经网络 蚁群算法 粒子群算法 混合算法
2
特点： • 基于客观世界中的一些自
然现象； • 建立在计算机迭代计算的
基础上； • 具有普适性，可解决实际
应用问题。
现代优化算法
现代优化算法又称智能优化算法或现代启 发式算法，是一种具有全局优化性能、通用性 强、且适合于并行处理的算法。这种算法一般 具有严密的理论依据,而不是单纯凭借专家经验， 理论上可以在一定的时间内找到最优解或近似 最优解。
23
生物进化理论和遗传学的基本知识
遗传学基本概念与术语 染色体（chromosome）：遗传物质的载体； 脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋
结构；
遗传因子（gene）：DNA或RNA长链结构中占有一定 位置的基本遗传单位；
24
生物进化理论和遗传学的基本知识
遗传学基本概念与术语 基因型（genotype）：遗传因子组合的模型； 表现型（phenotype）：由染色体决定性状的外部表现；
A
00000000 … 00000001 = 1
A+δ

…
…
11111111 … 11111111 = 2L-1
B
34
二进制编码与解码(续)
假设某一个个体的编码是：

X：xLxl-1xl-2…x2x1
则上述二进制编码对应的解码公式为(转化为十 进制形式)：
x

A

L i1
16
遗传算法(GA)
局部
全局
17
遗传算法(GA)
GA-----第0代
I am not at the top. My high is better!
We have a dream!!
I am at the top
Height is ...
18
I will continue
遗传算法(GA)
GA----第1代
New one Dead one
19
遗传算法(GA)
GA----第?代
Not at the top, Come Up!!!
20
遗传算法(GA)
GA----第N代
I am the BEST !!!
21
遗传算法(GA)
适者生存(Survival of the Fittest)
GA主要采用的进化规则是“适者生存” 较好的解保留，较差的解淘汰
xi 2i1

A

BA 2L 1
L i1
xi
2i1
35
符号编码方法举例
对TSP问题可以按一条回路城市的次序进行编码。 比如码串“1 3 4 5 6 7 8 2 9”表示从城市1开始，依次是城 市3,4,5,6,7,8,2,9，最后回到城市1。
一般情况是从城市w1开始，依次经过城市w2,……， wn， 最后回到城市w1，我们就有如下编码表示：
14
遗传算法(GA)
Darwin(1859): “物竟天择，适者生存” John Holland (university of Michigan, 1975)
《Adaptation in Natural and Artificial System》
遗传算法作为一种有效的工具，已广泛地应用于最 优化问题求解之中。
常用的遗传算子有选择、交叉、变异。 32
编码与解码
遗传算法把许多很复杂的应用问题, 化为简单的 位串形式的编码来表示. 编码: 将问题结构变换为位串形式编码表示的过程. 解码: 将位串形式的编码表示变换为原问题的结构的 过程,也叫译码,它是编码的反过程.
遗传算法最常用的编码方法的二进制编码。 除此之外，还有其他的编码方法，如：浮点数编码方 法, Gray(格雷，灰度)编码，符号编码等。
与自然界相似，遗传算法对求解问题的本身一无所知，它所需 要的仅是对算法所产生的每个染色体进行评价，并基于适应值 来选择染色体，使适应性好的染色体有更多的繁殖机会。
在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基 因的作用，随机产生一个体字符串的初始群体，每个个体给予 一个数值评价，称为适应度，取消低适应度的个体，选择高适 应度的个体参加操作。
的情况。 4)模拟退火算法和遗传算法等可应用于大规模、多峰多
态函数、含离散变量等全局优化问题;求解速度和质 量远超过常规方法。
5
常用的现代优化算法
遗传算法
Genetic Algorithm，简称GA
模拟退火算法
Simulated Annealing，简称SA
禁忌搜索算法
Tabu Search，简称TS ……
A：既然你是数学教授，那你帮我算这个题，今天是 个特殊日子：我三个儿子都在今天庆祝生日！那么你 能算出他们都有多大吗？ B：好，但你得跟我讲讲他们的情况。 A：好的，我给你一些提示，他们三个年龄之积是36. B：很好，但我还需要更多提示。
8
三个孩子的年龄(2)
A：他们三个年龄之和等于那幢房子的窗户个数。 A指着对面的一幢房子说。 B考虑了一下说，但是，我还有一点信息来解决你的这 个难题。 A：我的大儿子的眼睛是蓝色的。 B：哦，够了， B给出了正确的答案，即三个小孩的年龄。
遗传算法的基本思想
遗传算法先将搜索结构编码为字符串形式, 每个字符串结构被 称为个体。
然后对一组字符串结构(被称为一个群体)进行循环操作。每次 循环被称作一代,包括一个保存字符串中较优结构的过程和一个 有结构的、随机的字符串间的信息交换过程。
类似于自然进化，遗传算法通过作用于染色体上的基因寻找好 的染色体来求解问题。
w1 w2 …… wn 由于是回路，记wn+1= w1。 要注意w1,w2 ,……，wn是互不相同的。
36
遗传算法的基本机理——适应度函数
通过适应度函数来决定染色体的优劣程度,它体现 了自然进化中的优胜劣汰原则. 对于优化问题,适应度函数就是目标函数,要能够有 效地反映每一个染色体与问题最优解染色体之间的 差距.
第一个小 36 18 12
9
9
6
孩年龄
第二个小 1
2
3
4
2
6
孩年龄
第三个小 1
1
1
1
2
1
孩年龄
窗户数: 38 21 16 14 13 13
6
4
3
3
2
3
11 10
如果窗户数为38、21、16、14、11、10即可得出答案
B还需信息，即窗户数为13. 则可能为(9、2、2)或(6、6、1)
信息2:大儿子眼睛是蓝色的 得答案：(9、2、2)
1111111
1110111
25
生物进化理论和遗传学的基本知识
遗传学基本概念与术语 基因座（locus）：遗传基因在染色体中所占据的位置，
同一基因座可能有的全部基因称为等位基因（allele）； 个体（individual）：指染色体带有特征的实体； 种群（population）：个体的集合，该集合内个体数称
29
遗传算法的基本思想
遗传算法的基本思想
30
生物进化与遗传算法对应关系
生物进化
环境 适者生存
个体 染色体 基因 群体 种群 交叉 变异
31
遗传算法
适应度函数 适应函数值最大的解被保留的概率最大