粒子群算法自适应行为分析研究

现实世界,存在着各种各样的自适应行为,例如,生物在进化过程中不断调整自身结构以适应外界环境变化;人体的免疫系统在遇到抗原入侵时会自适应改变自身结构去维持人体的正常生理功能。无论在自然系统还是在人工系统中,其系统的环境适应能力以及系统演化通常都可以通过自适应来解释。因此,对自适应行为的研究越来越受到研究者们的关注。就计算机算法领域而言,近年来涌现出诸多模拟生物演化或者社会协作过程的算法,例如遗传算法、粒子群算法等。对算法自适应行为的群体动态行为分析和理解将有助于设计有效的指导原则来保证算法收敛性和提高收敛速度。而对自适应行为进行有效的度量刻画是我们深入理解自适应行为的前提。总的来说,现有的群体行为研究主要集中于算法是否收敛以及算法的收敛速度方面,而对算法自适应行为进行研究的侧重点应该注重于算法在演化过程中的动态行为刻画方面。本文主要针对粒子群算法运行过程中的群体动态行为进行研究,尝试分析与讨论粒子群算法在演化过程中所体现出来的自适应行为,对自适应行为进行度量,对自适应过程中的信息利用方式进行讨论。在深入分析已有演化算法群体动态行为研究方法的基础之上,提出了更为明确的刻画群体动态行为的方法,首先将信息熵引入到粒子群算法的自适应行为研究中。定义了Hit Counter、Hit Distance和Mean Fitness三个指标的信息熵,使用这三个信息熵来刻画群体在演化过程中的混乱和秩序程度,并结合群体半径,来观测定量的群体在演化过程中整体有序程度的变化。进一步的,本文又在信息熵的基础之上,提出了基于群体进化动力分布的相关分析方法—相对熵和相关性来刻画群体动态行为。该方法主要定义了4种指标,分别是:函数值增量与位置增量的相对熵、函数值增量与位置增量的相关系数、(70)和2)(70)相关指标。其中,相对熵和相关系数是用来对群体动态行为的进化过程进行分段的,(70)和2)(70)相关指标可以确定群体的收敛状态。为了说明本文提出的自适应行为研究方法的有效性,本文使用最具代表性的6种粒子群算法对21个极小值优化的标准测试函数进行了测试,并分别针对这些函数的2维、5维、10维和30维问题进行了实验。实验结果表明,信息熵的变化可以体现出群体在演化过程中整体有序程度的变化。同时,使用基于相对熵和相关性的相关指标,可以将群体的动态行为划分为三个阶段:随机搜索阶段、精细搜索阶段和收敛阶段。且基于相对熵和相关性相结合的方法可以刻画进化算法的进化特征以及分析不同类方法的优缺点,例如影响演化速度,收敛速度以及计算精度的具体因素。以上实验结果有效的验证了本文提出的相关指标能够精细的刻画粒子群算法进化过程中的群体状态转变以及相关行为特征,并且通过对比得到不同粒子群算法在收敛速度以及搜索能力方面的不同表现,为算法选择和群体行为分析提供了一种新的理论指导和解释方式。