Research

This is a collection of my current research interests, some recent technical reports and comments on the commercialisation of this research.

Publications

Angus, D., Smith, A.E., Wiles, J. "Conceptual Recurrence Plots: Revealing Patterns in Human Discourse", IEEE Transactions on Visualization and Computer Graphics (in press), 2011.

Lai, J., Reilly, J., Wiles, J., Angus, D., Smith, A.E., "Conversational Narratives in School-Age Children With High-Functioning Autism", 2011 American Speech-Language-Hearing Association Convention, San Diego, CA, 2011.

Watson, B., Angus, D., Farmer, J., Wiles, J., Smith, A.E., "Evaluating Effective Open Disclosure Through Visualisation: What Works and for Whom?", 61st Annual Conference of the International Communication Association, Boston, 2011.

Angus, D. "Niching for Ant Colony Optimisation" Lewis, A.; Mostaghim, S. & Randall, M. (ed.) Biologically-Inspired Optimisation Methods: Parallel Algorithms, Systems and Applications, Springer, 2009

Angus, D. & Woodward, C. "Multiple Objective Ant Colony Optimisation" Swarm Intelligence, 2009, 3, p.69-85

Angus, D. & Deller, A. "Computational Intelligence in Radio Astronomy: Using Computational Intelligence Techniques to Solve Geodesy Models" Simulated Evolution and Learning, Seventh International Conference, SEAL 2008, 2008

Angus, D. "Population-Based Ant Colony Optimisation for Multi-objective Function Optimisation" Progress in Artificial Life, Third Australian Conference, ACAL 2007, 2007

Angus, D. "Crowding Population-based Ant Colony Optimisation for the Multi-objective Travelling Salesman Problem" 2007 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making (MCDM 2007), 2007

Angus, D. "Niching for Population-based Ant Colony Optimization" 2nd International IEEE Conference on e-Science and Grid Computing, Workshop on Biologically-inspired Optimisation Methods for Parallel and Distributed Architectures: Algorithms, Systems and Applications, 2006

Angus, D. & Hendtlass, T. "Dynamic ant colony optimisation" Applied intelligence, 2005

Angus, D. & Hendtlass, T. "Ant Colony Optimisation Applied to a Dynamically Changing Problem" 15th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2002

Back to homepage

PhD Thesis

Niching Ant Colony Optimisation

Optimisation, in the mathematical sense, is the process of finding solutions to a problem such that one or many objectives are minimised or maximised. Optimisation problems are diverse in form, necessitating the need for many different optimisation algorithms. These algorithms can be defined in two categories: deterministic and non-deterministic algorithms. Deterministic algorithms usually have set execution schedules and are fairly exhaustive search methods. Non-deterministic algorithms use randomness and prove useful for problems where it may not be possible to execute a deterministic algorithm due to the size, or nature of the problem search space. In these cases a deterministic algorithm may take days or months to find an optimal solution, whereas a non-deterministic algorithm can usually find an approximate but still near-optimal solution in a matter of minutes or seconds.

Ant Colony Optimisation (ACO), a non-deterministic algorithm class, aims to mimic (and exploit) the behaviours of real ant colonies to solve real-world optimisation problems. ACO algorithms are a class of constructive heuristic algorithms, which build solutions to a given optimisation problem, one solution component at a time, according to a defined set of rules (heuristics), i.e. starting with an `empty' solution add solution components until a complete solution is built. ACO algorithms are unique in this class by their use of past solutions in manipulating an artificial `pheromone'. The pheromone being a measure associated to every unique solution component which reflects the estimated utility of this solution component. These pheromone values are used to bias solution construction by influencing the probability of a solution component being added to a growing solution based on the amount of pheromone it contains.

The Population-based Ant Colony Optimisation (PACO) algorithm is a recently developed ant-inspired algorithm which, unlike traditional ACO algorithms, maintains a finite population of solutions as well as pheromone information. It has been demonstrated to be an efficient optimisation algorithm when applied to a range of difficult single-objective, multi-objective and dynamic problem instances. In this thesis a review of existing PACO algorithms is offered and an identification of common features is used in the development of a Population-based ACO framework.

Using the new Population-based ACO framework, several new PACO algorithms imbued with a diversity preservation technique known as niching are defined. Niching has been used extensively in the field of Evolutionary Computation, but to the best knowledge of the author, has never been explicitly applied to an ACO algorithm per se. An empirical analysis of these novel implementations is presented using a variety of single and multiple objective continuous function and combinatorial optimisation problems. These optimisation problems have been chosen since they demonstrate the advantages and disadvantages of adding niching to a PACO algorithm. To conclude, two of these new PACO algorithms are applied to a real-world optimisation problem.

Back to homepage

Recent Research (last 3 years)

Ant Colony Optimisation applied to Multiple-Objective Optimisation

Ant inspired algorithms have recently gained popularity for use in multi-objective problem domains. One specific algorithm, Population-based ACO, which uses a population as well as the traditional pheromone matrix, has been shown to be effective at solving combinatorial multi-objective optimisation problems. This research aims at extending the Population-based ACO algorithm with a crowding population replacement scheme to increase the search efficacy and efficiency. Several Multi-objective Travelling Salesman Problems of varying complexity are used to determine algorithm performance. This work was published at the IEEE 2007 Symposium on Multi Criteria Decision Making and was fortunate to receive the award for best student paper. A copy of the paper can be found here.

Niching for Population-based Ant Colony Optimisation

This research was presented at the Workshop on Biologically-inspired Optimisation Methods for Parallel and Distributed Architectures: Algorithms, Systems and Applications at the 2nd International Conference on e-Science and Grid Computing. The paper uses 4 multimodal test functions, details of which can be found in an earlier technical report (also listed below in Technical Reports).

The software used for this research is available here

Population based representations in Ant Colony Optimisation

This research is similar to work done by Guntsch & Middendorf. The majority of ACO techniques store search history in a common pheromone mapping and the discrete solution information is discarded. Population based techniques maintain discrete solution information between generations in an attempt to leverage more information thereby improving search efficacy and efficiency. 

Evolutionary Computation Techniques in Ant Colony Optimisation

The field of Evolutionary Computation (Evolutionary Algorithms, Genetic Programming & Evolutionary Strategies) contains many techniques useful in increasing search efficacy and efficiency of algorithms applied to optimisation problems. The hypothesis is that these techniques may also prove useful when applied to ACO. The difficulty is that most EC techniques cannot be directly applied to the canonical ACO algorithms in their current form since EC techniques are usually applied to population based strategies (such as a genetic algorithm) rather than construction based heuristic algorithms. 

Ant Colony Optimisation applied to Function Optimisation

Most ACO algorithms are applied to Combinatorial Optimisation Problems such as: Shortest Path, Travelling Salesman, etc. Function Optimisation problems are interesting because canonical ACO algorithms are usually associated with these discrete optimisation problems rather than continuous optimisation problems. The application of ACO to Continuous Optimisation problems serves to increase the applicability of the ACO paradigm to a wider range of optimisation.

Back to homepage

Past Research (more than 3 years old)

Back to homepage

Technical Reports

Niching for Ant Colony Optimisation (Technical report) (August 2006)

The ability of ACO algorithms to solve more difficult artificial problem instances is an important result for researchers, as these are often more akin to industrial (real-world) applications. While most ACO algorithms are able to find a single (or few) optimal, or near-optimal, solution to difficult (NP-hard) problems, these solutions are often located in the same neighbourhood of solution space. A small change to the problem can have a large impact on a specific solution by decreasing its quality, or worse still, by rendering it infeasible.

Over the past 20 years, niching methods, such as fitness sharing and crowding, have been implemented with success in the field of Evolutionary Computation (EC). Such niching methods try to simultaneously locate and maintain multiple optima to increase search robustness - typically in multi-modal function optimization.

In this report it is shown that a niching technique applied to an ACO algorithm permits the niching ACO algorithm to simultaneously locate and maintain multiple areas of interest in the search space, with minimal impact on the quality of solutions found.

Ant Colony Optimisation: From Biological Inspiration to an Algorithmic Framework (Technical report) (April 2006)

The Ant Colony Optimisation algorithm framework (ACO) is a new algorithmic framework which is inspired by the foraging patterns of biological ants. Any ACO algorithm (of which there are many) serves to optimise some problem instance by generating a series of solutions to the problem and using the utility (goodness) of these solutions to influence future solution construction.

This report outlines the biological inspiration behind the development of the first ant-inspired algorithms. The report then identifies two of these ant-inspired algorithms, their relation to the biological models and offers a contrast and comparison between them. Finally the report describes and analyses the ACO meta-heuristic framework to which a subset of ant-inspired algorithms belong.

The Current State of Ant Colony Optimisation Applied to Dynamic Problems (Technical report) (April 2006)

In recent years Ant Colony Optimisation (ACO) algorithms have been applied to more challenging and complex problem domains, one such domain being dynamic problems. The majority of dynamic problems addressed using biologically inspired computation techniques are from the general field of Operations Research and are usually modifications of popular static problem domains such as the travelling salesman problem and the vehicle routing problem. This document aims to summarise the current state of the field with regard to ACO algorithms and their application to dynamic problems. 

Back to homepage

Industrial Application

Even though Ant Colony Optimisation (ACO) may seem obscure there is a lot of potential for industrial application of this research. The main areas to date which have attracted attention from the field have been scheduling and operations research applications which include:

For the applications listed above ACO is usually applied as part of a hybrid approach which includes the use of other algorithms. In this way ACO can be thought of as a 'speed-up' for applications where standard approaches prove impractical due to the high cost of computation.

Back to homepage

Other Material

Back to homepage

Back to homepage