A shared-memory ACO plus GA hybrid for combinatorial optimization

Abstract

A novel hybrid algorithm combining the search capabilities of evolutionary genetic and artificial ant colony optimization algorithms through a common library of partial permutations is introduced. The two algorithms work independently in parallel to construct two different populations of individuals representing potential solutions. A shared memory containing variable size and partially incomplete permutations from above-average individuals of the two populations is used as the medium for information exchange between the two algorithms. The aim is to support the solution construction procedures of the two algorithms by knowledge incorporation through a shared external memory that contains experienced based knowledge gained through two different solution methods. Constructed solutions are also used to update the memory. The proposed approach is used for the solution of TSP and QAP for which the obtained results demonstrate that both the speed and solution quality are improved compared to the two individual component algorithms.