Rnfinity - Combining Genetic Algorithm with Local Search Method in...

Abstract

This research focuses on evolutionary algorithms, particularly genetic and memetic algorithms. The study examines a graph theory problem related to finding a minimal Hamiltonian cycle in a complete undirected graph (Travelling Salesman Problem-TSP). The paper presents implementations of two approximate algorithms for solving this problem: genetic and memetic. The main objective is to determine the influence of the local search method versus the genetic crossover operator on the quality of solutions generated by the memetic algorithm for the same input data. Results show that as the number of possible Hamiltonian cycles increases, the memetic algorithm finds better solutions. The execution time of both algorithms is comparable. Additionally, the number of solutions that mutated during the genetic algorithm's execution exceeds 50% of all solutions generated by the crossover operator, while in the memetic algorithm, this number does not exceed 10%.

Key Questions

1. What is a genetic algorithm?

A genetic algorithm is a type of evolutionary algorithm that uses techniques inspired by natural selection to solve optimization problems. It works by evolving a population of potential solutions through processes like selection, crossover, and mutation[1].

2. How does a memetic algorithm differ from a genetic algorithm?

A memetic algorithm is an extension of genetic algorithms that incorporates local search methods. In this study, the memetic algorithm combines the genetic algorithm's evolutionary approach with a local search technique to improve solution quality[1].

3. What is the Travelling Salesman Problem (TSP)?

The Travelling Salesman Problem is a classic optimization problem in graph theory. It involves finding the shortest possible route that visits each city exactly once and returns to the starting city in a complete undirected graph[2].

4. How do genetic and memetic algorithms perform in solving the TSP?

The study shows that both algorithms can find good approximate solutions for the TSP. However, as the number of possible Hamiltonian cycles increases, the memetic algorithm tends to find better solutions than the genetic algorithm, while maintaining comparable execution times.

5. What are the key findings regarding mutation in genetic and memetic algorithms?

In the genetic algorithm, over 50% of solutions generated by the crossover operator undergo mutation. In contrast, the memetic algorithm sees less than 10% of solutions mutate, indicating that it maintains a more diverse population of solutions.

Summary Video Not Available

Review 0

ARTICLE USAGE

Article usage: Dec-2024 to Jun-2025

Show by month	Manuscript	Video Summary
2025 June	19	19
2025 May	25	25
2025 April	14	14
2025 March	19	19
2025 February	23	23
2025 January	9	9
2024 December	13	13
Total	122	122

Show by month	Manuscript	Video Summary
2025 June	19	19
2025 May	25	25
2025 April	14	14
2025 March	19	19
2025 February	23	23
2025 January	9	9
2024 December	13	13
Total	122	122

Combining Genetic Algorithm with Local Search Method in Solving Optimization Problems

Added on