进化计算及其应用课件.ppt

《进化计算及其应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分计算智能引言Ch2进化计算及其应用Ch3群智能算法及其应用Ch4其它近邻搜索算法2优化问题的分类许多工程问题都可以看成为最优化问题。根据优化目标，最优化问题可以分为：最小化问题和最大化问题。从数学模型的表现形式来看，最优化问题可以分类为：函数优化问题或组合优化问题。3函数优化问题以最小化问题为例，优化对象：一定区间S内的连续变量。问题的一般描述：求XminS使f(Xmin)在S上全局最小。符号化表示为：XS:f(Xmin)f(X)。S为Rn上的有界子集，即变量的定义域。f:S→R为n维实值函数。Xmax最大4组合优化问题优化对象：

2、解空间中的离散状态问题的一般描述：寻找最优解s*，si，C(s*)=minC(si)={s1,s2,…,sn}为所有状态构成的离散解空间。C(si)为状态si对应的目标函数值。典型的组合优化问题：TSP问题、加工调度问题、0-1背包问题、装箱问题等。特点：问题的描述很简单，有很强的工程代表性，最优化求解很困难，主要原因是“组合爆炸”。maxCh2进化算法及其应用1.进化算法简介2.遗传算法的基本理论3.进化策略的基本理论4.进化规划的基本理论5.进化算法的应用实例5产生背景主要特点理论基础基本框架分类说明1.进化算法简介对自身的大脑信息处

3、理机制进行模拟----人工神经网络理论。对自身模糊性的思维方式进行类比----模糊系统。对自然界中动植物的免疫机理进行模拟----免疫系统。对自身进化这一更为宏观的过程学习----进化算法(EvolutionaryComputation，EC)。1.1进化算法的产生背景进化算法以达尔文的进化论思想为基础，通过模拟生物进化过程与机制来求解问题的自组织、自适应的人工智能技术。生物进化是通过繁殖、变异、竞争和选择实现的。进化算法主要通过选择、重组和变异这三种操作实现优化问题的求解。1.1进化算法的产生背景1.2进化算法的主要特点是一种全局优化、自适应概

4、率搜索算法，主要特点有：有指导的搜索：依据是每个个体的适应度值。自适应搜索：通过进化操作改进群体性能。渐进式寻优：每代进化的结果都优于上一代。并行式搜索：对每一代群体所有个体同时进行。黑箱式结构：只要研究输入和输出而不需考虑过程。全局最优解：在整个搜索区域的各个部分同时进行。稳健性强：不同的条件和环境下，算法都适用且有效。1.3进化算法的理论基础具有深厚的生物学理论基础。遗传：父代利用遗传基因将自身的基因信息复制给下一代（子代），属性特征相同或相近。变异：子代和父代，以及子代各个体之间存在着一定的差异，在进化过程中是随机发生的。生存斗争和适者生存

5、：适应性变异较强的个体被保留下来，而适应性变异较弱的个体则被淘汰。1.4进化算法的基本框架Begint=0初始化群体p(0)评估初始化群体p(0)While终止条件不满足do重组操作：p(t)=r(p(t))变异操作：p(t)=m(p(t))评估操作：p(t)选择操作：p(t+1)=s(p(t)Q)t=t+1endEnd1.5进化算法的分类与进化算法相关的算法可细分为：遗传算法(GeneticAlgorithms)、遗传规划(GeneticProgramming)、进化策略(EvolutionStrategies)和进化规划(Evolution

6、Programming)四种典型方法。第一类方法比较成熟，现已广泛应用。进化策略和进化规划在科研和实际问题中的应用也越来越广泛。遗传算法最具代表性也是最基本的。2.遗传算法的基本理论1.遗传算法与生物进化学说2.遗传算法的计算机实现3.遗传算法解决TSP问题4.遗传算法的特点5.遗传规划13142.1遗传算法与生物进化学说1885年，达尔文用自然选择来解释物种的起源和生物的进化。达尔文的自然选择学说包括三个方面：遗传变异生存斗争和适者生存152.1遗传算法与生物进化学说上世纪20年代，一些学者用统计生物学和种群遗传学重新解释达尔文自然选择理论，形

7、成现代综合进化论。种群遗传学认为：在一定地域中一个物种的全体成员构成一个种群；生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。162.1遗传算法与生物进化学说GA中与生物学相关的概念与术语：个体种群适应度选择交叉变异优化问题中的描述：解解集/解空间评价/目标/寻优函数产生新解的方法2.2遗传算法的计算机实现上世纪60年代中期，Holland提出位串编码技术。这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。Holland将该算法用于自然和人工系统的自适应行为研究中，在1

8、975出版了开创性著作“AdaptationinNaturalandArtificalSystem”。之后，他将算法应用到优化以及学习中