A new hyperheuristic algorithm for cross-domain search problems

Abstract

Hyperheuristiken bilden ein aufstrebendes Forschungsgebiet für Suchstrategien, welche die Einführung einer neuen Abstraktionsebene nützen um komputational schwierigen Problemen zu begegnen. Anstatt einen einzelnen Algorithmus zu verwenden, der auf eine bestimmte Klasse von Probleminstanzen optimiert ist, versuchen Hyperheuristiken die individuelle Leistungsfähigkeit einer gegebenen Menge von problemspezifischen Heuristiken auszunutzen. Durch die unterschiedliche Kombination und Parametrisierung dieser Heuristiken sind Hyperheuristiken theoretisch dazu in der Lage, gute Ergebnisse über einen größeren Bereich von Probleminstanzen zu erzielen. Idealerweise operieren Hyperheuristiken ohne jegliches Wissen bezüglich der zu lösenden Problemklasse und nur mit sehr geringem Wissen über die zur Verfügung stehenden untergeordneten Heuristiken. Aus diesem Grund können Hyperheuristiken auch oft ohne große Modifikationen auf neue Problemklassen angewendet werden. Damit stellen sie einen weiteren Schritt auf dem Weg zu einem universellen Problemlösungsalgorithmus dar.<br />Die vorliegende Arbeit beschreibt eine neue Hyperheuristik, die speziell darauf ausgelegt wurde, gänzlich unabhängig von einer bestimmten Problemklasse zu arbeiten und die sich dafür einer sehr klaren Abstraktionsebene bedient. Der Algorithmus ist in eine Anzahl unterschiedlicher Suchphasen untergliedert, welche für ein geeignetes Verhältnis zwischen der Intensivierung und der Diversifizierung des Suchprozesses sorgen. Die verfügbaren untergeordneten Heuristiken werden fortlaufend anhand mehrerer Eigenschaften bewertet und mit einer neuen qualitätsbasierten Metrik gereiht. Weiters vereinigt der Algorithmus eine Reihe von Ansätzen aus verschiedenen Gebieten der Forschung an Metaheuristiken, namentlich Iterated Local Search, Simulated Annealing, Tabusuche und genetischen Algorithmen.<br />Das Hauptziel dieser Arbeit war die Entwicklung einer Hyperheuristik die gute universelle Leistung über eine Vielzahl unterschiedlicher Problemklassen aufweist. Um die allgemeinen Problemlösungseigenschaften des Algorithmus bewerten zu können, wurde er anhand sechs verschiedener populärer Problemklassen aus dem Bereich der kombinatorischen Optimierung getestet. Eine Variante des Algorithmus wurde als Kandidat bei der Cross-domain Heuristic Search Challenge 2011 von der University of Nottingham eingereicht. Unter den 20 teilnehmenden Kandidaten aus aller Welt belegte unser Algorithmus im finalen Bewerb den sechsten Platz.<br />

Hyperheuristics are an emergent area of search methodologies which try to address computationally hard problems at a new level of abstraction. Instead of having a single algorithm that is optimised to perform well on a certain class of problem instances, hyperheuristics try to leverage the power of a whole set of problem specific heuristic algorithms. By combining and parametrising these heuristics or heuristic components in different ways, the overall algorithm should be able to perform better over a wider range of problem instances. Ideally, a hyperheuristic does not need to know anything about the problem class it operates on and only very little about the available heuristics. Because of this, hyperheuristics can often be applied without modifications to whole new problem domains and therefore represent a further step towards a very general problem solving algorithm.<br />This thesis describes a new hyperheuristic algorithm that was specifically designed to be completely problem domain independent and which works at a clearly defined level of abstraction. The algorithm is structured in different search phases that try to balance intensification and diversification of the search process. The available low-level heuristics are evaluated repeatedly in terms of certain properties and ranked according to a quality based metric that was found to work well across all tested low-level heuristics. Furthermore, the algorithm incorporates ideas from a number of different areas of metaheuristic research, such as iterated local search, simulated annealing, tabu search and genetic algorithms. The main goal of this work was to develop a hyperheuristic that achieves good overall performance on a wide variety of unrelated search domains.<br />In order to assess the generality of the algorithm, it was tested on six different, well-studied problem domains from the field of combinatorial optimisation. A version of the algorithm was also submitted as a candidate for the Cross-domain Heuristic Search Challenge 2011 organised by the University of Nottingham. Out of the twenty participants from all over the world, our algorithm was ranked sixth in the final competition.