D7ZvSWFk

1Research Article
2Genetic Algorithm for Traveling Salesman Problem with
3Modified Cycle Crossover Operator
4Abid Hussain,1 Yousaf Shad Muhammad,1 M. Nauman Sajid,2
5Ijaz Hussain,1 Alaa Mohamd Shoukry,3,4 and Showkat Gani5
61Department of Statistics, Quaid-i-Azam University, Islamabad, Pakistan
72Department of Computer Science, Foundation University, Islamabad, Pakistan
83Arriyadh Community College, King Saud University, Riyadh, Saudi Arabia
94KSAWorkers University, El Mansoura, Egypt
105College of Business Administration, King Saud University, Muzahimiyah, Saudi Arabia
11Correspondence should be addressed to Yousaf Shad Muhammad; yousuf@qau.edu.pk
12Received 1 June 2017; Revised 17 July 2017; Accepted 7 August 2017; Published 25 October 2017
13Academic Editor: Silvia Conforto
14Copyright © 2017 Abid Hussain et al. This is an open access article distributed under the Creative Commons Attribution License,
15which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
16Genetic algorithms are evolutionary techniques used for optimization purposes according to survival of the fittest idea. These
17methods do not ensure optimal solutions; however, they give good approximation usually in time.The genetic algorithms are useful
18for NP-hard problems, especially the traveling salesman problem.The genetic algorithm depends on selection criteria, crossover,
19and mutation operators. To tackle the traveling salesman problem using genetic algorithms, there are various representations such
20as binary, path, adjacency, ordinal, and matrix representations. In this article, we propose a new crossover operator for traveling
21salesman problem to minimize the total distance. This approach has been linked with path representation, which is the most natural
22way to represent a legal tour. Computational results are also reported with some traditional path representation methods like
23partially mapped and order crossovers along with new cycle crossover operator for some benchmark TSPLIB instances and found
24improvements.
251. Introduction
26Genetic algorithms (GAs) are derivative-free stochastic
27approach based on biological evolutionary processes proposed
28by Holland [1]. In nature, the most suitable individuals
29are likely to survive and mate; therefore, the next generation
30should be healthier and fitter than previous one. A lot
31of work and applications have been done about GAs in
32a frequently cited book by Golberg [2]. GAs work with
33population of chromosomes that are represented by some
34underlying parameters set codes.
35The traveling salesman problem (TSP) is one of the
36most famous benchmarks, significant, historic, and very hard
37combinatorial optimization problem. TSP was documented
38by Euler in 1759, whose interest was in solving the knight’s
39tour problem [3]. It is the fundamental problem in the
40fields of computer science, engineering, operations research,
41discrete mathematics, graph theory, and so forth. TSP can be
42described as the minimization of the total distance traveled
43by touring all cities exactly once and return to depot city.The
44traveling salesman problems (TSPs) are classified into two
45groups on the basis of the structure of the distance matrix as
46symmetric and asymmetric.The TSP is symmetric if 𝑐𝑖𝑗 = 𝑐𝑗𝑖,
47∀𝑖, 𝑗, where 𝑖 and 𝑗 represent the rowand columnof a distance
48(cost)matrix, respectively, otherwise asymmetric. For 𝑛 cities,
49there are (𝑛 − 1)! possible ways to find the tour after fixing
50the starting city for asymmetric and its half for symmetric
51TSP. If we have only 10 cities, then there are 362,880 and
52181,440ways for asymmetric and symmetric TSP, respectively.
53This is the reason to say TSP is NP-hard problem. TSP has
54many applications such as variety of routing and scheduling
55problems, computer wiring, and movement of people, X-ray
56Hindawi
57Computational Intelligence and Neuroscience
58Volume 2017, Article ID 7430125, 7 pages
59https://doi.org/10.1155/2017/7430125
602 Computational Intelligence and Neuroscience
61crystallography [4], and automatic drilling of printed circuit
62boards and threading of scan cells in a testable Very-Large-
63Scale-Integrated (VLSI) circuits [5].
64Over the last three decades, TSP received considerable
65attention and various approaches are proposed to solve the
66problem, such as branch and bound [6], cutting planes [7],
672-opt [8], particle swarm [9], simulated annealing [10], ant
68colony [11, 12], neural network [13], tabu search [14], and
69genetic algorithms [3, 15–17]. Some of these methods are
70exact,while others are heuristic algorithms.Acomprehensive
71study about GAs approaches are successfully applied to the
72TSP [18]. A survey of GAs approaches for TSP was presented
73by Potvin [17]. A new sequential constructive crossover
74generates high quality solution to the TSP by Ahmed [19].
75A new genetic algorithm for asymmetric TSP is proposed
76by Nagata and Soler [20]. Three new variations for order
77crossover are presented with improvements by Deep and
78Adane [21]. Ghadle and Muley presented modified one’s
79algorithm with MATLAB programming to solve TSP [22].
80Piwonska associated a profit based genetic algorithm with
81TSP and obtained good results to be tested on networks
82of cities in some voivodeships of Poland [23]. Kumar et
83al. presented the comparative analysis of different crossover
84operators for TSP and showed partially mapped crossover
85gives shortest path [24]. A simple and pure genetic algorithm
86can be defined in the following steps.
87Step 1. Create an initial population of P chromosomes.
88Step 2. Evaluate the fitness of each chromosome.
89Step 3. Choose P/2 parents from the current population via
90proportional selection.
91Step 4. Randomly select two parents to create offspring using
92crossover operator.
93Step 5. Apply mutation operators for minor changes in the
94results.
95Step 6. Repeat Steps 4 and 5 until all parents are selected and
96mated.
97Step 7. Replace old population of chromosomes with new
98one.
99Step 8. Evaluate the fitness of each chromosome in the new
100population.
101Step 9. Terminate if the number of generations meets some
102upper bound; otherwise go to Step 3.
103The selection criteria, crossover, and mutation are major
104operators, but crossover plays a vital role in GAs. A lot of
105crossover operators have been proposed in literature and
106all have their significant importance. In this article, we also
107proposed a new crossover operator for TSP which is moved
108within two selected parents as previous cycle crossover operator.
109In Section 2, we present crossover operators for TSP and
110proposed a new crossover operator for path representation in
111Table 1: Summary of crossover operators for TSP.
112Representation Crossover operators Proposed year
113Binary Classical + repair operator 1991
114Path
115Partially mapped crossover 1985
116Order crossover 1985
117Cycle crossover 1987
118Heuristic crossover 1987
119Order based crossover 1991
120Position based crossover 1991
121Adjacency
122Alternative edge crossover 1985
123Heuristic crossover 1 1985
124Heuristic crossover 2 1989
125Heuristic crossover 3 1987
126Ordinal Classical operators 1985
127Matrix Intersection crossover 1987
128Union crossover 1987
129Section 3; computational experiments and discussion are in
130Section 4 and conclusion is in Section 5.
1312. Crossover Operators for TSP
132In literature, there are many representations to solve the TSP
133using the GAs. Among these binary, path, adjacency, ordinal,
134and matrix representations are important. The further types
135of these representations are given in Table 1. We are limiting
136our self only with the path representation which is most
137natural and legal way to represent a tour and skip the others
138representations.
1392.1. Path Representation. The most natural way to present
140a legal tour is probably by using path representation. For
141example, a tour 1 → 4 → 8 → 2 → 5 → 3 → 6 → 7
142can be represented simply as (1 4 8 2 5 3 6 7).
143Since the TSPs in combinatorial with the path representation
144and the classical crossover operators such as onepoint,
145two-point, and uniform crossovers are not suitable,
146we choose only partially mapped, order, and cycle crossover
147operators from path representation which are mostly used in
148literature and also we can compare our proposed crossover
149operator with these operators.
1502.1.1. Partially Mapped Crossover Operator. The partially
151mapped crossover (PMX) was proposed by Goldberg and
152Lingle [25]. After choosing two randomcut points on parents
153to build offspring, the portion between cut points, one
154parent’s string is mapped onto the other parent’s string
155and the remaining information is exchanged. Consider, for
156example, the two parents tours with randomly one cut point
157between 3rd and 4th bits and other cut point between 6th and
1587th bits are as follows (the two cut points marked with “|”):
159𝑃1 = (3 4 8 | 2 7 1 | 6 5) ,
160𝑃2 = (4 2 5 | 1 6 8 | 3 7) .
161(1)
162Computational Intelligence and Neuroscience 3
163The mapping sections are between the cut points. In this
164example, the mapping systems are2 ↔ 1,7 ↔ 6, and1 ↔ 8.
165Now two mapping sections are copied with each other to
166make offspring as follows:
167𝑂1=(× × ×| 1 6 8 | × ×) ,
168𝑂2=(× × ×| 2 7 1 | × ×) .
169(2)
170Then we can fill further bits (from the original parents),
171for thosewhich have no conflict as follows:
172𝑂1 = (3 4 × | 1 6 8 | × 5) ,
173𝑂2 = (4 × 5 | 2 7 1 | 3 ×) .
174(3)
175Hence, the first × in the first offspring is 8 which comes
176fromfirst parent but 8 is already in this offspring, so we check
177mapping 1 ↔ 8 and see again 1 existing in this offspring,
178again check mapping2 ↔ 1, so 2 occupies atfirst ×. Similarly,
179the second × in first offspring is 6 which comes from first
180parent but 6 exists in this offspring; we checkmapping7 ↔ 6
181as well, so 7 occupies at second ×. Thus the offspring 1 is
182𝑂1 = (3 4 2 | 1 6 8 | 7 5) . (4)
183Analogously, we complete second offspring as well:
184𝑂2 = (4 8 5 | 2 7 1 | 3 6) . (5)
1852.1.2. Order Crossover Operator. The order crossover (OX)
186was proposed by Davis [26]. It builds offspring by choosing
187a subtour of a parent and preserving the relative order of bits
188of the other parent. Consider, for example, the two parents
189tours are as follows (with randomly two cut points marked
190by “|”):
191𝑃1 = (3 4 8 | 2 7 1 | 6 5) ,
192𝑃2 = (4 2 5 | 1 6 8 | 3 7) .
193(6)
194Theoffspring are produced in the followingway. First, the bits
195are copied down between the cuts with similar way into the
196offspring, which gives
197𝑂1=(× × ×| 2 7 1 | × ×) ,
198𝑂2=(× × ×| 1 6 8 | × ×) .
199(7)
200After this, starting from the second cut point of one parent,
201the bits from the other parent are copied in the same order
202omitting existing bits.The sequence of the bits in the second
203parent from the second cut point is “3 → 7 → 4 → 2 →
2045 → 1 → 6 → 8.” After removal of bits 2, 7, and 1, which are
205already in the first offspring, the new sequence is “3 → 4 →
2065 → 6 → 8.”This sequence is placed in the first offspring
207starting from the second cut point:
208𝑂1 = (5 6 8 | 2 7 1 | 3 4) . (8)
209Analogously, we complete second offspring as well:
210𝑂2 = (4 2 7 | 1 6 8 | 5 3) . (9)
2112.1.3. Cycle Crossover Operator. The cycle crossover (CX)
212operator was first proposed by Oliver et al. [27]. Using this
213technique to create offspring in such a way that each bit with
214its position comes from one of the parents. For example,
215consider the tours of two parents:
216𝑃1 = (1 2 3 4 5 6 7 8) ,
217𝑃2 = (8 5 2 1 3 6 4 7) .
218(10)
219Now it is up to us howwe choose the first bit for the offspring
220to be either from the first or from the second parent. In our
221example, the first bit of the offspring has to be 1 or 8. Let us
222choose it be 1:
223𝑂1 = (1 × × × × × × ×) . (11)
224Now every bit in the offspring should be taken from one of
225its parents with the same position, it means that further we
226do not have any choice, so the next bit to be considered must
227be bit 8, as the bit from the second parent is just below the
228selected bit 1. In first parent this bit is at 8th position; thus
229𝑂1 = (1 × × × × × × 8) . (12)
230This turnout implies bit 7, which is the bit of second parent
231just below the selected bit at 7th position in first parent.Thus
232𝑂1 = (1 × × × × × 7 8) . (13)
233Next, this forced us to put 4 at 4th position as
234𝑂1 = (1 × × 4 × × 7 8) . (14)
235After this, 1 comes which is already in the list; thus we have
236completed a cycle and filling the remaining blank positions
237with the bits of those positions which are in second parent:
238𝑂1 = (1 5 2 4 3 6 7 8) . (15)
239Similarly the second offspring is
240𝑂2 = (8 2 3 1 5 6 4 7) . (16)
241But there is a drawback that sometimes this technique
242produces same offspring, for example, the following two
243parents:
244𝑃1 = (3 4 8 2 7 1 6 5) ,
245𝑃2 = (4 2 5 1 6 8 3 7) .
246(17)
247After applying CX technique, the resultant offspring are as
248follows:
249𝑂1 = (3 4 8 2 7 1 6 5) ,
250𝑂2 = (4 2 5 1 6 8 3 7) ,
251(18)
252which are the exactly the same as their parents.
2534 Computational Intelligence and Neuroscience
2543. Proposed Crossover Operators
255We are going to propose a new crossover operator which
256works similarly as CX, so we suggest it as CX2. At the same
257time it generates both offspring from parents using cycle(s)
258till last bit.We differentiate CX2 in the following steps.
259Step 1. Choose two parents for mating.
260Step 2. Select 1st bit from second parent as a 1st bit of first
261offspring.
262Step 3. The selected bit from Step 2 would be found in first
263parent and pick the exact same position bit which is in second
264parent and that bit would be found again in the first parent
265and, finally, the exact same position bit which is in second
266parent will be selected for 1st bit of second offspring.
267Step 4. The selected bit from Step 3 would be found in first
268parent and pick the exact same position bit which is in second
269parent as the next bit for first offspring. (Note: for the first
270offspring, we choose bits only with one move and two moves
271for second offspring’s bits.)
272Step 5. Repeat Steps 3 and 4 till 1st bit of first parent will not
273come in second offspring (complete a cycle) and process may
274be terminated.
275Step 6. If some bits are left, then the same bits in first parent
276and in second offspring till now and vice versa are left out
277from both parents. For remaining bits repeat Steps 2, 3, and
2784 to complete the process.
279According to the previous steps, we derive two cases for
280CX2. First case of CX2 will be terminated within Step 5 and
281second will take all six steps.We provide detailed examples of
282both cases in next subsections.
2833.1. CX2: Case 1. Consider the two selected parents as mentioned
284in Step 1:
285𝑃1 = (3 4 8 2 7 1 6 5) ,
286𝑃2 = (4 2 5 1 6 8 3 7) .
287(19)
288Using Step 2,
289𝑂1 = (4 × × × × × × ×) . (20)
290As using Step 3 which selected 4 in Step 2, where 4 is found
291at second position in first parent and the bit at this position in
292second parent is 2. For searching again, 2 is at fourth position
293in first parent and 1 is at same position in second parent, so 1
294is selected for second offspring as follows:
295𝑂2 = (1 × × × × × × ×) . (21)
296To follow Step 4, the previous bit was 1 and it is located at 6th
297position in first parent and at this position bit is 8 in second
298parent, so
299𝑂1 = (4 8 × × × × × ×) . (22)
300And for two moves below 8 is 5 and below 5 is 7, so
301𝑂2 = (1 7 × × × × × ×) . (23)
302Hence similarly,
303𝑂1 = (4 8 6 2 5 3 1 7) ,
304𝑂2 = (1 7 4 8 6 2 5 3) .
305(24)
306We see that the last bit of second offspring is 3 which was the
3071st bit of first parent. Hence proposed scheme is over within
308one cycle.
3093.2. CX2: Case 2. Consider the two selected parents as
310mentioned in Step 1:
311𝑃1 = (1 2 3 4 5 6 7 8) ,
312𝑃2 = (2 7 5 8 4 1 6 3) .
313(25)
314Now using Step 2 of the scheme,
315𝑂1 = (2 × × × × × × ×) . (26)
316After this, Step 3 calls us to locate the position of bit 2 in first
317parent, which is at 2nd and 7 is at same position in second
318parent, again searching bit 7 in first parent and located at 7th
319position and 6 is at the same position in second parent, so we
320choose bit 6 for second offspring:
321𝑂2 = (6 × × × × × × ×) . (27)
322Continue Steps 4 and 5 as well:
323𝑂1 = (2 1 6 7 × × × ×) ,
324𝑂2 = (6 7 2 1 × × × ×) .
325(28)
326The Step 5 is finished because bit 1 has come in second
327offspring which was in 1st position of first parent. Now before
328applying Step 6, we match first offspring’s bits with second
329parent or vice versa and leave out the existing bits with their
330position in both parents as follwos:
331𝑃1 = (∙ ∙ 3 4 5 ∙ ∙ 8) ,
332𝑃2 = (∙ ∙ 5 8 4 ∙ ∙ 3) .
333(29)
334Now filled positions of parents and “×” positions of offspring
335are considered 1st, 2nd, and 3rd positions, and so forth, so we
336can complete Step 6 as well:
337𝑂1 = (2 1 6 7 | 5 3 8 4) ,
338𝑂2 = (6 7 2 1 | 8 4 5 3) .
339(30)
340Hence the scheme is over with efficient work.
341To apply this crossover operator, we made a MATLAB
342code for genetic algorithms and have given pseudo-code in
343Algorithm 1.
344Computational Intelligence and Neuroscience 5
345𝑁←No. of Edges
346𝑀←Population Size
347𝐺 ←No. of Generations
348𝐴 ←Random Population
349For each 1 ≤ 𝑖 ≤ 𝑁
350{
351For each 1 ≤ 𝑗 ≤ 𝑁
352{
353Distance←square-root((𝑥1 − 𝑥2)2 + (𝑦1 − 𝑦2)2)
354}
355}
356For each 1 ≤ 𝑖 ≤ 𝑀
357{
358𝑅(𝑖, :) ← Rand perm(𝑁)
359}
360For each 1 ≤ generation ≤ G
361{
362For each 1 ≤ 𝑖 ≤ 𝑀
363{
364Sum1←Distance(𝑅(𝑖, 1), 𝑅(𝑖, 𝑁))
365For each 1 ≤ 𝑗 ≤ 𝑁 − 1
366{
367Sum2 ← Distance(𝑅(𝑖, 𝑗), 𝑅(𝑖, 𝑗 + 1)) + Sum2
368}
369𝑅(𝑁 + 1)←Sum1 + Sum2
370}
371𝑅 ←Sort(𝑅)
372𝐵 ← 0.8 ∗𝑀
373𝐶 ← 0.1 ∗𝑀
374Length←Length(𝐵)/2
375For each 1 ≤ 𝑖 ≤ Length
376{
377C1←zeros(𝑁)
378C2←zeros(𝑁)
379𝑃1 ← 𝑅(𝐵(2 ∗ 𝑖 − 1), 1 : 𝑁)
380𝑃2 ← 𝑅(𝐵(2 ∗ 𝑖), 1 : 𝑁)
381St1←0
382St2←0
383Where (Length(C1) ∼= Length(P1))
384}
385𝐶1(St1)← 𝑃2(St1)
386While (St1 < 𝑁)
387{
388Ind1←find(P1 == C1(St1))
389Val1←P2(Ind1)
390𝐶2(St2)←Val1
391St1←St1 + 1
392Ind2←find(P2 == C2(St2))
393Val2← 𝑃1(Ind2)
394C1(St1)←Val2
395St2←St2 + 1
396}
397}
398𝑅(𝑀+ 2 ∗ 𝑖 − 1,1 : 𝑁) = 𝐶1
399𝑅(𝑀+ 2 ∗ 𝑖,1 : 𝑁) = 𝐶1
400For each 1 ≤ 𝑖 ≤ (𝑀 + 0.8 ∗ 𝑀)
401{
402Sum1←Distance(𝑅(1), 𝑅(2))
403For each 1 ≤ 𝑗 ≤ 𝑁 − 1
404{
405Sum2←Distance(𝑅(𝑗), 𝑅(𝑗 + 1)) + Sum1
406Algorithm 1: Continued.
407}
408𝑅(𝑁 + 1) ← (Sum1 + Sum2)
409R←Sort(𝑅)
410𝑅 ← 𝑅(1 : 𝑀)
411𝑍 ← min(𝑅)
412Plot(𝑍)
413}
414}
415Algorithm 1: Pseudo-code of proposed algorithm CX2.
416Table 2: Transition distance between cities.
417City 1 2 3 4 5 6 7
4181 0 34 36 37 31 33 35
4192 — 0 29 23 22 25 24
4203 — — 0 17 12 18 17
4214 — — — 0 32 30 29
4225 — — — — 0 26 24
4236 — — — — — 0 19
4247 — — — — — — 0
425Table 3: Comparison of three crossover operators (30 runs).
426Crossover Optimum Average
427value Best value Worst value
428PMX 17/30 159.7 159 165
429OX 14/30 160.3 159 163
430CX2 24/30 159.2 159 162
4314. Computational Experiments and Discussion
432We use genetic algorithm in MATLAB software to compare
433the proposed crossover operator with some traditional path
434representation crossover operators. Our first experiment has
4357 cities and we impose the transition distance between cities
436in Table 2. To solve this problem using GAs, the genetic
437parameters are set as population size, 𝑀 = 30; maximum
438generation, 𝐺 = 10; crossover probability, 𝑃𝑐 = 0.8; mutation
439probability, 𝑃𝑚 = 0.1. In this experiment, the optimal path and
440optimal value are6 → 1 → 5 → 3 → 4 → 2 → 7and 159,
441respectively.
442Table 3 summarizes the results and shows that the
443performance of CX2 is much better than the two existing
444crossover operators with 30 runs.
4454.1. Benchmark Problems. We perform the proposed crossover
446operator CX2 along two traditional crossover operators
447PMX and OX on twelve benchmark instances which are
448taken from the TSPLIB [28]. In these twelve problems, the
449ftv33, ftv38, ft53, kro124p, ftv170, rbg323, rbg358, rbg403, and
450rbg443, are asymmetric and gr21, fri26, and dantzig42 are
451symmetric TSPs.Theexperiments are performed 30 times (30
452runs) for each instance.The common parameters are selected
453for GAs, that is, population size, maximum generation,
454crossover, and mutation probabilities are 150, 500, 0.80, and
4556 Computational Intelligence and Neuroscience
456Table 4: Comparison results among three crossover operators.
457Instance 𝑁 Optimum
458value Results PMX OX CX2
459Best 2962 3005 2995
460gr21 21 2707 Worst 3322 3693 3576
461Average 3127 3208 3145
462Best 1056 1051 1099
463fri26 26 937 Worst 1294 1323 1278
464Average 1133 1158 1128
465Best 1708 1804 1811
466ftv33 34 1286 Worst 2399 2366 2322
467Average 2012 2098 2083
468Best 2345 2371 2252
469ftv38 39 1530 Worst 2726 2913 2718
470Average 2578 2617 2560
471Best 1298 1222 0699
472dantzig42 42 699 Worst 1606 1562 0920
473Average 1425 1301 0802
474Best 13445 13826 10987
475ft53 53 6905 Worst 16947 16279 13055
476Average 14949 14724 12243
477Generation = 500.
4780.10, respectively, for less than 100 size instances and results
479describes in Table 4. Only two changes for more than 100 size
480instances, that is, population size and maximum generation
481are 200 and 1000, respectively, and results are described in
482Table 5. Both tables demonstrate comparison of proposed
483crossover operatorwith two existing crossover operatorswith
484best, worst, and average results. These results show that the
485solution quality of the proposed algorithm and with existing
486crossovers operators are insensitive to the number of runs but
487number of generations are sensitive, especially in Table 5.
488In Table 4, CX2 is performing with other two operators,
489for instance, gr21 and ftv33, on average basis. Proposed
490operator gives best average results for instances fri26, ftv38,
491dantzig42, and ft53. For instance dantzig42, the proposed
492operator CX2, gives exact optimum value (best known value)
493sixteen out of thirty times. But for this instance, PMX andOX
494do not give us an exact value for any run and also we found
495that the best tour generated with CX2 is 75 and 86 percent
496shorter than the OX and PMX best tours, respectively. For
497instance ft53, we found 22 and 26 percent shorter distance
498than PMX and OX best tours respectively. More interesting
499aspect about CX2 is that the worst values of dantzig42 and
500ft53 are much better than others best values.
501In Table 5, the results show that all crossover operators
502work on similar pattern and also found less variations among
503best,worst, and average values. PMXandOXperformslightly
504better than CX2 in the instance for rbg323 and for all
505others instances; the performance of CX2 falls between other
506two operators except ftv170. For instance, for ftv170, CX2
507performsmuch better than other two with 108 and 137 percent
508Table 5: Comparison results among three crossover operators.
509Instance 𝑁 Optimum
510value Results PMX OX CX2
511Best 090231 097122 092450
512kro124p 100 36230 Worst 118386 122497 121513
513Average 100335 103457 101229
514Best 13346 15202 6421
515ftv170 171 2755 Worst 19314 19708 8416
516Average 16775 17569 7019
517Best 4123 3998 4212
518rbg323 323 1326 Worst 5147 5385 5342
519Average 4434 4602 4654
520Best 5380 5630 5404
521rbg358 358 1163 Worst 5915 5948 6004
522Average 5532 5830 5622
523Best 6231 6196 6257
524rbg403 403 2465 Worst 6653 6629 6671
525Average 6536 6386 6455
526Best 6754 6932 6854
527rbg443 443 2720 Worst 7209 7351 7388
528Average 6905 7121 6981
529Generation = 1000.
530shorter distance of best tours values from PMX and OX,
531respectively.
532Finally, the overall results summarize that the proposed
533approach CX2 performs better on some aspects similar to
534existing PMX and OX crossover operators.
5355. Conclusion
536Various crossover operators have been presented for TSPwith
537different applications by using GAs.The PMX and OX along
538with proposed crossover operator CX2 are mainly focused
539in this article. At first, we apply these three operators on a
540manual experiment and found that CX2 performs better than
541PMX and OX crossovers. Also, for a global performance, we
542take twelve benchmark instances from the TSPLIB (traveling
543salesman problem library). We apply all three crossover
544operators on these benchmark problems.We observe that the
545proposed operator works over 20, 70, and 100 percent for
546ft53, dantzig42, and ftv170 problems, respectively, compared
547to the other two operators. We see that, for large number of
548instances, the proposed operator CX2 is performing much
549better thanPMXandOX operators.We suggest that CX2 may
550be a good candidate to get accurate results or may be a fast
551convergent. Moreover, researchers will be more confident to
552use it for comparisons.
553Conflicts of Interest
554The authors declare that there are no conflicts of interest
555regarding the publication of this paper.
556Computational Intelligence and Neuroscience 7
557Acknowledgments
558The authors extend their appreciation to the Deanship of
559Scientific Research at King Saud University for funding this
560work through Research Group no. RG-1437-027.
561References
562[1] J. H. Holland, Adaptation in Natural and Artificial Systems: An
563Introductory Analysis with Applications to Biology, Control, and
564Artificial Intelligence,University ofMichigan Press,Oxford, UK,
5651975.
566[2] D. E. Golberg, Genetic algorithms in search, optimization and
567machine learning, Addison-Wesley Publishing Company, 1989.
568[3] P. LarraËœnaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and
569S. Dizdarevic, “Genetic algorithms for the travelling salesman
570problem: a review of representations and operators,” Artificial
571Intelligence Review, vol. 13, no. 2, pp. 129–170, 1999.
572[4] R. G. Bland and D. F. Shallcross, “Large traveling salesman
573problems arising from experiments in x-ray crystallography:
574a preliminary report on computation,” Operations Research
575Letters, vol. 8, no. 3, pp. 125–128, 1989.
576[5] C. Ravikumar, “Parallel techniques for solving large scale travelling
577salesperson problems,” Microprocessors and Microsystems,
578vol. 16, no. 3, pp. 149–158, 1992.
579[6] G. Finke, A. Claus, and E. Gunn, “A two-commodity network
580flow approach to the traveling salesman problem,” vol. 41, pp.
581167–178.
582[7] P. Miliotis, “Using cutting planes to solve the symmetric
583Travelling Salesman problem,”Mathematical Programming, vol.
58415, no. 1, pp. 177–188, 1978.
585[8] S. Lin and B. W. Kernighan, “An effective heuristic algorithm
586for the traveling-salesman problem,” Operations Research, vol.
58721, pp. 498–516, 1973.
588[9] J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm intelligence,
589morgan kaufmann publishers, Inc., San Francisco, CA, USA,
5902001.
591[10] S.Kirkpatrick and G. Toulouse, “Configuration space analysis of
592travelling salesman problems,” Le Journal de Physique, vol. 46,
593no. 8, pp. 1277–1292, 1985.
594[11] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative
595learning approach to the traveling salesman problem,”
596IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp.
59753–66, 1997.
598[12] M.Dorigo,V.Maniezzo, and A. Colorni, “Ant system: optimization
599by a colony of cooperating agents,” IEEE Transactions on
600Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 26, no.
6011, pp. 29–41, 1996.
602[13] S. Bhide, N. John, and M. R. Kabuka, “A Boolean Neural
603Network Approach for the Traveling Salesman Problem,” IEEE
604Transactions on Computers, vol. 42, no. 10, pp. 1271–1278, 1993.
605[14] F. Glover, “Artificial intelligence, heuristic frameworks and tabu
606search,” Managerial and Decision Economics, vol. 11, no. 5, pp.
607365–375, 1990.
608[15] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution
609Programs, Springer, New York, NY, USA, 1996.
610[16] C. Moon, J. Kim, G. Choi, and Y. Seo, “An efficient genetic
611algorithm for the traveling salesman problem with precedence
612constraints,” European Journal of Operational Research, vol. 140,
613no. 3, pp. 606–617, 2002.
614[17] J.-Y. Potvin, “Genetic algorithms for the traveling salesman
615problem,” Annals of Operations Research, vol. 63, pp. 339–370,
6161996.
617[18] M. Gen and R. Cheng, Genetic Algorithms and Engineering
618Design, JohnWiley & Sons, London, UK, 1997.
619[19] H. Z. Ahmed, “Genetic algorithm for the traveling salesman
620problem using sequential constructive crossover operator,” in
621Proceedings of the International Journal of Biometrics & Bioinformatics
622(IJBB), vol. 3, p. 96, 2010.
623[20] Y. Nagata and D. Soler, “A new genetic algorithm for the
624asymmetric traveling salesman problem,” Expert Systems with
625Applications, vol. 39, no. 10, pp. 8947–8953, 2012.
626[21] K. Deep and H. M. Adane, “New variations of order crossover
627for travelling salesman problem,” International Journal of Combinatorial
628Optimization Problems and Informatics, vol. 2, no. 1,
6292011.
630[22] K. P. Ghadle and Y. M. Muley, “Travelling salesman problem
631with MATLAB programming,” International Journal of
632Advances in Applied Mathematics and Mechanics, vol. 2, no. 3,
633pp. 258–266, 2015.
634[23] A. Piwonska, “Genetic algorithm finds routes in travelling
635salesman problem with profits. Zeszyty Naukowe Politechniki
636Bia lostockiej,” Informatyka, pp. 51–65, 2010.
637[24] N.Kumar, R. K.Karambir et al., “Acomparative analysis of pmx,
638cx and ox crossover operators for solving traveling salesman
639problem,” International Journal of Latest Research in Science and
640Technology, vol. 1, 2012.
641[25] D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling
642Salesman Problem,” in Proceedings of the 1st International
643Conference on Genetic Algorithms and Their Applications, vol.
6441985, pp. 154–159, Los Angeles, USA.
645[26] L. Davis, “Applying adaptive algorithms to epistatic domains,”
646IJCAI, vol. 85, pp. 162–164, 1985.
647[27] I. M. Oliver,D. J. d. Smith, andR. C. J.Holland, “Study of permutation
648crossover operators on the traveling salesman problem,”
649in Genetic algorithms and their applications: proceedings of the
650second International Conference on Genetic Algorithms: July 28-
65131, 1987 at theMassachusetts Institute of Technology, Cambridge,
652MA, USA, 1987.
653[28] G. Reinelt, http://www.iwr.uni-heidelberg.de/group/comopt/
654software.
655Submit your manuscripts at
656https://www.hindawi.com
657Computer Games
658Technology
659International Journal of
660Hindawi Publishing Corporation
661http://www.hindawi.com Volume 2014
662Hindawi Publishing Corporation
663http://www.hindawi.com Volume 2014
664Distributed
665Sensor Networks
666International Journal of
667Advances in
668Fuzzy
669Systems
670Hindawi Publishing Corporation
671http://www.hindawi.com
672Volume 2014
673International Journal of
674Reconfigurable
675Computing
676Hindawi Publishing Corporation
677http://www.hindawi.com Volume 2014
678Hindawi Publishing Corporation
679http://www.hindawi.com Volume 201ô€€—
680Applied
681Computational
682Intelligence and Soft
683Computing
684Advances in
685Artificial
686Intelligence
687Hindawi Publishing Corporation
688http://www.hindawi.com Volume 2014
689Advances in
690Software Engineering
691Hindawi Publishing Corporation
692http://www.hindawi.com Volume 2014
693Hindawi Publishing Corporation
694http://www.hindawi.com Volume 2014
695Electrical and Computer
696Engineering
697Journal of
698􀀭􀁒􀁘􀁕􀁑􀁄􀁏􀀃􀁒􀁉
699􀀦􀁒􀁐􀁓􀁘􀁗􀁈􀁕􀀃􀀱􀁈􀁗􀁚􀁒􀁕􀁎􀁖􀀃
700􀁄􀁑􀁇􀀃􀀦􀁒􀁐􀁐􀁘􀁑􀁌􀁆􀁄􀁗􀁌􀁒􀁑􀁖
701􀀫􀁌􀁑􀁇􀁄􀁚􀁌􀀃􀀳􀁘􀁅􀁏􀁌􀁖􀁋􀁌􀁑􀁊􀀃􀀦􀁒􀁕􀁓􀁒􀁕􀁄􀁗􀁌􀁒􀁑
702􀁋􀁗􀁗􀁓􀀝􀀒􀀒􀁚􀁚􀁚􀀑􀁋􀁌􀁑􀁇􀁄􀁚􀁌􀀑􀁆􀁒􀁐 􀀹􀁒􀁏􀁘􀁐􀁈􀀃􀀕􀀓􀀔􀀗
703Hindawi Publishing Corporation
704http://www.hindawi.com Volume 2014
705Advances in
706Multimedia
707International Journal of
708Biomedical Imaging
709Hindawi Publishing Corporation
710http://www.hindawi.com Volume 2014
711􀀤􀁕􀁗􀁌􀃀􀁆􀁌􀁄􀁏
712􀀱􀁈􀁘􀁕􀁄􀁏􀀃􀀶􀁜􀁖􀁗􀁈􀁐􀁖
713Advances in
714Hindawi Publishing Corporation
715http://www.hindawi.com Volume 201ô€€—
716Robotics
717Journal of
718Hindawi Publishing Corporation
719http://www.hindawi.com Volume 2014
720Hindawi Publishing Corporation
721http://www.hindawi.com Volume 2014
722Computational
723Intelligence and
724Neuroscience
725Industrial Engineering
726Journal of
727Hindawi Publishing Corporation
728http://www.hindawi.com Volume 2014
729Modelling &
730Simulation
731in Engineering
732Hindawi Publishing Corporation
733http://www.hindawi.com Volume 2014
734The Scientific
735World Journal
736Hindawi Publishing Corporation
737http://www.hindawi.com Volume 2014
738Hindawi Publishing Corporation
739http://www.hindawi.com Volume 2014
740Human-Computer
741Interaction
742Advances in
743Computer Engineering
744Advances in
745Hindawi Publishing Corporation
746http://www.hindawi.com Volume 2014