A Game Theory-Based Multi-Agent System for Expensive Optimisation Problems

This paper is concerned with the development of a novel approach to solve expensive optimisation problems. The approach relies on game theory and a multi-agent framework in which a number of existing algorithms, cast as agents, are deployed with the aim to solve the problem in hand as efficiently as possible. The key factor for the success of this approach is a dynamic resource allocation biased toward promising algorithms on the given problem. This is achieved by allowing the agents to play a cooperative-competitive game the outcomes of which will be used to decide which algorithms, if any, will drop out of the list of solver-agents and which will remain in use. A successful implementation of this framework will result in the most suited algorithm(s) for the given problem being predominantly used on the available computing platform. In other words it guarantees the best use of the resources both algorithms and hardware with the by-product being the best approximate solution for the problem given the available resources. GTMAS is tested on a standard collection of TSP problems. The results are included.