《遗传算法机器人与智能技术室课件.ppt》由会员分享，可在线阅读，更多相关《遗传算法机器人与智能技术室课件.ppt（55页珍藏版）》请在三一办公上搜索。
1、目录,第一章绪论第二章搜索技术第三章知识表示第四章推理技术 第五章 机器学习第六章计算智能 第七章数据挖掘第八章 智能体技术,可求解与难求解问题遗传算法群智能算法,现实世界中的问题分类,6.1 可求解与难求解问题,计算机在有限时间内能够求解的(可求解问题)计算机在有限时间内不能求解的(难求解问题)计算机完全不能求解的(不可计算问题),计算复杂性是指问题的一种特性，即利用计算机求解问题的难易性或难易程度，其衡量标准：计算所需的步数或指令条数(即时间复杂度)计算所需的存储空间大小(即空间复杂度)-通常表达为关于问题规模n的一个函数 O(f(n),问题的计算复杂性,20！=1.2161017203=
2、8000,O(n3)与O(3n)的差别 O(n!)与O(n3)的差别,O(bn),O(n!),O(1),O(log n),O(n),O(n log n),O(nb),6.1 可求解与难求解问题,P类问题，NP类问题，NPC类问题,P类问题：多项式问题(Polynomial Problem)，指计算机可以在有限时间内求解的问题，即：P类问题是可以找出一个呈现O(na)复杂性算法的问题，其中a为常数。NP类问题：非确定性多项式问题(Non-deterministic Polynomial)。有些问题，其答案是无法直接计算得到的，只能通过间接的猜算或试算来得到结果，这就是非确定性问题(Non-det
3、erministic)。虽然在多项式时间内难于求解但不难判断给定一个解的正确性的问题，即：在多项式时间内可以由一个算法验证一个解是否正确的非确定性问题，就是NP类问题。NPC问题：完全非确定性多项式问题(NP-Complete)。如果NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算的话就叫做完全非确定性多项式问题，即NP-Complete问题。,6.1 可求解与难求解问题,6.1 可求解与难求解问题,旅行商问题 对于销售员旅行问题（Travelling Salesman Problem,TSP），设有n个城市，城市I和城市j之间的距离为d(i,j)，要求找到一条遍访每个城市一次而且
4、恰好一次的旅行线路，使其路径总长度为最短。,NPC类问题求解,穷举法或称遍历法：对解空间中的每一个可能解进行验证，直到所有的解都被验证是否正确，便能得到精确的结果-精确解,可能是O(n!)或O(an),近似解求解算法-近似解,应该是O(na),=|近似解 精确解|满意解：充分小时的近似解,TSP问题的遍历算法,TSP问题的贪心算法,仿生学算法,进化算法，遗传算法，蚁群算法，蜂群算法,6.1 可求解与难求解问题,6.2 遗传算法,生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。,6.2 遗传算法,生物染色体用数学方式或计算机方式来
5、体现就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的数值来衡量；染色体的选择或淘汰问题是按求最大还是最小问题来进行。遗传算法（Genetic AlgorichmsGA）是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形式。,6.2 遗传算法,遗传算法提出：于20世纪60年代由密歇根(Michigan)大学Hollstien,Bagleyh和Rosenberg等人在其博士论文中首先加以研究；1975年，美国J.H.Holland教授在其著作“Adaptation in Natural and Arti
6、ficial Systems”中系统地阐述了遗传算法，给出了遗传算法的基本定理和大量的数学理论证明。遗传算法发展：David E.Goldberg教授1989年出版了“Genetic Algorichms”一书，这一著作通常被认为是遗传算法的方法、理论及应用的全面系统的总结。从1985年起，国际上开始陆续举行遗传算法的国际会议，后来又更名为进化计算。参加进化计算国际会议的人数及收录文章的数量、广度和深度逐年扩大。从此，进化计算逐渐成为人们用来解决高度复杂问题的新思路和新方法。,6.2 遗传算法,遗传算法特点：遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的
7、理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点：(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。,6.2 遗传算法,6.2.1 遗传算法的基本原理 霍兰德提出的遗传算法通常称为简单遗传算法（SGA）。编码与解码 许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的
8、过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。,6.2 遗传算法,对于TSP问题，可以按一条回路中城市的次序进行编码。从城市w1开始，依次经过城市w2，wn，最后回到城市w1，我们就有如下编码表示：w1 w2 wn由于是回路，记wn+1=w1。它其实是1，n的一个循环排列。要注意w1，w2，wn是互不相同的。,6.2 遗传算法,适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function）。TSP的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为TSP问题的适应度函数:其中wn+1=w1适应度函数要有
9、效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。,6.2 遗传算法,遗传操作简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法采用赌轮选择机制，令fi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi/fi。,6.2 遗传算法,交叉
10、操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。产生一个17之间的随机数c，假设为3，则将P1和P2的低3位交换,P1：,P2：,P1：,P2：,Q1：,Q2：,6.2 遗传算法,变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。随机产生一个18之间的数k，假设k=5，对从右往左第5位变异操作。,1,6.2 遗传算法,控制参数交叉发生的概率：0.60.95 变异的概率：0.0010.01 种群的个数：30100 个体的长度：定长和变长,6.2 遗传算法,6.2.2 遗传算法的结构选择：由个
11、体适应度值决定 的某个规则。交叉：按概率Pc进行变异：按概率Pm进行终止条件：完成了预先给定的进化代数 种群中的最优个体在连续若干代 没有改进或平均适应度在连续若 干代基本没有改进,开始,初始化种群,选择操作,终止条件,否,适应度最有优个体,计算适应度值,交叉操作,变异操作,结束,6.2 遗传算法,6.2.3 遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素：种群的数量：太小缺少多样性，太多影响效率 适应度函数：提升优良个体的适应度 交叉和变异：不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率：,分析：对该问题虽然也可以采用枚举的方法来解决,但枚举法却是一种效率很低的方
12、法.可运用遗传算法来求解该问题.解：首先对问题进行初始化，以获得初始种群;（1）确定编码方案：将x编码表示为染色体的数字符号串。针对本题自变量x定义域,取值范围为0，31,考虑采用二进制数来对其编码,由25=32,故使用5位无符号二进制数组成染色体数字字符串,用以表达变量x及问题的解答过程。,例:设有函数f(x)=x2,用遗传算法求其自变量x在区间0，31 取整数值时的最大值。,6.2 遗传算法,（2）选择初始种群:通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位又称之为基因(genes)，使用计算机在01之间产生随机数K，并按照数K的变化区域来规定基因代码如下：0
13、，（0K0.5）1，（0.5K1）,6.2 遗传算法,于是随机生成4个染色体的数字符串为：01101110000100010011从而构造了初始种群，完成了遗传算法的准备。,6.2 遗传算法,表6.1 初始种群染色体及对应的适应值,6.2 遗传算法,（3）复制(选择)选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其子孙。要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则：低于0.125以下的染色体被淘汰；在0.1250.375之间的染色体被复制一个；在0.3750.625之间的染色体被复制两个；在0.6250.875之间的染色体被复制三个；在0.875以
14、上的染色体可复制四个。,6.2 遗传算法,对应于上例，按照适应度的计算，经复制操作后，得到新的染色体种群为 01101 11000 11000 10011,6.2 遗传算法,某个染色体是否被复制,可以通过概率决策法、适应度比例法或“轮盘赌”的随机方法来断定。对应轮盘赌转盘的随机方法,根据表6.1数据，绘制出的轮盘赌转盘,如图所示:,6.2 遗传算法,01101 11000 11000 10011,6.2 遗传算法,初始种群染色体准备复制操作的各项计算数据,（4）交叉 交叉具体分两步：将新复制产生的染色体随机两两匹配,称其为双亲染色体；再把双亲染色体进行交叉繁殖。交叉的实现:设染色体数字串长度为
15、L，把L个数字位间空隙分别标记为：1，2，L1 随机从1，L1中选取某一整数位置k，0kL 交换双亲染色体交换点位置k右边的部分，就形成了两个新的数字符串（也可以只交换其中的第k基因），得到了两个新的染色体，又称之为下一代染色体。,6.2 遗传算法,例如，将上例初始种群的两个体A1=01101A2=11000假定从1到4间选取两个随机数，得到1=2，2=4，那么经过交叉操作之后将得到如下两组新的数字符串A1#=01000 A2#=11101,6.2 遗传算法,A3#=01100A4#=11001,前一组数字串是使用1=2,即将第2位后的35位交换得到；后一组数字串是使用2=4，即仅将第5位因子
16、进行交换而得。,6.2 遗传算法,复制、交叉操作的各项数据,（5）变异 设变异概率取为0.001,则对于种群总共有20个基因位.期望的变异串位数计算:200.001=0.02(位),故一般来说,该例中无基因位数值的改变.从表中可以看出,每经过一次复制、交叉和变异操作后,目标函数的最优值和平均值就会有所提高。在上例中，种群的平均适应值从293增至446.5;最大的适应度数值从576增至841。特点：每经一次进化计算步骤,问题解答便向着最优方向前进了一步;若该过程一直进行下去,就将最终走向全局的最优解.可见进化计算的每一步操作简单,并且系统的求解过程是依照计算方法与规律来决定,与本源问题自身的特性
17、很少相关。,6.2 遗传算法,作业调度问题（job shop scheduling problem，JSSP）对工场内的作业进行组织、调度和管理。例：完成下述三个作业：j1：型号a产品30件；j2：型号b产品45件；j3：型号a产品50件；产品a,b的生产流程有下述几种选择：a:流程a1(opr2,opr7,opr9)；a:流程a2(opr1,opr3,opr7，opr8)；a:流程a3(opr4,opr6)；b:流程b1(opr2,opr6,opr7)；a:流程b2(opr1,opr9)；,6.2 遗传算法,作业调度问题（job shop scheduling problem，JSSP）此处
18、opri 表示第i种操作过程，每种操作所需要的机器及时间为：opr1：(m1 10)(m3 20)opr2：(m2 20)opr3：(m2 20)(m3 30)opr4：(m1 10)(m2 30)(m3 20)opr5：(m1 10)(m3 30)opr6：(m1 40)opr7：(m3 20)opr8：(m1 50)(m2 30)(m3 10)opr9：(m2 20)(m3 40)此处(mj t)表示占用机器j共t个时间单元。还可以假设机器关机后的启动时间为 m1:3，m2:5，m3:7,6.2 遗传算法,作业调度问题（job shop scheduling problem，JSSP）编码
19、策略：为每台机器建立一个优先表（preference list）。该表的第一个元素为机器的启动时刻，接着是个作业的操作顺序，另外两项为“等待”（wait）和“闲置”（idle）。其译码过程为：只要在某机器的启动时刻，该机器可用，则首先选择其优先表中的第一个允许操作。例如：m1:（40 j3 j1 j2 wait idle）译码为：在第40时间步从作业j3中找一产品用机器m1生产。如不成功，再从j1中搜索产品进行,遗传算子：闲置（run-idle）：仅从那些已经等待1小时以上机器的优先表进行操作。交叉：交换所选机器的有先表打乱（scramble）：该操作“打乱”优先表中的成员。,6.2 遗传算法
20、,地球上的生物物种在漫长的过程中形成了丰富的行为特性，并且一直不断地完善和发展，以更好地适应其所生存的环境。生物群体和自然生态系统可以通过自身的演化就能使许多在人类看起来高度复杂的优化问题得到完美解决。因此，各种模仿生物群体的智能仿生算法被相继提出，得到了深入研究和应用实践。群智能思想的产生主要源于复杂适应系统理论以及人工生命的研究。,6.3 群智能算法,群智能(Swarm Intelligence,SI)：1992年由 Beni,Hack-wood 和 Wang在分子自动机系统中提出。1999 年,Bonabeau,Dorigo 和 Theraulaz 在 Swarm Intel-ligen
21、ce:From Natural to Artificial Systems中对群智能进行了详细的论述和分析。2003年 IEEE 第一届国际群智能研讨会在美国印第安纳州首府召开。群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。,6.3 群智能算法,Swarm 可被描述为一些相互作用相邻个体的集合体,蜂群、蚁群、鸟群、鱼群都是Swarm的典型例子。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且
22、群内个体还能处理信息，并根据所获得的信息(包括环境信息和附近其它个体的信息)改变自身的一些行为模式和规范,这样就使得群体涌现出一些单个个体所不具备的能力和特性,尤其是对环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能,也就是说动物个体通过聚集成群而涌现出了智能。,6.3 群智能算法,6.3 群智能算法,SI 的定义进一步推广（Bonabeau）:无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。群智能理论还非常不成熟,但已成为有别于传统人工智能中连接主义、行为主义和符号主义的一种新的关于智能的描述方法,并成为人工智能领域的新研究热点。,6.3.1 蚁群算法
23、蚁群算法(Ant Colony OptimizationACO)由 Colorni,Dorigo 和 Maniezzo 于 1991 年提出,它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡,如果一只蚂蚁找到食物,它就返回巢中通知同伴并沿途留下“信息素”(pheromone)作为蚁群前往食物所在地的标记。信息素会逐渐挥发,如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气味会比较淡,蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的“蚂蚁”,让它们摸索不同路线,并留下会随时
24、间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则,即可选择出最佳路线。,6.3 群智能算法,ACO算法首先应用于 TSP 问题中,这里以 TSP 问题为例对算法作简单介绍。当某一个蚂蚁走到一个城市,下一步可选的路径集合为 E,集合中任一条路径 eE 上的信息素浓度为e,走这条路的代价为 e,那么选择某一条路径 vE 的几率为：,6.3 群智能算法,其中,和 两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为:e(t+1)=(1-)e(t)+e 其中，0 1 用于控制信息素随时间挥发的速度，e是上次蚂蚁经过此路段所留下的信息素
25、，未经过则为 0。上式以及e可以根据问题进行设计。,6.3 群智能算法,ACO算法应用 车辆路径问题（vehicle routing problem，VRP）已知一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干派送车辆，运载能力给定，每两车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆、最小的车辆总行程完成货物的派送任务。与TSP区别：TSP中每只蚂蚁均要经过所有节点，VRP中每只蚂蚁并不需要遍历所有节点；TSP中每只蚂蚁移动只需考虑路径距离和信息量，VRP中还需考虑车辆容量限制；TSP中每只蚂蚁构造出来的路径均是一个可行解，VRP中每只蚂蚁所构造的回路仅是可行
26、解的一部分。,6.3 群智能算法,ACO算法应用 机组最优投入问题（unit commitment，UC）机组最优投入是寻求一个周期内各个负荷水平下机组的最优组合方式及开停机计划，使运行费用最小，它是一个高维度、非凸的、离散的非线性组合优化问题，很难找出理论上的最优解。UC的目标函数中主要包括两个基本部分：（1）机组的发电费用；（2）机组的费用，同时还必须满足一定的约束条件。,6.3 群智能算法,ACO算法应用 PID参数优化（proportional-integral-differential，PID）PID控制器本质上是一种对“过去”、“现在”和“未来”信息估计的控制算法。在控制工程领域中
27、约90%的控制回路具有PID结构。在常规PID控制算法上发展了大量改进PID算法，如非线性PID、最优PID、智能PID、自适应PID等。任何PID控制器的性能取决于其控制参数优化，三个部分（比例-积分-微分）参数分别是Kp、Ki、Kd，目标函数主要考虑单位阶跃响应超调量、上升时间tr以及调整时间ts。,6.3 群智能算法,ACO算法应用 其他应用：岩土工程：边坡非圆弧临界滑动面搜索技术，边坡稳定性分析，高填石路堤稳定性和边坡稳定性分析。化学工程：化学计量学科的光谱解析，反应动力学参数估计。生命科学：蛋白质折叠问题是生物信息学中的一个重要问题，它研究蛋白质从一维序列到三维结构的过程。亲-疏水格
28、点（hydrophobic and polarmonomers，HP）模型是研究该复杂过程的一个最重要的简化模型。蛋白质折叠问题已被证明是一个NP-C问题。ACO算法可用于HP模型测试序列求解。,6.3 群智能算法,6.3.2 粒子群算法 粒子群优化算法（Particle Swarm OptimizationPSO)源于 1987 年 Reynolds 对鸟群社会系统boids的仿真研究，boids 也是一个 CAS。在 boids 中,一群鸟在空中飞行,每个鸟遵守以下三条规则:（1）避免与相邻的鸟发生碰撞冲突;（2）尽量与自己周围的鸟在速度上保持协调和一致;（3）尽量试图向自己所认为的群体中
29、心靠近。仅仅通过使用这三条规则,boids 系统就出现非常逼真的群体聚集行为,鸟成群地在空中飞行,当遇到障碍时它们会分开绕行而过,随后又会重新形成群体。不过 Reynolds 仅仅将其作为 CAS的一个实例作仿真研究,而并未将它用于优化计算中,也无任何实用价值。,6.3 群智能算法,Kennedy和 Eberhart（1995年）在 boids 中加入了一个特定点,定义为食物,鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象,然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力,尤其是在多维空间寻优中。由于最初的仿真系统中每个鸟在计算机屏幕上表示为一个点,
30、而“点(Points)”这个词在数学领域具有非常多的意义,因此作者用了“粒子(Particle)”来表示每一个个体。于是也就得到了基本 PSO算法。,6.3 群智能算法,6.3 群智能算法,粒子群特性,6.3 群智能算法,在PSO系统初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己,同时也通过跟踪它们实现粒子间的信息交换。第一个就是粒子本身所找到的最优解,这个解叫作个体极值pBest(“自身经验”)。另一个极值是整个群体目前找到的最优解,这个极值是群体极值 gBest(群体的“社会经验”)。,6.3 群智能算法,1998 年,Shi 和
31、 Eberhart 正式给出标准 PSO算法的数学描述如下:设搜索空间为 M维,粒子数为 N。第 i 个粒子位置表示为向量 Xi=(xi1,xi2,xiD);第 i 个粒子“飞行”历史中的过去最优位置(即该位置对应解最优)为 Pi=(pi1,pi2,piD)也就是 pBest，其中所有 Pi(i=1,N)中的最优个体被记作 Pg 也就是 gBest；第 i 个粒子的位置变化率(速度)为向量 Vi=(vi1,vi2,viD)。每个粒子的位置按如下公式进行变化(“飞行”):,6.3 群智能算法,其中,c1,c2 为正常数,称为加速因子;rand()为0,1之间的随机数;w称惯性因子。第d(1dM)
32、维的位置变化范围和速度变化范围分别为-xd,max,xd,max和-vd,max,vd,max(变化范围可通过平移处理使之对称),迭代中若某一维的 xid 或 vid 超过边界则取边界值。粒子群初始位置和速度随机产生,然后按公式进行迭代,直至满足停止条件。,6.3 群智能算法,vid(t+1)=w*vid(t)+c1*rand()*(pid(t)-xid(t)+c2*rand()*(pgd(t)-xid(t)xid(t+1)=xid(t)+vid(t+1),6.3.3 EC与SI算法异同 基于 SI 的优化算法和 EC都是基于群体迭代的启发式随机优化算法,有着非常多相似之处,它们都是对自然中随
33、机系统的仿真,都具有本质并行性。另外,与 EC一样的是,SI 的目的并不是为了忠实地模拟自然现象,而是利用它们的某些特点去解决实际问题。ACO和 PSO也一度曾被归类于 EC之中,但它们与 EC之间的区别也是明显的。ACO、PSO在本质上不能用广义 EC算法的流程进行描述。首先，EC和 SI 所模拟的自然随机系统不一样。EC是模拟生物系统进化过程,其最基本单位是基因(Gene),它在生物体的每一代之间传播;已有的基于 SI 的优化算法都是源于对动物社会通过协作解决问题行为的模拟,它主要强调对社会系统中个体之间相互协同作用的模拟,其最基本单位是敏因。,6.3 群智能算法,其次，EC中强调“适者生存”,不好的个体在竞争中被淘汰;SI 强调“协同合作”,不好的个体通过学习向好的方向转变,不好的个体被保留还可以增强群体的多样性。EC中最好的个体通过产生更多的后代来传播自己的基因,而 SI 中的优秀个体通过吸引其它个体向它靠近来传播自己的敏因。最后，EC的迭代由选择、变异和交叉重组操作组成，而 SI的迭代中的操作是“跟随”，ACO中蚂蚁跟随信息素浓度爬行,PSO中粒子跟随最优粒子飞行。在某种程度上看，SI 的跟随操作中隐含了选择、变异和交叉重组操作。,6.3 群智能算法,
