Franciszek Seredynski

Competitive Coevolutionary Multi-Agent Systems: the Application to Mapping and Scheduling Problems

838

Abstract

A new paradigm for a parallel and distributed evolutionary computation is proposed in the paper. The main idea of the proposed approach is based on considering a given system as a multi-agent system with game-theoretic models of interaction between players. For this purpose a model of noncooperative {\it N}-person games with limited interaction is considered. Each player in the game has a payoff function and a set of actions. While players compete to maximize their payoffs, we are interested in the global behavior of the team of players, measured by the average payoff received by the team. To evolve a global behavior in the system, we propose three distributed schemes with evaluation of only local fitness functions. The first scheme uses $\varepsilon$~-~learning automata and is compared with two coevolutionary schemes, which we call loosely coupled genetic algorithms, and loosely coupled classifier systems respectively. We present simulation results which indicate that the global behavior in the systems emerges, and is achieved in particular by only a local cooperation between players acting without global information about the system. The models of multi-agent systems are applied to develop parallel and distributed algorithms of dynamic mapping and scheduling tasks in parallel computers.

Key words: distributed artificial intelligence, evolutionary computation, game theory, learning automata, multi-agent systems, multiprocessors, parallel mapping and scheduling.