第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势.

Presentation on theme: "第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势."— Presentation transcript:

1 第 4 章 基于遗传算法的随机优化搜索 4.1 基本概念 4.2 基本遗传算法 4.3 遗传算法应用举例 4.4 遗传算法的特点与优势

2 4.1 基本概念 1. 个体与种群 ● 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 ● 种群 (population) 就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。

3 2. 适应度与适应度函数 ● 适应度 (fitness) 就是借鉴生物个体对环境的 适应程度, 而对问题中的个体对象所设计的 表征其优劣的一种测度。 ● 适应度函数 (fitness function) 就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。

4 3. 染色体与基因 染色体（ chromosome ）就是问题中个体的 某种字符串形式的编码表示。字符串中的字符 也就称为基因（ gene ）。 例如： 个体 染色体 9 ---- 1001 （ 2 ， 5 ， 6 ） ---- 010 101 110

5 4. 遗传操作 亦称遗传算子 (genetic operator) ，就是关 于染色体的运算。遗传算法中有三种遗传操作 : ● 选择 - 复制 (selection-reproduction) ● 交叉 (crossover ，亦称交换、交配或杂交 ) ● 变异 (mutation ，亦称突变 )

6 选择 - 复制 通常做法是：对于一个规模为 N 的种群 S, 按每个染色体 x i ∈ S 的选择概率 P(x i ) 所决定 的选中机会, 分 N 次从 S 中随机选定 N 个染色体, 并 进行复制。 这里的选择概率 P(x i ) 的计算公式为

7 交叉 就是互换两个染色体某些位上的基因。 s 1 ′=01000101, s 2 ′=10011011 可以看做是原染色体 s 1 和 s 2 的子代染色体。 例如, 设染色体 s 1 =01001011, s 2 =10010101, 交换其后 4 位基因, 即

8 变异 就是改变染色体某个 ( 些 ) 位上的基因。 例如, 设染色体 s=11001101 将其第三位上的 0 变为 1, 即 s=11001101 →11101101= s′ 。 s′ 也可以看做是原染色体 s 的子代染色体。

9 4.2 基本遗传算法 遗传算法基本流程框图 生成初始种群 计算适应度 选择 - 复制 交叉 变异 生成新一代种群 终止 ? 结束

10 算法中的一些控制参数： ■ 种群规模 ■ 最大换代数 ■ 交叉率 (crossover rate) 就是参加交叉运算的染 色体个数占全体染色体总数的比例，记为 P c, 取 值范围一般为 0.4 ～ 0.99 。 ■ 变异率 (mutation rate) 是指发生变异的基因位 数所占全体染色体的基因总位数的比例，记为 P m ，取值范围一般为 0.0001 ～ 0.1 。

11 基本遗传算法 步 1 在搜索空间 U 上定义一个适应度函数 f(x) ，给定种群规模 N ，交叉率 P c 和变异率 P m ， 代数 T ； 步 2 随机产生 U 中的 N 个个体 s 1, s 2, …, s N ， 组成初始种群 S={s 1, s 2, …, s N } ，置代数计数 器 t=1 ； 步 3 计算 S 中每个个体的适应度 f() ； 步 4 若终止条件满足，则取 S 中适应度最 大的个体作为所求结果，算法结束。

12 步 5 按选择概率 P(x i ) 所决定的选中机会， 每次从 S 中随机选定 1 个个体并将其染色体复制， 共做 N 次，然后将复制所得的 N 个染色体组成 群体 S 1 ； 步 6 按交叉率 P c 所决定的参加交叉的染色 体数 c ，从 S 1 中随机确定 c 个染色体，配对进行 交叉操作，并用产生的新染色体代替原染色体， 得群体 S 2 ；

13 步 7 按变异率 P m 所决定的变异次数 m ，从 S 2 中随机确定 m 个染色体，分别进行变异操作，并 用产生的新染色体代替原染色体，得群体 S 3 ； 步 8 将群体 S 3 作为新一代种群，即用 S 3 代替 S ， t = t+1 ，转步 3 ；

14 4.3 遗传算法应用举例 例 4.1 利用遗传算法求解区间［ 0,31 ］上的 二次函数 y=x 2 的最大值。 y=x2y=x2 31 X Y

15 分析 原问题可转化为在区间［ 0, 31 ］中搜索能 使 y 取最大值的点 a 的问题。那么，［ 0, 31 ］ 中 的点 x 就是个体, 函数值 f(x) 恰好就可以作为 x 的 适应度，区间［ 0, 31 ］就是一个 ( 解 ) 空间 。这 样, 只要能给出个体 x 的适当染色体编码, 该问 题就可以用遗传算法来解决。

16 解 (1) 设定种群规模, 编码染色体，产生初始种 群。 将种群规模设定为 4 ；用 5 位二进制数编码染 色体；取下列个体组成初始种群 S 1 : s 1 = 13 (01101), s 2 = 24 (11000) s 3 = 8 (01000), s 4 = 19 (10011) (2) 定义适应度函数, 取适应度函数： f (x)=x 2

17 (3) 计算各代种群中的各个体的适应度, 并 对其染色体进行遗传操作, 直到适应度最高的个 体 ( 即 31 （ 11111 ） ) 出现为止。

18 首先计算种群 S 1 中各个体 s 1 = 13(01101), s 2 = 24(11000) s 3 = 8(01000), s 4 = 19(10011) 的适应度 f (s i ) 。 容易求得 f (s 1 ) = f(13) = 13 2 = 169 f (s 2 ) = f(24) = 24 2 = 576 f (s 3 ) = f(8) = 8 2 = 64 f (s 4 ) = f(19) = 19 2 = 361

19 再计算种群 S 1 中各个体的选择概率。 选择概率的计算公式为 由此可求得 P(s 1 ) = P(13) = 0.14 P(s 2 ) = P(24) = 0.49 P(s 3 ) = P(8) = 0.06 P(s 4 ) = P(19) = 0.31

20 赌轮选择示意 s 4 0.31 s 2 0.49 s 1 0.14 s 3 0.0 6 ● 赌轮选择法

21 在算法中赌轮选择法可用下面的子过程来模拟 : ① 在［ 0, 1 ］区间内产生一个均匀分布的随机 数 r 。 ② 若 r≤q 1, 则染色体 x 1 被选中。 ③ 若 q k-1 <r≤q k (2≤k≤N), 则染色体 x k 被选中。 其 中的 q i 称为染色体 x i (i=1, 2, …, n) 的积累概率, 其 计算公式为

22 选择 - 复制 设从区间［ 0, 1 ］中产生 4 个随机数如下 : r 1 = 0.450126, r 2 = 0.110347 r 3 = 0.572496, r 4 = 0.98503 染色体 适应度选择概率积累概率选中次数 s 1 =01101 169 0.14 1 s 2 =11000 576 0.49 0.63 2 s 3 =01000 64 0.06 0.69 0 s 4 =10011 361 0.31 1.00 1

23 于是，经复制得群体： s 1 ’ =11000 （ 24 ）, s 2 ’ =01101 （ 13 ） s 3 ’ =11000 （ 24 ）, s 4 ’ =10011 （ 19 ）

24 交叉 设交叉率 p c =100% ，即 S 1 中的全体染色体都 参加交叉运算。 设 s 1 ’ 与 s 2 ’ 配对， s 3 ’ 与 s 4 ’ 配对。分别交换后 两位基因，得新染色体： s 1 ’’ =11001 （ 25 ）, s 2 ’’ =01100 （ 12 ） s 3 ’’ =11011 （ 27 ）, s 4 ’’ =10000 （ 16 ）

25 变异 设变异率 p m =0.001 。 这样，群体 S 1 中共有 5 × 4 × 0.001=0.02 位基因可以变异。 0.02 位显然不足 1 位，所以本轮遗传操作不 做变异。

26 于是，得到第二代种群 S 2 ： s 1 =11001 （ 25 ）, s 2 =01100 （ 12 ） s 3 =11011 （ 27 ）, s 4 =10000 （ 16 ）

27 第二代种群 S 2 中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s 1 =11001 625 0.36 1 s 2 =01100 144 0.08 0.44 0 s 3 =11011 729 0.41 0.85 2 s 4 =10000 256 0.15 1.00 1

28 假设这一轮选择 - 复制操作中，种群 S 2 中的 4 个染色体都被选中，则得到群体： s 1 ’ =11001 （ 25 ）, s 2 ’ = 01100 （ 12 ） s 3 ’ =11011 （ 27 ）, s 4 ’ = 10000 （ 16 ） 做交叉运算，让 s 1 ’ 与 s 2 ’ ， s 3 ’ 与 s 4 ’ 分别交换后 三位基因，得 s 1 ’’ =11100 （ 28 ）, s 2 ’’ = 01001 （ 9 ） s 3 ’’ =11000 （ 24 ）, s 4 ’’ = 10011 （ 19 ） 这一轮仍然不会发生变异。

29 于是，得第三代种群 S3 ： s 1 =11100 （ 28 ）, s 2 =01001 （ 9 ） s 3 =11000 （ 24 ）, s 4 =10011 （ 19 ）

30 第三代种群 S 3 中各染色体的情况 染色体 适应度选择概率积累概率 估计的 选中次数 s 1 =11100 784 0.44 2 s 2 =01001 81 0.04 0.48 0 s 3 =11000 576 0.32 0.80 1 s 4 =10011 361 0.20 1.00 1

31 设这一轮的选择 - 复制结果为： s 1 ’ =11100 （ 28 ）, s 2 ’ =11100 （ 28 ） s 3 ’ =11000 （ 24 ）, s 4 ’ =10011 （ 19 ） 做交叉运算，让 s 1 ’ 与 s 4 ’ ， s 2 ’ 与 s 3 ’ 分别交换后 两位基因，得 s 1 ’’ =11111 （ 31 ）, s 2 ’’ =11100 （ 28 ） s 3 ’’ =11000 （ 24 ）, s 4 ’’ =10000 （ 16 ） 这一轮仍然不会发生变异。

32 于是，得第四代种群 S 4 ： s 1 =11111 （ 31 ）, s 2 =11100 （ 28 ） s 3 =11000 （ 24 ）, s 4 =10000 （ 16 ）

33 显然，在这一代种群中已经出现了适应度最 高的染色体 s 1 =11111 。于是，遗传操作终止，将 染色体 “ 11111 ” 作为最终结果输出。 然后，将染色体 “11111” 解码为表现型，即 得所求的最优解： 31 。 将 31 代入函数 y=x 2 中，即得原问题的解，即函 数 y=x 2 的最大值为 961 。

34 Y Y y=x2y=x2 8 13 19 24 X 第一代种群及其适应度 y=x2y=x2 12 16 25 27 X Y 第二代种群及其适应度 y=x2y=x2 9 19 24 28 X Y 第三代种群及其适应度 y=x2y=x2 16 24 28 31 X 第四代种群及其适应度

35 例 4.2 用遗传算法求解 TSP 。 分析 由于其任一可能解 —— 一个合法的城市序 列，即 n 个城市的一个排列，都可以事先构造出 来。于是，我们就可以直接在解空间（所有合 法的城市序列）中搜索最佳解。这正适合用遗 传算法求解。

36 （ 1 ）定义适应度函数 我们将一个合法的城市序列 s= （ c 1, c 2, …, c n, c n+1 ） (c n+1 就是 c 1 ) 作为一个个体。这个序列中相邻两城之间 的距离之和的倒数就可作为相应个体 s 的适应度，从 而适应度函数就是

37 （ 2 ）对个体 s= （ c 1, c 2, …, c n, c n+1 ）进行编码。 但对于这样的个体如何编码却不是一件直截了 当的事情。因为如果编码不当，就会在实施交 叉或变异操作时出现非法城市序列即无效解。 例如，对于 5 个城市的 TSP ，我们用符号 A 、 B 、 C 、 D 、 E 代表相应的城市，用这 5 个符号的序列 表示可能解即染色体。

38 然后进行遗传操作。设 s 1 = （ A, C, B, E, D, A ）， s 2 = （ A, E, D, C, B, A ） 实施常规的交叉或变异操作，如交换后三位，得 s 1 ’ = （ A,C,B,C,B,A ）， s 2 ’ = （ A,E,D,E,D,A ） 或者将染色体 s1 第二位的 C 变为 E ，得 s 1 ’’ = （ A, E, B, E, D, A ） 可以看出，上面得到的 s 1 ’ ， s 2 ’ 和 s 1 ’’ 都是 非法的城市序列。

39 为此，对 TSP 必须设计合适的染色体和 相应的遗传运算。 事实上，人们针对 TSP 提出了许多编码 方法和相应的特殊化了的交叉、变异操作， 如顺序编码或整数编码、随机键编码、部分 映射交叉、顺序交叉、循环交叉、位置交叉、 反转变异、移位变异、互换变异等等。从而 巧妙地用遗传算法解决了 TSP 。

40 4.4 遗传算法的特点与优势 ◆遗传算法的主要特点 —— 遗传算法一般是直接在解空间搜索, 而 不像图搜索那样一般是在问题空间搜索, 最后 才找到解。 —— 遗传算法的搜索随机地始于搜索空间 的一个点集, 而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点, 所以遗传算法 是一种随机搜索算法。

41 —— 遗传算法总是在寻找优解, 而不像图搜 索那样并非总是要求优解, 而一般是设法尽快找 到解, 所以遗传算法又是一种优化搜索算法。 —— 遗传算法的搜索过程是从空间的一个点集 ( 种群 ) 到另一个点集 ( 种群 ) 的搜索, 而不像图搜 索那样一般是从空间的一个点到另一个点地搜 索。 因而它实际是一种并行搜索, 适合大规模 并行计算, 而且这种种群到种群的搜索有能力跳 出局部最优解。

42 —— 遗传算法的适应性强, 除需知适应度函 数外, 几乎不需要其他的先验知识。 —— 遗传算法长于全局搜索, 它不受搜索 空间的限制性假设的约束, 不要求连续性, 能以 很大的概率从离散的、多极值的、 含有噪声的 高维问题中找到全局最优解。

43 ◆遗传算法的应用  遗传算法在人工智能的众多领域便得到了广泛 应用。例如，机器学习、聚类、控制（如煤气 管道控制）、规划（如生产任务规划）、设计 （如通信网络设计、布局设计）、调度（如作 业车间调度、机器调度、运输问题）、配置 （机器配置、分配问题）、组合优化（如 TSP 、 背包问题）、函数的最大值以及图像处理和信 号处理等等。

44  另一方面，人们又将遗传算法与其他智能 算法和技术相结合，使其问题求解能力得 到进一步扩展和提高。例如，将遗传算法 与模糊技术、神经网络相结合，已取得了 不少成果。

45 对遗传算法的进一步研究将涉及 到模式定理和隐性、并行性等内容。 有兴趣的同学可参阅有关专著。