Augmenting evolution with agency
During the last decades intelligent/autonomous software agents have been gaining more and more applications in various domains, such as power systems management, flood forecasting, business process management, intersection management, or solving difficult optimization problems just to mention a few. The key to understand the concept of a multi-agent system (MAS) is an intelligent interaction (like coordination, cooperation, or negotiation). Thus multi-agent systems are ideally suited for representing problems that have many solving methods, involve many perspectives and/or may be solved by many entities. That is why, one of major application areas of multi-agent systems is largescale computing.
Agents play an important role in the integration of AI sub-disciplines, which is often related to the hybrid design of modern intelligent systems. At this site a hybrid evolutionary-agent approach has been described. In most of similar applications, an evolutionary algorithm is used by an agent to aid realisation of some of its tasks, often connected with learning or reasoning, or to support coordination of some group (team) activity. In other approaches, agents constitute a management infrastructure for a distributed realisation of an evolutionary algorithm.
Evolutionary processes are by nature decentralised and therefore one may imagine the incorporation of evolutionary processes into a multi-agent system at a population level. It means that agents are able to reproduce (generate new agents), which is a kind of cooperative interaction and may die (be eliminated from the system), which is the result of competition (selection). The key idea of the decentralised model of evolution employed by an evolutionary multi-agent system - EMAS was to ensure full autonomy of agents.
Such a system consists of a relatively large number of rather simple (reactive), often homogenous agents, which possess or produce solutions to the same problem (a common goal), it is rather closed and static, but non-determinitic. Because of both computational simplicity and a huge number of the agents, the influence of each single agent’s behaviour on the overall system operation may be neglected, which allows for the efficient realisation in large-scale environments with lightweight infrastructure.
Evolutionary algorithms are universal technique for general optimization. Instead of directly solving the given problem, the problem is encoded in a special way (genotype) and random populations of potential solutions are constructed. Based on the existing fitness function (evaluating the genotype), selection is performed (so the mating pool is created) and based on the mating pool, the subsequent population is created with use of predefined variation operators (such as crossover and mutation). The process continues until some stopping condition is reached (e.g., number of generations, lack of changes in the best solution found so far). This kind of search has some drawbacks (as possibility of premature convergence), thus several techniques, as multi-deme approaches are applied.
A scheme of a general evolutionary algorithm is given in a figure below:
It may be seen, that the population of potential (encoded) solutions of a given problem is decomposed into evolutionary islands (there is also a possibility of migration between them). The most important fact is that the evolutionary algorithm is common to all islands, all operators are applied one by one, during each of generations, to all parts of the population. After meeting some kind of stopping condition, the best solution so far is presented as the optimal one. One of the main drawbacks of such an approach is global (god-like) selection algorithm - possibilities of its de-globalization will be described later.
Problems with evolutionary algorithms
Evolutionary algorithms are particularly useful when classical computational methods turn out to be ineffective, because corresponding models are too complex, or formulas applied too complicated, or even some formulations must be rejected in the face of numerical instability of available solvers. Unfortunately, one of the main drawbacks of evolutionary algorithms is no guarantee to find satisfactory solutions. Moreover, their performance aspects for particular problems must be verified empirically.
Many algorithms tend to prematurely loose the useful population diversity and therefore the risk arises that the population might get stuck in some part of the search space (e.g. in the basin of attraction of a certain local extremum instead of searching for a global one). Loosing the population diversity also limits the possibilities of their application in some areas such as multi-objective optimisation or multi-modal optimisation.
Another problem with evolutionary algorithms is that the selection of the proper evolutionary algorithm for the given task is an open problem. One of the reasons for that is the weakness of the theory of evolutionary algorithms: “We know that they work, but we do not know why” as T. Back, U. Hammel and H.-P. Schwefel expressed. What is more, the model of evolution followed by most EAs (with noticeable exceptions) is much simplified and lacks many important features observed in organic evolutions:
- dynamically changing environmental conditions,
- many criteria in consideration,
- neither global knowledge nor generational synchronisation assumed,
- co-evolution of species,
- evolving genotype-fenotype mapping.
The idea of decentralised evolutionary computation, realized as an evolutionary multi-agent system may help to avoid some of the shortcomings of the model of evolution employed in classical evolutionary computation techniques.
Agent-based evolutionary computation
Among lots of issues related to agent technology one can find also evolutionary computation present in multi-agent systems (MAS). In most such cases an evolutionary algorithm is used by an agent (see figure below) to aid realization of some its tasks (e.g. connected with learning or reasoning) or to support coordination of some group (team) activity.
Thus, each agent locally applies selection and variation operators, and therefore may (in possibly intelligent way) change the parameters of the search, communicate with other agents in order to refine the search criteria, evaluate the stopping condition etc. Each agent performs its tasks autonomously, so each part of the algorithm may be adapted. In this way, an important way in de-centralizing of the global control in evolutionary algorithms has been made.
Yet it seems that interesting results may be achieved applying some model of evolution in MAS at a population level (see figure below) i.e. among agents. In this case, genetic operators together with selection/reproduciton mechanisms search for (near) optimal configuration of the agents constituting a particular population or the whole system. Such a new class of adaptive multi-agent systems where evolutionary processes help to accomplish population level goals is called evolutionary multi-agent systems (EMAS).
In this approach, agents gain even deeper insight into evolution process, constituting one being with a possible solution of the problem. So, an agent may transform its genotype in any possible way, not constrained by the classical variation operators only. In this way, another step in decentralization of the control of evolutionary-like algorithms is made.