Modified genetic algorithm with novel crossover and mutation operator for travelling salesman proble

Abstract

Keywords: Crossover Operator; Genetic Algorithm; Muation Operator; Python Coding; Travelling Salesman Problem

Introduction

Almost The basic concept of genetic algorithms (GA) is a search-based optimisation approach and is introduced by Holland [1]. The ‘survival of the fittest’ premise is the foundation for GA, which are metaheuristics relies on natural selection and Genetics principles. GA are often utilised to produce high quality and superior solutions for search and optimisation challenges. In other words, GA tend to find and offer near-optimal solutions to scenarios that could require a lot of time. GA are frequently employed in numerous

disciplines, comprises of soft computing, machine learning, and operations research. It can optimise for continuous or discrete variables without needing to know the derivatives. Additionally, it works with numerically generated data, experimental data, or analytical data and delivers a set of optimal variables rather than simply one solution. GA processes sustain a population of individuals and are iterative in character. In essence, GAs can be described as composed of two primary phases: the first is “Selection” for producing the next generation, and the second is “Manipulation,”

*Corresponding author. *E-mail address: vnm@igntu.ac.in; vishnunarayanmishra@gmail.com This paper was recommended for publication in revised form by Regional Editor Ahmet Selim Dalkilic Published by Yıldız Technical University Press, İstanbul, Turkey Copyright 2021, Yıldız Technical University. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

which manipulates the selected individuals to produce the next generation using various techniques, including crossover and mutation. Each iteration in GA is referred to as “a generation,” and a population of new candidate solutions is created utilising various biologically inspired operators including mutation, crossover, and selection. In GA, each individual is represented by a string known as chromosome and may also be regarded as a problem-solving strategy. These strings comprise characters known as genes, which contain certain values known as alleles. GAs is appropriate candidate to tackle the constrained, unconstrained and combinatorial problem. Using genetic operations like selection, fitness, crossover, and mutation processes, GA seeks for the optimal results. • Fitness: The fitness value quantifies the similarity between two individuals and is a favourable utility metric that is determined for every individual in the population. • Selection: Each member of the population receives several copies, which are used up in the mating pool to create an entirely novel population. Therefore, the likelihood that an individual will produce additional copies in the mating pool increases as fitness value increases. • Crossover: Recombination of individuals generates new individuals known as offspring or children. Onepoint and two-point crossover are popular recombination strategies. • Mutation: Maintaining diversity in the population can be done through mutation. Each individual is mutated with a minute or extremely low chance, such as less than 1.0. The procedures below can be used to define an uncomplicated genetic algorithm and the flow chart for illustrating various steps is shown in Figure 1. The 2-diemnsional array encompassing population size and chromosome size defined the population. Here, population initialization can be done by utilizing two methods namely random and heuristic initialization.The fitness function ought to be quick enough to calculate. It must quantify the degree to which a given solution is fit or the degree to which fit people can be created from the provided solution. When a GA run ends, a lot depends on the termination condition of the GA. In general, we want a termination condition that, at the end of the run, puts the outcome very near to the bestone. The following are the termination criteria’s for the GA• when X iterations have passed with no population improvement. • when the number of generations is fixed. • when the value of the objective function reaches a specific, predetermined value. I. Using n chromosomes, create a starting generation. Here the population is initialized. II. Assess each chromosome’s fitness.

Proportionally pick n/2 parents of the present population. IV. Use the crossover operator to produce children by picking two parents at random. V. Employ mutation to vary findings a little bit. VI. Until all parents have been chosen and mated, repeat steps 4 and 5. VII. An entirely new population of chromosomes will replace the old one. VIII. Determine each chromosome’s level of fitness in novel population. IX. Stop when the number of generations reaches a predetermined maximum; otherwise, proceed to Step III. We have numerous representations in literature employing the GAs. Path, binary, adjacency,ordinal and matrixrepresentation are some significant representations and the summary of these representation with novel crossover operator is given in Table 1. Arqub et al. [13] employ the continuous GA to solve singular two-point boundary value problems. Arqub and Hammour [14] discussed a method for employing continuous GA for solving systems of second-order boundary value problems. In order to validate this method, a few test problems were created and solved. Hammour et al. [15] presented a GA approach for the modelling of dynamical III.

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

systems. For numerically approximating the solutions of Troesch’s and Bratu’s problems, Hammour et al. [16] introduce continuous GA. Recently, to approximate a class of Lebesgue integrable functions, Raiz et al. [17] introduced a novel sequence of linear positive operators. Schurer Beta bivariate operators were initially developed by Mishra et al. [18] in terms of generalisation exponential functions and their approximation characteristics. The Travelling Salesman Problem (TSP) is one of the most well-known combinatorial issues in optimising. The TSP is one of the most recent optimisation problems to have undergone extensive deliberation. It was initially formulated as an optimisation problem in 1930. In TSP, the objective is to determine probable tour such that a travelling salesman visits each city exactly once and back to the initial city in order to minimize the total cost devoted or total distance covered. Since there are n! various approaches to locate the tour for n cities, specifically for 11 cities, there are 39916 800 possible route to optimize the total cost. So, the complexity of finding the best route increases as the number of cities increases. Thus, TSP is a candidate of NP (NonPolynomial) hard combinatorial optimization problems. In existing literature, exact and metaheuristic algorithms are two approaches to tackle TSP as shown in table

1. In case of exact algorithms, following are major exact

algorithms in literature introduced to encounter with TSP; Dantzig et al. [19] introduced a methodology to solve the large-scale TSP. Later, Petberg [20] proposed a branch and cut method to get the optimal solution of symmetric TSP. A cutting plane approach is proposed by Fleischmann [21] in order to tackle the TSP in case of a road network. Thereafter, Petberg and Homg [22] proposed branch and cut method

to optimize symmetric TSP with 532 cities. On the other hand, various heuristic algorithms are also introduced in order to tackle the TSP. Initially, Brady [5] proposed a GA approach deal with TSP. Bhide et al. [23] proposed a Boolean approach with the help of neural network to deal with TSP. Dorigo and Gambardella [24] proposed an approach with the help of ant colony system to tackle the TSP. Knox [25] proposed the tabu search approach to solve the symmetric TSP. Later, Chiang and Russell [26] proposed simulated annealing algorithms to cope with vehicle routing problem. Thereafter, Focacci et al. [27] developed a hybrid exact method for TSP. A local search strategy was presented by Ibarki et al. [28] for addressing and arranging issues with extensive time window limitations. Larranaga et al. [11] reviewed the various methodologies used to resolve TSP by utilizing GA. Also, presented different crossover and mutation operators which are proposed to tackle the TSP with the GA. Thereafter, An amalgam GA was suggested by Nguyen et al. [29] to discover the TSP solution. Ghadle and Muley [30] proposed a modified version of GA encoded by using MATLAB to tackle the TSP. Kumar and Gupta [31] proposed a methodology to solve the TSP with fuzzy L-R parameters. Majumdar and Bhunia [32] modelled an asymmetric TSP in a way that the distance between each pair of cities travelled is denoted as an interval value instead of a precise value. Thereafter, Changdar et al. [33] modelled a multi-objective TSP with triangular fuzzy parameters and, proposed an effectual GA to tackle this modelled TSP. Maity et al. [34] proposed a modified GA to cope with constrained solid TSP in different settings including fuzzy and crisp. We suggest a novel crossover operator for the TSP along with its Python source code. We entailed a mutation operator in addition to the Python pseudo coding to improve the effectiveness of GA in calculating the shortest distance in the TSP. We additionally employ examples to demonstrate the proposed crossover and mutation operator at various stages. We combined our newly designed crossover and mutation operator with path representation because this is an obvious way to express a tour. This article is organized as follows; Section one is completely devoted to the basics of GA and the literature review of GA and TSP. The mathematical formulation of the TSP

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

is described in section two. Several types of representation involved in GA are described in section three. Major crossover operators for path representation are presented in section four. Novel crossover operator is illustrated in section five. On the other hand, the novel mutation operator is given in section six. Finally, the section seven is devoted to the conclusion of the article. Mathematical Formulation of TSP One way to represent the TSP is as an integer linear programming. The Dantzig-Fulkerson-Johnson (DFJ) formulation and the Miller-Tucker-Zemlin (MTZ) formulation are well-known formulations of TSP available in the literature (Dantzig [35] & Velednitsky [36]). In some circumstances, the MTZ formulation is still beneficial, although the DFJ formulation is stronger. Let n be the number of cities, cij be the cost (distance) form ith to jth city, and ui be the dummy variable. xij is a binary variable and defined as:

Different Types Of Representation

There have been a wide range of representations of a chromosome to solve TSP problem by employing GA. Binary, path, adjacency, ordinal and matrix representation are major representation forms available in literature. Binary Representation Each city in the n-cities TSP is represented in binary as a string of [log2n] bits, and an individual is represented as a string of n[log2n] bits. Example: In case of a 6-cities TSP, each city assigned by 3-bit string. The tour 2-1-3-6-5-4 depicted as by using Table 3. (001 000 010 011 100 101) Table 3. An illustration of a visit of six cities in binary i

The MTZ formulation of TSP is as follows: Path Representation The elementary representation of a tour in TSP can be done in a more appropriate way by using path representation. For a tour of n cities, if city i is the jth element of the list, city i is the jth city to be visited. Example:If n = 8. Then the tour is 4-2-3-1-7-5-8-6 is represented as a string (4 2 3 1 7 5 8 6).

Here, the last constraint, known as a subtour elimination constraint, assures that no appropriate subset Q can form a sub-tour, resulting in a single tour as the solution and not a union of smaller tours.

Ordinal Representation In ordinal representation, ith member in set is a integer between 1 to n - i + 1 and an ordered set consisting of various destinations act as guide also exists. Example: Let n = 8 and O = (1 2 3 4 5 6 7 8) be a reference list, then the tour 1-5-3-2-8-4-7-6 is represented by T = (1 4 1 2 1 4 1 2 1) Matrix Representation In matrix representation, member ith row and jth column is 1 iff city i is visited before the city j Example: The matrix representation of tour 2-3-1-4 is

Crossover Operators For TSP In PATH Representatoion

Partially Mapped (PMX), Cycle (CX), Cycle (CX2) are predominantly used crossover operators of path representation in the current literature.

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

Partially Mapped (PMX) Partially Mapped Crossover operator (PMX) was introduced by Goldberg and Lingle [3] for path representation of chromosomes in path representation. In PMX, after choosing two random cut locations on the parents to produce offspring, one parent’s string is mapped onto the other parent’s string. Thereafter, a remaining bit are filled with the help of mapping with the constraint that no bit is repeated in the offspring. Example:Let us consider two parents P1 and P2 with two random cut points P1 = (1 2 | 3 4 5 6 | 7 8) P2 = (2 7 | 5 8 4 1 | 6 3) Then, the mapping segment between the cut points replicated with each other in order to build offspring, the mapping is 2 1,7 6,1 8. O1 = ( × × | 1 4 5 8 | × ×) O2 = (× × | 3 4 5 6 | × ×)

Cycle Crossover Operator (CX) Cycle crossover (CX) operator was first introduced by Oliver et al. [37]. Any bit in this operator is obtained via any of the parents to determine its position. Let P1 and P2 be two parent string to illustrate the operator P1 = (1 2 3 4 5 6 7 8) P2 = (2 4 6 8 7 5 3 1) Now, select 1st element of offspring from first element of either of P1 or P2. Here from two options (1or 2), we will choose 1. For last element of O1, we must consider 8, as if 1 is taken then it would not result as a legal tour. O1 = (1 × × × × × × 8) Similarly, for 2nd and 4th element, we have 2 and 4 respectively. O1 = (1 2 × 4 × × × 8) The relative positions of the elements selected up until this point are considered to form a tour. Think about the 3rd element of the O1. Any of the parents can be the source for this component. Let’s say we choose it to come from parent

2. This indicates that the second parent must also be picked

for the 5th, 6th, and 7th components of offspring because they make up another cycle. As a result, we discover the following offspring: O1 = (1 2 6 4 7 5 3 8) Cycle Crossover Operator (CX) 2 Hussain et al. [38] proposed cycle crossover operator 2 (CX2) for TSP to optimize distance travelled. Step 1. Let us consider two parents for mating. Choose the 1st bit of the 1st offspring using 2nd parent string. Step 2. The bit selected in Step 1 is present in the 1st parent, followed by the same similar location bit selected in the 2nd parent, which is present in the 1st parent, and the similar location bit selected in the 2nd parent, which is then selected for the first bit of the 2nd offspring. Step 3. The 1st parent will have the chosen bit from Step 3, and the 1st offspring would contain the following bit in the 2nd parent’s identical place. Step 4. Continue Steps 2 and 3 until the 1st bit of the 1st parent does not appear in the 2nd offspring, at which point the procedure may be stopped. Step 5. If any bits remain, they will be similar in the 1st parent and the 2nd offspring up to this point, and vice versa for both parents. Example: Let us consider two parent chromosomes for mating P1 = (3 4 8 2 7 1 6 5 ) P2 = (4 2 5 1 6 8 3 7) By employing above steps, the two offspring initiated are as follows: O1 = (4 8 6 2 5 3 1 7) O2 = ( 1 7 4 8 6 2 5 3)

Proposed Crossover Operator

In this section we will propose the Increasing partially mapped crossover operator (IPMX) and the python coding of the proposed operator is given in Figure 2. The proposed operator is defined by the following steps.

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

Table 4. Summary of mutation operator in GA Mutation Operator

Step 1. Select a pair of chromosome parents for mating. Step 2. Pick out two random cut points on each parent to construct two offspring. Step 3. First arrange the bits between two random cuts in the increasing order for each parent chromosome Step 4. Now these portions between cut points are mapped onto other parent strings. Step 5. Fill the remaining bits from the primary parent such that there is no dispute. Step 6. To fill the bits with conflict, use the notion of partial mapping. Example: Let us consider two parent chromosomes for mating with randomly two cut points marked by “|”. P1 = (1 2 | 3 4 5 6 | 7 8) P2 = (2 7 | 5 8 4 1 | 6 3) The two children O1 and O2 are constructed as follows: Initially arrange all bits of randomly selected segment in the increasing order. Then mapped the resulted strings between cut points onto other parents. O1 = (× × | 1 4 5 8 | × ×) O2 = (× × | 3 4 5 6 | × ×) Now, fill the bits from original parent which does not have any conflict. Here for O1, 2,7 are filled and for O2, 2,7 are filled. O1 = (× 2 | 1 4 5 8 | 7 ×) O2 = (2 7 | 3 4 5 6 | × ×) To fill the remaining bits, use the notion of partially mapping. The first × in first offspring O1 is 1 which comes from P1 but 1 is already present in O1. So, in P1 we check the element corresponding to 1 of P2, here 1 ↔ 6, first × is occupies by 6. Again, the second × in the O1 is 8 but 8 is already present in O1. So, in P1 we check the element corresponding to 8 of P2, here 8 ↔ 4, but 4 is present in O1, again check mapping 4 ↔ 5. But 5 is existing in O1, again check 5 ↔ 3, 3 occupies the second × of in P1 O1 = ( 6 2 | 1 4 5 8 | 7 3) O2 = (2 7 | 3 4 5 6 | 1 8) Similarly, we complete the second offspring O1.

Proposed Mutation Operator

GAs employ mutation to help the procedure evade local solutions and give the population newly developed, completely improbable instances. The summary of mutation

Figure 3. Python coding of proposed mutation operator. operators is presented in Table 4. In this section, we propose a novel mutation operator of path representation in GA. This operator is completely defined by a linear function and is mathematically defined as follows: Let xi be the bits in chromosome of n size L(xi)= xi + 1 ∀xi where xi represent bits in chromosome The python coding of the proposed operator is presented in Figure 3. Example: Let us consider p = (2 3 5 6 1 4 7 8) be a parent chromosome to emphasize the proposed mutation operator in a better way. By applying the Linear function of mutation operator, we get a child chromosome as C = (3 4 6 7 2 5 78 1)

Conclusion

Utilising the survival of the fittest principle, GA a form of evolution method to deal with optimisation issues. They have been effectively utilized in several types of optimization issues, including the TSP. In TSP, our main aim to locate a tour of every node in a weighted network and minimise the overall weight, we must solve the TSP. We have examined various methods of representations of a tour in TSP which are available in literature that could be employed in genetic algorithms attempting to solve the TSP. We also reviewed partially mapped (PMX), cycle (CX) and cycle crossover 2 (CX2) available in literature for path representation as it the any form of tour is originally represented as path. In this article, we proposed modified version of GA by introducing an increasing partially mapped crossover operator (IPMX) and a mutation operator to get optimize solution of a TSP. We also, provide python coding of our novel crossover and mutation operator for the better implementation of modified version of GA. GA and its modified versions are applicable in different types of optimization

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

problems other than TSP such as transportation problem, vehicle routing problem, neural networks, and so on.

Data Availability Statement

The authors confirm that the data that supports the findings of this study are available within the article. Raw data that support the finding of this study are available from the corresponding author, upon reasonable request.

Conflict Of Interest

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Ethics

There are no ethical issues with the publication of this manuscript.

Share and Cite