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.
Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:570686 |
Date | January 2013 |
Creators | Martin, Simon |
Contributors | Ouelhadj, Djamila ; Jones, Dylan Francis |
Publisher | University of Portsmouth |
Source Sets | Ethos UK |
Detected Language | English |
Type | Electronic Thesis or Dissertation |
Source | https://researchportal.port.ac.uk/portal/en/theses/multiagent-based-cooperative-search-in-combinatorial-optimisation(7fcdfce2-57fa-4a03-b6cc-ef6b70979cb8).html |
Page generated in 0.0037 seconds