截图
简介
这是遗传算法在组合优化问题中的应用ppt，包括了遗传算法概述，遗传算法的改进，遗传算法的应用，遗传算法的产生与发展等内容，欢迎点击下载。
遗传算法在组合优化问题中的应用ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
遗传算法原理及其应用
中山大学智能交通研究中心
2010年4月
目 录
目 录
1.1 遗传算法的产生与发展
产生
早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；
1963年，德国柏林技术大学的I. Rechenberg和H. P. Schwefel，做风洞实验时，产生了进化策略的初步思想；
60年代， L. J. Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了《基于模拟进化的人工智能》，系统阐述了进化规划的思想。
60年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术；
1967年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；
1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。
1.1 遗传算法的产生与发展
发展
70年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；
1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；
1989年，Holland的学生D. J. Goldherg出版了“Genetic Algorithms in Search， Optimization， and Machine Learning”，对遗传算法及其应用作了全面而系统的论述；
1991年，L. Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。
1.2 遗传学基本概念与术语
染色体（chromosome）：遗传物质的载体；
脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；
RNA
遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；
基因型（genotype）：遗传因子组合的模型；
表现型（phenotype）：由染色体决定性状的外部表现；
个体（individual）：指染色体带有特征的实体；
种群（population）：个体的集合，该集合内个体数称为种群的大小；
进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；
适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;
选择（selection）：指决定以一定的概率从种群中选择若干个体的操作 （实现优胜劣汰）；
复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;
交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;
变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;
编码（coding）：表现型到基因型的映射；
解码（decoding）：从基因型到表现型的映射。
大象灰颜色皮肤为例
1.3 遗传算法的原理与特点
原理
遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：
在每一代，概据问题域中个体的适应度大小挑选个体；
并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。
这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。
基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。
1.3 遗传算法的原理与特点
遗传算法的基本流程
1.3 遗传算法的原理与特点
特点
遗传算法的本质并行性。
首先，遗传算法并行的方式从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。
其次，算法内含并行性，遗传算法采用种群方式组织搜索，因而可同时搜索妥空间的多个区域(n-n3)，并相互交流信息，能以较小的计算获得较大的收益。
遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。
遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。
具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
遗传算法可更直接的应用，对给定的问题，可以产生许多潜在解，最终选择可以由使用者指定，通用性高，应用范围广。
1.4 遗传算法的基本操作
遗传基因型(编码)
编码方式
二进制编码、浮点数编码、格雷码编码、符号编码、复数编码、DNA编码等。
以大象灰色皮肤为例：二进制编码： 1111111 ，浮点编码：127.0
编码原则
完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；
健全性（soundness）：任何一个基因型都对应于一个可能解；
非冗余性（non-redundancy）：问题空间和表达空间一一对应。
二进制编码与浮点数编码的比较
在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；
在变异操作时，二进制编码的种群稳定性比浮点数编码差。
1.4 遗传算法的基本操作
选择
适应度计算：
按比例的适应度函数（proportional fitness assignment）
基于排序的适应度计算（Rank-based fitness assignment）
选择算法：
轮盘赌选择（roulette wheel selection）
随机遍历抽样（stochastic universal selection）
局部选择（local selection）
截断选择（truncation selection）
锦标赛选择（tournament selection）
交叉或基因重组
二进制交叉（binary valued crossover）：
单点交叉（single-point crossover）
多点交叉（multiple-point crossover）
均匀交叉（uniform crossover）
洗牌交叉（shuffle crossover）
缩小代理交叉（crossover with reduced surrogate）
实值重组（real valued recombination） ：
离散重组（discrete recombination）
中间重组（intermediate recombination）
线性重组（linear recombination）（均匀、非均匀）
扩展线性重组（extended linear recombination
交叉方式
半种群交叉(N/2)
对群体中的要交叉的个体进行两两随机配对。若群体大小为M，则最多共有 [ M/2 ]对相互配对的个体组参与交叉。(若种群数为奇数，则其中任一个个体多选一次配对)
2) 全种群交叉(N)
对群体中要交叉的个体，从种群中随机挑选一个个体与其完成交叉操作，最多共有M对相互配对的个体参与变异。
变异方法
二进制变异
单点变异
逆序变异
均匀变异
实值变异
随机变异
边界变异
非一致变异
自适应变异
高斯变异
变异方式
基于个体的变异
即对任意一个个体，判断其是否进行变异操作，如果是，则随机生成一变异基因发生变异操作。
基于基因座的变异
即对种群中的个体，判断每一个个体的每一位基因是否进行变异操作，如果是，则发生变异操作。
1.5 遗传算法的应用
函数优化
是遗传算法的经典应用领域;
组合优化
实践证明，遗传算法对于组合优化中的NP完全问题非常有效;
自动控制
如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;
机器人智能控制
遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;
组合图像处理和模式识别
目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;
人工生命
基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；
遗传程序设计
Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;
机器学习
机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规 划系统中得到了成功的应用。
2 基本遗传算法
遗传算法在自然与社会现象的模拟、工程计算等方面得到了广泛的应用。
在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进。
为不至于混淆，把Holland提出的算法称为基本遗传算法，简称为SGA（Simple Genetic Algorithm ) ，也有称其为(GA、CGA)。
以SGA为例，阐述遗传算法的设计与实现方法。
2.1 基本遗传算法描述
2.1.1 SGA的构成要素
(1) 染色体编码方法
基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集{0，1}组成。
初始群体中各个个体的基因值用均匀分布的随机数来生成。如：
x：100111001000101101
就可表示一个个体，该个体的染色体长度是 l＝18。
(2) 个体适应度评价
基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。
为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。
2.2 基本遗传算法的实现
2.2.1 编码与解码
(1) 编码
假设某一参数的取值范围是[umin ， umax]，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下：
00000000…00000000＝0 umin
00000000…00000001＝1 umin +
……
11111111…11111111=2l–1 umax
[例] 设 -3.0 ≤ x ≤ 12.1 ， 精度要求 =1/10000，由公式：
2.2.2 个体适应度评价
如前所述，要求所有个体的适应度必须为正数或零，不能是负数。
(1) 当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体
的适应度F(X)就等于相应的目标函数值f(X)，即：
F(X)＝f(X)
(2) 对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就
可将其转化为求目标函数最大值的优化问题，即：
min f(X)＝max ( - f(X))
但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有
求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个
要求，需要进行适应度函数尺度转换，将目标函数值 f(x)变换为个体的适应度F(x) 。
2.3 GA算法流程图
2.4 简单函数优化实例
3 遗传算法的改进
传统的GA在解决时就存在如下问题：
首先，模型复杂，参数太多难以达到优化目的，优化速度慢且达不到最优解。
其次，约束条件复杂、繁多，算法收敛的时候很难满足约束条件。因此，在处理交通控制问题上扬长避短，需要改进遗传算法，使其达到智能控制的效果。
改进措施
改变遗传算法的组成成分；
采用混合遗传算法；
采用动态自适应技术；
采用非标准的遗传操作算子；
采用并行遗传算法等。
退火进化算法
退火进化算法(annealing evolution algorithm， AEA ）
遗传算法（GA)模拟退火算法（SA）是人工智能中用于解决组合优化问题的经典 但是，SA 在全局搜索能力方面不足，GA 在局部搜索能力方面不足。而退火进化算法（annealing evolution algorithm， AEA)综合了SA和GA算法，优势互补，发挥SA 局部搜索能力和GA 全局搜索能力，克服SA 全局搜索能力差及效率不高的问题和GA 局部搜索能力差及其早熟现象。AEA把SA算法与GA结合在一起，通过变异与选择不断改善解群体，并行搜索解空间，从而有可能更迅速地找到全局最优解。由于在选择中采用Metropolis准则，因而保留了SA算法易跳出某局部极值“陷阱”的优点，易于向全局极小值快速收敛。
算法求解过程如下：
(1)初始化进化代数计数器k←0，随机给出种群P(k)初值，给定初试退火温度T0。
(2)评价当前群体P(k)的适应度。
(3)个体交叉操作（附带保优操作）： P(k)’←Crossover[P(k)]。
(4)个体变异操作（附带保优操作）： P(k)”←Mutation[P(k)’]。
(5)由SA状态函数产生新个体。
(6)个体模拟退火操作(Metropolis准则接受新个体)： P(k)”’←SA[P(k)”]。
(7)判断SA抽样是否稳定，若不稳定，则返回(5)；若稳定，则往下执行退温操作T←T’
(8)个体复制操作，由择优选择模型保留最佳种群：P(k+1)←Reproduction[P(k)∪P(k)”’]。
(9)终止条件判断，若不满足终止条件，则k←k+1，转到(2)；若满足终止条件，则输出当前最优个体，结束算法。
4 遗传算法的应用
遗传算法在交通中的应用
解决带约束的函数优化问题
交通规划
解决多目标优化问题
交通信号控制
解决组合优化问题(TSP问题)
TSP问题
遗传算法在过程建模中的应用
BP、模糊等参数优化
在模式识别中的应用
图像处理
1 解决带约束的函数优化问题
遗传算法在过程建模中的应用
遗传算法在模式识别中的应用
解决组合优化问题
展开
