A comparison of differential evolution and a genetic algorithm applied to the longest path problem

Abstract: Genetic algorithms and differential evolution are two well-established types of generic algorithms that can be applied to a great numberof optimization problems. Both are subgroups of evolutionary algorithms that are inspired by nature, with many practical implementations in for instance research and the industry. In this paper the algorithms are applied to the NP-hard longest path problem with the purpose of comparing their perfomances. The basics of the algorithms are provided along with defining their most important components, chromosome, gene, crossover, mutationand selection. All of which are further described in detail how they were implemented for this paper. Additionally a specialized type ofthe differential evolution algorithm is brought up, namely discrete differential evolution, as this version was implemented for this paper. The results show that the differential evolution algorithm performssignificantly better than the genetic algorithm and the possible underlying causes to this are discussed, one major cause being that the differential evolution algorithm is more adapted to the specified problem, longest path problem. The conclusion is that discrete differential evolution perfoms considerably better than a generic genetic algorithmon this particular problem, but no further general assumptions can bemade regarding their perfomance for all or any other types of problems.