求解SAT问题的多智能体社会进化算法

A Multi-Agent Social Evolutionary Algorithm for SAT Problem

基于Agent社会合作机制以及智能体对环境的感知和反作用能力提出了一种新的求解SAT问题的多智能体社会进化方法MASEA（Multi-AgentSocialEvolutionaryAlgorithm）。该方法在多智能体进化思想的基础上，引入人类社会“关系网模型”的概念来建立智能体所能感知的邻域环境；同时在保留原有的竞争算子和自学习算子前提下，根据智能体具有竞争协作的特性，设计了一个新的算子---协作算子来共同完成整个进化过程。以标准SATLIB库中变量个数从20～250的3700个不同规模的标准SAT问题以及基于RB模型所产生的随机实例对MASEA的性能进行了全面的测试，并与其他一些具有较高性能算法的结果进行了比较。结果表明，MASEA具有更高的成功率和更高的运算效率。

Based on the social cooperate mechanism of agents and the ability of agents in sensingand acting on the environment, a new algorithm, Multi-Agent Social Evolutionary Algorithm forSAT problem （MASEA）, is proposed. Based on the ideas of multi-agent evolutionary, this algo-rithm imports an acquaintance net, which denotes the relation of agents to construct the localenvironment for agents. On the basis of competition operator and self-learning operator, a newoperator is designed to complete the whole evolutionary process together. In the experiments,3700 benchmark SAT problems in SATLIB and some random examples generated from RB modelare used to test the performance of MASEA. Moreover, the performance of MASEA is comparedwith those of high performance algorithms. All experimental results show that MASEA has ahigher success ratio and a lower computational cost.