第1章群体智能算法概述

1975年，美国Michigan大学的JohnHolland[1]教授发表了其开创性的著作《AdapatationinNaturalandArtificailSystem》，在该著作中JohnHolland教授对智能系统及自然界中的自适应变化机制进行了详细阐述，并提出了计算机程序的自适应变化机制，该著作的发表被认为是群体智能（SwarmIntelligence）[2]算法的开山之作。随后，JohnHolland和他的学生对该算法机制进行了推广，并正式将该算法命名为遗传算法（GenticAlgorithm，GA）[3]~[5]。遗传算法的出现和成功，极大地鼓舞了广大研究工作者向大自然现象学习的热情。经过多年的发展，已经诞生了大量的群体智能算法，包括：遗传算法、蚁群优化（AntColonyOptimization，ACO）[6]~[7]算法、差异演化（DifferentialEvolution，DE）[8]~[12]算法、粒子群优化（ParticleSwarmOptimization，PSO）[13]~[16]算法等。随着群体智能算法在诸如机器学习、过程控制、经济预测、工程预测等领域取得了前所未有的成功，它已经引起了包括数学、物理学、计算机科学、社会科学、经济学及工程应用等领域的科学家们的极大兴趣。目前关于群体智能计算的国际会议在全世界各地定期召开，各种关于信息技术或计算机技术的国际会议也都将智能进化技术作为主要研讨课题之一。甚至有专家指出，群体智能计算技术、混沌分析技术、分形几何、神经网络等将会成为研究非线性现象和复杂系统的主要工具，也将会成为人们研究认知过程的主要方法和工具。1.1群体智能算法的特点1.1.1智能性群体智能算法通过向大自然界中的某些生命现象或自然现象学习，实现对于问题的求解，这一类算法中包含了自然界生命现象所具有的自组织、自学习和自适应性等特性。在运算过程中，通过获得的计算信息自行组织种群对解空间进行搜索。种群在搜索过程中依据事先设定的适应度函数值，采用适者生存、优胜劣汰的方式进化，所以算法具有一定的智能性。由于群体智能算法具有的这种优点，应用群体智能算法求解问题时，不需要事群体智能算法及其应用2先对待求解问题进行详细的求解思路描述。对于某些复杂性高的问题，高效求解成为可能。1.1.2隐含本质并行性群体智能算法通过设定相应的种群进化机制完成计算，而种群内的个体则具有一定的独立性，个体之间或需要，或不需要进行信息交流，而个体的进化方式则完全取决于自身的状态。所以，对于群体智能算法而言，其个体之间完全是一种本质上的并行机制。如果使用分布式多处理机来完成群体智能算法，可以将算法设置为多个种群并分别放置于不同的处理机实现进化，迭代期间完成一定的信息交流即可（注：信息交流并不是必要的），迭代完成之后，根据适应度值进行优胜劣汰。所以，群体智能算法这种隐含的本质并行性，能够更充分利用多处理器机制，实现并行编程，提高算法的求解能力。更加适合目前云计算等分布式计算技术迅速发展的背景。1.1.3解的近似性群体智能算法通常来自于对大自然中某种生命或其他事物的智能协作进化现象的模拟，利用某种进化机制指导种群对解空间进行搜索。由于该类算法缺乏严格的数学理论支持，对于问题的解空间采用反复迭代的概率性搜索，所以群体智能算法会存在早熟或解精度较低等问题，而这也是所有群体智能算法几乎都存在的弱点。所以，很多时候对求解的问题来说，群体智能算法仅仅得到的是一种昀佳解的近似解。1.2群体智能算法的计算模式不失一般性，考虑以昀小化（min{()|}fxx∈X）问题进行探讨（本书均以昀小化问题考虑，下同）。式中，X称为问题的解空间，即问题的所有可能解。X既可以是连续域nR的一个子集，也可以是离散域内一个有限集合。群体智能算法的优化求解就是从多个随机初始解开始，通过一定的规则不断迭代和进化产生新解的过程。在群体智能算法中，将多个解的集合称为种群（Population），记为()Pt，t表示种群进化的代数，种群的大小称为种群规模，一般记为POP或N。以12(),(),,()nxtxtxt表示种群中各个解，即种群的个体（Individual）或称染色体（Chromosome）。种群中新个体（Offspring）通常由父个体（Parent）以某种交配组第1章群体智能算法概述3合方式产生，这种交配方式称为进化模式（EvolutionaryModel）。进化计算的迭代过程可以归纳为社会协作、自我适应和竞争进化等三个基本环节。在社会协作过程中，个体之间进行彼此的信息交换和互相学习。种群内个体在自我适应过程中通过主动或被动的方式不断调节自身的状态以适应环境。相互竞争则是指种群内具有更优状态的个体将会获得较大的生存机会，进入子种群，即种群的更新策略。群体智能算法框架描述如下：算法1.1群体智能算法[13]输入：解空间内的初始种群。输出：昀佳个体gbest()tX。步骤1.初始化种群规模、迭代次数等参数。步骤2.在解空间内随机初始化种群12(){(),(),,()},0nPttttt==XXX。步骤3.While（终止条件不满足）Do。步骤4.计算()Pt中个体的适应值。步骤5.挑选部分个体进行社会协作操作。步骤6.自我适应。步骤7.竞争操作，生成新一代种群。步骤8.endwhile。步骤9.输出昀终解。通过以上计算框架可知，群体智能算法通过对附加于种群内个体的三种操作引导个体向昀佳解靠近，从而达到寻优的目的，其形式化模型如公式（1.1）所示。PIO{POP(),(),(),();}uSACtαβγ=（1.1）式中，POP()u代表种群，u表示其规模；SAC、、分别代表社会协作、自我适应机制和竞争操作，括号内表示该操作所需的相应信息，t表示算法迭代代数。1.2.1社会协作机制在本过程中，将通过一定的选择机制挑选部分个体进行信息交换和相互学习。所涉及的信息包括：个体选择的方法（schoi）,个体规模（snum），新实验个体的产生机制（sway），种群历史信息的使用方式（shis）等，可以用公式（1.2）进行形式化描述。(POP(),[schoi,snum,sway,shis])tSt（1.2）1.2.2自我适应机制自我适应机制是指个体通过主动或被动机制不断调整自身的状态，以适应其所群体智能算法及其应用4处的生存环境。个体通过两种搜索机制来调整自身的状态，全局搜索和局部搜索。全局搜索机制保证了个体在更加广泛的范围内探索新解的能力，能够更好地保证种群多样性，避免出现早熟收敛现象；局部搜索机制则与之相反，容易使算法提前收敛于局部昀佳，但是能够较快地提高个体的质量，加快算法的收敛速度。种群中个体的自我适应通常就是处理好两种搜索机制之间的平衡。通过上述两种过程，可以生成新的实验个体，新实验个体生成机制的形式化描述如公式（1.3）所示。new()((POP(),[schoi,snum,sway,shis],)tttAStβ=（1.3）1.2.3竞争机制群体智能算法通过竞争机制从POP个父个体和m个临时子个体中挑选个体进入下一代种群中。在大部分群体智能算法中，种群的规模POP一般选择固定不变，个体替换策略分为整代替换策略(POP,)rm和部分替换策略(POP)rm+；前者指POP个父个体完全被m个子代个体所替换，后者指POP个父个体中只有部分个体被替换。当然，如果为了保存精英个体，可以选择精英保留策略，即父代个体中的优秀个体不被替换而进入下一代个体。产生子种群的形式化描述如公式（1.4）所示。POP(1)(POP(),New(),[,,elitist])ttCttpr+=（1.4）上述公式（1.4）中p代表种群个体，r代表替换模式，elitist代表精英个体。1.3遗传算法遗传算法采用随机机制对解空间进行搜索，并在搜索过程中不断迭代、进化。由于该算法采用了模拟生物界中的生物遗传原理进行随机解空间搜索，所以它具有一定的广泛性和适应性。在实际的操作中，遗传算法利用自然界中的适者生存机制作为算法进化中的主要进化机制，同时将随机的信息交换机制吸收进来，较好地消除了迭代过程中出现的不适应因素，有力地提高了收敛速度。自遗传算法被提出以来，已经被广泛应用于各种领域问题的求解，并表现出了非常好的求解效率。比如，求解组合优化问题（TSP问题、背包问题等）、神经网络的结构优化问题、灾害评价与预报、网络路由选择等。遗传算法的操作对象是被称为种群的一组二进制串，而其中的单个个体称为染第1章群体智能算法概述5色体或者叫个体，每一个染色体对应于问题的一个解。遗传算法的操作流程是：从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异不断产生下一代群体。如此迭代，直至满足期望的终止条件。该算法的形式化描述如下：GA((0),,,,,,,)PNlsgpft=其中，12(0)((0),(0),,(0))nPXXX=表示初始种群；N表示种群中含有个体的个数；l表示二进制串的长度；s表示选择策略；g表示遗传算子；p表示遗传算子的操作概率；f表示适应度函数（fitnessfunction）；t表示终止准则。1.3.1标准遗传算法原理应用遗传算法求解问题时，主要经过种群初始化、计算适应度函数值、父个体交叉、变异等操作，算法流程图如图1-1所示。算法1.2标准遗传算法（GA）输入：种群P。输出：昀优个体gbest()tX。步骤1.初始化群体(0)P,迭代次数t=0。步骤2.计算()Pt中个体的适应度。步骤3.如果满足终止条件，则终止算法，输出昀优个体；否则继续下一步。步骤4.m=0。步骤5.如果m≥N，即已经将全部的父个体处理完毕，则跳转到步骤2；否则，执行下一步。步骤6.根据个体的适应值比例选择两个父个体。步骤7.确定随机值β，如果该值随机大于1，则将两父个体进行杂交操作，然后将个体变异后插入到P(t+1)中，并且跳转到步骤9。步骤8.β如果在随机值0和1之间，则将两个父个体直接变异后，插入下一代个体P(t+1)中。步骤9.m=m+2；并且跳转到步骤5。设计一个求解实际问题的遗传算法的步骤如下。群体智能算法及其应用6开始随机产生N个个体组成初始种群P(0)对当前种群中的个体进行评价终止吗？m=0随机选择两个个体满足PC？两个个体做临时子个体对若干临时子个体执行变异操作MN?迭代次数+1NYY输出结果两个个体交叉生成临时子个体YN结束N图1-1标准遗传算法流程图（1）确定编码方案遗传算法求解问题不是直接作用在问题的解空间上，而是利用解的某种编码表示。选择何种编码表示对算法的质量和效率会产生较大的影响。遗传算法一般采用如下三种编码：二进制编码、十进制编码和格雷编码。（2）确定适应函数一般以目标函数或费用函数的形式表示。解的适应度值是进化过程中进行个体选择的唯一依据。应用适应度函数来评价解的质量，它通常依赖于解的行为和环境的关系。第1章群体智能算法概述7（3）设计遗传算子包括繁殖操作、杂交操作、变异操作。（4）设计终止条件遗传算法没有利用目标函数的梯度信息，无法确定个体在解空间中的位置。从而无法用传统的方法判定算法是否收敛，并终止算法，所以一般都是预先设定一个昀大的进化代数或检测种群的平均适应度连续几代的变化是否趋于平稳，以判断是否终止算法。1.3.2编码机制与主要算子1．编码机制遗传算法的求解主要是通过位串的操作实现对解空间的搜索，所以不同编码方式会影响算法的问题表达和解空间的搜索。（1）二进制编码将原问题的解映射为一个二进制串描述（0,1表示），然后，通过对位串的操作实现对问题的求解，昀后将结果再还原为其解空间的解。例如，染色体（0,1,0,1,1,1）表示为长度为6的串。（2）十进制编码将问题的解描述为一个0～9组成的十进制串。（3）实数编码实数编码将问题的解用实数来描述，实现了在解的表现型上直接进行遗传算法操作。即，问题的解空间实际就是遗传算法的运行空间。（4）格雷编码格雷编码其实质也是一种二进制的表示形式，与普通二进制不同的是，格雷编码是通过一个特定的格雷变换得到的二进制串。例如，