The evolution of specialization in a multi-agent system is studied both by computer simulation and Markov process model. Many individual agents search for and exploit resources to get global optimization in an environment without complete information. With the selection acting on agent specialization at the level of system and under the condition of increasing returns, the division of labor emerges as the results of long-term optimizing evolution. Mathematical analysis gives the optimum division of agents and a Markov chain model is proposed to describe the evolutionary dynamics. The results are in good agreement with that of simulation model.

Key Words: division of labor, evolutionary dynamics, multi-agent system, emergence.
Zengru Di, Jiawei Chen, Yougui Wang, and Zhangang Han
Department of Systems Science, Beijing Normal University, Beijing, 100875, China

INTRODUCTION Ⅰ
The emergence of collective behavior in multi-agent systems has been an interesting area of complexity research. Multi-agent systems are characterized by vast number of agents trying to gain access to limited resources in an unpredictable environment. This description applies to a wide range of systems, ranging from ecology, economy to computer networks. In a distributed multi-agent system, be it natural or social, agents usually do not have complete information about the system in which they are embedded, and at the same time they must successfully interact with each other in order to get global optimization. Although the interactions among agents are simple and local, it can lead to complex dynamics at the global scale. Studies of computational ecology have shown that when the agents make choices in the presence of delayed and imperfect knowledge about the state of the system, their dynamics could give rise to nonlinear oscillations, clustered volatilities and chaos that drive the system far from optimality. In natural and social systems for example in the ecologically important social insects, the colony is self-organized as an integrated unit. The agents in the system have a hierarchical organization that determines the partitioning of reproduction, resources, and tasks. So the colony as a whole is able to manage a complex and changing foraging area.

Holland has argued that these complexities arise from the self-adaptive properties of the individual agent. The approach of complex adaptive systems has been applied to a wide range of systems, including biological ecosystems and economic systems.

Specialization or division of labor observed in many complex systems is one of the most striking examples of collective behavior. Roughly speaking, an economic organizational pattern is said to involve division of labor if it allocates labor of different individuals to different activities. Hence the specialization of individuals and the number of professional activities are the two sides of division of labor. Division of labor is a fundamental way to improve efficiency and utilization so as to get global optimization for the system. In social insects colony, the most obvious sign of the division of labor is the existence of castes. The individuals belonging to different castes are usually specialized for the performance of a series of precise tasks. A lot of works have been done to study the formation of division of labor and the mechanism for tasks allocation. In order to understand the mechanisms behind the formation of specialization, evolutionary processes and principles are helpful.

From the viewpoint of long-term evolution, selection acting on agent specialization must take place at the level of the colony. Some colonies survive and reproduce more than others because they have a division of labor that is better adapted for a particular environment. Actually, the evolutionary processes and principles play a fundamental role for the development of both natural and man-made systems. This includes molecular, genetic or cellular level as well as ecological, economic, social and technological problems. Despite the diversity of time and space scales involved all these processes are governed by the same principles of competition, mutation and selection. In this paper, a simple model for studying the evolutionary process of specialization is developed. The model describes a system of many individual agents that search for and exploit resources to get global optimization in an environment without complete information. There are two kinds of tasks for every agent: searching in the area to find unknown resources or exploiting the resource that is known as the best one to the agent. The behavior character of every agent - that is the probability for the agent to search for or to exploit resources - is described by a real number and it can be changed in the process of evolution. In each period we reward agents according to their actual performance to the global optimization of the system. An algorithm is given to describe the genetic variation and natural selection. As well shall see, with long-term evolution the system usually forms a certain macroscopic structure. Under the condition of increasing returns, specialization in deterministic exploiting and stochastic searching behavior is always the results from the global optimizing evolution from certain given initial conditions, such as the agents are all homogenous, random or uniform distributed. The results reveal that the random mutation in evolutionary process is necessary to form macroscopic structure and to reach global optimum. Meanwhile the stochastic behavior of some agents is meaningful for the system to deal with uncertain environments. A mathematical analysis based on Markov chain process gives similar results. Our work provides several insights that are useful knowledge for us to understanding the evolutionary dynamics in biology and the formation of organization.

The presentation is organized into two major parts. In Section II the model for computer simulation is presented. Resources distribution and related growth dynamics are qualified. Agent’s behaviors, total returns of all agents as fitness function of the system, and algorithm for evolutionary process are also given. Then the computer simulation results are reported. In Section III , capturing the basic features of the above simulation model, we present a simpler situation for mathematical analysis.

We show that when there is increasing returns in agents’ behavior, the division of agents in searching and exploiting is a necessary condition for global optimization. A Markov chain process model to describe the evolutionary dynamics of the system is introduced. The corresponding results of mathematical and simulation model are consistent well. In Section IV , we provide a summary of our results and a brief discussion of some unresolved issues that remain.

Source, and complete item