Optimized Crossover JumpX in Genetic Algorithm for General Routing Problems: A Crossover Survey and Enhancement

Optimized Crossover JumpX in Genetic Algorithm for General Routing Problems: A Crossover Survey and Enhancement

Hicham El Hassani (ENSEM Casablanca, Morocco), Said Benkachcha (ENSEM Casablanca, Morocco) and Jamal Benhra (ENSEM Casablanca, Morocco)
Copyright: © 2018 |Pages: 26
DOI: 10.4018/978-1-5225-4151-6.ch009

Abstract

Inspired by nature, genetic algorithms (GA) are among the greatest meta-heuristics optimization methods that have proved their effectiveness to conventional NP-hard problems, especially the traveling salesman problem (TSP) which is one of the most studied Supply chain management problems. This paper proposes a new crossover operator called Jump Crossover (JMPX) for solving the travelling salesmen problem using a genetic algorithm (GA) for near-optimal solutions, to conclude on its efficiency compared to solutions quality given by other conventional operators to the same problem, namely, Partially matched crossover (PMX), Edge recombination Crossover (ERX) and r-opt heuristic with consideration of computational overload. We adopt the path representation technique for our chromosome which is the most direct representation and a low mutation rate to isolate the search space exploration ability of each crossover. The experimental results show that in most cases JMPX can remarkably improve the solution quality of the GA compared to the two existing classic crossover approaches and the r-opt heuristic.
Chapter Preview
Top

Introduction

NP-hard problems generally require exponential time depending on the problem size to find exact optimal solutions. This is why many metaheuristics are used to obtain approximate solutions to problems of such difficulty.To legitimate using metaheuristics to solve an optimization problem, a complexity analysis of a problem can be driven to give an indication on the hardness of the problem. It is also important to know the size of input instances the algorithm is supposed to solve. Even if a problem is NP-hard, small instances or even large-size instances with a specific structure may be solved in optimality by exact approach. Moreover, the required search time to solve a given problem is an important issue in the selection of an optimization algorithm. It is unwise to use metaheuristics to solve problems where efficient exact algorithms are available. For instance, one should not use a metaheuristic to find a minimum spanning tree or a shortest path in a graph. Known polynomial-time exact algorithms exist for those problems.

There are several powerful optimization techniques that are inspired by nature. Evolutionary algorithms (EAs) have been developed based on the principles of natural genetics to perform research and optimization in complex spaces. The most important components of the Evolutionary algorithms family are: Genetic Algorithms, Genetic Programming and Evolutionary Strategies.

Various other bio-inspired research and optimization techniqueswhich was created, developed, hybridized, enhanced and used in numerous fields of optimization, such as Particle Swarm Optimization (PSO) in (Shweta & Kamal, 2014; Soleimani & Kannan, 2015; Wang, Ma, Xu, Liu, & Wang, 2015), Ant Colony Optimization (ACO) in (Ahmed Hamza, Ahmad Taher, & Aboul Ella, 2014), A.hamza developed a New Heuristic Function, Differential Evolution (DE) in (Zhu, Fang, Tang, Zhang, & Du, 2012), Artificial Bee Colony (ABC) in (Rahul, Senthilnath, Omkar, & Narendra, 2016), Cuckoo Search and Chaotic Flower Pollination optimization algorithm in(Binh, Hanh, Van Quan, & Dey, 2016),(Dey, Samanta, Yang, Das, & Chaudhuri, 2013), (Ashour et al., 2015), Firefly algorithmin (Dey, Samanta, et al., 2014),Neural Networks in (Hore et al., 2017), and Simulated Annealing in (Bouttier et al., 2017), are also classified among the metaheuristics techniques. In (Reza, 2016), a new Meta heuristic algorithm inspired of the biologic nephron performance for optimization of objective functions in Np-hard problems is introduced (NAO).In (Dey, Chakraborty, & Samanta, 2014) the author is using Particle Swarm Optimization and Genetic Algorithm based techniques and offers MATLAB result sets, tables, flow charts and illustrations to exemplify the complicated concepts discussed in the text.

Over the past years, hybridization of metaheuristics has become an important issue, to the point that all the different metaheuristics that we have cited, and other techniques, are now seen as starting points for the development of new optimization algorithms. In (A. Meryem & Salim, 2016), authors present a new approach based on the cooperation of many variants of metaheuristics in order to solve the large existing benchmark instances of the capacitated vehicle routing problem (CVRP). (Amal Mahmoud & Sawsan, 2015) propose a new variation of ABC that uses multi-parent crossover named multi parent crossover operator artificial bee colony (MPCO-ABC). In the proposed technique the crossover operator is used to generate three new parents based on memory.

Complete Chapter List

Search this Book:
Reset