Biomedical
Combining Genetic Algorithm with Local Search Method in Solving Optimization Problems
Velin Kralev,
Radoslava Kraleva
Peer Reviewed
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%.
