A Memetic Algorithm with self-adaptive local search: TSP as a case study

TLDR

The paper proposes a hybrid Memetic Algorithm that combines a Genetic Algorithm with a self‑adaptive Monte Carlo stage for solving the Traveling Salesman Problem. The algorithm couples a Genetic Algorithm with a self‑adaptive Monte Carlo stage that functions as a local search when the population is diverse and as a diversification operator when the population converges, with the GA guiding long‑term optimization. Preliminary experiments show statistically significant improvements on TSP instances, and the method also performs well on a protein‑folding problem. Paper Category: Genetic Scheduling and TSP.

Abstract

In this paper we introduce a promising hybridization scheme for a Memetic Algorithm (MA). Our MA is composed of two optimization processes, a Genetic Algorithm and a Monte Carlo method (MC). In contrast with other GA-Monte Carlo hybridized memetic algorithms, in our work the MC stage serves two purposes: • when the population is diverse it acts like a local search procedure and • when the population converges its goal is to diversify the search. To achieve this, the MC is self-adaptive based on observations from the underlying GA behavior; the GA controls the long-term optimization process. We present preliminary, yet statistically significant, results on the application of this approach to the TSP problem. We also comment it successful application to a molecular conformational problem: Protein Folding. Paper Category: Genetic Scheduling and TSP