Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
We propose a new genetic algorithm with optimal recombination for the asymmetric instances of travelling salesman problem. The algorithm incorporates several new features that contribute to its effectiveness: (i) Optimal recombination problem is solved within crossover operator. (ii) A new mutation operator performs a random jump within 3-opt or 4-opt neighborhood. (iii) Greedy constructive heuristic of W.Zhang and 3-opt local search heuristic are used to generate the initial population. A computational experiment on TSPLIB instances shows that the proposed algorithm yields competitive results to other well-known memetic algorithms for asymmetric travelling salesman problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Perfect Edge-Transmitting Recombination of Permutations
Crossover is the process of recombining the genetic features of two parents. For many applications where crossover is applied to permutations, relevant genetic features are pairs of adjacent elements, also called edges i…
Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria
We consider the bicriteria asymmetric travelling salesman problem (bi-ATSP). Optimal solution to a multicriteria problem is usually supposed to be the Pareto set, which is rather wide in real-world problems. For the firs…
Analysis of Optimal Recombination in Genetic Algorithm for a Scheduling Problem with Setups
In this paper, we perform an experimental study of optimal recombination operator for makespan minimization problem on single machine with sequence-dependent setup times ($1|s_{vu}|C_{\max}$). The computational experimen…
SchedulingOptimal Recombination in Genetic Algorithms
This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent …
A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem
This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a state-of-the-art self-adaptive genetic algorithm. The Flying Sidekick Travelling Salesman Problem is a combi…