Principal Investigator: Zahid Hussain

My research work involves solving NP complete optimisation problems using heuristic local search methods(Genetic Algorithm (GA), Simulated Annealing (SA), Tabu Search (TS) etc.) and comparing their performance in a statistical way. I am seeking to make use of public domain libraries of different heuristics (e.g. Matthew Wall's GAlib from MIT) to develop my own software tool to generate data using each heuristic method for performance analysis. Initially, work has been started using GAs on the Travelling Salesman Problem.

In my transfer report the most widely used heuristic local search methods used in solving NP complete optimisation problems are surveyed and described. Methods of implementing these using object-oriented computing techniques are discussed, and some appropriate object/class libraries are explored. Ideas are collected for the design of a computer-based workbench to be used for testing heuristic methods on optimisation problems.

My work has focussed on questions of performance and comparison of different heuristics. Because the heuristics involve statistical variability, the methods needed to compare performance on the intended work-bench must relate to the ideas of sampling and hypothesis testing. The issues in which sampling and testing raise, and the comparison metrics which are appropriate, have been examined carefully. The results have been used to define a number of sampling and metrics related to the degree of suboptimality, the consistency and robustness, and the time-complexity of heuristics. I have delineated the boundaries for further research needed to provide a sound statistical foundation for the intended work bench.