第10章　社会进化算法

10.1　社会进化算法的提出

多智能体社会进化算法（Multi-Agent Social Evolutionary Algorithm for Multiobjective，MOMASEA，简记MASEA）是2009年由潘晓英、刘芳和焦李成提出的一种用以求解多目标优化问题的进化算法^[41-43]。

多目标优化问题是工程中常见的问题，其各目标之间的相互矛盾性使得问题不存在使所有目标函数同时达到最优化的最优解，而是存在“矛盾目标集”，即Pareto解集。求解Pareto解集的传统方法是将多目标问题转换为多个不同的单目标优化问题分别加以求解。这些算法对于Pareto前端非凸的情形不能求出所有的Pareto最优解，而且多个目标之间很难进行比较。这些方法为了获得近似的Pareto最优解集，需要多次运行求解单目标优化问题，计算开销非常大，对于复杂的多目标优化问题往往无能为力。

通过多智能体进化的思想来完成Pareto解集的寻优过程的仿真实验结果表明，该算法能够较好地收敛到Pareto最优解集上，并且具有良好的多样性。另外，对智能体局部邻域环境建立方式的分析结果表明，引入“关系网模型”可有效提高算法的收敛速度，并能在一定程度上提高解的质量。

10.2　社会进化算法的基本思想

社会进化算法是一种将多智能体系统和传统演化技术相结合的多目标进化算法。该算法将遗传机制融合到多智能体系统，将进化算法中的个体作为一个具有局部感知、竞争协作和自学习能力的智能体，通过智能体与环境及智能体之间的相互作用达到全局优化的目的。

社会进化算法通过定义可信任度来表示智能体之间的历史活动信息，并据此确定智能体的邻域、控制智能体之间的行为。根据多智能体的社会进化模型中需要遵循的一些原则，以及多目标优化问题的特点，算法设计了两个种群：一是普通的智能体种群；二是存储Pareto解的存储种群，并设计了竞争、协作和自学习策略。在智能体种群中，每个智能体视为一个节点，以可信任度作为连接的权值，并据此确定智能体的邻域，控制智能体之间的行为。

遗传变异和适者生存机理及多智能体的相互竞争和自学习的特性，使得算法表现出优越的性能。竞争算子体现了适者生存、弱肉强食及多样性的原则。通过智能体之间的竞争作用，使得能量较高的智能体具有较强的竞争能力，能够更容易生存下去。协作算子体现了个体的交配，将优良的基因保留到下一代。采用正交交叉算子完成智能体之间的协作过程，使得智能体种群中的个体多样性增加。由于该算法利用了智能体的自学习特性，因此能够充分利用它本身所具有的先验知识进行启发式搜索的过程，并采用“擂台赛法则”构造Pareto解的存储种群。利用“关系网模型”完成多智能体邻域的建立及更新过程，更贴近真实的复杂适应系统，可以更加快速而有效地完成整体进化过程。利用“擂台赛法则”构造存储集种群可以有效地降低构造非支配集的复杂度，提高运行效率。各种因素的综合作用，使得该算法在求解多目标优化问题的Pareto解集上具有较优越的性能。

10.3　多智能体社会进化系统

1. 多智能体进化思想

智能体agent是一个物理的或抽象的实体，它能作用于自身和环境中，并能对环境做出反应。多智能体进化系统的基本思想是使传统遗传算法中的每个个体形成智能体，每个智能体采用进化机制，能够同时与环境和其他智能体交换信息，互相影响彼此的进化过程，使各个智能体之间能够产生协作行为，最终形成各个智能体之间及智能体与环境之间的共同适应。

在多智能体进化模型中，将遵循以下一些原则：每个agent都有初始能量；agent具有局部性，其感知能力和行为只能针对有限的局部环境，即邻域；由于环境资源的有限性，agent之间存在着激烈的竞争，能量较低的agent将死亡，这一行为称为适者生存原则；由于agent死亡而空余出来的节点会由其邻域内能量最高的agent产生一个子agent来替代，这一行为称为弱肉强食，或者由随机生成的一个agent占据，这种行为称为多样化原则。每个agent具有交配能力，agent在其邻域内找到合适的配偶进行交配，把优良的基因传给下一代。另外，agent具有知识，它可以利用知识进行启发式搜索，以提高自身的能量和对环境的适应能力。

2. 智能体协作机制——关系网模型

陈刚等人对agent社会组织方法和agent协作行为表现进行了研究，引入了一个表示agent之间联系的“熟人关系网模型”，同时对agent之间信任度的关系进行了讨论。

【定义10.1】　可信任度。agenta认为agentb在时间t的可信任度为trust（a，b，t），规定trust（a，b，t）∈［-1，+1］，并将初始时间t=0时agentb的可信任度设为0，即trust（a，b，0）=0。

智能体a的属性包括name、address、capability与contact-list，其中，name（a）表示名称；address（a）表示联系地址；capability（a）用于描述a对问题的求解能力；contact-list（a）表示a所有熟人通信信息的列表，表示为contact-list（a）=（L₁，L₂，…，L_s），列表中的每一个元素L_i称为熟人i的联系信息，有L_i=（name，address，trust），其中name（i），address（i），trust（i）分别表示熟人i的名称、联系地址及可信任度，与可信任度值大的熟人合作，成功的可能性也就越大。

10.4　社会进化算法的描述

1. 智能体的定义

【定义10.2】　智能体a表示待优化函数的一个候选解，其能量等于根据Zitzler所提出的适应度赋值方法计算所得的值，其目标为尽可能地增加智能体的能量。

智能体a可表示为a=（address，body，energy，neighbor），其中，address为智能体的联系地址，这里即为标号；body为智能体所包含的内容，以编码表示；energy为智能体的能量；neighbor=（A₁，A₂，…，A_w）表示智能体所能感知的局部环境，称为邻域。其中A_i=（address，trust）为邻域中的一个智能体，其可信任度trust表示两个智能体之间可信任的程度，用来控制智能体之间的行为。所有的智能体均在规模为lat×lat的网格上生存，每个智能体占据网格上的一个节点，且不能移动，如图10.1所示。

通过一种人类社会“关系网模型”新的智能体协作机制，来完成智能体邻域的建立及更新，使其更符合真实的复杂适应系统，进一步加快信息的扩散过程，快速而有效地完成整体进化过程。

2. 邻域的建立及其更新

（1）邻域初始化：对智能体种群中的智能体a，随机选择4个智能体形成其初始邻域，放入a.neighbor中。

（2）邻域更新：随着智能体与智能体及环境之间不断地相互作用，其局部感知环境也在不断地发生变化。agent系统的活动在很大程度上看是一种社会现象，可以通过构造agent社会关系网模型来表示协作agent的基本信息。设计智能体邻域扩充方式如下。

①令a=（address，body，energy，neighbor），其中，a.neighbor=（l₁，l₂，…，l_s）。在网格中随机选取位于（i，j）上的智能体b加入到a的邻域中，即a.neighbor=（l₁，l₂，…，l_s，b），其中，trust（a，b）=0。

②若b∈a.neighbor，c∈b.neighbor，且trust（a，b）=1，trust（b，c）=1，则c∈a.neighbor，trust（a，c）=0。

类似地，其邻域缩减方式为：若a.neighbor=（l₁，l₂，…，l_s，b），trust（a，b）=-1，则a.neighbor=（l₁，l₂，…，l_s）。

根据多社会进化模型中需要遵循的一些原则及多目标优化问题的特点，算法设计了两个种群：一是普通的智能体种群，二是存储Pareto解的存储种群；还设计了竞争、协作和自学习策略。在智能体种群中，每个智能体视为一个节点，以可信任度作为连接的权值，并据此确定智能体的邻域，控制智能体之间的行为；竞争算子体现了适者生存、弱肉强食及多样性原则。协作算子体现了个体的交配，将优良的基因保留到下一代；自学习算子完成智能体利用其自身知识进行启发式搜索的过程，并采用擂台赛法则构造Pareto解的存储种群。

3. 算法的进化策略

1）竞争行为

竞争行为模拟的是“社会中的竞争，失败的agent将无法继续生存”。对种群中的每个智能体，都将与其邻域内能量最大的智能体进行竞争操作。当智能体的能量小于其邻域中智能体的最大能量时，该智能体即无法继续存活，其位置由新的智能体来替代。通过竞争算子，可以清除种群中能量较低的智能体，提高群体总的能量水平，具体描述如下。

设网格内某智能体为a=（（i，j）（a₁，a₂，…，a_n），energy，neighbor），m=（（k，l）（m₁，m₂，…，m_n），energy，neighbor）为智能体a的邻域内能量最高的智能体。如果a.energy＜m.energy，则a死亡，并产生一个新智能体child=（（i，j）（c₁，c₂，…，c_n），energy，neighbor）代替a。其中，child.neighbor=a.neighbor，body部分（c₁，c₂，…，c_n）根据式（10.1）产生。

c_i=m_i+U（-1，+1）×（m_i-a_i），　i=1，2，…，n（10.1）

其中，U（·）为均匀分布的随机数。

为了同时体现弱肉强食和多样性原则，采用占据概率poccupy来确定以何种方式产生的智能体去替代原智能体的位置。若rand≤poccupy，则以产生的child替代；否则，以随机产生的一个智能体来替代。竞争操作的主要目的是清除能量较低的智能体，以提高整个智能体系统的整体能量。因此，poccupy的取值应较大。

2）协作行为

协作行为模拟了“从别处获得经验”。对于生存在环境中的智能体，它将与其局部环境中的智能体发生协作关系，以提高自身能量。智能体将以概率pcross+trust×0.1与其局部环境中的所有智能体进行合作操作，保证智能体与其所信任的智能体之间会有更多的概率进行合作。这非常符合人类社会中的协作机制，减少了可能无效的操作，可进一步加快搜索速度。

假设（a′，b′）=cooperate（a，b），判断a和a′的占优情况。若，则认为合作失败，保持原有的a不变，同时令trust（a，b）=trust（a，b）-0.2；若，则合作成功，以a′替代原有的a，并令trust（a，b）=trust（a，b）+0.1；若a～a′，则根据其拥挤程度来选择保留的agent。这里所遵循的是人类社会中“知己难觅，冤家易结”的原则，即一次失败的合作对其信任度的影响要大于一次成功的合作。将正交交叉算子作用在a.body及其邻域内的智能体上，形成邻域正交交叉算子，完成智能体的协作行为。

3）自学习行为

自学习行为模拟了“根据自身能力学习环境以提升能量”。在该行为中，智能体利用自己的知识来提高自身的能量，以增强竞争能力。为了减少计算量，该行为只作用于当前代能量最优的智能体上。

假设该代中Pareto最优解的智能体为CSAgent，其中CSAgent.body=（v₁，v₂，…，v_n），根据式（10.2）产生一个新的解（c₁，c₂，…，c_n）为

其中，G（0，1/t）表示高斯分布的随机数产生器；t为进化代数。若新的解支配原有解，则替代原有解成为CSAgent.body。该算子的作用是对Pareto最优解进行局部爬山操作。

4. 存储集种群构造规则

在基于Pareto的优化算法中，多目标进化群体的最优解集都是通过构造当前进化群体的非支配集来实现的。为尽量减小时间复杂度，这里采用了擂台赛法则来构造非支配集，并形成存储集种群。假设L为k个目标的多智能体进化群体，初始时令非支配集Nds=∅，并令Q=L。存储集种群构造的具体过程如下。

（1）从Q中任意选取一个个体x作为比较对象。

（2）令Q=Q-x，RK=∅，R=∅。

（3）若Q为空，则转步骤（5），否则转步骤（4）。

（4）一次从Q中取一个个体y，与x比较其相互关系。

①若，则令Q=Q-y，转步骤（3）。

②若，则令x=y，Q=Q-y，RK=RK∪R，R=∅。

③若x与y无关，则令R=R∪｛y｝，Q=Q-y，转步骤（3）。

（5）令，Nds=Nds∪｛x｝。

（6）令Q=RK′∪R，若|Q|＞1，则转步骤（1）；否则，令Nds=Nds∪Q，结束。

10.5　社会进化算法的实现步骤

假设多智能体种群L的规模为N，存储集种群为P，规模为M，占据概率为poccupy，交叉概率为pcross。

（1）初始化L（0），同时计算每个智能体的能量值，令P←∅，gen←0。

（2）停机条件判断。若满足停机条件，则算法停止运行并输出结果，否则转步骤（3）。

（3）存储集种群构造。对智能体种群L中的智能体根据擂台赛法则构造非支配集，将其添加到存储集种群P中，并删除P中的劣解；若P的规模大于预设规模M，则删除较拥挤的解，结果仍记为P。

（4）对L（gen）中的每个智能体执行邻域竞争操作，得到L（gen+1/3）。

（5）对L（gen+1/3）中的每个智能体进行邻域协同操作，得到L（gen+2/3），并更新智能体局部环境。

（6）对L（gen+2/3）中的Pareto最优个体进行自学习操作，得到下一代的初始智能体L（gen+1）。

（7）令gen←gen+1，并转步骤（2）继续操作。