《自然计算》PPT课件.ppt

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