A new approach for the development of problem-solvers for combinatorial problems is proposed in this thesis. The approach combines incremental knowledge acquisition and probabilistic search algorithms, such as evolutionary algorithms, to allow a human to rapidly develop problem-solvers in new domains in a framework called HeurEAKA. The approach addresses a known problem, that is, adapting evolutionary algorithms to the search domain by 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 is to adapt a general purpose search strategy to the problem domain. This is motivated by the observation that in order to scale an algorithm to solve complex problems, domain knowledge is needed. At present there is no systematic approach allowing one to efficiently engineer a specialpurpose search strategy for a given search problem. This means that, for example, adapting evolutionary algorithms (which are general purpose algorithms) is often very difficult and has lead some people to refer to their use as a ???black art???. In the HeurEAKA approach, domain knowledge is introduced by incrementally building a knowledge base that controls parts of the evolutionary algorithm. For example, the fitness function and the mutation operators in a genetic algorithm. An evolutionary search algorithm ismonitored by a human whomakes recommendations on search strategy based on individual solution candidates. It is assumed that the human has a reasonable intuition of the search problem. The human adds rules to a knowledge base describing how candidate solutions can be 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) Ripple Down Rules. This approach sees a human provide exception rules to rules already existing in the knowledge base using concrete examples of inappropriate performance of the existing knowledge base. The Nested Ripple Down Rules (NRDR) approach allows humans to compose rules using concepts that are natural and intuitive to them. In HeurEAKA, NRDR are significantly adapted to form part of a probabilistic search algorithm. The probabilistic search algorithms used in the presented system are a genetic algorithm and a hierarchical bayesian optimization algorithm. The success of the HeurEAKA approach is demonstrated in experiments undertaken on industrially relevant domains. Problem-solvers were developed for detailed channel and switchbox 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 large amount of effort has gone into developing existing algorithms. Experiments show that chosen benchmark problems are solved as well or better than existing approaches. Particularly in the traffic light optimisation domain excellent results are achieved.
| Identifer | oai:union.ndltd.org:ADTP/187131 |
| Date | January 2006 |
| Creators | Bekmann, Joachim Peter, Computer Science & Engineering, Faculty of Engineering, UNSW |
| Publisher | Awarded by:University of New South Wales. School of Computer Science and Engineering |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright Joachim Peter Bekmann, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.0019 seconds