遗传算法的实现技术
21/20
符点数编码方法:指个体的每个基因值用某一 范围内的一个浮点数来表示个体的编码长度等于 其决策变量的个数，个体变量的长度等于去决策 变量的真实值，所以也叫真值编码方法 . 符号编码方法是指个体染色体编码串中的基 因值取自一个无数值含义，而只有代码含义的符 号集。这个符号集可以是一个字母表，如 { A, B, C, D, …} ；也可以是一个数宇序号表，如 { 1, 2, 3, 4, 5, …} ；还可以是一个代码表，如 { Al, A2, A3, A4, A5, … } 等等。
遗传算法基本概念与原理
8/20
遗传算法的基本思想正是基于模仿生物 界遗传学的遗传过程．它把问题的参数用 基因代表，把问题的解用染色体代表（在 计算机里用二进制码表示），从而得到一 个由具有不同染色体的个体组成的群体． 这个群体在问题特定的环境里生存竞争， 适者有最好的机会生存和产生后代．后代 随机化地继承了父代的最好特征，并也在 生存环境的控制支配下继续这一过程。
变异
例如,设染色体 s=11001101 将其第三位上的0变为1, 即
16/20
就是改变染色体某个(些)位上的基因。
s=11001101 →11101101= s′。 s′也可以看做是原染色体s的子代染色体。
遗传算法基本概念与原理
生成初始种群 计算适应度 终止 ? 选择-复制
17/20
结束
交叉
变异 遗传算法基本流程框图 生成新一代种群
Matlab遗传算法GUI求函数最大值
函数：
30/20
f ( x ) x sin(10 x ) 2.0
4 3.5 3 2.5 2 1.5 1 0.5 0 -1
x [ 1, 2]
-0.5
0
0.5
1
1.5
2
Matlab遗传算法GUI求函数最大值
31/20
步骤： 首先编写目标函数的M文件并以文件名myfun存盘。 function y=myfun(x) if x(:,1)<=2&x(:,1)>=-1 y=-(x*sin(10*pi*x)+2.0); else y=0 end 然后，在MATLAB工作窗口 >> gatool 打开遗传算法的GUI，在“fitness function”窗口输入 @myfun，在“number of variables”窗口输入变量数目1 。然后，单击“start”运行遗传算法，得到如下图结果。
遗传算法提供了一种求解复杂系统问题的通用框架，它
5/20
不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以
GA在函数优化，组合优化、生产调度问题、自动控制、机器人
学、图象处理、人工生命、遗传编码和机器学习等方面获得了广 泛的运用。从遗传算法的理论和技术两方面概述目前的研究现状；
描述遗传算法的主要特点、基本原理；应用遗传算法来解决函数
遗传算法基本概念与原理
选择-复制
14/20
通常做法是：对于一个规模为 N
的种群 S ,按每个染色体 x i ∈ S 的选择概率 P ( x i )所
决定的选中机会, 分 N 次从 S 中随机选定 N 个染色
体, 并进行复制。 这里的选择概率P(xi)的计算公式 为
P ( xi ) f ( xi )
研究一些遗 传算法的基 本实现技术， 如编码方法， 适应度函数， 选择算子， 交叉算子， 变异算子等
应用遗传算 法来解决几 个函数优化 问题以及用 MATLAB编 程来实现遗 传算法解决 函数优化的 实例
对整个毕业 设计进行全 面的总结， 提出本人对 设计过程中 各个方面的 看法、建议 与心得体会。
遗传算法基本概念与原理
序号 遗传学概念 遗传算法概念 数学概念
9/20
1
2 3 4 5 6 7 8 9 10 11 12 13
个体
群体 染色体 基因 基因位 适应值 种群 选择 交叉 交叉概率 变异 变异概率 进化、 适者生存
要处理的基本对象、结构
个体的集合 个体的表现形式 染色体中的元素 某一基因在染色体中的位置 个体对于环境的适应程度，或在环境压力下的 生存能力 被选定的一组染色体或个体 从群体中选择优胜的个体，淘汰劣质个体的操 作 一组染色体上对应基因段的交换 染色体对应基因段交换的概率（可能性大小） 染色体水平上基因变化 染色体上基因变化的概率（可能性大小） 个体进行优胜劣汰的进化，一代又一代地优化
遗传算法的实现技术
26/20
具体操作过程： （1）找出当前群体中适应度最高的个体 和适应度最低的个体。 （2）若当前群体中最佳个体的适应度比 总的迄今为止的最好个体的适应度还高， 则以当前种群中的最佳个体作为新的迄今 为止的最好个体。 （3）用迄今为止的最好个体替换掉当 前群体中的最差个体。
遗传算法的实现技术
11/20
2. 适应度与适应度函数 ● 适应度(fitness)就是借鉴生物个体对环 境的适应程度,而对问题中的个体对象所设 计的表征其优劣的一种测度。 ● 适应度函数(fitness function)就是问题 中的全体个体与其适应度之间的一个对应 关系该函数就是遗传算法中指导搜索的评 价函数。
也就是可行解
被选定的一组可行解 可行解的编码 编码中的元素 元素在编码中的位置 可行解所对应的适应函数值 根据入选概率定出的一组可行解 保留或复制适应值大的可行解，去掉小的 可行解 根据交叉原则产生的一组新解 闭区间[0,1]上的一个值，一般为 0.65~0.90 编码的某些元素被改变 开区间(0,1)内的一个值, 一般为 0.001~0.01 目标函数取到最大值，最优的可行解
遗传算法及其应用
姓 专
名：车少帅 业：信息与计算科学
指导教师：武 斌
论文章节
研究目的与意义 遗传算法的基本概念与原理 遗传算法的实现技术
2/20
遗传算法求解函数优化问题
结论
论文主要工作
第1章 第2章 第3章 结论
3/20
认识遗传算法 的基本概念， 个体与种群、 适应度与适应 度函数、染色 体与基因、选 择、交叉、变 异等概念，掌 握基本遗传算 法基本原理与 步骤
优化、组合优化等方面的案例。
论文研究背景、目的与意义 主要内容： 认识遗传算法的基本概念，掌
6/20
握基本步骤。
学习基本实现技术， 应用遗传算 法来解决函数优化问题。
遗传算法基本概念与原理
7/20
遗传算法是模拟达尔文的遗传选择和 自然淘汰的生物进化过程的计算模型，它 是由美国Michigan大学的J.Holland教授于 1975年首先提出的．遗传算法作为一种新 的全局优化搜索算法，以其简单通用、鲁 棒性强、适于并行处理及应用范围广等显 著特点，奠定了它作为21世纪关键智能计 算之一的地位。
遗传算法的实现技术
20/20
编码方法 : 二进制编码方法是遗传算法中最常用的一种 编码方法，它使用的编码符号集是由二进制符号0 和1组成的二值符号集，它所构成的个体基因型是 一个二进制编码符号串。 格雷码，连续的两个整数所对应的编码值之 间只有一个码位不相同。格雷码有这样一个特点 ：任意两个整数的差是这两个整数所对应的海明 距离。这个特点是遗传算法中使用格雷码进行个 体编码的主要原因。
遗传算法基本概念与原理
19/的选中机会，每 次从S中随机选定1个个体并将其染色体复制，共 做N次，然后将复制所得的N个染色体组成群体S1 ；
步6 按交叉率Pc所决定的参加交叉的染色体 数c，从S1中随机确定c个染色体，配对进行交叉 操作，并用产生的新染色体代替原染色体，得群 体 S 2；

N
f (x j )
j 1
遗传算法基本概念与原理
交叉 就是互换两个染色体某些位上的基因。 例如, 设染色体 s1=01001011,
15/20
s2=10010101,
交换其后4位基因, 即
s1′=01000101,
s2′=10011011
可以看做是原染色体s1和s2的子代染色体。
遗传算法基本概念与原理
遗传算法基本概念与原理
12/20
3. 染色体与基因 染色体（chromosome）就是问题中个体 的某种字符串形式的编码表示。字符串中 的字符也就称为基因（gene）。 例如： 个体 染色体 9 ---1001 （2，5，6）---- 010 101 110
遗传算法基本概念与原理
13/20
4. 遗传操作 亦称遗传算子(genetic operator)，就 是关于染色体的运算。遗传算法中有三种 遗传操作: 选择-复制,交叉(亦称交换、交 配或杂交),变异(亦称突变)。
遗传算法的实现技术
23/20
选择算子 : 选择算子（也叫复制算子Reproduction Operator）来对群体中的个体进行优胜劣 汰操作：适应度较高的个体被遗传到下一 代的概率较大；适应度较低的个体被遗传 到下一代的概率较小。选择操作建立在对 个体的适应度进行评价的基础上。选择的 主要目的为了避免基因缺失、提高全局收 敛性和计算效率。
遗传算法的实现技术
22/20
适应度函数 : 适应度较高的个体遗传到下一代的概率就相对大一 些；而适应度较低的个体遗传到下一代的概率就 相对较小一些。度量个体适应度的函数就称为适 应度函数。 根据个体的适应值，就可决定在此环境下的生存能 力。个体适应度大小决定该个体被遗传到下一代 群体中的概率。遗传算法仅使用所求问题的目标 函数值就可以得到下一步的有关搜索信息。目标 函数值的使用是通过评价个体适应度来体现的。
单点交叉运算 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000