人工生命算法研究综述

人工生命算法研究综述

1人工生命算法的基本原理1987年9月21日，在美国洛斯阿拉莫斯的人类生活研讨会上，人类生活是一个新的研究科学。c.g.langoon教授是人性生命概念的创始人，被公认为“人性生命之父”。他将人工生命定义为“人工生命是研究能够展示出自然生命系统特征的人造系统”。该系统能够演示具有自然生命特征如自我繁衍、进化、自组织等行为。人工生命系统,首先由Andrew和Norman提出,它是一个人工生命群落的模型。这个群落中的智能个体能够收集食物,交换食物,消化食物,在这个过程中群落得到不停的进化,最终可以形成突现聚类。基于这种思想,Hayashi,Yang提出了所谓的人工生命优化算法。其基本思路是:如果将人工生命环境视为一个优化问题的解空间,那些其中的智能个体就可以在解空间中搜索。例如要求解一个函数的最小值,只要赋予智能个体相应的搜索能力,它们就可以在人工生命环境中与函数较小解空间相对应的区域形成突现聚类。在聚类的过程中,个体与食物的坐标对应着求解问题的优化变量,每个个体都向邻域中处于目标函数值较小位置的食物移动,所以整体上就可以在目标函数优化解四周形成突现聚类。人工生命算法是一种分布式优化技术,在所有人工组织的范围内寻优,不需要梯度信息,在优化非线形连续多模态函数时,具有良好的全局收敛性。算法采用自下而上的设计方法,设计的关键是底层的人工组织个体行为的表现。算法的进行就是智能个体的自适应的行为活动,最优解将在该过程中突现出来。每个智能个体作为一个实体,该实体封装着自身的状态和行为,实体每活动一次,就是算法的一次迭代。人工生命算法的突出特点是突现聚类,“突现”指在复杂的(非线形)形态中许多相对简单单元彼此相互作用时产生出来的显著的整体特性,在个体的作用过程中,只要高于个体行为就可称为突现,突现本身可能也是多层次的。兰顿提出了一个更加实际的定义:突现是介于微观和宏观行为之间的反馈。最优解域是人工组织经过若干代迭代后在人工世界中形成的突现聚类。2资源和其他人工组织的匹配优化算法1)标准算法人工世界(Artificialworld)定义为一个具有最低限和最高限的空间,,(i=1,2,……n)。在这个空间中,假定有4种资源(resource)(白、红、绿、蓝)和4种人工组织(ArtificialOrganisms)(白、红、绿、蓝)。人工组织可以在人工世界中任意移动,同时消耗能量资源(EnergyResource)和产生废物(Waste)。这4种人工组织构成一个循环的食物链,一个物种产生的废物是另一个物种的食物。当它们代谢(Metabolize)资源时,内部能量增加,并在邻域内的任意位置产生废物,这个废物成为其他人工组织的食物。例如白色的人工组织代谢蓝色的资源,并产生白色废物。然后这个废物变成白色资源,成为红色人工组织所需要的食物。如图1所示。人工组织的邻域定义为D为人工组织活动的区域,个体只能在这个区域内搜索资源和交配。D可以定义为整个迭代过程中的常量,也可以是随着迭代次数增长而变化的变量。人工生命算法的一个不足之处是搜索精度不高,本文为了提高搜索精度,将D定义为随着年龄增加而减小的变量,这样随着迭代次数的增加,其搜索范围逐渐减小。人工组织具有知觉系统,能够让它们在人工世界中看到资源和其他人工组织,并且判断哪些资源和人工组织位于其邻域内。智能个体可以在邻域D内搜索具有较高适应度的资源,这个资源的位置成为驱使它们向前移动的目标。人工组织必须维持一个最小的内部能量以维持生存,一旦它的能量水平低于这个最低限,将被视为“死亡”并从人工世界中移除出去。当人工组织的年龄增加1岁,内部能量相应的减少。因此,人工组织的年龄越大,就需要更多的能量以维持生存。最终,如果一个人工组织搜索不到资源,获得能量将死亡。这有效地为人工组织强加了一个生命的限度。当人工组织达到一定的年龄,并且具有足够高的内部能量,可以在邻域内与同样达到繁殖条件的同类人工组织进行交配,然后在邻域内适应度高于父体的位置生产后代,这个子代的人工组织具有初始化的内部能量,参与人工生命循环。人工组织寻找食物的过程,也是目标函数搜索最优值的过程。资源和个体的位置是目标函数的变量,最终形成的突现聚类,是目标函数的最优解域。资源和个体的适应度代表目标函数值的大小,适应度越高,目标函数值越接近最优值。觅食行为是循着食物适应度高的方向游动的一种行为,在寻优方法中则是向较优方向前进的迭代方式,在这个过程中,智能个体总是尝试向更优的方向前进,奠定了算法收敛的基础。优化问题可以用如下的一个多模态非线形函数来表示。计算步骤:①初始化在人工世界中,任意位置初始化4种相同数量的人工组织。为每一个人工组织初始化内部能量,同时初始化与人工组织数目相同的4种资源,随机地分布于人工组织不存在的位置上。根据实验得知,如果初始化3种人工生命,则突现聚类形成时间太短,如果初始化5种,则计算时间太长,因此,在算法的应用中通常初始化4种人工组织。②搜索资源在邻域内,人工组织搜索能够代谢的资源。③移动首先,如果人工组织在邻域内搜索到距其当前位置最近且为其所需要的资源,则向该资源移动。其次,如果没有找到这样的资源,它们在邻域内随机移动。④代谢如果人工组织找到了所需要的资源,则移向这个资源,获得能量,并在邻域内任意位置产生废物。⑤增加年龄在这一过程中,人工组织的年龄增加1岁。⑥繁殖下一代如果人工组织符合繁殖条件,即达到一定的年龄和具有一定的内部能量,可以在邻域内与同样达到繁殖条件的同类人工组织进行交配,选择距离当前位置最近的个体进行交配。如果交配成功,在邻域内,适应度高于父体的位置产生下一代。⑦减少能量在这一过程中,所有人工组织的内部能量减少,如果个体的内部能量低于最低限,将被视为死亡,并从人工世界中移除。⑧增加代在这一过程中,增加一代。返回步骤②。2)算法改进人工生命算法在优化过程中具有不需要梯度信息、良好的全局收敛性等优点,同时也存在收敛速度慢、寻优精度不高等缺点。以下是对人工生命算法的一些改进。①混合人工生命算法由于人工生命算法是由有限个人工生命组织和资源形成突现聚类,不能给出精度很高的最优解域,因此单纯使用人工生命算法,难以达到优化目的。而与其他优化算法结合,可以较好地提高精度。标准人工生命算法的缺点是搜索速度比较慢,形成突现聚类的时间比较长,因此考虑到蚂蚁算法是一个自催化的优化过程,将蚂蚁算法的这种正反馈原理引入到现有的人工生命算法中,将提高人工生命优化算法的搜索速度。将蚂蚁算法引入到人工生命算法的捕食策略中,智能个体在捕食过程中根据食物距离的远近和食物上面信息素的多少来确定自己的食物。如果个体找到了自己所需的食物,它就可以将食物消化从而获得能量。在所排泄的废物上根据目标函数值施上信息素。仿真结果表明,这种结合了蚂蚁算法正反馈原理的人工生命算法比较直接利用函数值作为驱动目标人工生命算法能够更快地找到优化解。相对于蚂蚁算法而言,这种混合优化算法理论可以直接用于优化问题,具有更普遍和实际的意义。在此基础上人工生命算法与遗传算法结合,将生命算法中出现的突现聚类,作为遗传算法的最初种群,即在人工生命系统形成的聚类中选择足够的个体形成遗传算法的初始种群,然后采用浮点编码的遗传算法在优化解较小的区域内进一步求解。采用这种两阶段算法进行优化时,第一阶段引入蚁群算法的混合优化算法可以在优化解区域形成突现聚类,由于很多的智能个体进行并行搜索,因此这种聚类可以找到优化问题的所有最优解的区域。第二阶段遗传算法在这些区域中进行进一步精确搜索,可以很快找到全局最优解并可适用于多解的情况。这种两阶段优化算法的优化结果在很大程度上取决于最初种群的选择,能否从第一阶段的聚类中为第二阶段的遗传算法找到好的初始解群将在很大程度上决定优化结果的好坏,因此初始种群的选择方法应该同时考虑人工生命系统的性质和遗传算法对初始解群的要求。文献在此基础上提出《基于密度-距离初始解群选择方法的两阶段优化算法》,文中指出虽然突现聚类能够在优化解区域形成,但是总会有一些个体散布在这个区域之外,可以认为是一些坏解,同时在优化区域内部,有些个体彼此会靠得比较近,如果选择相隔不远的个体作为遗传算法的初始解,会大大影响到初始解群的多样性,从而会导致过早的局部收敛,影响对全局优化值的求解。为了解决上述问题,定义两个定量指标-密度量值和距离量值。在人工世界中,并不是所有的人工组织都能进入突现区域,显然,在突现聚类外的个体不能作为最初种群。定义密度值如下:这里d是一个根据突现区域大小而定的常量,满足上式的个体,可以被选择。此外,在满足密度的基础上,还应该保证个体的多样性。C是所选择的突现聚类区域,在这个区域内,被选择的个体之间的距离值应该满足上式。采用密度-距离选择方法可以在排除逸出个体的同时尽可能地覆盖整个优化解区域,个体之间保持一定的距离。②引入捕食者引入捕食者的目的是为了提高算法的寻优精度,捕食者能够捕获游离于聚类之外的个体,由于算法中散布于聚类之外的个体不满足优化结果的要求,捕食者的引入可以减少聚类形成的时间。根据生态系统的金字塔法则,在人工世界中设置数目为人工组织数目20%的捕食者。捕食者的活动范围要大于人工组织。捕食者需要能量以维持生存,当能量降低到一定值时,开始进行捕食行为。在算法迭代初期,不能进行捕食行为。因为此时捕食者具有较高的内部能量,当其内部能量值降低到一定水平时,人工组织形成了一定的突现聚类,捕食行为开始活动,捕食者开始在游离于突现区域以外的人工组织中捕食,这样加快了突现聚类形成的时间,也就是加快了算法的收敛速度。捕食者算法步骤:捕食者等待能量下降。捕食者确认在其邻域内存在人工组织;计算邻域内人工组织的数量,如果数量少于规定值,转,否则转;判断人工组织是否处于单独状态且符合捕食条件,如果存在一个以上这样的个体,开始捕食行动,捕食者将捕获适应度差的个体,增加内部能量。如果内部能量高于限定值,返回,否则返回;如果邻域内没有满足捕食条件的个体,捕食者随机移动,等到内部能量低于限定值时,返回⑥。3人工生命算法人工生命算法已经吸引了许多研究领域的关注,但是在工程问题优化方面还没有得到广泛的应用,国外只有Hayashi,Yang,Lee等学者将人工生命算法应用在实际问题中。在文献中,韩国学者B.S.Yang将人工生命算法应用于机械设计,通过优化设计短轴承的实例,将人工生命算法与遗传算法的优化结果进行了对比。进一步证明了人工生命算法在工程实践中的应用价值。东北大学的博士研究生喻海飞将人工生命算法应用到了供应链操作管理的实际问题中。文献提出了将人工生命算法中的食物链规则应用到实际供应链管理及企业伙伴的选择等问题中。4人工生命算法的设计原则人工生命算法是一种新兴的有潜力的优化技术,在优化函数问题上取得了一定的效果,具有以下特点:①算法只需要比较目标函数值,对目标函数的性质要求不高;②算法对初值的要求不高,可以随机产生;③算法没有过多的参数设定,有较大的容许范围;④算法不需要梯度信息;⑤算法具备全局寻优的能力。目前我国针对人工生命算法的研究还很少,基于算法特性的应用研究还处于起步阶段,算法的设计也有很多有待改进