协同进化算法优化方案

协同进化（Coevolution）一词最早由Ehrlich和Rave在讨论植物和植食昆虫（蝴蝶）相互之间的进化影响时提出来的，但他们未给协同进化下定义，不同的研究者对该词常有不同的定义。Jazen给协同进化下了一个严格的定义：协同进化是一个物种的性状作为对另一个物种性状的反应而进化，而后一物种的这一性状本身又是作为对前一物种性状的反应而进化。这一定义要求：特定性，即每一个性状的进化都是由于另一个性状；相互性，即两个性状都必须进化。更严格的定义还要求同时性，即两个性状必须同时进化。但在协同进化是扩散型时，就不具备同时性的标准，在这种情况下，协同进化只表明了物种对生物环境特征的适应。协同进化在最广义上可等价于进化。协同进化的研究内容极为广泛，包括：竞争物种间的协同进化；捕食者与猎物系统的协同进化；寄生物与寄主系统的协同进化；拟态的协同进化；互利作用的协同进化等。在达尔文进化论的体系中，最主要的是自然选择学说。自然选择学说认为，生物要生存下去，就必须进行生存斗争。而协同进化与达尔文进化论有些不同，其认为某些生物种属的进化与另一些生物种属的进化相互关联、相互受益，既表现为不同物种、不同个体之间的相互受益，也表现为不同物种、不同个体之间的相互制约。协同进化基于生物多样性的相互依赖、相互制约、相互得益、相互协调。

协同进化算法是近十几年来在协同进化基础上提出的一种新的进化算法，最早由Hillis于1990年提出。它模拟了自然界物种之间的竞争、捕食、共生等关系，以及在这些相互作用下各物种协同互补进化（是整个生态系统由低级向高级进化的过程），并采用与之相似的方式进行问题求解。

协同进化算法（Co-Evolutionary Algorithms，CEA）按所采用的生物模型，可分为竞争式协同进化算法、基于捕食-猎物机制的协同进化算法、合作式协同进化算法，在一些复杂的场景下这几种关系可能同时存在。

（1）竞争式协同进化算法。竞争式协同进化算法中一方要在与对手的对抗中取胜才有收益，而这同时意味着对手的损失。该算法一般把种群分为几个子种群，这几个子种群主要处于竞争关系。竞争式协同进化算法中，个体的适应度由与其他个体（opponent）竞争的结果来决定。Paredis给出了竞争式协同进化算法在神经网络分类问题和约束满足问题上的应用；Husbands用合作/竞争的多种群协同进化遗传算法，处理多准则的车间调度问题。竞争式协同进化算法通常用于两类问题。一是问题内部交互关系复杂，很难构造一个独立固定的适应度函数用于进化计算。例如，Stanley和Miikkulainen在机器学习中，用竞争式协同进化算法发现了更多、更好的策略；Angeline和Pollack用竞争适应度函数取代传统的适应度函数。二是用于动态博弈问题观察分析，Lindgren和Johansson通过竞争式协同进化“囚徒困境”问题的策略，考察个体如何做出决策反应。曹先彬、郑浩然等人提出了基于生态竞争模型的竞争式协同进化算法。该算法在每次迭代中都依次进行进化和协同过程，其中进化采用遗传算法的操作方法，协同过程通过种群竞争方程计算种群密度，并根据计算出的种群密度调整各子群体的规模，从而实现根据适应度的情况动态地调整各个模式在种群中的比例。

（2）协同进化遗传算法。捕食-猎物关系是遭受选择压力个体间的一种反馈机制，这种反馈机制为系统走向复杂提供了有力的驱动。猎物为了尽可能不被猎食，通过发展某些手段（如跑得更快，更好的伪装等）更好地保护自己，但同时导致捕食者发展更好的袭击策略。这种协同进化过程导致捕食者和猎物之间的复杂性逐步增加。Hillis把捕食-猎物协同进化作为计算模型，并把这一类算法称为协同进化遗传算法（Coevolutionary Genetic Algorithm，CGA）。在上述方法的基础上有两个应用：神经网络分类问题和约束满足问题，这两个例子都利用捕食-猎物关系增强智能搜索的能力，并与传统遗传算法进行性能比较。Paredis和Matriks提出了一个采用生命期限适应度评价（Life-time Fitness Evaluation）的协同进化遗传算法，用于一类“Test-solution”问题（包括归纳学习，约束满足问题）。这种算法有两个种群：候选解种群和测试种群。前者是问题的解，后者是事例或约束条件。候选解种群的个体适应度等于最近20个事例中它满足的个数，而测试种群的个体适应度等于最近20个个体中个体不满足它的个数。因此，候选解种群内个体与测试种群内个体具有相反的适应度，它们间构成了一个捕食-猎物系统。协同进化遗传算法的操作作用在这两个具有相互作用的种群上。一般情况下，对候选解种群进行进化，也可以对两个种群都进行进化。

（3）合作式协同进化算法。合作式协同进化算法把问题分解为若干个子问题，每一个子问题用一个子种群进行进化，通过种群之间的相互合作来协同进化，也就是说，每个子种群中的个体代表问题解的一部分，个体适应度与该子种群对整个问题求解的贡献相关，各子种群都为问题求解的总体目标承担各自的义务，通过子种群之间的相互合作来共同完成问题的求解。

一种常用的合作式协同进化框架（CCEA）是Potter等在1994年给出的，用于求解高维函数优化问题。由于Potter是以遗传算法（Genetic Algorithm，GA）为算法基础，可称其为合作式协同进化算法（Cooperative Co-Evolutionary Genetic Algorithm，CCGA）。根据Potter的研究，该框架伪代码如图1.5所示。

图1.5　合作式协同进化框架伪代码

2004年，Bergh等人又将Potter框架用在粒子群优化算法（Particle Swarm Optimization，PSO）上，得到CPSO算法（Cooperative PSO），其仿真实验结果表明，CPSO的优化性能好于PSO。同年，Jansen等人通过Cooperative Coevolutionary（1+1）EA算法（种群规模为1）的演化，从理论上分析和证明了Potter框架的收敛性和有效性。在国内，钟求喜在网络计算中多任务分配与调度中采用了CCGA；荔建琦根据Potter模型采用GA给出了一种异质合作进化算法（所谓异质合作指不同的演化算法的合作）；陈浩勇展望了协同进化算法在电力系统中的应用前景，重点推荐了Potter模型。2005年，史彦军研究了协同差异演化方法（CCDE）。该方法在Potter的合作式协同进化框架的基础上，将复杂问题空间分解为多个子空间并分配给相应的子种群，然后各子种群内部采用差异演化算法进行演化，并应用此方法求解了带复杂性能约束的卫星舱布局设计问题。可见，Potter的合作式协同进化框架是一种开放的、有效的通用计算框架。(www.xing528.com)

2000年，郑浩然等提出多模式共生进化算法（Multi-pattern Symbiotic Evolutionary Algorithm，MSEA），与CGGA不同之处在于：其一，MSEA把优化函数变量分成几组，称为模式，各个模式采用不同的进化方式；其二，个体适应度的计算方法不同，对于某个种群内的个体a，MSEA首先从各个种群随机选取n个个体与a组成n个的完整解，然后计算这n个完整解的适应度，把这些解的适应度的平均值作为个体a的适应度。这虽然能够克服CGGA的缺点，但计算个体适应度的计算量较大。

Seredynski针对N人博弈问题提出了协同进化多智能体系统模型。由于采用非合作策略，不能使系统在到达Nash平衡点的同时获得最大报酬，因此Seredynski提出了局部合作算子，个体适应度等于其邻域内所有个体适应度的平均。同时证明了这种局部合作算子能够把最大化收益点转变成Nash平衡点。在这个模型的基础上，Seredynski又提出了松散连结遗传算法。该算法把问题分成几个子问题，每个子问题维持一个种群，个体适应度等于相邻个体适应度和的平均值。同时将局部合作算子用于信用度分配机制，提出了松散连结分类系统。

Kim Jae-Yun等人提出了一个网格上的共生进化算法。这种算法有3个种群：Pop-A，Pop-B和Pop-AB。其中Pop-A和Pop-B中的个体各自包含问题的一部分解，而Pop-AB的个体是问题的一个完整解。Pop-AB中的个体与Pop-A，Pop-B中的个体是竞争关系，同时Pop-AB可以独自进化。它把种群Pop-A和Pop-B的局部优化和Pop-AB的全局优化结合起来以提高算法搜索效率。

在应用CCEA求解优化问题时，除了考虑传统演化算法中解的编码和解码方式、种群的演化机制、演化算子的设计和算法终止条件等问题外，还需要解决以下几个与CCEA相关的重要问题。

①问题分解，也就是用何种方式将大的问题搜索空间分解为多个子问题以形成多子种群的协同进化。问题分解的主要原则是使分解之后的问题尽量简单、易解，而且子问题之间尽可能保持相互独立，耦合程度尽可能小。

②子种群中个体适应度的计算方法。在计算子群体中某个个体适应度时，评价个体时需要从其他种群挑选代表（Representatives or Collaborators）构成一个问题的完整解，计算出适应度值。选择代表的方法（包括选择代表的数量和原则）本质上就是一种协同方式，这种方式既体现了个体间的相互作用，也形成了一种潜在的环境压力，引导着进化搜索的方向，但是选择代表个体也存在着可信度问题，并不能保证各个子群体一定能向着统一目标方向进行进化，且随着问题复杂耦合程度的增大，越难以进行一致性协调，因此引出了协同进化的下一个关键问题：子种群间的一致性协调问题。

③子种群间的一致性协调问题。CCEA中问题分解的原则是尽可能使分解之后的问题尽量简单、易解，而且子问题之间尽可能保持相互独立，耦合程度尽可能小，但是对于复杂工程问题，一般很难分解为相互独立的子问题，分解后的各子问题之间很可能存在着或弱或强的耦合关系，虽然通过子群体之间个体评价的“隐式”协同可在一定程度上对各个子群体进行优化方向的引导，但随着问题复杂耦合程度的增大，这种个体评价的“隐式”协同很难进行群体间一致性的引导，因此如何进行一致性协调，才能使具有耦合关系的各个子问题在优化过程中达到一致性优化目标是亟待解决的问题。

上述问题的解决对于CCEA的成功运作具有关键性作用。

综上所述，3种协同进化算法都取得了初步的研究成果，但还有许多问题有待于进一步研究，其中竞争式协同进化算法和协同进化遗传算法主要侧重于群体间竞争机制的研究，而合作式协同进化算法更侧重于群体间互利共生协同机制的研究，它与本书研究的布局问题中的各个子问题在互相制约、互相协调的基础上搜索系统整体最优解的关系有着本质的相似性，因此本书研究合作式协同进化算法。

对于合作式协同进化算法，目前的研究多侧重于问题分解和子问题适应度评价，子问题间进化一致性主要通过合作个体机制来保持，属于一种在个体适应度评价层面上的“隐式”协同机制，此协同机制较敏感，与子问题间的耦合程度密切相关，针对本书所研究问题乃至耦合性更强的复杂工程问题，目标函数以及约束之间往往具有一定的复杂耦合关系，较难很好地保持子问题间进化一致性。同时，本书的应用背景之一（航天器舱布局优化问题）具有一定的弱耦合性质，因此基于合作式协同进化框架，研究求解一类复杂布局问题的带启发式协调机制的协同进化算法，并将其应用于求解航天器舱和TBM刀盘布局设计问题。可以从两个方面进行启发式协调机制方式研究：基于全局耦合性约束的协调机制来协调各个子问题在整个求解过程中搜索方向的一致性；基于启发式规则的启发式协调机制来缓解各个子问题之间耦合复杂性，加快各个子问题搜索后期的收敛速度并确定原问题布局方案。