Multiagent Evolutionary Models And Algorithms

Multiagent systems and evolutionary computation are two valuable fields in practical applications. Although they have been widely used in many fields, a little research has been made to integrate them together. This thesis is focused on integrating multi-agent systems and evolutionary computation together to overcome their disadvantages, and form high efficient new algorithms. Systematic researches have been made along numerical optimization, combinatorial optimization, constraint satisfaction problems, constrained layout optimization, and multicast routing problems. Different behaviors are designed for agents and different methods are proposed to deal different problems, and can be summarized as follows:(1) Based on the ability of agents in sensing and acting on the environment, a new method, multiagent genetic algorithm, is proposed for the global numerical optimization. In this method, all agents live in a latticelike environment, with each agent fixed on a lattice-point. In order to increase energies, they compete or cooperate with their neighbors, and they can also use knowledge. Theoretical analyses show that it converges to the global optimum. In the experiments, 10 benchmark functions with 20~10 000 dimensions are used to validate the performance. The results show that even when the dimensions increase to as high as 10 000, it still can find high quality solutions at a low computational cost. Therefore, the method has a good scalability and is a competent algorithm for solving high dimensional optimization problems.(2) Genetic algorithms strongly depend on the lower and upper bounds for numerical optimization, which is inconvenient to practical applications. To cure this problem, we propose a search space expansion scheme. Then, this scheme is combined with multiagent genetic algorithm to form a new method to the problem of approximation of linear systems. A stable linear system and an unstable linear system are used to test its performance, with a satisfactory result obtained.(3) For decomposable functions, a macro-agent evolutionary model is proposed. Then, it is combined with multiagent genetic algorithm to form a new method, hierarchical multiagent genetic algorithm. In the experiments, for the Rosenbrock function, even when the dimension increases to 50 000, it can still find high quality solutions with a low computational cost.(4) For combinatorial optimization, a new algorithm, multiagent evolutionary algorithm for combinatorial optimization, is proposed. Theoretical analyses show that it converges to the global optimum. In the experiments, various deceptive problems, such as the ones with strong-linkage, weak-linkage and overlapping-linkage, and hierarchical problems are used to validate the performance. In order to test its performance on solving large-scale problems, it is used to solve deceptive problems and hierarchical problems with thousands of dimensions, and the computational complexity is analyzed. All results show that it has a low computational cost and obtains a good performance.(5) With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, several behaviors are designed for agents. These behaviors are controlled by means of evolution, so that multiagent evolutionary algorithm for constraint satisfaction problems results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. Theoretical analyses show that the method has a linear space complexity and converges to the global optimum. The first part of the experiments uses 250 benchmark binary CSPs to analyze the effect of the parameters. The second part of the experiments uses w-queen problems to test the performance. The method achieves a good performance when n increases from 10~4 to 10~7.(6) For two practical cases, constrained layout optimization and multicast routing problems, the solving way by multiagent evolutionary algorithms are proposed. For constrained layout optimization, the problems with 5, 7, and 40 circles are used to test t...