免疫部分的复习与补充内容.ppt

智能算法复习及补充智能算法复习及补充主要内容：n概述概述n算法简介算法简介 遗传算法（Genetic Algorithm）免疫算法（Immune Algorithm）蚁群算法（Ant Colony Optimization）粒子群算法（Particle Swarm Optimization）模拟退火算法（Simulated Annealing Algorithm）引例:求函数的最值n求 的最小值n求以下函数的最大值怎么解决？n遍历 如何确定搜索范围和搜索精度？n随机搜索 可能永远也无法找到最大值其它方法？其它方法？n随机的取一些初始点n根据某种算法某种算法，通过这些初始点相互作用，得出最终结果遗传算法（GA）采用的方法：自然计算(nature inspired computation)The investigation of mathematical and/or engineering tools that have been imbued with selected higher level(systemic)characteristics that emerge from lower level component interactions and processes,inspired by a biological system or systemsn具有模仿自然界的特点，通常是一类具有自适应、自组织、自学习能力的算法，能够解决传统计算方法难于解决的各种复杂问题n包括目前已被广泛研究的进化计算、神经计算、生态计算、量子计算和复杂自适应系统等多个领域n已成功地应用于组合优化、机器学习、工程设计等问题，并取得了很好的效果遗传算法（Genetic Algorithm）n1962年，美国Michigan大学 J.HollandnInspired:自然界的进化准则：适者生存、优胜劣汰适者生存、优胜劣汰 达尔文(1858)自然选择n遗传（heredity）n变异（variation）n生存斗争和适者生存亲代把生物信息交给子代，子代按照所得的信息发育、分化，与亲代具有相同或相似性状物种能够稳定存在物种能够稳定存在亲代和子代、子代不同个体之间有差异随机发生，保证生命的多样性随机发生，保证生命的多样性具有适应性变异的个体被保留，不适应的被淘汰物种朝着适应环境的方向发展物种朝着适应环境的方向发展初始种群初始种群计算适应度计算适应度满足终满足终止条件止条件最佳个体最佳个体YesNo选选择择交交叉叉变变异异population个体(individual)的集合初始种群初始种群计算适应度计算适应度满足终满足终止条件止条件最佳个体最佳个体YesNo选选择择交交叉叉变变异异fitness评价个体好坏的依据初始种群初始种群计算适应度计算适应度满足终满足终止条件止条件最佳个体最佳个体YesNo选选择择交交叉叉变变异异终止进化的代数初始种群初始种群计算适应度计算适应度满足终满足终止条件止条件最佳个体最佳个体YesNo选选择择交交叉叉变变异异遗传算子遗传算子遗传算子n选择算子（selection）n交叉算子（crossover）n变异算子（mutation）n选择算子是对群体中的个体进行优胜劣汰的操作 用来确定重组或交叉个体，以及被选个体将产生多少个子代个体n常见的选择操作 轮盘赌选择法（roulette wheel selection）随机遍历抽样法（stochastic universal sampling）局部选择法（local selection）截断选择法（truncation selection）锦标赛选择法（tournament selection）选择算子(Selection Operator)交叉算子(Crossover Operation)n交叉算子是结合来自父代交配种群的信息产生新的个体n按个体编码方式，分为 实值重组实值重组 二进制交叉二进制交叉离散重组、中间重组、线性重组单点交叉、多点交叉、均匀交叉单点交叉：单点交叉：多点交叉：多点交叉：变异算子(Mutation Operator)n子代基因按小概率扰动产生的变化n按个体编码方式，分为 实值变异实值变异 二进制变异二进制变异随机变异、非均匀变异随机变异、非均匀变异单点变异：单点变异：多点变异：多点变异：应用情况n函数优化n组合优化n生产调度问题n自动控制n机器人智能控制n人工生命n机器学习免疫算法（Immune Algorithm）nInspired:生物自然科学中生物体的免疫免疫功能免疫的基本思想n对抗原反应有明显的专一性，是特异性免疫反应特异性免疫反应的主要细胞n具有摄取抗原、处理抗原并将处理后的抗原以某种方式提供给前一类细胞作用，在参与非特异性免疫反应非特异性免疫反应的同时，也能积极的参与特异性免疫反应免疫概念的提出是受生物自然科学的启发。在生命科学中，免疫功能主要由参与免疫反应的细胞完成的。免疫算子（Immune Operator）n引入了一个新的算子免疫算子免疫算子非特异性免疫特异性免疫免疫算子目标免疫（Target Immunity）全免疫（Full Immunity）免疫算子n全免疫全免疫指群体中每个个体变异操作后，对每一环节都进行一次免疫操作，它主要用于个体进化的初始阶段n目标免疫目标免疫指个体在进行变异操作后，经过一定判断，个体仅在作用点处发生免疫反应，其作用将伴随群体进化的全部过程对所求解的问题进行具体分析，从中提取出最基本的特征信息，即疫苗(vaccine)免疫算法流程图按照先验知识修改个体某些基因位上的基因，使个体以较大概率具有更高的适应度。设有种群c，对c接种疫苗是指在c中按比例（01）随机抽取 n=n个个体进行操作免疫算法流程图对接种了疫苗的个体进行检测，若其适应度不如父代，则用父代中的对应个体取代该个体；否则，以概率选择个体xi进入新的父代种群。其中，f（xi）为xi的适应度 Tk 为趋于0的温度序列且初温T0应尽可能的大，它与各状态目标值的方差有关，温度更新函数为(g为当前代数):免疫算法流程图免疫算法流程图应用情况n具备免疫特征和功能的人工生命系统人工免疫系统n基于免疫网络理论设计自治式多Agent系统n免疫性自适应系统n免疫型安全系统或抗干扰系统n面向医学应用的数字免疫监控系统 蚁群算法（Ant Colony Optimization）n1992年，意大利 Marco DorigonInspired:自然界中的蚂蚁可以找到从巢穴到食物 源的最短回路最短回路自然界中的蚂蚁n可以相互交流信息信息素信息素（pheromone）n倾向于选择留有信息素的道路n道路上留下的信息素越多，被选中概率越大用蚁群算法求最短路程 n一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回 n蚂蚁在往返途中，在路上留下外激素标志。n外激素将随时间逐渐蒸发（一般可用负指数函数来描述，即乘上因子exp(-a*t)）n由蚁穴出发的蚂蚁,其选择路径的概率与各路径上的外激素浓度成正比 蚁群算法（Ant Colony Optimization）应用n重建路由通讯 最短路由选择n求解TSP问题 旅行商问题：求周游所有指定的城市，最后回到出发 点的最短路径合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院 图像信息处理研究室图像信息处理研究室 Tel:2901393 Email: http:/ 仿照蚂蚁这种功能,设计蚂蚁的分类算法分类算法美国MCIWorld-com公司一直研究人工蚂蚁，用于管理公司的电话网；对用户记帐收费等工作一群蚂蚁同心协力搬大食物，设计多机器人合作规划问题 蚁群中蚂蚁的职责分工明确（蚁皇、工蚁、兵蚁）各司其职美国西北大学研究人工蚂蚁算法用于卡车厂中的油漆车间，使工厂各车间改变颜色的次数更少 粒子群算法（Particle Swarm Optimization）n1995年，Prof.J.Kennedy Prof.R.C.EberhartnInspired:社会系统，群智能（swarm intelligence）由简单个体组成的群落与环境以及个体之间的互动行为系统利用局部信息从而可能产生不可预测的群体行为鸟类觅食行为n一群鸟在随机搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。n找到食物的最优策略最优策略？搜寻目前离食物最近的鸟的周围区域粒子群算法（PSO）n每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子粒子”n所有的粒子都有一个由被优化的函数决定的适应值适应值n每个粒子还有一个速度速度决定他们飞翔的方向和距离n粒子追随当前的最优粒子最优粒子在解空间中搜索初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是令PSO初始化为一群随机粒子(随机解)，粒子i的信息可以用D维向量表示，则位置表示为：Xi=(xi1,xi2,xiD)T速度表示为：Vi=(vi1,vi2,viD)T初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是计算粒子的适应度值，如果好于该粒子当前的个体极值，则将pbest设置为该粒子的位置，更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值，则将gbest设置为该粒子的位置，记录该粒子的序号，且更新全局极值 初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是在每一次迭代中,粒子通过跟踪两个“极值”来更新自己，它们分别是个体极值点（pbest）和全局极值点(gbest）。速度更新方程为：vidk+1=vidk+c1rand1k(pbestidk-xidk)+c2rand2k(gbestdk-xidk）其中，加速常数c1和c2代表将每个微粒推向pbest和gbest位置的统计加速项的权重；通常，c1和c2为常数时可以得到较好的解 初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是位置更新方程为：xidk+1=xidk+vidk+1初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是检验是否符合结束条件：如果当前的迭代次数达到了预先设定的最大次数(或达到最小错误要求),则停止迭代,输出最优解；否则转到对粒子的适应度值的计算初始化粒子以及粒子速度初始化粒子以及粒子速度粒子适应度检测粒子适应度检测粒子速度、位置更新粒子速度、位置更新Present优于优于pbest?pbest=PresentPresent优于优于gbest?gbest=Present算法的收敛准则满足？算法的收敛准则满足？输出输出gbest否否否否否否是是是是是是应用情况n数值优化n神经网络训练n模糊系统控制n人工生命n在一些实际应用领域的进展：对医学中震颤行为的分析、模糊控制器的设计、车间任务调度、实时机器人路径规划、图像分割、EEG信号模拟、语音识别、烧伤诊断以及探测移动目标等 模拟退火算法（Simulated Annealing Algorithm）n1953年，MetroplisnInspired:固体退火原理固体退火n将固体加温至充分高，再让其徐徐冷却n加温时，固体内部粒子随温升变为无序无序状，内能增大n徐徐冷却时粒子渐趋有序有序，在每个温度都达到平衡平衡态n在常温时达到基基态，内能减为最小 模拟退火n算法开始时，设置较高的初温n较高概率移向 non-optimaln随着温度不断降低，算法终止于能量最低点E系统能量；T温度；kBoltzmann常数算法步骤：(1)初始化：初温T(充分大)，初始解S，迭代次数L(2)对k=1L做第(3)至第6步(3)产生新解(4)计算增量 (5)若 则接受 作为新的当前解；否则以概率概率接受其作为新的当前解(6)满足终止条件则输出当前解作为最优解，结束程序(7)T逐渐减少，且T趋于0，转第2步应用n组合优化(TSP)n最大截问题(Max Cut Problem)n0-1背包问题(Zero One Knapsack Problem)n图着色问题(Graph Colouring Problem)n调度问题(Scheduling Problem)总结大多数演化计算技术都是用同样的过程1.种群随机初始化2.对种群内的每一个个体计算适应值，适应值与最优解的距离直接有关3.种群根据适应值进行复制 4.如果终止条件满足的话，就停止，否则转步骤2关键问题n个体编码（Encoding）n适应度函数（Fitness）适应度适应度：度量某个物种对于生存环境的适应程度个体问题 二进制编码二进制编码 浮点数编码浮点数编码 格雷码、DNA编码谢谢！谢谢！