An investigation of performance on Two Phase Local Search and Multi-Objective Ant Colony Optimization

School of Science and Technology 科技學院
Computing Programmes 電腦學系

An investigation of performance on Two Phase Local Search and Multi-Objective Ant Colony Optimization

LEUNG Chun Wa


Programme	Bachelor of Computing with Honours in Internet Technology
Supervisor	Dr. Vanessa Ng
Areas	Algorithms
Year of Completion	2017
Award Received	Champion, IEEE Computational Intelligence Chapter FYP Competition 2017

Objectives

Three objectives were carried out to come up with the project. First, introduce hybrid paradigms of Two Phase local search (TPLS) and multi-objective ant colony optimization (MOACO). Second, implement the Iterated Local Search – Variable Neighborhood Search (ILS-VNS) as the first phase in TPLS; and then, to investigate the performance of proposed algorithm with different settings of local search choice and population size. To specify, comparison of choice of TPLS using with WLS and PLS is also considered. A statistical testing will be carried out to evaluate the significance of the result. More importantly, further analyze on population size effect on solution archive size and performance.

Background and Methodology

Accord to Dubois (Dubois-Lacoste et al., 2013), noted there is two main approaches of optimization, scalarization-based method and dominance-based method are the ways the algorithm finding solutions.

Scalarization-based method

Scalarization-based method trying to solve multi-objective optimization problem by combining objective functions into single objective functions. And solve the problems by using single objective optimization approach. This method is easy to implement and usually produce a very good Pareto Front. But in the same time, the number of solutions return may be small.

Dominance-based method

Essentially, algorithms in this paradigm accepts solutions based on the comparison of Pareto dominance relations. For instance, PLS updates solutions when the newly explored solution is not weakly dominating the current solution.

Furthermore, he described these two approaches can come into a hybridization. The hybridization can be done with either one or both paradigm instances described above. Two categories of hybridization techniques were presented.

Sequential hybridization

Sequential hybridization switching algorithms in sequence without alternating. TPLS is one of the example using this approach. When the first phase local search returns a set of good quality solutions, the output is immediately used as the initial solution to the second phase local search.

Iterative hybridization

Iterative hybridization alternating algorithms in an iterative way. For instance, MOACO is inherently an iterative hybridized algorithm. As an iterative improvement algorithm, it was usually cooperated with a local search algorithm to improve solutions after ants' solution construction phase every iteration.

Figure 1: TPLS + PLS + MOACO Framework

Figure 2: MOACO + TPLS

Conclusion and Future Development

In this project, MOACO were further enhanced with a state-of-art approach. A hybridization of Two Phase Local Search and Multi-Objective Ant Colony Optimization was introduced. To improve the initial solution for MOACO, Two Phase Local Search were proposed to combine with MOACO. To aim at a higher quality of supported efficient solution set as the initial solution, Iterated Local Search – Variable Neighborhood Search is proposed. A series of experimental testing examined the performance of algorithms for Bi-objective Traveling Salesman Problem. Several performance indicator and statistical testing were adopted to investigate and verify the significance of the result. The result had shown the proposed algorithm TPLS + PLS + MOACO outperformed the conventional algorithm. More importantly, the population size setting was also compared to test the best parameter. The result was shown S_size=100 perform the best averagely on TPLS + PLS + MOACO.

In future, the proposed algorithm can be investigated more concisely with its intrinsic components. For instance, testing the algorithmic components of PLS, as the author did in the paper (Dubois-Lacoste, 2011). On the other hand, the restarting strategy in the first phase of TPLS could be improved rather than restart from a random solution. Also, stop condition for ILS-VNS could be analyzed in detail to generate a better solution within a shorter time.