Solving SAT problem with a multiagent evolutionary algorithm

With the intrinsic properties of satisfiability problem (SAT problem) in mind, we integrate the multiagent systems and evolutionary algorithms to form a new algorithm, Multiagent Evolutionary Algorithm for SAT problem (MAEA-SAT). In MAEA-SAT, all agents live in a latticeilke environment. Making use of the designed behaviors, MAEA-SAT realizes the ability of agents to sense and act on the environment in which they live. During the process of interacting with the environment and other agents, each agent increases energy as much as possible, so that MAEA-SAT can find the optima. The benchmarks about SAT problems of different scales in SATLIB are used to test the performance of MAEA-SAT, and we compared MAEA-SAT with standard GA (namely SGA). The experimental results show that the MAEA-SAT obtained an outstanding performance in solving large-scale SAT problems.