A new approach for the development of problem-solvers for combinatorial problems isproposed in this thesis. The approach combines incremental knowledge acquisition and probabilisticsearch algorithms, such as evolutionary algorithms, to allow a human to rapidlydevelop problem-solvers in new domains in a framework called HeurEAKA. The approachaddresses a known problem, that is, adapting evolutionary algorithms to the search domainby the introduction of domain knowledge.The development of specialised problem-solvers has historically been labour intensive.Implementing a problem-solver from scratch is very time consuming. Another approach isto adapt a general purpose search strategy to the problem domain. This is motivated by theobservation that in order to scale an algorithm to solve complex problems, domain knowledgeis needed. At present there is no systematic approach allowing one to efficiently engineer a specialpurposesearch strategy for a given search problem. This means that, for example, adaptingevolutionary algorithms (which are general purpose algorithms) is often very difficult and haslead some people to refer to their use as a “black art”.In the HeurEAKA approach, domain knowledge is introduced by incrementally buildinga knowledge base that controls parts of the evolutionary algorithm. For example, the fitnessfunction and the mutation operators in a genetic algorithm. An evolutionary search algorithmismonitored by a human whomakes recommendations on search strategy based on individualsolution candidates. It is assumed that the human has a reasonable intuition of the searchproblem. The human adds rules to a knowledge base describing how candidate solutions canbe improved, or why they are desirable or undesirable in the search for a good solution.The incremental knowledge acquisition approach is inspired by the idea of (Nested) RippleDown Rules. This approach sees a human provide exception rules to rules already existingin the knowledge base using concrete examples of inappropriate performance of the existingknowledge base. The Nested Ripple Down Rules (NRDR) approach allows humans to composerules using concepts that are natural and intuitive to them. In HeurEAKA, NRDR aresignificantly adapted to form part of a probabilistic search algorithm. The probabilistic searchalgorithms used in the presented system are a genetic algorithm and a hierarchical bayesianoptimization algorithm.The success of the HeurEAKA approach is demonstrated in experiments undertaken onindustrially relevant domains. Problem-solvers were developed for detailed channel andswitchbox routing in VLSI design and traffic light optimisation for urban road networks.The problem-solvers were developed in a short amount of time, in domains where a largeamount of effort has gone into developing existing algorithms. Experiments show that chosenbenchmark problems are solved as well or better than existing approaches. Particularlyin the traffic light optimisation domain excellent results are achieved.
展开▼
