Multi-agent based cooperative search in combinatorial optimisation

  • Simon Martin

Student thesis: Doctoral Thesis


Cooperative search provides a class of strategies to design more effective search methodologies by combining (meta-) heuristics for solving combinatorial optimisation problems. This area has been little explored in operational research. This thesis proposes a general agent-based distributed framework where each agent implements a (meta-) heuristic. An agent continuously adapts itself during the search process using a cooperation protocol based on reinforcement learning and pattern matching. Good patterns which make up improving solutions are identified and shared by the agents. A theoretical approach to the understanding of the potential of agent-based systems is also proposed. This agent-based system aims to raise the level of generality by providing a flexible framework to deal with a variety of different problem domains. The proposed framework so far has been tested on Permutation Flow-shop Scheduling, Travelling Salesman Problem and Nurse Rostering. These instances have yielded some promising results. As part of the nurse rostering work a novel approach to modelling fairer nurse rosters is proposed.
Date of AwardFeb 2013
Original languageEnglish
SupervisorDjamila Ouelhadj (Supervisor) & Dylan Jones (Supervisor)

Cite this