基于函数优化的生物智能进化算法综述

基于函数优化的生物智能进化算法综述关键词：函数优化，生物智能，进化算法1引言近些年来,在理论和实际应用中优化问题随处可见,同时随着问题复杂程度的提高对优化技术也有了非常高的要求。传统的优化方式(如梯度下降法、迭代法等)[1]在解决这些问题时,显现出其局限性与缺陷,所以更多的学者对复杂函数的优化问题的研究集中在分析现有生物智能进化算法[2],这些算法在解决这些复杂函数的优化问题时具有操作简便、易于实现及计算量小等一系列的优点,可以看出现代生物智能进化算法应用于复杂的函数优化问题的研究具有重要的意义。2函数优化的问题描述函数优化问题[4]主要是对较为复杂的函数进行优化。函数优化的本质是通过迭代发现一个目标函数的最优解。一般情况下,搜索的目标都是通过对目标函数的“函数”进行优化,通常所描述的函数特征通常包括函数的连续性、离散性、线性、非线性、凸凹性等。对于有约束条件的函数优化问题可以利用设计专门算子使问题解始终保持可行,或者通过采用惩罚函数的方式把它转化为无约束问题,因此主要以无约束条件的函数进行优化作为研究重点。一般的函数优化问题可以描述为如下形式[3]:其中为搜索空间;成为目标函数;式(1)中描述的是目标函数的极大值,式(2)描述的为极小值。通常最大值和最小值问题之间是可以相互转化的,最大值问题的目标函数取负就成了极小值,反之亦成立。3函数优化问题中的常用的生物智能优化算法研究现状3.1遗传算法3.1.1遗传算法的概述遗传算法[5](GeneticAlgorithms简称GA)是模拟遗传选择和优胜劣汰的生物进化过程的一种随机搜索与全局优化算法。遗传算法具有运算快捷、简便、适用范围广等优点,并且在搜索过程中并不直接作用在变量上,而是在参数集对个体进行编码,这个特点能够使遗传算法可直接对结构对象进行操作。遗传算法的基本流程如下图所示:但该算法在函数寻优中也存在无法保证收敛到全局最优解,群体中适用度高的染色体可能会丢失,在进化过程中过早的收敛等一系列的问题,所以许多学者通过利用一种算法的优点同时与其它方法相结合来避免该算法的不足,借鉴这一思想来求解函数优化问题具有更大的发展潜力。3.1.2基于函数优化的遗传算法的现阶段研究现状针对使用遗传算法对函数优化过程中存在早熟收敛、全局收敛能力较差及对目标函数的性质(可导性、连续性等)有较高的要求等问题,李宏[6]等人将简化的二次插值法融入实数的编码遗传算法中(含有二次插值法的遗传算法)。在文中,二次插值法作为一个局部搜索算子,构成适于求解函数优化问题的混合遗传算法,此混合算法从理论上能够提高算法的搜索能力,并能快速向全局最优解靠近。为了对混合算法的性能进行评估,对多个测试函数仿真实验,证明该方法能够克服遗传算法具有的早熟收敛、全局收敛能力较差及对目标函数的性质有较高的要求等问题。尽管含有二次插值法的遗传算法在搜索效率上较大的提高,但此混合算法在进化后期仍然存在收敛速度慢、易早熟收敛的问题,为避免此类问题降低函数优化的质量,薛文涛[7]等人提出以免疫学习机制[8,9]为基础的遗传算法(基于免疫学习机制的遗传算法),为了保持种群的多样性,引入以浓度为基础的选择机制,改善算法的全局收敛能力。文中提出弱小保护策略,从而更高效地找到全局最优解。仿真实验表明,对复杂函数进行优化时,以免疫机制为基础的遗传算法要比遗传算法及二次差值法的遗传算法有更高的搜索效率,并能在搜索后期提高收敛速度。自适应控制是一种能根据环境变化智能调节自身特性的反馈控制系统,并通过控制使系统能按照一些设定的标准工作在最优状态。为解决遗传算法求解函数优化问题中普遍存在的问题,张常泉[10]等人提出一种自适应遗传算法,该算法根据适应值大小自动调节参数,在运算的前期、运算过程中及运算后期,分别在不同的阶段采用不同的策略对交叉算子和变异算子进行自适应调节,从而能够保持群体的多样性、能达到对优秀的个体的保留和增加收敛的稳定性等一系列优点。并通过对函数优化问题中的两个函数最大值的快速求解证明该改进算法的有效性。小生境技术[11]主要借鉴生物种群生存环境的多样性特性,具有使一般的进化算法发现多个最优解的优点。由于对自适应遗传算法的改进无法有效平衡快速收敛和保持种群多样性的冲突,并针对多模态函数优化问题,陆青梁[12]等人提出一种自适应小生境遗传算法。在该算法中,设计一种改进的小生境识别方法来确定小生境范围,引入度量种群多样性的小生境熵概念,并利用小生境熵自适应调整进化参数的取值,同时在识别的小生境基础上将交叉分为境外交叉和境内交叉来提高算法的全局搜索能力和局部收敛速度。通过仿真实验结果验证本文提出的算法的正确性和有效性,并且该算法在解决多模态函数优化问题具有收敛速度快、计算量小等多个优点。3.2以蚁群算法为基础的函数优化问题研究现状3.2.1蚁群算法的概述蚁群算法[13](AntColonyOptimization,ACO)由意大利学者M.Dorigo[14]于二十世纪九十年代提出,它源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法的鲁棒性较好、全局搜索能力较强,针对函数的不连续、不可微、局部极值点过密等情况具有较好的解决能力,基本的蚁群算法可以通过以下几个式子来表示:三式中代表蚂蚁的数量;为迭代次数;代表蚂蚁所在的位置;表示蚂蚁可以到达的位置;表示蚂蚁可以到达的所有位置的集合;代表启发性信息;为目标函数;表示由到u的路径的信息素强度;和为路径权和启发性信息的权;和分别为路径上信息素数量的蒸发系数和信息素质量系数;表示第个蚂蚁从位置移动到位置的转移概率。蚁群算法在计算过程中有以上优点,但它也存在如计算时间较长、容易出现停滞现象、局部搜索能力较差、搜索初期积累信息素时间过长、求解速度较慢等缺点,由于以上缺点的存在,当再利用该算法对复杂函数优化时其结果也不会另人满意,所以许多学者在蚁群算法的基础上进行改进。3.2.2基于函数优化的蚁群算法的现阶段研究现状对于蚁群算法在对函数优化过程中存在运算初期信息素匾乏,需要较长的搜索时间,并且当规模较大时容易陷入局部最优解等问题,熊伟清[15]等人将遗传算法和蚁群算法进行融合(称为二进制蚁群进化算法),在该算法中,采用二进制编码对单个蚂蚁的智能行为要求比较低,对应的存储空间相对较少,使得算法的效率有较大的提高,不仅适用于可以求解连续参数优化的问题,也适用于求解离散的组合优化问题。通过函数优化仿真实验结果充分说明该文给出的二进制蚁群进化是实用而有效的,求解结果是令人满意。为进一步提高函数的寻优质量、算法的收敛速度、改善全局最优解的搜索能力及提高种群的多样性,张小广[16]等人在蚁群算法的基础上引入PBIL算法和遗传算法(基于PBIL算法及遗传算法为基础的蚁群算法)。在该文中,主要采用PBIL算法指导信息素的分布,同时根据信息素的散布来启发PBIL算法对概率模型的建立,从而信息素的散布模型概率和PBIL算法概率模型可以相互融合与并相互指导。此混合算法可以大大减少蚁群算法由于信息素的正反馈机制而造成容易陷入局部最优的缺陷。通过函数测试实验可以看出,该算法不仅能够克服遗传蚁群算法对函数优化过程中存在的常见问题,而且还具有很强的全局搜索能力,并在收敛速度方面也有很大的提高。针对一般的蚁群算法在处理离散的函数优化问题时具有局限性和收敛速度慢等缺陷,李盼池[17]等人提出求解连续空间优化问题的量子蚁群算法。在该改进的算法中,每只蚂蚁携带一组表示蚂蚁当前位置信息的量子比特,根据信息素强度和可见度来计算其选择概率,决定蚂蚁的前进目标,之后采用量子旋转门更新蚂蚁携带的量子比特,从而实现蚂蚁的移动。通过对离散的函数极值和神经网络权值优化问题仿真结果说明该算法的有效性,同时也说明该算法是具有一定潜力并是值得推荐的优化算法。3.3粒子群算法3.3.1粒子群算法的概述粒子群优化算法[18,19](ParticleSwarmOptimization,PSO)是在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能进化的优化算法[20]。粒子群算法是在解空间中跟随最优粒子进行搜索的智能进化算法,所以具有计算简便、需要调节的参数、容易实现等优点。粒子群算法首先初始化粒子种群,之后通过迭代操作来寻找最优解,在每一次迭代操作中,粒子通过个体极值与全局极值更新其粒子的速度和位置:其中:是第个粒子的速度;是第个粒子的位置;是惯性权重;是第个粒子经历的最好位置;是群体所有微粒经历的最好位置;是均匀分布在(0,1)之间的随机数;和是学因子。标准的粒子群算法的基本流程如下所示:第一步:粒子群初始化,其中包括对粒子群的速度和位置;第二步:计算初始粒子群的适应度值;第三步:根据粒子计算出的适应度值与其经历的最好位置相比较,如果优于经历的位置,则用其取代当前的最好位置;;第四步:根据式(6)(7)更新粒子群的速度和位置;第五步:判断是否满足终止条件(通常达到一个较好的适应度值或是满足迭代次数),若不满足条件则返回到第二步。在对粒子群算法做进一步的研究过程中,许多学者发现当使用粒子群算法对复杂函数进行优化时存在搜索的初期收敛速度过快,而在搜后期却易于陷入局部最优,针对缺陷众多学者提出了对粒子群的改进方法。3.3.2基于函数优化的粒子群算法的现阶段研究现状方伟[21]等人提出一种基于群体多样性控制的粒子群算法,该方法能够使粒子在收缩的状态下充分搜索,并能够在发散状态下飞离群体的聚集位置,在经历不断的收缩、发散过程中,能够保证群体能在较大的空间进行搜索,减少了粒子群算法在最优搜索过程中存在早熟收敛等现象。通过对多个标准测试函数的寻优实验结果表明,该算法在复杂优化问题中具有较强的全局搜索能力,而且比基本粒子群算法具有更好的性能。对现有粒子群优化算法存在局部收敛和可调参数敏感等缺点,巩敦卫[22]等人提出一种新型粒子群优化算法,该新型算法通过分析社会个体对其环境的认知规律,来简化粒子更新公式,使粒子位置的更新只与粒子自身速度和它邻域内最优粒子位置有关。并以粒子速度划分为基础提出一种优势粒子速度小概率变异、劣势速度随机赋值方法。在文中通过优化几个典型测试函数,证明本文研究的新型粒子群优化算法在优化解的质量、算法收敛速度及鲁棒性等方面的性能都非常良好。由于粒子群算法对函数优化过程中存在惯性权重自适应问题,杨帆[23]等人提出一种基于蚁群系统的惯性权重自适应粒子群算法(基于蚁群系统的参数自适应粒子群算法)。在文中,通过对惯性权重取值区间离散化,将惯性权重子区间作为蚁群算法的行动路径,根据各条路径上的信息素浓度与粒子的空间分布信息来选择路径,实现粒子进化搜索。通过对几个典型测试函数优化的仿真研究表明,该混合算法的惯性权重能随着算法搜索的进化而进行自适应进化调整,保证算法的全局寻优性能与局部搜索能力,提高算法的收敛速度及解的精度,从而进一步提高函数的寻优质量。3.4蜂群算法3.4.1蜂群算法概述人工蜂群算法(BeeColonyAlgorithm,BCA)是在2005年由英国学者DTPham提出的一种基于蜜蜂群智能搜索行为的优化算法。蜂群算法的研究虽处于初级阶段,但由于具有其控制参数少、鲁棒性及其适应性较强、计算简洁等优点,已被越来越多的学者所关注。人工蜂群算法中重要有三个部分组成:即为引领蜂、跟随蜂、侦查蜂,这三个部分在不同的阶段起着重要的作用。引领蜂和跟随蜂依据公式(8)进行食物源位置更新:式(9)中的第个解的适应度值,为解的个数。式(10)为随机产生一个新的解来替代被淘汰的解。下面简要的介绍的人工蜂群算法的主要流程:第一步:初始化种群为,同时计算出每个初始种群解的适应度值;第二步:引领蜂根据公式(8)做邻域搜索产生新解,并且计算其适应度值;第三步:把的适应度值与的适应度值做比较,考虑是否保留不变;第四步:根据公式(9)计算与相关的概率值;第五步:跟随蜂凭借选择食物源(解),并根据式(8)进行邻域搜索产生新解,计算其适应度值;第六步:判断解的满意度,决定侦查蜂是否根据式(10)产生一个新解替换它;第七步:保留当前最好解。第八步:判断是否满足循环终止条件,如满足则