A hybrid algorithm combining genetic algorithm with ant colony algorithm for the minimum latency problem.

Ban Hà Bằng, Nguyễn Đức Nghĩa

Abstract


MinimumLatency Problem is a class of combinatorial optimization problems that have many practical applications. In the general case, the problem is proven to be NP-hard. Therefore, using a meta-heuristic algorithm is a suitable approach for solving this problem. In this paper, we propose a meta-heuristic algorithm which combines Ant Colony (ACO) and Genetic Algorithm (GA). In our algorithm, ACO generates a population for GA. Meanwhile, the genetic information of GA helps ants to create a better population in the next step. In addition, to maintain the diversity of population, our algorithm uses three types of the ants which have different characteristics. We evaluate the  algorithm on five benchmark data sets. The experimental results show that our algorithm gives a better solution than the state-of-the-art meta-heuristic algorithms on several instances of datasets.

Keywords


Minimum latency problem - MLP, meta-heuristic, ACO, GA.



DOI: https://doi.org/10.15625/1813-9663/29/3/2779

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology