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

免疫部分的复习与补充内容免疫部分的复习与补充内容第1页主要内容：概述算法介绍

遗传算法（GeneticAlgorithm）

免疫算法（ImmuneAlgorithm）

蚁群算法（AntColonyOptimization）

粒子群算法（ParticleSwarmOptimization）

模拟退火算法（SimulatedAnnealingAlgorithm）免疫部分的复习与补充内容第2页引例:求函数最值求最小值免疫部分的复习与补充内容第3页免疫部分的复习与补充内容第4页求以下函数最大值免疫部分的复习与补充内容第5页免疫部分的复习与补充内容第6页怎么处理？遍历

怎样确定搜索范围和搜索精度？随机搜索

可能永远也无法找到最大值其它方法？免疫部分的复习与补充内容第7页免疫部分的复习与补充内容第8页随机取一些初始点依据某种算法，经过这些初始点相互作用，得出最终止果遗传算法（GA）采取方法：免疫部分的复习与补充内容第9页自然计算

(natureinspiredcomputation)Theinvestigationofmathematicaland/orengineeringtoolsthathavebeenimbuedwithselectedhigherlevel(systemic)characteristicsthatemergefromlowerlevelcomponentinteractionsandprocesses,inspiredbyabiologicalsystemorsystems免疫部分的复习与补充内容第10页含有模仿自然界特点，通常是一类含有自适应、自组织、自学习能力算法，能够处理传统计算方法难于处理各种复杂问题包含当前已被广泛研究进化计算、神经计算、生态计算、量子计算和复杂自适应系统等多个领域已成功地应用于组合优化、机器学习、工程设计等问题，并取得了很好效果免疫部分的复习与补充内容第11页遗传算法（GeneticAlgorithm）1962年，美国Michigan大学J.HollandInspired:自然界进化准则：适者生存、优胜劣汰

免疫部分的复习与补充内容第12页达尔文(1858)——自然选择遗传（heredity）变异（variation）生存斗争和适者生存亲代把生物信息交给子代，子代按照所得信息发育、分化，与亲代含有相同或相同性状物种能够稳定存在亲代和子代、子代不一样个体之间有差异随机发生，确保生命多样性含有适应性变异个体被保留，不适应被淘汰物种朝着适应环境方向发展免疫部分的复习与补充内容第13页初始种群计算适应度满足终止条件最正确个体YesNo选择交叉变异population个体(individual)集合免疫部分的复习与补充内容第14页初始种群计算适应度满足终止条件最正确个体YesNo选择交叉变异fitness评价个体好坏依据免疫部分的复习与补充内容第15页初始种群计算适应度满足终止条件最正确个体YesNo选择交叉变异终止进化代数免疫部分的复习与补充内容第16页初始种群计算适应度满足终止条件最正确个体YesNo选择交叉变异遗传算子免疫部分的复习与补充内容第17页遗传算子选择算子（selection）交叉算子（crossover）变异算子（mutation）免疫部分的复习与补充内容第18页选择算子是对群体中个体进行优胜劣汰操作

用来确定重组或交叉个体，以及被选个体将产生多少个子代个体常见选择操作

轮盘赌选择法（roulettewheelselection）随机遍历抽样法（stochasticuniversalsampling）局部选择法（localselection）截断选择法（truncationselection）锦标赛选择法（tournamentselection）选择算子(SelectionOperator)免疫部分的复习与补充内容第19页

交叉算子

(CrossoverOperation)交叉算子是结合来自父代交配种群信息产生新个体按个体编码方式，分为实值重组二进制交叉离散重组、中间重组、线性重组单点交叉、多点交叉、均匀交叉免疫部分的复习与补充内容第20页单点交叉：多点交叉：免疫部分的复习与补充内容第21页变异算子(MutationOperator)子代基因按小概率扰动产生改变按个体编码方式，分为实值变异二进制变异随机变异、非均匀变异随机变异、非均匀变异免疫部分的复习与补充内容第22页单点变异：多点变异：免疫部分的复习与补充内容第23页应用情况函数优化组合优化生产调度问题自动控制机器人智能控制人工生命机器学习免疫部分的复习与补充内容第24页免疫算法（ImmuneAlgorithm）Inspired:

生物自然科学中生物体免疫功效免疫部分的复习与补充内容第25页免疫基础思想反抗原反应有显著专一性，是特异性免疫反应主要细胞含有摄取抗原、处理抗原并将处理后抗原以某种方式提供给前一类细胞作用，在参加非特异性免疫反应同时，也能主动参加特异性免疫反应免疫概念提出是受生物自然科学启发。在生命科学中，免疫功效主要由参加免疫反应细胞完成。免疫部分的复习与补充内容第26页免疫算子（ImmuneOperator）引入了一个新算子——免疫算子非特异性免疫特异性免疫免疫算子目标免疫（TargetImmunity）全免疫（FullImmunity）免疫部分的复习与补充内容第27页免疫算子全免疫指群体中每个个体变异操作后，对每一步骤都进行一次免疫操作，它主要用于个体进化初始阶段目标免疫指个体在进行变异操作后，经过一定判断，个体仅在作用点处发生免疫反应，其作用将伴随群体进化全部过程免疫部分的复习与补充内容第28页对所求解问题进行详细分析，从中提取出最基础特征信息，即疫苗(vaccine)免疫算法流程图免疫部分的复习与补充内容第29页按照先验知识修改个体一些基因位上基因，使个体以较大约率含有更高适应度。设有种群c，对c接种疫苗是指在c中按百分比α（0＜α≤1）随机抽取nα=αn个个体进行操作免疫算法流程图免疫部分的复习与补充内容第30页对接种了疫苗个体进行检测，若其适应度不如父代，则用父代中对应个体取代该个体；不然，以概率选择个体xi进入新父代种群。其中，f（xi）为xi适应度

{Tk}

为趋于0温度序列且初温T0应尽可能大，它与各状态目标值方差相关，温度更新函数为(g为当前代数):

免疫算法流程图免疫部分的复习与补充内容第31页免疫算法流程图免疫部分的复习与补充内容第32页应用情况具备免疫特征和功效人工生命系统——人工免疫系统基于免疫网络理论设计自治式多Agent系统免疫性自适应系统免疫型安全系统或抗干扰系统面向医学应用数字免疫监控系统免疫部分的复习与补充内容第33页

蚁群算法

（AntColonyOptimization）1992年，意大利MarcoDorigoInspired:

自然界中蚂蚁能够找到从巢穴到食物源最短回路免疫部分的复习与补充内容第34页自然界中蚂蚁能够相互交流信息——信息素（pheromone）倾向于选择留有信息素道路道路上留下信息素越多，被选中概率越大免疫部分的复习与补充内容第35页免疫部分的复习与补充内容第36页用蚁群算法求最短旅程一群蚂蚁随机从出发点出发，碰到食物，衔住食物，沿原路返回蚂蚁在往返途中，在路上留下外激素标志。外激素将随时间逐步蒸发（普通可用负指数函数来描述，即乘上因子exp(-a*t)）由蚁穴出发蚂蚁,其选择路径概率与各路径上外激素浓度成正比

蚁群算法

（AntColonyOptimization）免疫部分的复习与补充内容第37页应用重建路由通讯

最短路由选择求解TSP问题

旅行商问题：求周游全部指定城市，最终回到出发点最短路径免疫部分的复习与补充内容第38页合肥工业大学计算机与信息学院图像信息处理研究室

Tel:2901393Email:images@/organ/images其它算法蚂蚁去除垃圾蚂蚁搬大食物任务分配问题蚂蚁能将巢里垃圾或死蚂蚁,清扫成几大堆给以去除

仿照蚂蚁这种功效,设计蚂蚁分类算法美国MCIWorld-com企业一直研究人工蚂蚁，用于管理企业电话网；对用户记帐收费等工作一群蚂蚁同心协力搬大食物，设计多机器人合作规划问题

蚁群中蚂蚁职责分工明确（蚁皇、工蚁、兵蚁）各司其职美国西北大学研究人工蚂蚁算法用于卡车厂中油漆车间，使工厂各车间改变颜色次数更少免疫部分的复习与补充内容第39页

粒子群算法

（ParticleSwarmOptimization）1995年，Prof.J.KennedyProf.R.C.EberhartInspired:

社会系统，群智能（swarmintelligence）由简单个体组成群落与环境以及个体之间互动行为系统利用局部信息从而可能产生不可预测群体行为免疫部分的复习与补充内容第40页鸟类觅食行为一群鸟在随机搜索食物，在这个区域里只有一块食物，全部鸟都不知道食物在那里。不过他们知道当前位置离食物还有多远。找到食物最优策略？搜寻当前离食物最近鸟周围区域免疫部分的复习与补充内容第41页粒子群算法（PSO）每个优化问题解都是搜索空间中一只鸟，称之为“粒子”全部粒子都有一个由被优化函数决定适应值每个粒子还有一个速度决定他们翱翔方向和距离粒子追随当前最优粒子在解空间中搜索免疫部分的复习与补充内容第42页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新Present优于pbest?pbest=PresentPresent优于gbest?gbest=Present算法收敛准则满足？输出gbest否否否是是是令PSO初始化为一群随机粒子(随机解)，粒子i信息能够用D维向量表示，则位置表示为：Xi=(xi1,xi2,…,xiD)T速度表示为：Vi=(vi1,vi2,…,viD)T免疫部分的复习与补充内容第43页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新Present优于pbest?pbest=PresentPresent优于gbest?gbest=Present算法收敛准则满足？输出gbest否否否是是是计算粒子适应度值，假如好于该粒子当前个体极值，则将pbest设置为该粒子位置，更新个体极值。假如全部粒子个体极值中最好好于当前全局极值，则将gbest设置为该粒子位置，统计该粒子序号，且更新全局极值

免疫部分的复习与补充内容第44页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新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为常数时能够得到很好解免疫部分的复习与补充内容第45页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新Present优于pbest?pbest=PresentPresent优于gbest?gbest=Present算法收敛准则满足？输出gbest否否否是是是位置更新方程为：

xidk+1=xidk+vidk+1免疫部分的复习与补充内容第46页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新Present优于pbest?pbest=PresentPresent优于gbest?gbest=Present算法收敛准则满足？输出gbest否否否是是是检验是否符合结束条件：假如当前迭代次数到达了预先设定最大次数(或到达最小错误要求),则停顿迭代,输出最优解；不然转到对粒子适应度值计算免疫部分的复习与补充内容第47页初始化粒子以及粒子速度粒子适应度检测粒子速度、位置更新Present优于pbest?pbest=PresentPresent优于gbest?gbest=Present算法收敛准则满足？输出gbest否否否是是是免疫部分的复习与补充内容第48页应用情况数值优化神经网络训练含糊系统控制人工生命在一些实际应用领域进展：

对医学中震颤行为分析、含糊控制器设计、车间任务调度、实时机器人路径规划、图像分割、EEG信号模拟、语音识别、烧伤诊疗以及探测移动目标等免疫部分的复习与补充内容第49页

模拟退火算法

（SimulatedAnnealingAlgorithm）1953年，MetroplisInspired:

固体退火原理免疫部分的复习与补充内容第50页固体退火将固体加温至充分高，再让其渐渐冷却加温时，固体内部粒子随温升变为无序状，内能增大渐渐冷却时粒子渐趋有序，在每个温度都到达平衡态在常温时到达基态，内能减为最小

免疫部分的复习与补充内容第51页模拟退火算法开始时，设置较高初温较高概率移向non-optim