Population-Based Ant Colony Optimisation for Multi-objective Function Optimisation
Ant inspired algorithms have recently gained popularity for use in multi-objective problem domains. The Population-based ACO, which uses a population of solutions as well as the traditional pheromone matrix, has been demonstrated as an effective problem s
- PDF / 505,598 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 11 Downloads / 246 Views
Abstract. Ant inspired algorithms have recently gained popularity for use in multi-objective problem domains. The Population-based ACO, which uses a population of solutions as well as the traditional pheromone matrix, has been demonstrated as an effective problem solving strategy for solving combinatorial multi-objective optimisation problems, although this algorithm has yet to be applied to multi-objective function optimisation problems. This paper tests the suitability of a Populationbased ACO algorithm for the multi-objective function optimisation problem. Results are given for a suite of problems of varying complexity.
1
Introduction
Ant Colony Optimisation (ACO) [10, 13], an optimisation methodology based on the foraging behaviour of Argentine ants, has been shown to be useful in the location of optimal or near-optimal solutions to optimisation problems. The first applications of ACO algorithms were to combinatorial optimisation problems such as the Travelling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP), although in recent years the paradigm has been applied to a much wider range of problem domains. A problem domain that remains relatively unexplored by ACO though is Multi-objective Function Optimisation (MOFO). Multiple Objective Optimisation (MOO) is concerned with finding multiple ‘trade-off’ solutions in order to optimise many (in most cases conflicting or orthogonal) objectives. MOO problems are found frequently in real-world applications and a commonly cited example is designing an automobile, where a designer may be attempting to simultaneously decrease cost and increase safety and comfort. In this example it is fairly clear that the designer must be willing to make trade-offs between all of these objectives because they are non-complimentary. For all MOO problems there is a set of optimal trade-off solutions which are referred to as the Pareto set, after the economist Vilfredo Pareto. To be classified as Pareto optimal a solution must not be worse then any other valid solution in all objectives. A Pareto optimal solution cannot increase its quality in any objective without simultaneously decreasing its quality in another objective. M. Randall, H.A. Abbass, and J. Wiles (Eds.): ACAL 2007, LNAI 4828, pp. 232–244, 2007. c Springer-Verlag Berlin Heidelberg 2007
Population-Based ACO for Multi-objective Function Optimisation
233
This study is concerned with the evaluation of a new Population-based ACO algorithm: Population-based ACO for Multi-objective Function Optimisation (PACO-MOFO). The PACO-MOFO algorithm is an extension of previously published work which includes the application of two novel Niching PACO algorithms to a suite of Single-objective Function Optimisation Problems [2] and an improvement of an existing PACO algorithm with a crowding replacement operation for the Multi-objective Travelling Salesman Problem (CPACO) [3]. The PACO-MOFO uses a similar approach to those of the previous works which is primarily the use of niching techniques such as crowding [9, 27] and fitness sha
Data Loading...
