Chapter 3: Background Knowledge

CHAPTER 3

This chapter provides some necessary knowledge on both single and multi-objective combinatorial problems and review of the available both exact and heuristic solution methodologies. However, this thesis focuses only on the methods which apply to the permutation representation, which is naturally more suitable with combinatorial problems. The solution methodologies involving the transformation of representations are not in the scope of the review.

Performance Indicators

State of the art algorithm

Combinatorial Optimization

Combinatorial problems are characterized by the consideration of a selection or permutation of a finite or a countable discrete set of structures. This class of problems arises in many areas of pure mathematics, notably in algebra, probability theory, topology and geometry. Their application includes ……………..

Combinatorial optimization considers the following problem:

z(S)= min_xϵSf(x)

Where x is a feasible solution belong to the discrete solution set S, usually called the decision space or solution space. The function f maps S to ℝ is called the objective function. Therefore f(x) describes the objective function value of the solution x

Multi-objective Combinatorial Optimization

Solution Methods for Combinatorial Optimization

This section introduces the generic form of metaheuristics including Simulated Annealing, Tabu search and ….

PROCEDURE SimulatedAnnealing

1. Find a feasible solution x

2. Set BestX = x and Set BestFx = f(x)

3. Initialize Temp

4. Repeat

5. select a random solution y from Neighborhood(x)

6. if f(y) > f(x) then Set x = y

7. else if exp((f(y)-f(x))/Temp) < random[0;1] then Set x = y

8. if f(x) > BestFx then {Set BestX=x and Set BestFx = f(x)}

9. Update(Temp)

10. Until Termination Condition is met

Figure 3.1 Basic version of Simulated Annealing

PROCEDURE TabuSearch

1. Find a feasible solution x

2. Set BestX = x and Set BestFx = f(x) and Set TabuList = {}

3. Repeat

4. Set y = Argmax {f(y) | y ∈  Neighbor(x)∧ MoveAttribute(x,y) ∉ Tabulist}

5. if length(TL) > TabulistLength then remove the oldElement from TabuList

6. add MoveAttribute(y,x) as the newest element to TabuList

7. Set x = y

8. if f(x) > BestFx then {Set BestX = x and Set BestFx = f(x) }

9. Until Termination Condition is met

Figure 3.2 Basic version of Tabu Search

PROCEDURE AntColonyOptimization

1. Find a feasible solution x

2. Set BestX = x and Set BestFx = f(x) and Set TabuList = {}

3. Repeat

4. Set y = Argmax {f(y) | y ∈  Neighbor(x)∧ MoveAttribute(x,y) ∉ Tabulist}

5. if length(TL) > TabulistLength then remove the oldElement from TabuList

6. add MoveAttribute(y,x) as the newest element to TabuList

7. Set x = y

8. if f(x) > BestFx then {Set BestX = x and Set BestFx = f(x) }

9. Until Termination Condition is met

Figure 3.3 Ant Colony Optimization

1. Exact Algorithms

The exact algorithms are designed to find the optimal solution to the Combinatorial Problem. They are usually computationally expensive because they must (implicitly) consider all solutions in order to identify the optimum. These exact algorithms are typically derived from the integer linear programming (ILP).

Branch and bound algorithms are commonly used to find an optimal solution to the TSP, and the AP-relaxation is useful to generate good lower bounds. However, Illustrate the limitation of branch and bound here

2. Heuristic Algorithms and Metaheuristics

In this section, the concept of heuristics and metaheuristics is introduce, Blum and Roli (2003) have reviewed and compared some of these metaheuristics methodologies, some of the publications can be found in the Metaheuristics Network Web http://www.metaheuristics.org/. The acronyms used to identify these metaheuristics are shown in Table 3.1

Table 3.1 Acronyms used for the metaheuristics

Illustrate the NP and heuristic algorithms here

Many COPs are belong to the class of NP-hard optimization problems (Garey and Johnson 1979)[]. This means that there the algorithms that guarantee to find the optimal solution within bounded time or exact algorithms might require the exponential computational time. Therefore, running an exact algorithm for hours on a powerful computer may not be very cost-effective if a solution, within a few percent of the optimum. Accordingly, heuristic or approximate algorithms are often preferred to exact algorithms for solving the COPs. Heuristic strategies are receiving more and more interest as they can find the reasonable good solution (but not necessarily an optimal one) compared to the given computational time. Heuristics algorithms are sometimes called the approximate algorithms.

The term “heuristic” derives from the Greek verb “heuriskein” (ενρισκειν) which means “to find” or “to discover” it is in optimization not so much used to describe how to find as how to search for good solutions (Reeves and Beasley, 1995). Generally, the exact algorithms can apply heuristic strategies, for example, to guide the search in a branch and bound procedure. However, the term heuristic is preferred to denote the approximate algorithm. There are mainly two types of heuristics, “Constructive Algorithms” and “Improvement Algorithms”. Constructive algorithms build a solution by joining together “pieces” or “components” of a solution, while Improvement algorithms start from a pre-existent solution and try to improve it by modifying some of its component. Constructive strategies are sometimes called recombination, while improvement strategies are usually known as local search. Some heuristics algorithm combines both constructive and improvement strategies altogether, we call these algorithm “Composite Algorithms” or “Hybrid Algorithms” or “Mimetic Algorithms”. These composite algorithms are now the most powerful heuristics for solving COPs. Among the new generation of composite heuristics, the most outstanding ones are the CCAO heuristic (Golden and Stewart), the iterated Lin-Kernighan heuristic (Johnson), and the GENIUS heuristic (Gendreau et al.). Unfortunately, most of the algorithms are problem-specific and are not in the scope of review as they usually combine the existing constructive and improvement strategies found in this chapter.

The Greek suffix “meta” used in the word metaheuristics means “beyond, in an upper level”. The term “metaheuristics” was first used by Glover (1986) to describe a heuristic that is superimposed on another heuristic. Generally speaking, metaheuristics are algorithms that combine heuristics (that are usually problem specific solvers) in a more general framework.

According to Blum and Roli, (2003), metaheuristics are high level concepts for exploring search spaces by using different strategies. These strategies should be chosen in such a way that a dynamic balance is given between the exploitation of the accumulated search experience (which is commonly called diversification). This balance is necessary on one side to quickly identify regions in the search space with high quality solutions and on the other side not to waste too much time in regions of the search space which are either already explored or don’t provide high quality solutions.

The vocabulary will probably look a little bit “esoteric”

Straightforward

Ant Colony Optimization

Genetic Algorithms

Underlying Principles

First, let us assume that some function f(x) is to be maximized over the set of integers ranging from 0 to 63. In this example, we ignore the obvious fact that such a small problem could be easily solved through complete enumeration. In order to apply a genetic algorithm to this problem, the variable x must first be coded as a bit string. Here, a bit string of length 6 is chosen, so that integer between 0 (000000) and 63 (111111) can be obtained. The fitness of each chromosome is f(x), where x is the integer value encoded in the chromosome. Assuming a population of eight chromosomes, it is possible to create an initial population by randomly generating eight different bit strings, and by evaluating their fitness, through f, as illustrated in figure3. For example, chromosome1 encodes the integer 49 and its fitness is f(49) = 90.

By looking at the similarities and differences between the chromosomes and by comparing their fitness values, it is possible to hypothesize that chromosomes with the high fitness values have two 1’s in the first two positions or two 1’s in the last two positions. These similarities are exploited by the genetic search via the concept of schemata (hyperplanes, similarity templates). A schema is composed of 0’s and 1’s, like the original chromosomes, but with the additional “wild card” or “don’t care” symbal *, standing either for 0 or 1. Via the don’t care symbol, schemata represent subsets of chromosomes in the population. For example, the schema 11**** contains chromosomes 1 and 3 in the population illustrated in figure3, while schema ****11 contains chromosomes 5 and6.

Two fundamental characteristics of schemata are the order and the defining length, namely:

(1) The order is the number of positions with fixed values (the schema 11**** is of order 2, the schema 110*00 is of order 5).

(2) The defining length is the distance between the first and last positions with fixed values (e.g., the schema 11**** has length 1, the schema 1****1 has maximal length 5).

A “building block” is a schema of low order, short defining length and above-average fitness (where the fitness of a schema is defined as the average fitness of its members in the population). Generally speaking, the genetic algorithm moves in the search space by combining building blocks from two parent chromosomes to create a new offspring. Consequently, the basic assumption at the core of the genetic algorithm is that a better chromosome is found by combining the best features of two good chromosomes. In the example above, genetic material (i.e. bits) would be exchanged between a chromosome with two 1’s in the first two positions and a chromosome with two 1’s in the last two positions in order to create an offspring with two 1’s in the first two positions and two 1’s in the last two positions (in the hope that the x value encoded in this chromosome would generate a higher f(x) value than both of its parents). Hence, the two above-average building blocks 11*** and ***11 are combined on a single chromosome to create an offspring with higher fitness.

Selection probability

The parent chromosomes are selected for mating via proportional selection, also known as “roulette wheel selection”.

1. Sum up the fitness values of all chromosomes in the population.

2. Generate a random number between 0 and the sum of the fitness values.

3. Select the first chromosome whose fitness value added to the sum of the fitness values of the previous chromosomes is greater than or equal to the random number.

One-point crossover

The one-point crossover operator is aimed at exchanging bit strings between two parent chromosomes. A random position between1 and L-1 is chosen along the two parent chromosomes, where L is the chromosome’s length. Then, the chromosomes are cut at the selected position, and their end parts are exchanged to create two offspring. In figure 4, for example, the parent chromosomes are cut at position 3.

A probability is associated to the application of the crossover operator. If the operator is not applied to the selected parents, they are copied to the new population without any modification. In this way, good chromosomes can be preserved from one generation to the next. The crossover rate can be related to the “aggressiveness” of the search. High crossover rates create more new offspring, at the risk of losing many good chromosomes in the current population. Conversely, low crossover rates tend to preserve the good chromosomes from one generation to the next, via a more conservative exploration of the search space. In [10], it is suggested that good performance requires the choice of a fairly high crossover rate, such as 0.6, so that about 60% of the selected parents will undergo crossover.

Characteristics of the genetic search

Broadly speaking, the search performed by a genetic algorithm can be characterized in the following way (Goldberg [20]):

1. Genetic algorithms manipulate bit strings or chromosomes encoding useful information about the problem, but they do not manipulate the information as such (no decoding or interpretation).

2. Genetic algorithms use the evaluation of a chromosome, as returned by the fitness function, to guide the search. They do not use any other information about the fitness function or the application domain.

3. The search is run in parallel from a population of chromosomes.

4. The transition from one chromosome to another in the search space is done stochastically.

In particular, points (a) and (b) explain the robustness of the genetic algorithms and their wide applicability as meta-heuristics in various application domains. However, the simple genetic search introduced in this session cannot be directly applied to a combinatorial optimization problem like the TSP. The next section will provide more explanations on this matter.

Genetic algorithms for the TSP

The description of the genetic algorithm included many genetic terms. In order to better understand how genetic algorithms can be applied to combinatorial optimization problems, the following equivalence will be useful.

In the TSP context, each chromosome encodes a solution to the problem (i.e., a tour). The fitness of the chromosome is related to the tour length, which in turn depends on the ordering of the cities. Since the TSP is a minimization problem, the tour length must be transformed so that high fitness values are associated with short tours, and conversely. A well-known approach is to subtract each tour length to the maximum tour length found in the current population. Other approaches are based on the rank of the tours in the population (as mentioned in the previous section).

Difficulties quickly arise when the simple “pure” genetic algorithm of section 2 is applied to a combinatorial optimization problem like the TSP. In particular, the encoding of a solution as a bit string is not convenient. Accordingly, most sequences in the search space would not correspond to feasible tours. For example, it would be easy to create a sequence with two occurrences of the same city, using the mutation operator. Moreover, when the number of cities is not a power of two, some bit sequences in the code would not correspond to any city. In the literature, fitness functions with penalty terms, and repair operators to transform infeasible solutions into feasible ones, have been proposed to alleviate these problems. However, these approaches were designed for very specific application domains, and are not always relevant in a TSP context.

The preferred research avenue for the TSP is to design representational frameworks that are more sophisticated than the bit string, and to develop specialized operators to manipulate these representations and create feasible sequences. For example, the chromosomes shown in figure 5 are based on the “path” representation of a tour (on cities 1 to 8). It is clear that the mutation operator and the one-point crossover are still likely to generate infeasible tours when they are applied to this integer representation. For example, applying the crossover operator at position 2 creates two infeasible offspring, as illustrated in figure5.

Figure 4. Application of the one-point crossover on the two permutation chromosomes

None of the two offspring is a permutation of the cities. The TSP, as opposed to most problems tackled by genetic algorithms, is a pure ordering problem. Namely, all chromosomes carry exactly the same values and differ only in the ordering of these values. Accordingly, specialized permutation operators must be developed for this problem.

The ordinal representation

In [22], the authors developed an ingenious coding scheme for the classical one-point crossover. With this coding scheme, the one-point crossover always generates feasible offspring. This representation is mostly of historical interest, because the sequencing information in the two parent chromosomes is not well transferred to the offspring, and the resulting search is close to a random search.

The encoding is based on a reference or canonic tour. For N=8 cities, let us assume that this canonic tour is 12345678. Then, the tour to be encoded is processed city by city. The position of the current city in the canonic tour is stored at the corresponding position in the resulting chromosome. The canonic tour is updated by deleting that city, and the procedure is repeated with the next city in the tour to be encoded.

This approach is illustrated in figure 6 using a small example. In this figure, the first string is the current tour to be encoded, the second string is the canonic tour and the third string is the resulting chromosome. The underlined city in the first string corresponds to the current city. The position of the current city in the canonic tour is used to build the ordinal representation.

The resulting chromosome 11332121 can be easily decoded into the original tour 12564387 by the inverse process. Interestingly enough, two parent chromosomes encoded in this way always generate a feasible offspring when they are processed by the one-point crossover. In fact, each value in the ordinal representation corresponds to a particular position in the canonic tour. Exchanging values between two parent chromosomes simply modified the order of selection of the cities in the canonic tour. Consequently, a permutation is always generated. For example, the two parent chromosomes in figure 7 encode the tours 12564387 and 14236578, respectively. After a cut at position 2, a feasible offspring is created.

The path representation

As opposed to the ordinal representation, the path representation is a natural way to encode TSP tours. However, a single tour can be represented in 2N district ways, because any city can be placed at position 1, and the two orientations of the tour are the same for a symmetric problem. Of course, the factor N can be removed by fixing a particular city at position 1 in the chromosome.

The crossover operators based on this representation typically generate offspring that inherit either the relative order or the absolute position of the cities from the parent chromosomes. We will now describe these operators in turn. In each case, a single offspring is shown. However, a second offspring can be easily generated by inverting the roles of the parents.

Crossover operators preserving the absolute position

The two crossover operators introduced in this section were among the first to be designed for the TSP. generally, speaking, the results achieved with these operators are not very impressive (as reported at the end of this section).

Partially-mapped crossover (PMX) (Goldberg and Lingle [18])

This operator first randomly selects two cut points on both parents. In order to create an offspring, the substring between the two cut points in the first parent replaces the corresponding substring in the second parent. Then, the inverse replacement is applied outside of the cut points, in order to eliminate duplicates and recover all cities.

In figure 8, the offspring is created by first replacing the substring 236 in parent 2 by the substring 564. Hence, city 5 replaces city 2, city 6 replaces city 3, and city 4 replaces city 6 (step 1). Since cities 4 and 5 are now duplicated in the offspring, the inverse replacement is applied outside of the cut points. Namely, city 2 replaces city 5, and city 3 replaces city 4 (step 2). In the latter case, city 6 first replaces city 4, but since city 6 is already found in the offspring at position 4, city 3 finally replaces city 6. Multiple replacements at a given position occur when a city is located between the cut points on both parents, like city 6 in this example.

Figure 8. The partially-mapped crossover

Clearly, PMX tries to preserve the absolute position of the cities when they are copied from the parents to the offspring. In fact, the number of cities that do not inherit their positions from one of the two parents is at most equal to the length of the string between the two cut points. In the above example, only cities 2 and 3 do not inherit their absolute position from one of the two parents.

Cycle crossover (CX) (oliver et al [47])

The cycle crossover focuses on subsets of cities that occupy the same subset of positions in both parents. Then, these cities are copied from the first parent to the offspring (at the same position), and the remaining positions are filled with the cities of the second parent. In this way, the position of each city is inherited from one of the two parents, However, many edges can be broken in the process, because the initial subset of cities is not necessarily located at consecutive positions in the parent tours.

In figure 9, the subset of cities {3, 4, 6} occupies the subset of positions {2, 4, 5} in both parents. Hence, an offspring is created by filling the positions 2, 4, and 5 with the cities found in parent 1, and filing the remaining positions with the cities found in parent 2.

Figure 9. the cycle crossover

Note that the crossover operator introduced in [6] is a restricted version of CX, where the subset of cities must occupy consecutive positions in both parents.

Modified crossover (Davis [9])

This crossover operator is an extension of the one-point crossover for permutation problems. A cut position is chosen at random on the first parent chromosome. Then, an offspring is created by appending the second parent chromosome to the initial segment of the first parent (before the cut point), and by eliminating the duplicates. An example is provided in figure 10.

Figure 10. The modified crossover

Note that the cities occupying the first positions in parent 2 tend to move forward in the resulting offspring (with respect to their positions in parent 1). For example, city 4 occupies the fifth position in parent 1, but since it occupies the second position in parent 2, it moves to the third position in the resulting offspring.

Order Crossover (OX) (Oliver et al. [47], Goldberg [20])

This crossover operator extends the modified crossover of Davis by allowing two cut points to be randomly chosen on the parent chromosomes. In order to create an offspring, the string between the two cut points in the first parent is first copied to the offspring. Then, the remaining positions are filled by considering the sequence of cities in the second parent, starting after the second cut point (when the end of the chromosome is reached, the sequence continues at position 1).

In figure 11, the substring 564 in parent 1 is first copied to the offspring (step 1). Then, the remaining positions are filled one by one after the second cut point, by considering the corresponding sequence of cities in parent 2, namely 57814236 (step 2). Hence, city 5 is first considered to occupy position 6, but it is discarded because it is already included in the offspring. City 7 is the next city to be considered, and it is inserted at position 6. Then, city 8 is inserted at position 7, city 1 is inserted at position 8, city 4 is discarded, city 2 is inserted at position 1, city 3 is inserted at position 2, and city 6 is discarded.

Figure 11. The order crossover

Clearly, OX tries to preserve the relative order of the cities in parent 2, rather than their absolute position. In figure 11, the offspring does not preserve the position of any city in parent 2. However, city 7 still appears before city 8 and city 2 before city 3 in the resulting offspring. It is worth noting that a variant of OX, known as the maximal preservative crossover, is also described in [21].

Order-based crossover (OBX) (Syswerda [58])

This crossover also focuses on the relative order of the cities on the parent chromosomes. First, a subset of cities is selected in the first parent. In the offspring, these cities appear in the same order as in the first parent, but at positions taken from the second parent. Then, the remaining positions are filled with the cities of the second parent.

In figure 12, cities 5, 4, 3 are first selected in parent 1, and must appear in this order in the offspring. Actually, these cities occupy positions 2, 4 and 6 in parent 2. Hence, cities 5, 4 and 3 occupy positions 2, 4 and 6, respectively, in the offspring. The remaining positions are filled with the cities found in parent 2.

Figure 12. The order-based crossover

Position-based crossover (PBX) (Syswerda [58])

Here, a subset of positions is selected in the first parent. Then, the cities found at these positions are copied to the offspring (at the same positions). The other positions are filled with the remaining cities, in the same order as in the second parent.

The name of this operator is a little bit misleading, because it is the relative order of the cities that is inherited from the parents (the absolute position of the cities inherited from the second parent is rarely preserved). This operator can be seen as an extension of the order crossover OX, where the cities inherited from the first parent do not necessarily occupy consecutive positions.

In figure 13, positions 3, 5 and 6 are first selected in parent 1. Cities 5, 4 and 3 are found at these positions, and occupy the same positions in the offspring. The other positions are filled one by one, starting at position 1, by inserting the remaining cities according to their relative order in parent 2, namely 12678.

Figure 13 The position-based crossover

Computational results

Studies by Oliver et al. [47] and Starkweather et al. [55] demonstrated that order-preserving crossover operators were clearly superior to the operators preserving the absolute position of the cities.

In [47], PMX, CX and OX were applied to the 30-city problem of Hopfield and Tank [28]. They found that the best tour generated with OX was 11% shorter than the best PMX tour, and 15% shorter than the best CX tour. In a later study [55], six different crossover operators were tested on the same problem [28]. Thirty different runs were performed with each operator. In this experiment, OX found the optimum 25 times (out of 30), while PMX found the optimum only once, and CX never found the optimum.

Table 1 summarizes the results in [55]. It is worth noting that the parameters of the genetic algorithm were tuned for each crossover operator, so as to provide the best possible results. Accordingly, the population size and number of trials (i.e., total number of tours generated) are not the same in each case. The edge recombination operator ER will be introduced in the next section, and should be ignored for now.

The adjacency representation

The adjacency representation is designed to facilitate the manipulation of edges. The crossover operators based on this representation generate offspring that inherit most of their edges from the parent chromosomes.

The adjacency representation can be described as follows: nodecity j occupies position i in the chromosome if there is an edge from city i to city j in the tour. For example, the chromosome 38526417 encodes the tour 13564287. City 3 occupies position 1 in the chromosome because edge (1, 3) is in the tour. Similarly, city 8 occupies position 2 because edge (2, 8) is in the tour, etc. As opposed to the path representation, a tour has only two different adjacency representations for symmetric TSPs.

Various crossover operators are designed to manipulate this representation, and are introduced in the next sections. These operators are aimed at transferring as many edges as possible from the parents to the offspring. However, it is important to note that they share a common weakness: the selection of the last edge, that connects the final city to the initial city, is not enforced. In other words, the last edge is added to the final solution, without any reference to the parents. Accordingly, this edge is rarely inherited.

Alternate edges crossover (Grefenstette el al. [22])

This operator is mainly of historical interest. As reported in [22], the results with the operator have been uniformly discouraging. However, it is a good introduction to the other edge-preserving operators.

Here, a starting edge (i, j) is selected at random in one parent. Then, the tour is extended by selecting the edge (j, k) in the other parent. The tour is progressively extended in this way by alternatively selecting the edges from the two parents. When an edge introduces a cycle, the new edge is selected at random (and is not inherited from the parents).

In figure 14, an offspring is generated from two parent chromosomes that encode the tours 13564287 and 14236578, respectively, using the adjacency representation. Here, edge (1,4) is first selected in parent 2 and city 4 in position 1 of parent 2 is copied at the same position in the offspring.

Then, the edges (4, 2) in parent 1, (2, 3) in parent 2, (3, 5) in parent 1 and (5, 7) in parent 2 are selected and inserted in the offspring. Then, edge (7, 1) is selected in parent 1. However, this edge introduces a cycle, and a new edge leading to a city not yet visited is selected at random. Let us assume that (7, 6) is chosen. Then, edge (6, 5) is selected in parent 2, but it also introduces a cycle. At this point, (6, 8) is the only selection that does not introduce a cycle. Finally, the tour is completed with edge (8, 1).

The final offspring encodes the tour 14235768, and all edges in the offspring are inherited from the parents, apart from the edges (7, 6) and (6, 8).

In the above description, an implicit orientation of the parent tours is assumed. For symmetric problems, the two edges that are incident to a given city can be considered. In the above example, when we get to city 7 and select the next edge in parent 1, edges (7, 1) and (7, 8) can both be considered. Since (7, 1) introduces a cycle, edge (7, 8) is selected. Finally, edges (8, 6) and (6, 1) complete the tour.

Edge recombination crossover (ER) (Whitley et al. [67])

Quite often, the alternate edge operator introduces many random edges in the offspring, particularly, the last edges, when the choices for extending the tour are limited. Since the offspring must inherit as many edges as possible from the parents, the introduction of random edges should be minimized. The edge recombination operator reduces the myopic behavior of the alternate edge approach with a special data structure called the “edge map”.

Basically, the edge map maintains the list of edges that are incident to each city in the parent tours and that lead to cities not yet included in the offspring. Hence, these edges are still available for extending the tour and are said to be active. The strategy is to extend the tour by selecting the edge that leads to the city with the minimum number of active edges. In the case of equality between two or more cities, one of these cities is selected at random. With this strategy, the approach is less likely to get trapped in a “dead end”, namely, a city with no remaining active edges (thus requiring the selection of a random edge).

For the tours 13564287 and 14236578 (path representation), the initial edge map is shown in figure 16.

The operation of the edge recombination crossover operator will not be illustrated on this initial edge map (see figure 17). To this end, the edge map will be updated after each city selection. In these edge maps, cities of particular interest are underlined (namely, cities are adjacent to the selected city in the parents and are not visited yet).

Let us assume that city 1 is selected as the starting city. Accordingly, all edges incident to city 1 must first be deleted from the initial edge map. From city 1, we can go to cities 3, 4, 7 or 8. City 3 has three active edges, while cities 4, 7 and 8 have two active edges, as shown by edge map (a) in figure 17. Hence, a random choice is made between cities 4, 7 and 8. We assume that city 8 is selected. From 8, we can go to cities 2 and 7. As indicated in edge map (b), city2 has two active edges and city 7 only one, so the latter is selected. From city 7, there is no choice but to go to city 5. From this point, edge map (d) offers a choice between cities 3 and 6 with two active edges. Let us assume that city 6 is randomly selected. From city 6, we can go to cities 3 and 4, and edge map (e) indicates that both cities have one active edge. We assume that city 4 is randomly selected. Finally, from city 4 we can only go to city 2, and from city 2 we must go to city 3. The final tour is 18756423 and all edges are inherited from both parents.

A variant which focuses on edges common to both parents is also described in [55]. The common edges are marked with an asterisk in the edge map, and are always selected first (even if they do not lead to the city with the minimum number of active edges). In the previous example, (2, 4), (5, 6) and (7, 8) are found in both parents and have priority over all other active edges. In the above example, the new approach generates the same tour, because the common edges always lead to the cities with the minimum number of active edges.

Heuristic crossover (HX) [Grefenstette et al. [22],Grefenstette [23]]

It is worth noting that the previous crossover operators did not exploit the distances between the cities (i.e., the length of the edges). In fact, it is a characteristic of the genetic approach to avoid any heuristic information about a specific application domain, apart from the overall evaluation or fitness of each chromosome. This characteristic explains the robustness of the genetic search and its wide applicability

However, some researchers departed from this line of thinking and introduced domain-dependent heuristics into the genetic search to create “hybrid” genetic algorithms. They have sacrificed robustness over a wide class of problems for better performance on a specific problem. The heuristic crossover HX is an example of this approach and can be described as follows:

Step 1. Choose a random starting city from one of the two parents.

Step 2. Compare the edges leaving the current city in both parents and select the shorter edge.

Step 3. If the shorter parental edge introduces a cycle in the partial tour, then extended the tour with a random edge that does not introduce a cycle.

Step 4. Repeat step 2 and 3 until all cities are included in the tour.

Note that a variant is proposed in [36, 56] to emphasize the inheritance of edges from the parents. Basically, step 3 is modified as follows:

Step 3’. If the shorter parental edge introduces a cycle, then try the other parental edge. If it also introduces a cycle, then extend the tour with a random edge that does not introduce a cycle.

Jog et al. [29] also proposed to replace the random edge selection by the selection of the shortest edge in a pool of random edges (the size of the pool being a parameter of the algorithm).

Table 2 summarizes sections 4 to 6 by providing a global view of the various crossover operators for the TSP. They are classified according to the type of information transferred to the offspring (i.e., relative order of the cities, absolute position of the cities, or edges).

Table 2

Information inheritance for nine crossover operators

Mutation operators

Mutation operators for the TSP are aimed at randomly generating new permutations of the cities. As opposed to the classical mutation operator, which introduces small perturbations into the chromosome, the permutation operators for the TSP often greatly modify the original tour. These operators are summarized below.

SWAP

Two cities are randomly selected and swapped (i.e., their positions are exchanged). This mutation operator is the closest in philosophy to the original mutation operator, because it only slightly modifies the original tour.

Local hill-climbing

Typically, a local edge exchange heuristic is applied to the tour (e.g., 2-opt, 3-opt). The exchange heuristic is applied for a fixed number of iterations, or until a local optimum is found. Note that the reordering operator known as inversion (Holland [26]) corresponds to a single 2-opt exchange.

Scramble

Two cut points are selected at random on the chromosome, and the cities within the two cut points are randomly permuted.

Multiobjective Combinatorial Optimization