人工智能课件-老师2014年春22计算智能part

1、Artificial Intelligence (AI)人工智能主讲：戚玉涛Email： 第五章：计算智能内容提要第五章：计算智能1.概述2.神经网络3.模糊计算4.遗传算法遗传算法遗传算法（Genetic Algorithm, GA）是模拟生物在自然环境种的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法最早由美国密西根大学的 J. Holland 教授提出，起源于20世纪60年代对自然和人工自适应系统的研究。70年代，De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法

2、的基本框架。遗传算法遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解。遗传算法从一组随机初始化的候选解出发按某种指标从解群中选取较优的个体利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群重复此过程，直到满足某种收敛指标为止。遗传算法基本遗传算法 （SGA）: 又称简单遗传算法或标准遗传算法，是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。 基本遗传算法的组成：染色体的编码（产生初始种群）染色体的适应度函数遗传算子（选择、交叉、变异）运行参数遗传算法SGA流

3、程图：遗传算法染色体编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。SGA使用二进制串进行编码。 遗传算法染色体的适应度函数（Affinity Function）：遗传算法对一个染色体（候选解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的重要标准（注意：并非唯一标准）。它的设计应结合求解问题本身的要求而定。 遗传算法遗传算子选择算子：实现对群体中的个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。交叉算子：对两个相互配对的染色体依据交叉概率

4、Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。变异算子：依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值替换，形成一个新的个体。遗传算法选择算子：选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。 各个个体被选中的概率与其适应度函数值大小成正比。 s40.31 s20.49 s10.14S30.06遗传算法交叉算子：交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 SGA中的交叉算子采用单点交叉算子。交叉前：父代1: 00000|01110000000010000父

5、代2: 11100|00000111111000101交叉后：子代1: 00000|00000111111000101子代2: 11100|01110000000010000交叉点遗传算法变异算子：遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 SGA中变异算子采用基本位变异算子。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。变异运算将被操作的基因位反置。遗传算法遗传算法的特点 (1) 遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算

6、法是从问题解的编码组（种群）开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。遗传算法遗传算法的优势 (1)适应度函数不受连续、可微等条件的约束，适用范围很广。(2)不容易陷入局部极值，能以很大的概率找到全局最优解。(3)由于其固有的并行性，适合于大规模并行计算。(4)不是盲目穷举，而是启发式搜索。内容提要第五章：计算智能（其他）1.粒子群算法2.蚁群算法内容提要第五章：计算智能（其他）1.粒子群算法2.蚁群算法粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群

7、算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（PSO）粒子群算法原理粒子群算法（ Particle Swarm Optimization , PSO）粒子群优化算法是进化计算的一个分支，是一种模拟自然界的生物活动的随机搜索算法。粒子群优化算法模拟了自然界鸟群捕食和鱼群捕食的过程。通过群体中的协作寻找到问题的全局最优解。它是1995年由美国学者Eberhart（电子电气工程师）和Kennedy（社会心理学家）提出的，现在已经广泛应用于各种工程领域的优化问题之中。粒子群算法原理PSO的思想来源生物界现象群体行为群体迁徙生物觅食社会心理学群体智慧个体认知社会影响粒子群优化

8、算法 人工生命鸟群觅食鱼群学习群理论粒子群算法原理从生物现象到 PSO算法鸟群觅食现象粒子群优化算法粒子群算法原理从生物现象到 PSO算法鸟群觅食现象鸟群觅食空间飞行速度所在位置个体认知与群体协作找到食物粒子群优化算法搜索空间的一组有效解问题的搜索空间解的速度向量解的位置向量速度与位置的更新找到全局最优解粒子群优化算法类比关系鸟群觅食现象算法流程PSO算法的相关定义PSO中的个体，也叫粒子，在多维搜索空间中飞行。PSO中的每个粒子维护两个向量位置向量xi ：粒子在解空间中的当前位置速度向量vi ：粒子在解空间中的飞行速度pBest ：粒子自身的历史最优位置gBest ：群体全局最优向量 lBe

9、st ：邻域中的最好位置更新速度 自身速度个体认知 社会引导算法流程粒子速度与位置的更新：惯性权重：加速系数（学习因子）：0,1区间上的随机数算法流程PSO算法驱动优化过程的是速度vi(t)向量。速度向量反映了粒子自身的经验知识和来自邻域粒子的社会交换信息。粒子的经验知识通常叫做认知部分，它和粒子与其自身的历史最优位置（ pbest ）的距离成正比。社会交换信息叫做速度方程的社会部分。邻域大小不同的两种算法gbest PSO，全局最佳粒子群优化lbest PSO，局部最佳粒子群优化算法流程gbest PSO：全局最佳粒子群优化粒子群算法粒子群算法的特点PSO算法收敛速度快，特别是在算法的早期，

10、但也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，无法继续优化，所能达到的精度也不高。内容提要第五章：计算智能（其他）1.粒子群算法2.蚁群算法蚁群算法原理蚁群的觅食行为蚁群算法原理蚁群的分工蚁群算法原理蚁穴的结构蚁群算法原理蚁穴的结构育婴室储备室寝室蚁后室日光浴场入口蚁群算法原理蚁群觅食的“双桥实验”蚁群算法蚁群觅食过程算法基本原理自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息

11、素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对应关系算法基本原理蚁群优化算法（ Ant Colony Optimization , ACO）蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他

12、路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。蚁群算法流程路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。ACO基本要素信息素更新当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。 蚂蚁系统 (Ant System，AS ) 的蚂蚁圈（Ant -cycle）版本是最基本的ACO算法，是以TS

13、P作为应用实例提出的。蚁群算法流程路径构建：伪随机比例选择规则对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i) 表示从城市i 可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。(i, j) 是一个启发式信息，通常由 (i, j)=1/dij 直接计算。 (i, j) 表示边(i, j)上的信息素量。蚁群算法流程路径构建：伪随机比例选择规则长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当 =0时，算法

14、演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当 =0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。蚁群算法流程信息素更新：(1) 在算法初始化时，问题空间中所有的边上的信息素都被初始化为0。(2) 算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数( : 信息素的蒸发率)。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。(3) 蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。(4) 迭代 (2)，直至算法终止。蚁群算法流程信息素更新：信息素的更新公式：m：蚂蚁个数；：信息素的蒸发率，规定0r1。 (i, j)：第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。Ck：路径长度，它是Rk中所