摘要
基于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.
出处
《计算机学报》
EI
CSCD
北大核心
2014年第9期2011-2020,共10页
Chinese Journal of Computers
基金
国家自然科学基金(61105064
61203311
61373116)
陕西省自然科学基金(2011JM8007)
陕西省普通高等学校重点学科专项资金建设项目资助~~
关键词
多智能体系统
进化算法
关系网模型
SAT问题
协作算子
multi-agent system
evolutionary algorithm
acquaintance net model
SAT problemcooperation operator