人工智能第12章群智能.pptx

《人工智能第12章群智能.pptx》由会员分享，可在线阅读，更多相关《人工智能第12章群智能.pptx（73页珍藏版）》请在三一办公上搜索。

1、人工智能,第十二章 群智能,12.1 群智能概述12.2 蚁群算法12.3 粒子群优化算法12.4 其他群智能优化算法,群智能（Swarm Intelligence，SI）优化算法通过模拟自然界中的昆虫、鸟群、鱼群等“社会性”生物群体的行为特征，利用群体性生物能够不断学习自身经验与其他个体经验的特性，在寻优过程中不断获取和积累寻优空间的知识，自适应地进行搜索寻优，从而得到最优解或准有解。群智能优化算法作为一种新兴的演化计算技术，具有较强的自学习性、自适应性、自组织性等智能特征，算法结构简单、收敛速度快、全局收敛性好，在旅行商问题、图着色问题、车间调度问题、数据聚类问题等领域得到广泛的应用，与进

2、化算法和人工神经网络并称为人工智能领域的三驾马车。,12.1 群智能概述,自然界中的群体生物，具有惊人的完成复杂行为的能力，群智能优化算法则是国内外研究学者受到群体生物的社会行为启发而提出。其中提出时间最早、应用最为广泛的群智能优化算法主要是模拟蚂蚁觅食行为的蚁群算法（Ant Colony Optimization，ACO）和模拟鸟类觅食行为的粒子群优化算法（Particle Swarm Optimization，PSO）。,12.1.1 群智能优化算法定义,鸟群通过协作进行捕食,房间偏僻角落里的蛋糕总会先被蚂蚁发现,鱼聚集成群可以有效的逃避捕食者,群智能优化算法主要源于对自然界中群体生物觅食

3、等行为的模拟，每个具有经验和智慧的个体通过相互作用机制形成强大的群体智慧来解决复杂问题。其主要算法流程如下。将寻优过程模拟成生物个体的觅食等行为过程，用搜索空间中的点模拟自然界中的生物个体；将求解问题的目标函数量化为生物个体对环境的适应能力；将生物个体觅食等行为过程类比为传统寻优方法用较优的可行解取代较差可行解的迭代过程，从而演化成为一种具有“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。,群智能主要算法流程,12.1.2 群智能优化算法原理,自然界中的昆虫、鸟群、鱼群等一些生物具有群体性的行为特征，计算机图形学家雷诺兹（C.Reynolds）认为以群落形式生存的生物

4、在觅食时一般遵循以下三个规则。1）分隔规则：尽可能避免与周边生物个体距离太近，造成拥挤；2）对准规则：尽可能与周边生物个体的平均移动方向保持一致，向目标方向移动；3）内聚规则：尽可能向周边生物个体的中心移动。,上述规则中，分隔规则体现出生物的个体信息特征，即个体根据自身当前状态进行决策；对准规则和内聚规则体现生物的群体信息特征，即个体根据群体状态进行决策。除个体信息与群体信息特征，生物行为还具有适应性、盲目性、自治性、突现性、并行性等特征。群智能优化算法就是利用雷诺兹模型模拟整个生物群体的行为，算法在迭代过程中不断利用个体最优值与群体最优值进行寻优搜索，完成个体信息与群体信息的交互。在群智能优

5、化算法中，个体最优值的随机性使得算法搜索方向具有多样性，能够避免算法收敛过早陷入局部最优；群体最优值能够把握全局寻优方向，提高算法的全局寻优能力，及时收敛。,12.1.3 群智能优化算法特点,群智能优化算法主要用来求解一些复杂的、难以用传统算法解决的问题。与传统优化算法不同，群智能优化算法是一种概率搜索算法，具有以下几个特点。具有较强的鲁棒性，群体中相互作用的个体是分布式的，没有直接的控制中心，不会因少数个体出现故障而影响对问题的求解。结构简单，易于实现，每个个体只能感知局部信息，个体遵循的规则简单。易于扩充，开销较少。具有自组织性，群体表现出的智能复杂行为由简单个体交互而来。,12.2 蚁群

6、算法,蚁群算法，又称为蚂蚁算法，1992年多里戈（M.Dorigo）受自然界中真实蚁群的群体觅食行为启发提出，是最早的群智能优化算法，起初被用来求解旅行商（Total Suspended Particulate，TSP）问题。,12.2.1 蚁群算法概述,蚂蚁是一种社会性生物，在寻找食物时，会在经过的路径上释放一种信息素，一定范围内的蚂蚁能够感觉到这种信息素，并移动到信息素浓度高的方向，因此蚁群通过蚂蚁个体的交互能够表现出复杂的行为特征。蚁群的群体性行为能够看作是一种正反馈现象，因此蚁群行为又可以被理解成增强型学习系统（Reinforcement Learning System）。,12.2.

7、2 蚁群算法的数学模型,蚁群优化算法的第一个应用是著名的旅行商问题。,旅行商问题,蚁群系统模型,旅行商问题（Traveling Salesman Problem，TSP）：在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。,蚂蚁搜索食物的过程：通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径。,符号表示,m 是蚁群中蚂蚁的数量；表示结点i（城市）和结点j（城市）之间的距离；表示t时刻在ij连线上残留的信息素，初始时刻，各条路径上 的信息素相等，蚂蚁k在运动过程中，根据各条路径上的信息 素决定转移方向。称为启发信息函数，等于距离的倒数；,表示在t

8、时刻蚂蚁 k 选择从结点（城市）i 转移到结点（城 市）j的概率，也称为随机比例规则。,信息素,局部启发信息,表示蚂蚁k下一步允许选择的城市 记录蚂蚁k当前所走过的城市 是信息素启发式因子，表示轨迹的相对重要性 表示期望启发式因子，表示能见度的相对重要程度,1-表示信息素残留因子，常数 为信息素挥发因子，表示路径上信息素的损耗程度；的大小关系到算法的全局搜索能力和收敛速度。蚂蚁完成一次循环，各路径上信息素浓度挥发规则为：蚁群的信息素浓度更新规则为：,根据信息素更新策略不同，多里戈提出了3种基本蚁群算法模型。,1、蚁周系统（Ant-cycle System）,单只蚂蚁所访问路径上的信息素浓度更新

9、规则为：Q 为常数Lk 为优化问题的目标函数值，表示第k只蚂蚁在本次循环中所走路径的长度。,2、蚁量系统（Ant-quantity System）,3、蚁密系统（Ant-density System）,三种模型比较,效果最好，通常作为蚁群优化算法的基本模型。,设置参数,初始化信息素浓度While（不满足条件时）dofor蚁群中的每只蚂蚁for每个解构造步骤(直到构造出完整的可行解)1）蚂蚁按照信息素及启发因子构造下一步问题的解；2）进行信息素局部更新。(可选)end forend for1）以已获得的解为起点进行局部搜索；(可选)2）根据已获得的解的质量进行全局信息素更新。end Whilee

10、nd,蚁群算法流程,12.2.3 蚁群算法的改进,为提高蚁群算法性能，诸多研究学者对蚁群算法进行了改进，其中主要包括蚂蚁-Q系统（Ant-Q System）、蚁群系统（Ant Colony System,ACS）、最大-最小蚂蚁系统（Max-Min Ant System，MMAS）、自适应蚁群算法。,蚂蚁-Q系统1995年，意大利学者卢卡（M.Luca）、甘巴德拉（L.M.Gambardella）、多里戈在ACO算法的基础上，进行了创新，提出了蚂蚁-Q系统。,在解构造过程中提出了伪随机比例状态迁移规则；信息素局部更新规则引入强化学习中的Q学习机制；在信息素的全局更新中采用了精英策略。,其概率分

11、布计算、AQ值更新规则分别为：,其中：,1996年，甘巴德拉和多里戈又在Ant-Q算法的基础上提出了蚁群系统，蚁群系统是Ant-Q算法的一种特例。其主要创新如下：,蚁群系统,相比ACO算法，蚁群系统中的蚂蚁在下一步移动之前，增加一次随机实验，将选择情况分成“利用已知信息”和“探索”两类。提出了精英策略（Elitist Strategy）。设置精英蚂蚁数目的最优范围：若低于该范围，增加精英蚂蚁数目，以便能够较快的发现最优路径；若高于该范围，精英蚂蚁会在搜索初期迫使寻优过程停留在次优解附近，降低算法性能。,其中状态转移规则为：,其中，Sk表示蚂蚁k所选中的下一个结点；q是一个随机变量，,为设定阈值

12、。,1997年，德国学者施蒂茨勒（T.Stutzle）提出了最大-最小蚂蚁系统。其主要创新如下：,最大-最小蚂蚁系统,为了避免算法收敛过早，陷入局部最优，将各条路径的信息素浓度限制到min,max区间范围内。采用了平滑机制，路径上信息素浓度的增加与max和当前浓度(i,j)之差成正比，即,其中，0 1。,自适应蚁群算法自适应蚁群算法能够根据搜索结果进行信息素浓度更新，如果算法陷入局部最优，自适应调整陷入局部最优的蚂蚁所经过路径中的信息素和信息素强度Q，使得算法能够较快的跳出局部最优，避免算法“早熟”，同时自适应蚁群算法限定所有路径上的信息素范围，有利于提高算法全局搜索能力。,蚁群算法最早被用来

13、解决旅行商问题，随后陆续被用于解决图着色问题、二次分配问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题、数据聚类问题、武器攻击目标分配和优化问题、区域性无线电频率自动分配问题等。,12.2.3 蚁群算法的应用示例,旅行商问题描述如下：假设,为一个加权图，,为顶点集，,为边集。,为顶点i到顶点j的距离，其中,且,，同时,。,经典TSP的数学模型为：,是图s的顶点数。,实际问题可以描述为：一行人要去27个城市旅行，其中城市坐标如表所示，该人从一城市出发，使用蚁群算法计算，应如何选择行进路线，以使总的行程最短。,应用基本蚁群算法进行建模，可计算得出行程最短路径为：城市19

14、城市4城市2城市24城市26城市8城市7城市3城市18城市1城市5城市10城市6城市25城市14城市15城市9城市21城市22城市11城市23城市12城市16城市20城市13城市27城市17。,12.3 粒子群优化算法,粒子群优化算法（Particle Swarm Optimization，PSO）源于对鸟群社会系统的研究，由美国普渡大学的埃伯哈特（J.Eberhart）和肯尼迪（R.Kennedy）于1995年提出。其核心思想是利用个体的信息共享促使群体在问题解空间从无序进行有序演化，最终得到问题的最优解。,可用如下经典描述直观理解粒子群优化算法：设想这么一个场景：一群鸟在寻找食物，在远处有

15、一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最优策略就是搜寻目前距离玉米地最近的鸟群的所在区域。粒子群优化算法就是从鸟群食物的觅食行为中得到启示，从而构建形成的一种优化方法。,12.3.1 粒子群优化算法基本思想,粒子群优化算法将每个问题的解类比为搜索空间中的一只鸟，称之为“粒子”，问题的最优解对应为鸟群要寻找的“玉米地”。每个粒子设定一个初始位置和速度向量，根据目标函数计算当前所在位置的适应度值（Fitness Value），可以将其理解为距离“玉米地”的距离。粒子在迭代过程中，根据自身的“经验”和群体中的最优粒子的“经验”进行学

16、习，从而确定下一次迭代时飞行的方向和速度。通过逐步迭代，整个群体逐步趋于最优解。,在n 维连续搜索空间中，对粒子群中的第i(i=1,2,m)个粒子进行定义：,：表示搜索空间中粒子的当前位置。,：表示该粒子至今所获得的具有最优适应度 的位置。,：表示该粒子的搜索方向。,12.3.2 粒子群优化算法基本框架,：表示每个粒子经历过的最优位置（Pbest）。,：群体经历过的最优位置（Gbest）。,c1，c2 是速度因子，均为非负值；r1 和 r2 为0,1 范围内的随机数。,早期的粒子群优化算法速度和位置向量更新公式如下：,=1,2,；,由于 的更新过于随机，使得粒子群优化算法具有较强的全局寻优能力

17、，但是局部寻优能力较差。为保证算法具有全局寻优能力的同时，提高其局部寻优能力。1998年Shi Yuhui和埃伯哈特在算法中引入惯性权重（Inertia Weight）系数w，修正了速度向量更新公式：,参数w取值范围为0,1，与物理中的惯性相似，w反映了粒子历史运动状态对当前运动的影响。如果w取值较小，历史运动状态对当前运动影响较小，粒子的速度能够很快的改变；相反，如果w取值较大，虽然提高了搜索空间范围，但是粒子运动方向不易改变，难于向较优位置收敛。因此w设置较大时，能够提高算法全局寻优能力，w设置较小时，又能够加快算法局部寻优。实际工程应用中w可采取自适应取值方式。,粒子群优化算法流程,pr

18、ocedure PSO for 每个粒子i 初始化每个粒子i，随机设置每个粒子的初始位置,和速度,计算每个粒子i的目标函数，Gbest=,end for Gbest=minPbesti while not stop for i=1 to m 更新粒子i的速度和位置 if fit(,)fit(Pbesti)Pbesti=,if fit(Pbesti)fit(Gbest)Gbest=Pbesti;end for end while print Gbestend procedure,12.3.3 粒子群优化算法参数分析与改进,粒子群优化算法中主要参数如下：种群规模m种群规模通常设置为20-40，可根

19、据不同问题进行自定义。惯性权重w惯性权重能够保持粒子运动惯性，扩展搜索空间，搜索新的区域。最大速度Vmax最大速度Vmax决定当前位置与最优位置之间的区域的精度。若Vmax过大，粒子可能跨过最优位置；若Vmax过小，粒子无法在局部最优值之外进行足够的探索，易陷入局部最优。限制最大速度可以有效防止计算溢出、决定问题空间搜索的粒度。迭代次数Gmax迭代次数Gmax根据工程应用具体问题决定。,学习因子c1、c2学习因子c1、c2分别控制个体认知分量和群体社会分量相对贡献的学习率。当c1=0、c2=0时，只有第1部分，粒子保持当前速度飞行，直到达边界，只能搜索有限的区域，无法找到最优解。w=0时，没有

20、第1部分，速度没有记忆性，只取决于粒子当前位置和其历史最优位置。当c1=0时，没有第2部分，粒子没有认知能力，只有“社会模型”。在粒子的相互作用下，有能力达到新的搜索空间。但是复杂问题容易陷入局部最优。当c2=0时，没有第3部分，粒子间没有社会共享信息，只有“认知模型”。个体间没有交互，群体中所有个体独立搜索，因此无法得到最优解。,粒子群优化算法的改进,粒子群优化算法具有收敛速度快的优点，但是在算法运行初期，算法存在精度较低、易发散等缺点。因此国内外诸多研究人员致力于提高粒子群优化算法的性能，现阶段主要侧重理论研究改进、拓扑结构改进、混合改进算法、参数优化等方面。,粒子群优化算法自提出至今，被

21、广泛的应用于神经网络训练、机器人、经济、通信、医学等多种领域。本节示例为粒子群优化算法在车辆路径问题（Vehicle Routing Problem，VRP）中的应用。,12.3.4 粒子群优化算法的应用示例,假定配送中心最多可以用 辆车对 个客户进行运输配送，表示仓库。每个车辆载重为，每个客户的需求为，客户i到客户 j 的运输成本为 cij（可以是距离，时间，费用等）。定义如下变量：,1、建立车辆路径问题的数学模型如下：,每辆车的能力约束：,保证每个客户都被服务：,保证客户是仅被一辆车访问：,保证客户是仅被一辆车访问：,消除子回路：,表示变量的取值范围：,表示变量的取值范围：,2、编码与初始

22、种群,对这类组合优化问题，编码方式、初始解的设置对问题的求解都有很大的影响。本问题采用常用的自然数编码方式。对于K辆车和L个客户的问题，用从1到L的自然数随机排列来产生一组解。然后分别用节约法或者最近插入法构造初始解。,粒子群优化算法的各个参数设置如下：种群规模p=50，迭代次数Gmax=1000，w的初始值为1，随着迭代的进行，线性减小到0，c1=c2=1.4，。,优化结果及其比较,12.4 其他群智能优化算法,随着蚁群算法、粒子群优化算法的广泛应用，各类群智能优化算法蜂拥而至。其中较为典型的几种包括人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）、细

23、菌觅食算法（Bacterial Foraging Optimization，BFO）、蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）、果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）等。,人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA），由李晓磊博士于2001年提出，是一种源于鱼群自治行为的群智能优化算法，通过构造人工鱼来模仿鱼群的觅食、聚群、追尾和随机行为，从而实现寻优，具有较快的收敛速度，可以用于解决有实时性要求的问题。,12.4.1 人工鱼群算法,人工鱼的结构图,假设人工

24、鱼当前状态为X，Visual代表其视野范围，Xv表示某时刻其视点所在位置。若该位置的状态优于当前状态，向当前位置方向前进一步到达状态Xnext；若状态Xv比当前状态差，继续巡视视野内的其他位置。巡视的次数越多，对视野范围内的信息了解越全面，从而能够全方位立体感知周围的环境，有助于对目标问题做出相应的判断和决策。,人工鱼群算法基本概念,人工鱼视觉的概念,其中，状态，状态，则该过程可以表示为：,式中，rand函数用来产生0,1之间的随机数；Step为移动步长。,人工鱼群算法采用面向对象的技术重构人工鱼的模型，将人工鱼封装成变量和函数两部分。其中变量部分包括人工鱼的总数N，人工鱼个体的状态,为待寻优

25、的变量），人工鱼移动的最大步长Step，人工鱼的视野Visual，尝试次数Try_number，拥挤度因子,，人工鱼个体i,j之间的距离。,函数部分包括人工鱼当前所处位置的食物浓度,人工鱼的各种行为函数（觅食行为Prey()、聚群行为Swarm()、追尾行为Follow()、随机行为Move()以及行为评价函数Evaluate()）。通过封装，人工鱼的状态能够被其他同伴感知。,（Y为目标函数值）,觅食行为,聚群行为,追尾行为,随机行为,人工鱼的四种基本行为算法描述,由于鱼类不具备复杂逻辑推理能力和综合判断能力，它们只能通过简单行为达到目的。因此通过模拟鱼类的四种行为觅食行为、聚群行为、追尾行为

26、和随机行为来使鱼类活动在周围的环境。,觅食行为是人工鱼趋向食物源的一种基本行为，一般通过视觉或味觉感知水中的食物数量或浓度，进行趋向选择。行为描述：设人工鱼i的当前状态为Xi，在其感知范围内随机选择一个状态Xj，则其中，rand是一个0,1之间的随机数，在求解问题极大值时，若YiYj，则向Xj方向前进一步：否则，再次随机选择状态Xj，判断是否满足前进条件，若反复尝试Try_number次后仍不满足前进条件，则随机移动一步：,觅食行为,这是鱼群生存和躲避危害的一种生活习性。在鱼群算法中，一般规定两条，一是尽量向邻近伙伴的中心移动，二是避免过分拥挤。行为描述：设人工鱼当前状态为Xi，当前搜索范围内

27、dijVisual，伙伴数目为，中心位置为Xo。若，表明伙伴中心食物较多且不存在过分拥挤，则向伙伴中心位置方向前进一步，即否则，执行觅食行为。,聚集行为,鱼群在游动过程中，当其中一条鱼或几条鱼发现食物时，其邻近的伙伴会尾随其快速到达食物点。行为描述：设人工鱼i当前状态为Xi，当前搜索范围内dijVisual，Xj为适应度值最优的伙伴，其适应度值为Yj。若，表明伙伴Xj附近食物浓度较高，且周围不够拥挤，则向Xj的方向前进一步：否则，执行觅食行为。,追尾行为,鱼类在水中自由地游来游去，表面看是随机的，目的也是为了在更大范围内寻找食物或伙伴。行为描述：随机行为是觅食行为的一个缺省行为，就是在视野中随

28、机选择一个状态，然后向该方向移动。人工鱼四种行为能够在不同的条件下进行相互转换，通过行为评价函数对行为进行评价，选取执行当前最优行为，寻找食物浓度最高的位置。对行为的评价是用来反应鱼自主行为的一种方式。在解决目标问题时，可以选用两种简单的评价方式：一种是选择执行当前最优行为；另一种是选择较优方向前进，任选一种行为，只要能向目标较优的方向前进即可。,随机行为,算法初始化；while 未达到满意结果 do switch(人工鱼群行为选择)case value1:觅食行为;case value2:聚群行为;default:追尾行为;end switch 随机行为;get_result();end w

29、hileend 人工鱼群算法end whileend,人工鱼群算法流程,在人工鱼群算法中，觅食行为确保了算法收敛性，群聚行为提高了算法收敛的稳定性，追尾行为提高了算法收敛的快速性和全局性，行为分析保障了算法收敛的速度和稳定性。,细菌觅食算法（Bacterial Foraging Optimization，BFO），由帕西诺（K.M.Passino）在2002年提出，是一种模拟Eeoli大肠杆菌在生物肠道内觅食行为的新型群智能优化算法。细菌觅食算法中，一个细菌代表一个解，具有简单、高效的特点。,12.4.2 细菌觅食算法,细菌觅食算法基本概念,细菌觅食算法是基于细菌觅食行为过程而提出的一种仿生随

30、机搜索算法，该算法主要通过模拟细菌群体的趋化，繁殖，驱散行为，实现对目标问题的优化。细菌觅食算法主要包括三层循环，外层是驱散操作，中间层是繁殖操作，内层是趋化操作。内层的趋化性操作是算法的核心，对应着细菌在寻找食物过程中采取的方向选择策略，与算法的收敛性息息相关。,1、趋化操作主要模拟细菌的游动和翻转两个主要的运动过程，细菌随机游动一步进行翻转运动，观察其适应度值是否得到改善，若得到改善，细菌则沿同一方向进行游动，直至适应度值无法继续改善或达到设定的游动步数。,2、繁殖操作繁殖操作主要模拟细菌个体优胜劣汰的繁殖过程，根据适应度值对所有细菌进行排序，将适应度值较差的一半细菌进行清除，保留较好的一

31、半进行复制，最终细菌总量不发生改变。,3、驱散操作驱散操作的目的是为了提高算法的全局寻优能力，当问题的解空间存在多个极值点时，细菌的群聚性使得多样性降低，算法易陷入局部最优。驱散操作过程是按照一定的概率P用新的个体来代替原有的个体，当某细菌个体满足驱散条件时，将其随机分配到解空间。,细菌觅食算法流程,假设大肠杆菌种群数量为S，最大游动步数用Ns表示，用m进行计数。将大肠杆菌i信息用 表示，；表示细菌i的当前位置，每个位置代表目标函数一个潜在解；D表示向量维数；j代表第j代趋化操作，k代表第k代繁殖操作，l代表第l代驱散操作。,细菌觅食算法更新公式为：,式中，c(i)0表示细菌的游动步长单位；表

32、示细菌翻转运动后随机改变的角度。,细菌觅食算法具体步骤,算法参数初始化，包括细菌个数S、趋化操作次数Nc、最大游动步数Ns、繁殖操作次数Nre、驱散操作次数Ned以及细菌个体驱散概率P、随机生成单个细菌的位置。种群位置初始化，计算每个细菌初始适应度值，j=0，k=0，l=0。驱散操作循环l=l+1。繁殖操作循环k=k+1。趋化操作循环i=i+1，每个细菌个体进行趋化操作。若j。繁殖操作，适应度值排在前S/2的个体进行繁殖，替换适应度值较小的另一半细菌。若k。驱散操作。当细菌i满足驱散概率，随机生成新的细菌替换细菌i。若l；否则，算法结束，输出问题最优结果。,12.4.3 混合蛙跳算法,混合蛙跳

33、算法（Shuffled Frog Leaping Algorithm，SFLA），由尤瑟夫（M.M.Eusuff）和兰西（K.E.Lansey）于2003年提出，是一种全新的后启发式群体智能算法，结合了模因演算MA（Memetic Algorithm）和粒子群优化算法2种算法的优点，具有高效的计算效率和良好的全局寻优能力。,混合蛙跳算法基本概念,混合蛙跳算法可以描述为：在一片空间区域内生活着一群青蛙，为了寻找食物较多的地方，蛙群首先按照一定的规则确定每只青蛙的初始位置。随后，每只青蛙利用个体信息在初始位置附近搜索食物更多的区域，跳跃完成个体位置更新。主要搜索规则为，蛙群利用青蛙的自组织性行为，

34、组成多个子种群，子种群中的青蛙个数基本相同，由子种群中的局部精英个体带领其他个体进行组团搜索。子种群完成一次搜索后，蛙群中的所有个体进行重新混合分组，继续执行组团。组团搜索与蛙群混合迭代进行，直至到达食物最丰富的位置。,混合蛙跳算法基本流程,混合蛙跳算法首先从可行域中随机产生一组初始解，每个解对应一只青蛙，形成初始种群；根据目标函数，计算每个青蛙的适应度值，进行由大到小排列；以一定的规则将蛙群划分为一定数量的子种群，每个子种群进行局部搜索，子种群内最差的青蛙根据更新策略向局部最优位置靠近；子种群完成一次局部搜索后，各子种群进行混合实现信息的交互；反复进行局部搜索和混合运算直至达到停止条件。,混

35、合蛙跳算法求解问题时，一般分为4个步骤。初始化从可行域中随机产生F个解 作为初始种群，其中S代表问题的维数。子种群划分根据目标函数，计算每个解的适应度值，将计算结果按照降序排列，并将适应度最优值记为 作为整个种群的最优解。根据排序结果开始子种群划分，第1个解进入子种群，第2个解进入子种群，直至第m个解进入子种群，然后第 个解进入，以此类推，直至所有的解分配完毕。最终可将蛙群等量划分为m个子种群，其中每个子种群包含n个解。每个子种群中，适应度值最佳和最差的解分别记为 和。,局部搜索在局部迭代过程中，各子种群只更新适应度值最差的解，其更新公式为：其中，；rand为取值范围0,1之间的随机数 为青蛙

36、的移动步长，表示允许青蛙移动的最大距离。,子种群混合将各子种群 重新混合为X，即，将X重新按适应度值进行降序排列，用整个种群中最优的青蛙位置更新，重新划分子种群，开始下一轮的局部搜索。经过上述4步就完成了混合蛙跳算法的一次迭代，问题解的位置得到了更新，反复进行子种群划分、局部搜索和混合运算直至满足算法停止条件得到问题最优解。,果蝇优化算法（Fruit Fly Optimization Algorithm）是基于果蝇觅食行为推演出寻求全局优化的新方法，由台湾学者潘文超博士于2011年提出。果蝇群体觅食行为主要依赖于自身强大的嗅觉与视觉能力，果蝇首先通过嗅觉搜索食物（可达40km远），当离食物较近

37、时，通过敏锐的视觉继续进行搜索，并最终找到食物源。,果蝇群体觅食行为过程,12.4.4 果蝇优化算法,根据果蝇群体搜索食物的特点，可将果蝇优化算法分为以下几个步骤：1、初始化果蝇群体位置(X_axis,Y_axis)。2、设定果蝇个体利用嗅觉器官搜寻食物的随机方向和距离。3、由于具体食物位置无法确定，先估计果蝇个体与原点的欧式距离Disti，再计算味道浓度判定值Si，Si为距离Disti的倒数。,果蝇优化算法流程,4、将味道浓度判定值Si代入味道浓度判定函数Function()，得出果蝇个体位置的味道浓度Smelli。5、找出该果蝇群体的中味道浓度值最高（求解极大值问题）/最低（求解极小值问题）的果蝇。,6、保留当前最佳味道浓度值与位置，果蝇群体利用视觉器官向该位置飞去。7、进行迭代寻优，重复执行步骤25，并判断当前味道浓度值是否优于上一代味道浓度值，若是则执行6。,