Yes / We present a thorough review of hyperheuristic research to date, and analyse/compare hyperheuristic papers based on the methods used.

Scheduling large real world problems is a complex process and finding high quality solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide scheduling solutions for many large companies, a problem is identified and modelled. It is a general model which encapsulates several important scheduling, routing and resource allocation problems in literature. Many of the state-of-the-art heuristics for solve scheduling problems and indeed other problems require specialised heuristics tailored for the problem they are to solve. While these provide good solutions a lot of expert time is needed to study the problem, and implement solutions. This research investigates methods to enhance existing search based methods. We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics raise the generality of the solution method by using a set of tools (low level heuristics) to work on the solution. These tools are problem specific and usually make small changes to the problem. It is the task of the hyperheuristic to determine which tool to use and when. Low level heuristics using exact/heuristic hybrid method are used in this thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU time required to produce good quality solutions. We also develop and investigate the Variable Fitness Function approach, which provides a new way of enhancing most search-based heuristics in terms of solution quality. If a fitness function is pushing hard in a certain direction, a heuristic may ultimately fail because it cannot escape local minima. The Variable Fitness Function allows the fitness function to change over the search and use objective measures not used in the fitness calculation. The Variable Fitness Function and its ability to generalise are extensively tested in this thesis. The two aims of the thesis are achieved and the methods are analysed in depth. General conclusions and areas of future work are also identified.

Scheduling large real world problems is a complex process and finding high quality solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide scheduling solutions for many large companies, a problem is identified and modelled. It is a general model which encapsulates several important scheduling, routing and resource allocation problems in literature. Many of the state-of-the-art heuristics for solve scheduling problems and indeed other problems require specialised heuristics tailored for the problem they are to solve. While these provide good solutions a lot of expert time is needed to study the problem, and implement solutions. This research investigates methods to enhance existing search based methods. We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics raise the generality of the solution method by using a set of tools (low level heuristics) to work on the solution. These tools are problem specific and usually make small changes to the problem. It is the task of the hyperheuristic to determine which tool to use and when. Low level heuristics using exact/heuristic hybrid method are used in this thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU time required to produce good quality solutions. We also develop and investigate the Variable Fitness Function approach, which provides a new way of enhancing most search-based heuristics in terms of solution quality. If a fitness function is pushing hard in a certain direction, a heuristic may ultimately fail because it cannot escape local minima. The Variable Fitness Function allows the fitness function to change over the search and use objective measures not used in the fitness calculation. The Variable Fitness Function and its ability to generalise are extensively tested in this thesis. The two aims of the thesis are achieved and the methods are analysed in depth. General conclusions and areas of future work are also identified.

Thesis (PhD (Logistics))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: The design of a water distribution system (WDS) involves finding an acceptable trade-off between cost minimisation and the maximisation of numerous system benefits, such as hydraulic reliability and surplus capacity. The primary design problem involves cost-effective specifica- tion of a pipe network layout and pipe sizes (which are typically available in a discrete set of commercial diameters) in order to satisfy expected consumer water demands within required pressure limits. The problem may be extended to consider the design of additional WDS com- ponents, such as reservoirs, tanks, pumps and valves. Practical designs must also cater for the uncertainty of demand, the requirement of surplus capacity for future growth, and the hydraulic reliability of the system under different demand and potential failure conditions. A detailed literature review of exact and approximate approaches towards single-objective (minimum cost) WDS design optimisation is provided. Essential topics which have to be included in any modern WDS design paradigm (such as demand estimation, reliability quantification, tank design and pipe layout) are discussed. A number of formative concepts in multi-objective evo- lutionary optimisation are also reviewed (including a generic problem formulation, performance evaluation measures, comparative testing strategies, and suitable classes of metaheuristics). The two central themes of this dissertation are conducting multi-objective WDS design optimi- sation using metaheuristics, and a critical examination of surrogate measures used to quantify WDS reliability. The aim in the first theme is to compare numerous modern metaheuristics, in- cluding several multi-objective evolutionary algorithms, an estimation of distribution algorithm and a recent hyperheuristic named AMALGAM (an evolutionary framework for the simulta- neous incorporation of multiple metaheuristics applied here for the first time to a real-world problem), in order to determine which approach is most capable with respect to WDS design optimisation. Several novel metaheuristics are developed, as well as a number of new variants of existing algorithms, so that a total of twenty-three algorithms were compared. Testing with respect to eight small-to-large-sized WDS benchmarks from the literature reveals that the four top-performing algorithms are mutually non-dominated with respect to the vari- ous performance metrics. These algorithms are NSGA-II, TAMALGAMJndu, TAMALGAMndu and AMALGAMSndp (the last three being novel variants of AMALGAM). However, when these four algorithms are applied to the design of a very large real-world benchmark, the AMALGAM paradigm outperforms NSGA-II convincingly, with AMALGAMSndp exhibiting the best perfor- mance overall. As part of this study, a novel multi-objective greedy algorithm is developed by combining several heuristic design methods from the literature in order to mimic the design strategy of a human engineer. This algorithm functions as a powerful local search. However, it is shown that such an algorithm cannot compete with modern metaheuristics, which employ advanced strategies in order to uncover better solutions with less computational effort. The second central theme involves the comparison of several popular WDS reliability surro- gate measures (namely the Resilience Index, Network Resilience, Flow Entropy, and a novel mixed surrogate measure) in terms of their ability to produce designs that are robust against pipe failure and water demand variation. This is the first systematic study on a number of WDS benchmarks in which regression analysis is used to compare reliability surrogate measures with probabilistic reliability typically derived via simulation, and failure reliability calculated by considering all single-pipe failure events, with both reliability types quantified by means of average demand satisfaction. Although no single measure consistently outperforms the others, it is shown that using the Resilience Index and Network Resilience yields designs that achieve a better positive correlation with both probabilistic and failure reliability, and while the Mixed Surrogate measure shows some promise, using Flow Entropy on its own as a quantifier of re- liability should be avoided. Network Resilience is identified as being a superior predictor of failure reliability, and also having the desirable property of supplying designs with fewer and less severe size discontinuities between adjacent pipes. For this reason, it is recommended as the surrogate measure of choice for practical application towards design in the WDS industry. AMALGAMSndp is also applied to the design of a real South African WDS design case study in Gauteng Province, achieving savings of millions of Rands as well as significant reliability improvements on a preliminary engineered design by a consulting engineering firm. / AFRIKAANSE OPSOMMING: Die ontwerp van waterverspreidingsnetwerke (WVNe) behels die soeke na ’n aanvaarbare afruiling tussen koste-minimering en die maksimering van ’n aantal netwerkvoordele, soos hidroliese betroubaarheid en surpluskapasiteit. Die primere ontwerpsprobleem behels ’n koste-doeltreffende spesifikasie van ’n netwerkuitleg en pypgroottes (wat tipies in ’n diskrete aantal kommersiele deursnedes beskikbaar is) wat aan gebruikersaanvraag binne sekere drukspesifikasies voldoen. Die probleem kan uitgebrei word om die ontwerp van verdere WVN-komponente, soos op- gaardamme, opgaartenks, pompe en kleppe in ag te neem. Praktiese WVN-ontwerpe moet ook voorsiening maak vir onsekerheid van aanvraag, genoegsame surpluskapsiteit vir toekom- stige netwerkuitbreidings en die hidroliese betroubaarheid van die netwerk onder verskillende aanvraag- en potensiele falingsvoorwaardes. ’n Omvattende literatuurstudie word oor eksakte en benaderde oplossingsbenaderings tot enkel- doelwit (minimum koste) WVN-ontwerpsoptimering gedoen. Sentrale temas wat by heden- daagse WVN-ontwerpsparadigmas ingesluit behoort te word (soos aanvraagvooruitskatting, die kwantifisering van betroubaarheid, tenkontwerp en netwerkuitleg), word uitgelig. ’n Aantal basiese konsepte in meerdoelige evolusionˆere optimering (soos ’n generiese probleemformulering, werkverrigtingsmaatstawwe, vergelykende toetsingstrategie¨e, en sinvolle klasse metaheuristieke vir WVN-ontwerp) word ook aangeraak. Die twee sentrale temas in hierdie proefskrif is meerdoelige WVN-ontwerpsoptimering deur mid- del van metaheuristieke, en ’n kritiese evaluering van verskeie surrogaatmaatstawwe vir die kwantifisering van netwerkbetroubaarheid. Die doel in die eerste tema is om ’n aantal moderne metaheuristieke, insluitend verskeie meerdoelige evolusionere algoritmes en die onlangse hiper- heuristiek AMALGAM (’n evolusionere raamwerk vir die gelyktydige insluiting van ’n aantal metaheuristieke wat hier vir die eerste keer op ’n praktiese probleem toegepas word), met mekaar te vergelyk om sodoende ’n ideale benadering tot WVN-ontwerpoptimering te identi- fiseer. Verskeie nuwe metaheuristieke sowel as ’n aantal nuwe variasies op bestaande algoritmes word ontwikkel, sodat drie en twintig algoritmes in totaal met mekaar vergelyk word. Toetse aan die hand van agt klein- tot mediumgrootteWVN-toetsprobleme uit die literatuur dui daarop dat die vier top algoritmes mekaar onderling ten opsigte van verskeie werkverrigtings- maatstawwe domineer. Hierdie algoritmes is NSGA-II, TAMALGAMJndu, TAMALGAMndu en AMALGAMSndp, waarvan laasgenoemde drie nuwe variasies op AMALGAM is. Wanneer hierdie vier algoritmes egter vir die ontwerp van ’n groot WVN-toetsprobleem ingespan word, oortref die AMALGAM-paradigma die NSGA-II oortui-gend, en lewer AMALGAMSndp die beste resultate. As deel van hierdie studie is ’n nuwe meerdoelige gulsige algoritme ontwerp wat verskeie heuristiese ontwerpsmetodologiee uit die literatuur kombineer om sodoende die on- twerpstrategie van ’n ingenieur na te boots. Hierdie algoritme funksioneer as ’n kragtige lokale soekprosedure, maar daar word aangetoon dat die algoritme nie met moderne metaheuristieke, wat gevorderde soekstrategie¨e inspan om beter oplossings met minder berekeningsmoeite daar te stel, kan meeding nie. Die tweede sentrale tema behels die vergelyking van ’n aantal gewilde surrogaatmaatstawwe vir die kwantifisering van WVN-betroubaarheid (naamlik die elastisiteitsindeks, netwerkelastisiteit, vloei-entropie en ’n gemengde surrogaatmaatstaf ) in terme van die mate waartoe hul gebruik kan word om WVNe te identifiseer wat robuust is ten opsigte van pypfaling en variasie in aanvraag. Hierdie proefskrif bevat die eerste sistematiese vergelyking deur middel van regressie-analise van ’n aantal surrogaatmaatstawwe vir die kwantifisering van WVN-betroubaarheid en stogastiese betroubaarheid (wat tipies via simulasie bepaal word) in terme van ’n aantal toetsprobleme in die literatuur. Alhoewel geen enkele maatstaf as die beste na vore tree nie, word daar getoon dat gebruik van die elastisiteitsindeks en netwerkelastisiteit lei na WNV-ontwerpe met ’n groter positiewe korrelasie ten opsigte van beide stogastiese betroubaarheid en falingsbetroubaarheid. Verder toon die gebruik van die gemengde surrogaatmaatstaf potensiaal, maar die gebruik van vloei-entropie op sy eie as kwantifiseerder van betroubaarheid behoort vermy te word. Netwerkelastisiteit word as ’n hoe-gehalte indikator van falingsbetroubaarheid geidentifiseer en het ook die eienskap dat dit daartoe instaat is om ontwerpe met ’n kleiner aantal diskontinuiteite sowel as van ’n minder ekstreme graad van diskontinuiteite tussen deursnedes van aangrensende pype daar te stel. Om hierdie rede word netwerkelastisiteit as die surogaatmaatstaf van voorkeur aanbeveel vir toepassings van WVN-ontwerpe in die praktyk. AMALGAM word ook ten opsigte van ’n werklike Suid-Afrikaanse WVN-ontwerp gevallestudie in Gauteng toegepas. Hierdie toepassing lei na die besparing van miljoene rande asook noe- menswaardige verbeterings in terme van netwerkbetroubaarheid in vergeleke met ’n aanvanklike ingenieursontwerp deur ’n konsultasiefirma.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.

Uma hiper-heurística é uma heurística que pode ser utilizada para lidar com qualquer problema de otimização, desde que a ela sejam fornecidos alguns parâmetros, como estruturas e abstrações, relacionados ao problema considerado. As hiper-heurísticas têm sido aplicadas a alguns problemas práticos e apresentadas como métodos de grande potencial, no que diz respeito à capacidade de possibilitar o desenvolvimento, em tempo bastante reduzido, de algoritmos capazes de lidar satisfatoriamente, do ponto de vista prático, com problemas de otimização complexos e pouco conhecidos. No entanto, é difícil situar as hiper-heurísticas em algum nível de qualidade e avaliar a robustez dessas abordagens caso não as apliquemos a problemas para os quais existam diversas instâncias disponíveis publicamente e já experimentadas por algoritmos relevantes. Este trabalho procura dar alguns passos importantes rumo a essas avaliações, além de ampliar o conjunto das hiper-heurísticas, compreender o impacto de algumas alternativas naturais de desenvolvimento e estabelecer comparações entre os resultados obtidos por diferentes métodos, o que ainda nos permite confrontar as duas diferentes classes de hiper-heurísticas que identificamos. Com essas finalidades em mente, desenvolvemos 3 novas hiper-heurísticas e implementamos 2 das hiper-heurísticas mais importantes criadas por outros autores. Para estas últimas, experimentamos ainda algumas extensões e modificações. Os dois métodos hiper-heurísticos selecionados podem ser vistos como respectivos representantes de duas classes distintas, que aparentemente englobam todas as hiper-heurísticas já desenvolvidas e nos permitem denominar cada um desses métodos como \"hiper-heurística de busca direta por entornos\" ou como \"hiper-heurística evolutiva indireta\". Implementamos cada hiper-heurística como uma biblioteca (em linguagem C), de forma a evidenciar e estimular a independência entre o nível em que se encontra a hiper-heurística e aquele onde se apresentam as estruturas e abstrações diretamente relacionadas ao problema considerado. Naturalmente, essa separação é de ingente importância para possibilitar a reutilização imediata das hiper-heurísticas e garantir que nelas haja total ausência de informações relativas a um problema de otimização específico. / A hyperheuristic is a heuristic that can be used to handle any optimization problem, provided that the algorithm is fed with some parameters, as structures and abstractions, related to the problem at hand. Hyperheuristics have been applied to some practical problems and presented as methods with great potential to allow the quick development of algorithms that are able to successfully deal, from a practical standpoint, with complex ill-known optimization problems. However, it\'s difficult to position hyperheuristics at some quality level and evaluate their robustness without applying them to problems for which there are many instances available in the public domain and already attacked by worthy algorithms. This work aims to give some important steps towards that process of evaluation, additionally increasing the number of available hyperheuristics, studying the impact of some natural development alternatives and comparing the results obtained by different methods, what also enables us to confront the two classes of hyperheuristics that we have identified. With those purposes in mind, we have developed 3 original hyperheuristics and implemented 2 of the most important hyperheuristics created by other authors. For those latter two approaches, we have also experimented with some modifications and extensions. The two methods we have chosen for implementation may be seen as respectively representing two distinct classes, which seem to contain all hyperheuristics developed so far and that allow us to classify any of these methods as either being a \"direct neighbourhood search hyperheuristic\" or an \"indirect evolutive hyperheuristic\". We have implemented each hyperheuristic as a library (in the C language), so as to clearly show and estimulate the independence between the level where the hyperheuristic is and that to which the structures and abstractions directly related to the problem at hand belong. Obviously, this separation of concerns is extremely important to make the immediate reuse of hyperheuristics possible and enforce in them the complete absence of information from a specific optimization problem.