几种智能算法的原理和应用介绍专题培训课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《几种智能算法的原理和应用介绍专题培训课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 智能 算法 原理 应用 介绍 专题 培训 课件
- 资源描述:
-
1、几种智能算法的原理几种智能算法的原理和应用介绍和应用介绍主要内容:主要内容:1. 1. 遗传算法遗传算法2. 2. 蚁群算法蚁群算法3. 3. 模拟退火算法模拟退火算法4. 4. 粒子群算法粒子群算法5. 5. 总结与体会总结与体会1. 遗传算法遗传算法1.1 1.1 遗传算法简介遗传算法简介1.2 1.2 遗传算法的基本思想遗传算法的基本思想1.3 1.3 遗传算法的基本操作遗传算法的基本操作1.4 1.4 遗传算法的构成要素遗传算法的构成要素1.5 1.5 遗传算法的操作步骤遗传算法的操作步骤1.6 1.6 遗传算法的特点遗传算法的特点1.7 1.7 遗传算法的应用领域遗传算法的应用领域1
2、.8 1.8 遗传算法的应用举例遗传算法的应用举例1.1 遗传算法简介遗传算法简介 遗传算法简称遗传算法简称GAGA(Genetic AlgorithmsGenetic Algorithms)是)是19621962年由美国年由美国MichiganMichigan大学的大学的HollandHolland教授提出的模拟自然界遗传机制和生物进教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。化论而成的一种并行随机搜索最优化方法。 遗传算法是以达尔文的遗传算法是以达尔文的自然选择学说自然选择学说为基础发展起来的。为基础发展起来的。自然选择学说自然选择学说包括以下三个方面:包括以
3、下三个方面: (1 1)遗传遗传:这是生物的普遍特征,亲代把生物信息交给子代,子代:这是生物的普遍特征,亲代把生物信息交给子代,子代总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳定存在。定存在。 (2 2)变异变异:亲代和子代之间以及子代的不同个体之间的差异,称为:亲代和子代之间以及子代的不同个体之间的差异,称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。 (3 3)生存斗争和适者生存生存斗争和适者生存:具有适应性变异的个体被保留下来,不:具有适
4、应性变异的个体被保留下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,性状逐渐逐渐与祖先有所不同,演变为新的物种。性状逐渐逐渐与祖先有所不同,演变为新的物种。1.2 遗传算法的基本思想遗传算法的基本思想 遗传算法将遗传算法将“优胜劣汰,适者生存优胜劣汰,适者生存”的生物进化原理引入优的生物进化原理引入优化参数形成的编码串联群体中,按所选择的适应度函数并通过遗化参数形成的编码串联群体中,按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使适适应度高的个体传中的复制、交叉及变异对个体进行筛选,使适适应度高
5、的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。遗传算法的算法简单,可并行处理,并能到到满足一定的条件。遗传算法的算法简单,可并行处理,并能到全局最优解。全局最优解。1.3 遗传算法的基本操作遗传算法的基本操作 遗传算法的基本操作主要有:遗传算法的基本操作主要有:复制复制、交叉交叉、变异变异。(1 1)复制(复制(Reproduction OperatorReproduction Operator
6、) 复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。 复制操作可以通过随机方法来实现。首先产生复制操作可以通过随机方法来实现。首先产生0101之间均匀分布的随之间均匀分布的随机数,若某串的复制概率为机数,若某串的复制概率为40%40%,则当产生的随机数在,则当产生的随机数在0.401.00.401.0之间时,之间时,该串被复制,否则被淘汰。该串被复制,否则被淘汰。1.3 遗传算法的基本操作遗传算法的基本操作(2
7、2)交叉(交叉(Crossover OperatorCrossover Operator) 复制操作能从旧种群中选择出优秀者,但不能创造新的染色体。而复制操作能从旧种群中选择出优秀者,但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象,通过两个染色体的交换组合,交叉模拟了生物进化过程中的繁殖现象,通过两个染色体的交换组合,来产生新的优良品种。来产生新的优良品种。 交叉的过程为:在匹配池中任选两个染色体,随机选择一点或多点交叉的过程为:在匹配池中任选两个染色体,随机选择一点或多点交换点位置;交换双亲染色体交换点右边的部分,即可得到两个新的染交换点位置;交换双亲染色体交换点右边的部分,即可
8、得到两个新的染色体数字串。色体数字串。 交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法,应用还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法,应用较广。它是指染色体切断点有一处,例:较广。它是指染色体切断点有一处,例:0101 0110011110 101100 :A1110 0010100101 001010 :B1.3 遗传算法的基本操作遗传算法的基本操作(3 3)变异变异(Mutation Operator)(Mutation Operator) 变异
9、运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变,它以很小的概率随机地改变遗传基因(表示染色体的符号串基因突变,它以很小的概率随机地改变遗传基因(表示染色体的符号串的某一位)的值。在染色体以二进制编码的系统中,它随机地将染色体的某一位)的值。在染色体以二进制编码的系统中,它随机地将染色体的某一个基因由的某一个基因由1 1变为变为0 0,或由,或由0 0变为变为1 1。 若只有选择和交叉,而没有变异,则无法在初始基因组合以外的空若只有选择和交叉,而没有变异,则无法在初始基因组合以外的空间进行搜索,使进化过程在早期就陷入局
10、部解而进入终止过程,从而影间进行搜索,使进化过程在早期就陷入局部解而进入终止过程,从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解,必须采响解的质量。为了在尽可能大的空间中获得质量较高的优化解,必须采用变异操作。变异操作如下所示:用变异操作。变异操作如下所示:1110 1 011011110 0 10110 :A1.4 遗传算法的构成要素遗传算法的构成要素 遗传算法的构成要素主要有:遗传算法的构成要素主要有:染色体编码方法染色体编码方法、个体适应度个体适应度评价评价、遗传算子遗传算子及及遗传算法的运行参数遗传算法的运行参数。(1 1)染色体编码方法染色体编码方法 基本遗传算法使用固
11、定长度的二进制符号来表示群体中的个体,基本遗传算法使用固定长度的二进制符号来表示群体中的个体,其等位基因是由二值符号集其等位基因是由二值符号集0,10,1所组成。初始个体基因值可用均匀分布所组成。初始个体基因值可用均匀分布的随机值生成,如:的随机值生成,如:就可表示一个个体,该个体的染色体长度是就可表示一个个体,该个体的染色体长度是1818。001011011001110010 x1.4 遗传算法的构成要素遗传算法的构成要素(2 2)个体适应度评价个体适应度评价 基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群
12、体中的概率多少。为正确计算这个概率,要求所有个体遗传到下一代群体中的概率多少。为正确计算这个概率,要求所有个体的适应度必须为正数或零。因此,必须先确定由目标函数值体的适应度必须为正数或零。因此,必须先确定由目标函数值J J到个体适到个体适应度应度f f之间的转换规则。之间的转换规则。(3 3)遗传算子遗传算子 基本遗传算法使用下述三种遗传算子:基本遗传算法使用下述三种遗传算子: 选择运算选择运算: :使用比例选择算子;使用比例选择算子; 交叉运算交叉运算: :使用单点交叉算子;使用单点交叉算子; 变异运算变异运算: :使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。1.4
13、遗传算法的构成要素遗传算法的构成要素(4 4)基本遗传算法的运行参数基本遗传算法的运行参数 有下述有下述4 4个运行参数需要提前设定:个运行参数需要提前设定: M M :群体大小,即群体中所含个体的数量,一般取为:群体大小,即群体中所含个体的数量,一般取为20-10020-100; G G :遗传算法的终止进化代数,一般取为:遗传算法的终止进化代数,一般取为100-500100-500; PcPc:交叉概率,一般取为:交叉概率,一般取为0.4-0.990.4-0.99; PmPm:变异概率,一般取为:变异概率,一般取为0.0001-0.10.0001-0.1。1.5 遗传算法的操作步骤遗传算法
14、的操作步骤 对于一个需要进行优化的实际问题,一般可按下述步骤构造遗对于一个需要进行优化的实际问题,一般可按下述步骤构造遗传算法:传算法: 第一步第一步:确定决策变量及各种约束条件;:确定决策变量及各种约束条件; 第二步第二步:建立优化模型,即确定出目标函数的类型及数学描述形式或:建立优化模型,即确定出目标函数的类型及数学描述形式或量化方法;量化方法; 第三步第三步:确定表示可行解的染色体编码方法;:确定表示可行解的染色体编码方法; 第四步第四步:确定解码方法;:确定解码方法; 第四步第四步:确定个体适应度的量化评价方法,即确定出由目标函数值到:确定个体适应度的量化评价方法,即确定出由目标函数值
15、到个体适应度的转换规则;个体适应度的转换规则; 第五步第五步:设计遗传算子,即确定选择运算、交叉运算、变异运算等遗:设计遗传算子,即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。传算子的具体操作方法。 第六步第六步:确定遗传算法的有关运行参数,即:确定遗传算法的有关运行参数,即M,G,Pc,PmM,G,Pc,Pm等参数。等参数。1.5 遗传算法的操作步骤遗传算法的操作步骤 遗传算法流程图:遗传算法流程图:1.6 遗传算法的特点遗传算法的特点遗传算法的主要特点有:遗传算法的主要特点有: (1 1)遗传算法是对参数的编码进行操作,而非对参数本身,遗传算法是对参数的编码进行操作,而非对参
16、数本身,这就是使得我们这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念,模仿自然界中生物的在优化计算过程中可以借鉴生物学中染色体和基因等概念,模仿自然界中生物的遗传和进化等机理;遗传和进化等机理; (2 2)遗传算法同时使用多个搜索点的搜索信息。遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程,单个搜索点所提供的信息不多,空间的单个初始点开始最优解的迭代搜索过程,单个搜索点所提供的信息不多,搜索效率不高,有时甚至使搜索过程局限于局部最优解而停滞不前。搜索效率不高,有时甚至使搜索过程局限于局部最优解而停
17、滞不前。 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程,而不是遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程,而不是从一个单一的个体开始搜索,这是遗传算法所特有的一种隐含并行性,因此遗传从一个单一的个体开始搜索,这是遗传算法所特有的一种隐含并行性,因此遗传算法的搜索效率较高。算法的搜索效率较高。 (3 3)遗传算法直接以目标函数作为搜索信息。遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用传统的优化算法不仅需要利用目标函数值,而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传目标函数值,而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算
18、法仅使用由目标函数值变换来的适应度函数值,就可以确定进一步的搜索方向算法仅使用由目标函数值变换来的适应度函数值,就可以确定进一步的搜索方向和搜索范围,无需目标函数的导数值等其他一些辅助信息。和搜索范围,无需目标函数的导数值等其他一些辅助信息。1.6 遗传算法的特点遗传算法的特点 遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题,以遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题,以及组合优化问题等。及组合优化问题等。 (4 4)遗传算法使用概率搜索技术。遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是遗传算法的选择、交叉、变异等运算都是以一种概率的方式
19、来进行的,因而遗传算法的搜索过程具有很好的灵活性。随着以一种概率的方式来进行的,因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行,遗传算法新的群体会更多地产生出许多新的优良的个体。进化过程的进行,遗传算法新的群体会更多地产生出许多新的优良的个体。 (5 5)遗传算法在解空间进行高效启发式搜索,而非盲目地穷举或完全随机搜遗传算法在解空间进行高效启发式搜索,而非盲目地穷举或完全随机搜索;索; (6 6)遗传算法对于待寻优的函数基本无限制,遗传算法对于待寻优的函数基本无限制,它既不要求函数连续,也不要它既不要求函数连续,也不要求函数可微,既可以是数学解析式所表示的显函数,又可以是映射矩阵甚
20、至是神求函数可微,既可以是数学解析式所表示的显函数,又可以是映射矩阵甚至是神经网络的隐函数,因而应用范围较广;经网络的隐函数,因而应用范围较广; (7 7)遗传算法具有并行计算的特点,遗传算法具有并行计算的特点,因而可通过大规模并行计算来提高计算因而可通过大规模并行计算来提高计算速度,适合大规模复杂问题的优化。速度,适合大规模复杂问题的优化。 1.7 遗传算法的应用领域遗传算法的应用领域 遗传算法的应用领域主要有:遗传算法的应用领域主要有:函数优化函数优化、组合优化组合优化、生产调生产调度问题度问题、自动控制自动控制、机器人机器人、图像处理等图像处理等。(1 1)函数优化函数优化 函数优化是遗
21、传算法的经典应用领域,也是遗传算法进行性能评价函数优化是遗传算法的经典应用领域,也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题,采用的常用算例。尤其是对非线性、多模型、多目标的函数优化问题,采用其他优化方法较难求解,而遗传算法却可以得到较好的结果。其他优化方法较难求解,而遗传算法却可以得到较好的结果。(2 2)组合优化组合优化。 随着问题的增大,组合优化问题的搜索空间也急剧扩大,采用传统随着问题的增大,组合优化问题的搜索空间也急剧扩大,采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳
22、工具。例如,遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划例如,遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。分问题等方面得到成功的应用。1.7 遗传算法的应用领域遗传算法的应用领域(3 3)生产调度问题生产调度问题 在很多情况下,采用建立数学模型的方法难以对生产调度问题进行精在很多情况下,采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生调度问题的有效工具,在单件生
23、产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。产规划、任务分配等方面遗传算法都得到了有效的应用。(4 4)自动控制自动控制 在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已经在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已经在其中得到了初步的应用。例如,利用遗传算法进行控制器参数的优化、在其中得到了初步的应用。例如,利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。遗传算法的神经网络结构的
24、优化和权值学习等。1.7 遗传算法的应用领域遗传算法的应用领域(5 5)机器人机器人 例如,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹例如,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。规划、机器人结构优化和行为协调等方面得到研究和应用。(6 6)图像处理图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。取等方
25、面得到了应用。1.8 遗传算法的应用举例遗传算法的应用举例1 1 用遗传算法求函数极值用遗传算法求函数极值利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值:函数的极大值:求解该问题遗传算法的构造过程:求解该问题遗传算法的构造过程:)2 , 1(048. 2048. 2)1 ()(100),(21222121ixxxxxxfi(1 1)确定决策变量和约束条件)确定决策变量和约束条件决策变量为:决策变量为:,1x.2x(2 2)建立优化模型)建立优化模型)2 , 1(048. 2048. 2),(max21ixxxfi1.8 遗传算法的应用举例遗传算法的应用举例(3
展开阅读全文