# Genetic Algorithm for Combinatorial Path Planning: The Subtour Problem

Authors: Giovanni Giardini; Tamás Kalmár-Nagy
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

The purpose of this paper is to present a combinatorial planner for autonomous systems. The approach is demonstrated
on the so-called subtour problem, a variant of the classical traveling salesman problem (TSP): given a set ofn possible goals/targets, the optimal strategy is sought that connects k≤n goals. The proposed solution method is a Genetic Algorithm coupled with a heuristic local search. To validate the approach, the method has been benchmarked against TSPs and subtour problems with known optimal solutions. Numerical experiments demonstrate the success
of the approach.


---

## Body

## 1. Introduction

To build systems that plan and act autonomously represents an important direction in the field of robotics and artificial intelligence. Many applications, ranging from space exploration [1–4] to search and rescue problems [5, 6], have underlined the need for autonomous systems capable to plan strategies with minimal or no human feedback. Autonomy might also be required for exploring hostile environments where human access is impossible, for example, volcano exploration [7] or for locating victims in collapsed buildings [8, 9].For intelligent systems, there are usually two well-separated modes of operation: the autonomous planning and scheduling of goals and actions [1, 10] and the subsequent autonomous navigation [11]. Even though autonomous navigation has vastly improved during the past decades, human instruction still plays a crucial role in the planning and scheduling phase [12–14].In order to increase the capability of robotic systems to handle uncertain and dynamic environments, the next natural step in autonomy will be the deeper integration of these two operational modes, that is, linking the autonomous navigation system with the planning and scheduling component [15, 16], moving the latter onboard the agent. The ultimate objective of this line of research is to develop a general purpose goal planner for autonomous multiagent systems. In this context “goals” are possible states of the system (e.g., locations on a map) and “actions” are transitions between these states. An intelligent planner/scheduler should be able to achieve a set of goals (planning phase) by computing an optimal sequence of actions (scheduling phase) so that human operators only have to define the highest-level goals for the vehicle (also referred to as agent) [17].For path planning involving many goals/locations, the planning phase turns into amission-level planning problem, where construction of a “route” is required [18, 19]. This planning phase is at a higher level of abstraction than the classic point-to-point navigation: at this level, goals are given locations on a map, and a plan represents a sequence of these locations to be visited. On the other hand, the low-level, point-to-point path planning is considered in the scheduling phase, and it is usually solved once the overall location route is known [20]. Another important difference between high and low level motion planning is their time and length scale separation, that is, local navigation occurs at a much smaller lengths and at a much faster rate than the high level planning. Due to this separation of scales, high level motion planning usually does not take the dynamics of the vehicle into account. Instead, low-level motion planning is usually responsible for obstacle avoidance and local interactions with the environment; the dynamical constraints of the vehicles can also be taken into account here [21].Our long-term objective is to realize a multiagentplanning system for a team of autonomous vehicles to cooperatively explore their environment [22]. To achieve this goal, given a set of locations (also referred to as targets), we require the vehicles to compute a coordinated exploration strategy for visiting them all. Specifically, the overall planning problem will be formulated as finding a near-optimal set of high-level paths/plans that allow the team of agents to visit the given number of targets in the shortest amount of time (similarly to the task-assignment problem described in [23]). More precisely, given m agents, we look for the time-optimal (min-max) team strategy for reaching a set of n given targets (every target must be visited only once).The first step to solve this problem is to construct a (near-)optimal strategy for a single agent to reach a subset of the given locations. Finding this single-agent strategy is what we call thek-from-n “Subtour Problem”: for a given set ofngoals/targets, an optimal sequence ofk≤nof these goals is sought.This problem is a variant of the well-known traveling salesman problem (TSP), wheren different locations/goals must be visited by the agent with the shortest possible path [24–26].Since a multiagent strategy is a set ofm subtours (see Figure 1), the main motivation of this paper is to implement a simple algorithm that yields good-quality subtours.Figure 1
Subtours are components of a multiagent plan. In this example, the multiagent plan of four agents starting from the same position (S) is shown.Subtour-type problems have already been studied in the literature. Gensch [27] modifies the classical Traveling Salesman Problem to include a more realistic scheduling time constraint. In this variant the salesman must select an optimal subset of the cities (the subtour) to be toured within the time constraint. Gensch provides a tight upper bound through Lagrangian relaxation, making the problem amenable to the branch and bound technique for problems of practical size. Laporte and Martello [28] formulates the selective traveling salesman problem that requires the determination of a length-constrained simple circuit with fixed starting point (the so-called depot) on a vertex-and-edge-weighted graph. They describe an exact algorithm for solving this problem that extends a simple path from the depot utilizing a breadth-first branch and bound process. Verweij and Aardal [29] consider the merchant subtour problem as finding a profit-maximizing directed, closed path (a cycle) over a vertex-and-edge-weighted and use linear programming techniques for its solution. Westerlund in his recent thesis [30] defines the traveling salesman subtour problem as the optimization problem to find a path from a specified depot on an undirected, vertex-and-edge-weighted graph with revenues and knapsack constraints on the vertex weights. This thesis provides a new formulation of the problem whose structure can be exploited by Lagrangian relaxation and using a stabilized column generation technique [31].The objective of this paper is to implement a genetic algorithm-based solver for the subtour problem. Evolutionary algorithms [32, 33] have already been proposed for the solution of the TSP and similar combinatorial problems [34–36]. Our method is a Genetic Algorithm [37–39] boosted with a heuristic local search. The tools used in this paper are common in the field of evolutionary computation, therefore the main contribution of this paper is the implementation of a solver for the Subtour Problem that can provide good-quality `motion primitives' for multiagent planners. Even though the genetic algorithm-based solution is heuristic in nature, we numerically demonstrate the efficacy of the proposed approach, benchmarking its results against exact TSP and subtour solutions. Once again, this work constitutes a starting step for developing a multiagent planner, results on which will be reported in a separate paper.The outline of the paper is as follows. First, some basic notation and the formulation of the subtour problem is introduced in Sections2 and 3. The basics of Genetic Algorithms are shortly presented in Section 4. The problem is defined in Section 5, followed by the genetic algorithm implementation in Section 6. Section 7 presents numerical results to demonstrate the efficiency of the proposed approach, including some preliminary examples for a multiagent planner. Conclusions are drawn in Section 8.


## 2. Notation

Graph theory has been instrumental for analyzing and solving problems in areas as diverse as computer network design, urban planning, and molecular biology. Graph theory has also been used to describe vehicle routing problems [40–42] and, therefore, is the natural framework for this study. The notation used in this paper is summarized below (good books on graph theory include [43, 44]).


### 2.1. Graphs, Subgraphs, Paths, and Cycles

GivenV={v1,…,vm}, a set of m elements referred to as vertices (nodes or targets), and E={(vi,vj)∣vi,vj∈V}, a set of edges connecting vertices vi and vj, a graphG is defined as the pair (V,E). All graphs considered in this work are undirected, that is, the edges are unordered pairs with the symmetry relation (vi,vj)=(vj,vi).Acomplete (also known as fully connected) graph is a graph where all vertices of V are connected to each other. The complete graph induced by the vertex set V is denoted by km(V), where m=|V| is the number of vertices. A graph G1=(V1,E1) is a subgraph of G (G1⊆G) if V1⊆V and E1⊆E such that(2.1)E1={(vi,vj)∣vi,vj∈V1}.
A subgraph P=(V1,E1) is called a path in G=(V,E) if V1 is a set of k distinct vertices of the original graph and(2.2)E1={(x1,x2),(x2,x3),…,(xk-1,xk)}⊆E
is the set of k-1 edges that connect those vertices. In other words, a path is a sequence of edges with each consecutive pair of edges having a vertex in common. Similarly, a subgraph C=(V2,E2) of G=(V,E) with(2.3)V2={x1,…,xk}⊆V,E2={(x1,x2),…,(xk-1,xk),(xk,x1)}⊆E
is called a cycle. The length of a path or cycle is the number of its edges. The set of all paths and cycles of length k in G will be denoted by 𝒫k(G) and 𝒞k(G), respectively.Paths and cycles with no repeated vertices are calledsimple. A simple path (cycle) that includes every vertex of the graph is known as a Hamiltonian path (cycle). Graph G is called weighted if a weight (or cost) w(vi,vj) is assigned to every edge (vi,vj). A weighted graph G is called symmetric if w(vi,vj)=w(vj,vi). The total cost c(·) of a path P∈𝒫k(G) is the sum of the weights of its edges(2.4)c(P)=∑i=1kw(xi,xi+1).
Analogously, for a cycle C∈𝒞k(G),(2.5)c(C)=∑i=1k-1w(xi,xi+1)+w(xk,x1).
After having introduced the necessary notation, we are now in the position to formalize the combinatorial problems of interest.


## 2.1. Graphs, Subgraphs, Paths, and Cycles

GivenV={v1,…,vm}, a set of m elements referred to as vertices (nodes or targets), and E={(vi,vj)∣vi,vj∈V}, a set of edges connecting vertices vi and vj, a graphG is defined as the pair (V,E). All graphs considered in this work are undirected, that is, the edges are unordered pairs with the symmetry relation (vi,vj)=(vj,vi).Acomplete (also known as fully connected) graph is a graph where all vertices of V are connected to each other. The complete graph induced by the vertex set V is denoted by km(V), where m=|V| is the number of vertices. A graph G1=(V1,E1) is a subgraph of G (G1⊆G) if V1⊆V and E1⊆E such that(2.1)E1={(vi,vj)∣vi,vj∈V1}.
A subgraph P=(V1,E1) is called a path in G=(V,E) if V1 is a set of k distinct vertices of the original graph and(2.2)E1={(x1,x2),(x2,x3),…,(xk-1,xk)}⊆E
is the set of k-1 edges that connect those vertices. In other words, a path is a sequence of edges with each consecutive pair of edges having a vertex in common. Similarly, a subgraph C=(V2,E2) of G=(V,E) with(2.3)V2={x1,…,xk}⊆V,E2={(x1,x2),…,(xk-1,xk),(xk,x1)}⊆E
is called a cycle. The length of a path or cycle is the number of its edges. The set of all paths and cycles of length k in G will be denoted by 𝒫k(G) and 𝒞k(G), respectively.Paths and cycles with no repeated vertices are calledsimple. A simple path (cycle) that includes every vertex of the graph is known as a Hamiltonian path (cycle). Graph G is called weighted if a weight (or cost) w(vi,vj) is assigned to every edge (vi,vj). A weighted graph G is called symmetric if w(vi,vj)=w(vj,vi). The total cost c(·) of a path P∈𝒫k(G) is the sum of the weights of its edges(2.4)c(P)=∑i=1kw(xi,xi+1).
Analogously, for a cycle C∈𝒞k(G),(2.5)c(C)=∑i=1k-1w(xi,xi+1)+w(xk,x1).
After having introduced the necessary notation, we are now in the position to formalize the combinatorial problems of interest.


## 3. The Traveling Salesman Problem and the Subtour Problem

LetT={t1,…,tn} be the set of n possible targets (goals) to be visited. The ith target ti is an object located in Euclidean space and its position is specified by the vector r(ti). The position of agent a is r(a) (Figure 2).Figure 2
The locations of the targetsT={t1,t2} and the agent a are specified by the vectors r(t1), r(t2), and r(a), respectively.Let us define the complete graphKn+1(V) generated by the augmented vertex set V=T∪a (see Figure 3).Given the set of targetsT={t1,…,t4} and the agent a, (b) shows the augmented vertex set V={v1,…,v5}=T∪a,  where (v5=a), while (c) shows the complete graph K5(V) generated by the augmented vertex set V.
(a)
Targets and agent(b)
Vertex setV=T∪a(c)
Complete graphK5(V)The weights associated with the edges are given by the Euclidean distance between the corresponding locations, that is,w(vi,vj)=w(vj,vi)=∥r(vi)-r(vj)∥, with vi,vj∈V, rendering Kn+1(V) a weighted and symmetric graph.TheSubtour Problem is now defined as finding a simple path P∈𝒫k(Kn+1(V)) of length k, starting at vertex x1=a and having the lowest cost c(P)=∑i=1kw(xi,xi+1). If k=n, the problem is equivalent to finding the “cheapest” Hamiltonian path, where all the n targets in T are to be visited (Figure 4(c)). The general Traveling Salesman Problem, or k-TSP, poses to find a simple cycle C∈𝒞k+1(Kn+1(V)) of minimal cost starting and ending at vertex a, visiting k targets. The special case of k-TSP is the classical traveling salesman problem, where C is a Hamiltonian cycle with minimal cost that visits all the n targets (Figure 4(e)).(a) Given the set of targetsT={t1,…,t4} and the agent a, V={v1,…,v5}=T∪a, with v5=a, is the augmented vertex set. In (b), a subtour of length 2 (the agent visits the targets associated with the vertices v2 and v1) is shown, while in (c), the cheapest Hamiltonian path (the agent visits all the given targets) is depicted. (d) shows the k-TSP with k=3, and in (e), the optimal solution of the Traveling Salesman Problem is drawn.
(a)
Targets and agent(b)
Subtour in𝒫2(K5)(c)
Hamiltonian path in𝒫4(K5)(d)
k-TSP in 𝒞4(K5(V))(e)
Classic TSPThe solution of the single agent planning problem is of great interest in our research, since a collection of Subtours will represent the starting solution for solving the multiagent planning problem. The multiagent planning problem [45] can be considered as a variant of the classical Multiple Traveling Salesman Problem, and can be formulated as follows. Let T={t1,…,tn} be the set of n targets to be visited and let a denote the unique depot the m agents share. The augmented vertex set is given by V=T∪a and the configuration space of the problem is the complete graph Kn+1(V).LetCi denote a cycle of length ki starting and ending at vertex a (the depot). The Multiple Traveling Salesmen Problem can be formulated as finding m cycles Ci of length ki(3.1)ℂ={C1,…,Cm},∑i=1mki=n+m,
such that each target is visited only once and by only one agent and the sum of the costs of all the m tours Ci(3.2)𝒲(ℂ)=∑i=1m𝒲(Ci)
is minimal.


## 4. Solving Combinatorial Planning Problems with Genetic Algorithms

The obvious difficulty with the subtour and the classic traveling salesman problem (TSP) is their combinatorial nature (they are NP-hard, and there is no known deterministic algorithm that solves them in polynomial time).For a TSP withn targets, there are (1/2)(n-1)! possible solutions, while for a Subtour Problem with 2≤k≤n visited targets, the number of possible solutions is n!/(n-k)!. Even though the dimension of the “search space” differs significantly for the two problems, a brute force approach is infeasible when n is large. A variety of exact algorithms (e.g., branch-and-bound algorithms and linear programming [46–48]) have been proposed to solve the classic TSP, and methods such as genetic algorithms, simulated annealing, and ant system were developed [34, 36] to sacrifice the optimality for a near-optimal solution obtained in shorter time or by simpler algorithms [49]. Greedy algorithms in many cases provide reasonable solutions to combinatorial problems. Such an algorithm could be connecting targets that are closest to one another. However, recent results on the nth nearest neighbor distribution of optimal TSP tours [50] show that this approach might be too simplistic.The method proposed here is a genetic algorithm [37–39] and is capable of solving the subtour problem, as well as the classic TSP.


### 4.1. Genetic Algorithms

A genetic algorithm (GA) is an optimization technique used to find approximate solutions of optimization problems [38]. Genetic algorithms are a particular class of evolutionary methods that use techniques inspired by Darwin's theory of evolution and evolutionary biology, such as inheritance, mutation, selection, and crossover (also called recombination). In these systems, populations of solutions compete and only the fittest survive.


#### 4.1.1. Cast of Characters of a Genetic Algorithm

Figure5 introduces the cast of characters of a GA.Figure 5
Cast of characters for genetic algorithms: allele set, genes, chromosomes, and population.The allele set is defined as the setL={gi} of l objects called genes. In a genetic algorithm, a possible solution is represented by a chromosome s (also called plan or individual), which is a sequence of k genes xi∈L (genes are the “building bricks” chromosomes are made of):(4.1)s=(x1,…,xk).
The length of a chromosome is the number of its genes. The jth gene in s will simply be denoted by s(j).A genetic algorithm works with a population of candidate solutions. A population composed ofp chromosomes si, with i=1,…,p, is Sp=[s1,…,sp]. Depending on the problem, chromosomes can have variable lengths; here, we work with fixed-length chromosomes.


#### 4.1.2. The Structure of Genetic Algorithms

A GA consists of two distinct components: the initialization and evolution phases. In the initialization phase (see Section6.1), a starting population is created—usually randomly—and is then evolved through a number of generations (see Section 6.2). At every generation step, some individuals, called parents, are chosen via a selection method and mated, that is, the parental genes are recombined through the use of genetic operators. The newly generated chromosomes (also called offspring) are evaluated by a predefined fitness function f(·) and the weakest (least fit) chromosomes are discarded.The objective of the GA is to improve the fitness of the chromosomes by evolving the population according to a set of rules until desirable solutions are found. Figure6 depicts the schematic representation of a classic GA, where the most important parts of the algorithm—selection phase, genetic operators, and evaluation phase—are presented. Usually, some stopping criterion is used to decide when the population contains solutions that are “good enough". In this work, the simulations are stopped after a fixed number of iterations, since the main goal of the paper is to demonstrate our approach.Figure 6
Flowchart of a basic genetic algorithm.


## 4.1. Genetic Algorithms

A genetic algorithm (GA) is an optimization technique used to find approximate solutions of optimization problems [38]. Genetic algorithms are a particular class of evolutionary methods that use techniques inspired by Darwin's theory of evolution and evolutionary biology, such as inheritance, mutation, selection, and crossover (also called recombination). In these systems, populations of solutions compete and only the fittest survive.


### 4.1.1. Cast of Characters of a Genetic Algorithm

Figure5 introduces the cast of characters of a GA.Figure 5
Cast of characters for genetic algorithms: allele set, genes, chromosomes, and population.The allele set is defined as the setL={gi} of l objects called genes. In a genetic algorithm, a possible solution is represented by a chromosome s (also called plan or individual), which is a sequence of k genes xi∈L (genes are the “building bricks” chromosomes are made of):(4.1)s=(x1,…,xk).
The length of a chromosome is the number of its genes. The jth gene in s will simply be denoted by s(j).A genetic algorithm works with a population of candidate solutions. A population composed ofp chromosomes si, with i=1,…,p, is Sp=[s1,…,sp]. Depending on the problem, chromosomes can have variable lengths; here, we work with fixed-length chromosomes.


### 4.1.2. The Structure of Genetic Algorithms

A GA consists of two distinct components: the initialization and evolution phases. In the initialization phase (see Section6.1), a starting population is created—usually randomly—and is then evolved through a number of generations (see Section 6.2). At every generation step, some individuals, called parents, are chosen via a selection method and mated, that is, the parental genes are recombined through the use of genetic operators. The newly generated chromosomes (also called offspring) are evaluated by a predefined fitness function f(·) and the weakest (least fit) chromosomes are discarded.The objective of the GA is to improve the fitness of the chromosomes by evolving the population according to a set of rules until desirable solutions are found. Figure6 depicts the schematic representation of a classic GA, where the most important parts of the algorithm—selection phase, genetic operators, and evaluation phase—are presented. Usually, some stopping criterion is used to decide when the population contains solutions that are “good enough". In this work, the simulations are stopped after a fixed number of iterations, since the main goal of the paper is to demonstrate our approach.Figure 6
Flowchart of a basic genetic algorithm.


## 4.1.1. Cast of Characters of a Genetic Algorithm

Figure5 introduces the cast of characters of a GA.Figure 5
Cast of characters for genetic algorithms: allele set, genes, chromosomes, and population.The allele set is defined as the setL={gi} of l objects called genes. In a genetic algorithm, a possible solution is represented by a chromosome s (also called plan or individual), which is a sequence of k genes xi∈L (genes are the “building bricks” chromosomes are made of):(4.1)s=(x1,…,xk).
The length of a chromosome is the number of its genes. The jth gene in s will simply be denoted by s(j).A genetic algorithm works with a population of candidate solutions. A population composed ofp chromosomes si, with i=1,…,p, is Sp=[s1,…,sp]. Depending on the problem, chromosomes can have variable lengths; here, we work with fixed-length chromosomes.


## 4.1.2. The Structure of Genetic Algorithms

A GA consists of two distinct components: the initialization and evolution phases. In the initialization phase (see Section6.1), a starting population is created—usually randomly—and is then evolved through a number of generations (see Section 6.2). At every generation step, some individuals, called parents, are chosen via a selection method and mated, that is, the parental genes are recombined through the use of genetic operators. The newly generated chromosomes (also called offspring) are evaluated by a predefined fitness function f(·) and the weakest (least fit) chromosomes are discarded.The objective of the GA is to improve the fitness of the chromosomes by evolving the population according to a set of rules until desirable solutions are found. Figure6 depicts the schematic representation of a classic GA, where the most important parts of the algorithm—selection phase, genetic operators, and evaluation phase—are presented. Usually, some stopping criterion is used to decide when the population contains solutions that are “good enough". In this work, the simulations are stopped after a fixed number of iterations, since the main goal of the paper is to demonstrate our approach.Figure 6
Flowchart of a basic genetic algorithm.


## 5. Subtour Problem: Formulation and Coding

In this work, a genetic algorithm (GA) has been designed to solve the subtour problem on the complete graphKn+1(V), where V=T∪a, T={t1,…,tn} is the set of n targets and a is the agent. More precisely, the GA attempts to find the shortest possible simple path P∈𝒫k(Kn+1(V)) starting from vertex a for 1≤k≤n targets. The GA presented here can also solve the k-TSP (k=n is the classic traveling salesman problem), finding a simple cycle C∈𝒞k+1(Kn+1(V)) of low cost for visiting k targets.Having defined the problem, the next step is to choose a suitable representation of solutions to the problem in terms of genes and chromosomes. Since the solutions of the subtour problem are simple pathsP∈𝒫k(Kn+1(V)), the set V=T∪a is designated as the allele set, and chromosomes are easily coded as the sequence of targets of the path in the order they are visited by the agent. The first element of a chromosome is always a, since the starting point of the agent is r(a). Therefore, a generic chromosome/path is represented as s=(x1,x2,…,xk), with x1=a and xi∈T. An additional constraint on the structure of the chromosome is imposed by the simplicity of the path (every target should be visited only once) therefore; the same gene must not appear in the chromosome more than once. The coding for the k-TSP is similar.The total costc(·) of a chromosome/path s=(x1,…,xk) is the sum of the weights of its edges (in other words the distance between targets)(5.1)c(s)=∑i=2k∥r(xi)-r(xi-1)∥,
while its fitness value is defined as 1/c(s) (the lower the cost, the higher the fitness and vice versa).The above representation is called order based, and the fitness of an individual depends on the order of the genes in the chromosome, as opposed to the traditional representation where the order is not important [38]. As an example, consider agent a and the complete graph Km(V) generated by the augmented vertex set V (with |V|=m). A generic path P=(V1,E1)∈𝒫k(Km(V)), with V1={x1,…,xk+1}, E1={(x1,x2),…,(xk,xk+1)} and x1=a, is coded in the chromosome s=(x1,…,xk+1) (see Figure 7).Order-based representation: the chromosome (possible solution) is coded as the sequence of visited targets. In (a), the set of targetsT={t1,…,t5} and the agent a are shown. In (b), a path visiting 4 targets (P∈𝒫4(K6(V))) is illustrated on the vertex set V=T∪a. The associated chromosome is represented as the sequence of the visited targets, with a=v6, thus s=(a,t1,t3,t5,t2) (see (c)).
(a)
Targets and agents(b)
Path in𝒫4(K6(V))(c)
ChromosomeA class of genetic operators have been developed for the variants of thek-TSP [38, 51] and some of these are described in the following (see Section 6.3).


## 6. Implementation of the Genetic Algorithm

In this section, a fixed-length chromosome implementation of the genetic algorithm (GA) for solving the subtour problem is described. The two main components of the GA are the initialization and the evolution phases.


### 6.1. Initialization Phase

The starting population of chromosomes determines not only the starting point for the evolutionary search, but also the effectiveness of the algorithm. One of the problems using GA is that the algorithm could prematurely converge to local minima instead of exploring more of the search space. This occurs when the population quickly reaches a state where the genetic operators can no longer produce offsprings outperforming their parents [52]. It is important to point out that the size of the starting population also influences the performance of the algorithm, since a population too small can lead to premature convergence, while a big one could bring the computation to a crawl.For the combinatorial problems of interest, a hard constraint is enforced: every gene (representing a target) must only be present once in every chromosome.


### 6.2. Genetic Evolution Phase

After the initialization phase, the initial population is evolved. The chromosomes of theith generation are combined, mutated and improved through genetic operators (see Section 6.3) to create new chromosomes (the offsprings). These are then evaluated by the fitness function: the weakest (least fit) solutions are discarded while the good ones are kept for the i+1th generation. The evolution phase consists of three main parts: selection of parents, application of genetic operators and creation of a new population by evaluation of the offsprings. If during the selection phase two identical parents are chosen, the recombination process may result in duplication of chromosomes which may decrease the heterogeneity of the population. This could lead to the quick reduction of the coverage of the search space and the consequently fast and irreversible convergence towards local minima far away from the optimal solution.This premature convergence is not desirable and different methods have been devised to get around this problem. For example, in the random offspring generation technique [51] the genetic operators are applied only if the genetic materials of the parents are different, otherwise at least one of the offsprings is randomly generated. Other, even more drastic, solutions have been proposed. In [53] the social disasters technique is applied to the TSP in order to maintain the genetic diversity of the population. This method checks the heterogeneity of the population and, if necessary, replaces a number of selected chromosomes by randomly generated ones.To counter the effect of premature convergence, we decided to maintain heterogeneity of the populations by introducing what we call asingular mating pool. This pool is created at each generation step from the population by removing all duplicates. Consequently, if the population has n individuals, the singular mating pool is always composed of nSMP≤n solutions. With this method, the probability of mating identical chromosomes is reduced. However, note that an individual can be selected and mated more than once. The singular mating pool does not preclude the duplication of individuals, it only reduces its frequency, resulting in a higher diversity of the solutions and avoiding premature convergence.For the selection phase the Tournament Selection method [38, 54] is adopted. A subset of the nSMP chromosomes is randomly chosen from the Singular Mating Pool and the best chromosome is selected for the so-called mating pool. This process is repeated until a predefined number of individuals, ntournament, is reached (in our simulations ntournament=nSMP/2).From the mating pool two parents are randomly selected, and to these, the genetic operators are applied with some predefined probability (see Section6.3). This process is repeated until nnew offsprings have been generated. These new chromosomes are then added to the singular mating pool (of size nSMP), returning a new temporary population of size ntemp=nSMP+nnew. In this work, nnew is chosen such that ntemp=1.5n. Since the required number of chromosomes in a population is n, the ntemp-n=n/2 weakest individuals (the ones with the highest cost c, c.f. (5.1)) are discarded. The adopted schema is shown in Figure 8.Figure 8
Genetic algorithm schema with the singular mating pool technique and the application of the genetic operators. Note that given two parents, first the crossover operator is applied, followed by the mutation. The offsprings are then “boosted” with the 2-opt method.


### 6.3. Genetic Operators

Genetic operators combine existing solutions into new ones (crossover) or introduce random variations (mutation) to maintain genetic diversity. These operators are applied in a fixed order (shown in Figure8) with a priori assigned probabilities. In addition to these operators, the heuristic 2-opt method to directly improve the fitness of the offsprings is used (see Section 6.3.4).Different crossover typologies have been developed for solving the classic TSP, including the partially matched crossover, order crossover, and cycle crossover operators [38]. These operators are all based on the constraint that TSP solutions include all the targets. Since this is not the case for the Subtour Problem, these operators cannot be directly applied. To overcome these limitations, we modified the classic operators according to the new problem constraints. In particular, we decided to use a standard genes recombination mechanism, while changing the rules for keeping the feasibility of the solutions.


#### 6.3.1. Single Cutting-Point Crossover

With the single cutting-point crossover (applied with probabilitypXO), both parents are halved at the same gene, the cutting point (see Figure 9).Figure 9
Single cutting-point crossover: parents are halved at the same gene.The cutting point is chosen either randomly or to break the longest edge in the parents (withplong-cut probability). Once the parents have been halved, two offsprings are created combining the first (second) half of the first parent with the second (first) half of the second parent, respectively. Care is taken to avoid duplication of genes (as every target should only be visited once) and the length of the chromosomes is kept constant. See Appendix A for an illustrative example.


#### 6.3.2. Double Cutting-Point Crossover

The double cutting-point crossover operator cuts the parents at two different genes (see Figure10), with probability pDXO.  The locations of the cutting points are chosen either randomly or to cut the longest edge in the parents (with plong-cut probability). The latter introduces an improvement over the single cutting-point operator, where only one parent was cut along its longest edge and this point was also used for the other parent. An important consequence of having two different cutting points is that the halves will in general have different number of genes. A simple recombination would thus lead to two offsprings with different lengths. The technique to maintain the original size of the chromosomes (which is necessary for producing feasible solutions) is described in Appendix B.Figure 10
Double cutting-point crossover: parents are cut at two different genes.


#### 6.3.3. Mutation Operator

After the application of the crossover operator, the mutation operator is applied to the new chromosomes withpmutation. The mutation operator generates a new offspring by randomly swapping genes (Figure 11) and/or randomly changing a gene to another one that is not already present in the chromosome (Figure 12). Note that with the simple TSP, this second type of mutation would not be possible, because there a chromosome already contains all possible genes. The probability of the mutation is a parameter of the genetic algorithm.Given a chromosomes1=(a,t1,t4,t3,t2,t5) (shown in (a)), (b) shows the chromosome s2=(a,t1,t2,t3,t4,t5) resulting after genes t4 and t2 are swapped.
(a)
Before gene swapping(b)
After gene swappingGiven a chromosomes1=(a,t1,t2,t3) (shown in (a)), (b) shows the chromosome s2=(a,t1,t4,t3) after t2 mutated into t4.
(a)
Before gene mutation(b)
After gene mutation


#### 6.3.4. Improving Offsprings

A common approach for improving the TSP solutions is the coupling of the genetic algorithm with a heuristic boosting technique. The local search method adopted here is the 2-opt method [55–57] that replaces solutions with better ones from their “neighborhood”.Let us consider a setT of n targets and the corresponding complete and weighted graph Kn+1(V) (V=T∪a with a being the agent). Let us consider a subtour P∈𝒫k(Kn+1), with 1≤k≤n, coded in the chromosome s=(x1,…,xk). The 2-opt method determines whether the inequality(6.1)w(xi,xi+1)+w(xj,xj+1)>w(xi,xj)+w(xi+1,xj+1),
between the four vertices xi, xi+1, xj and xj+1 of P holds, in which case edges (xi,xi+1) and (xj,xj+1) are replaced with the edges (xi,xj) and (xi+1,xj+1), respectively. This method provides a shorter path without intersecting edges. Consequently, the order of genes in the chromosome changes [58] (see Figure 13). This operator is applied with p2-opt probability.In this example the effects of the application of the 2-opt method are illustrated. In (a) chromosomes2=(a,t1,t2,t3,t4,t5,t6,t7) is shown. Since edge (t1,t2) crosses (t5,t6), (6.1) is satisfied and (b) shows chromosome s2=(a,t1,t5,t4,t3,t2,t6,t7) after edges (t1,t5) and (t2,t6) have been replaced by edges (t1,t2) and (t5,t6), respectively.
(a)
Before the application of the 2-opt method(b)
After the application of the 2-opt method


## 6.1. Initialization Phase

The starting population of chromosomes determines not only the starting point for the evolutionary search, but also the effectiveness of the algorithm. One of the problems using GA is that the algorithm could prematurely converge to local minima instead of exploring more of the search space. This occurs when the population quickly reaches a state where the genetic operators can no longer produce offsprings outperforming their parents [52]. It is important to point out that the size of the starting population also influences the performance of the algorithm, since a population too small can lead to premature convergence, while a big one could bring the computation to a crawl.For the combinatorial problems of interest, a hard constraint is enforced: every gene (representing a target) must only be present once in every chromosome.


## 6.2. Genetic Evolution Phase

After the initialization phase, the initial population is evolved. The chromosomes of theith generation are combined, mutated and improved through genetic operators (see Section 6.3) to create new chromosomes (the offsprings). These are then evaluated by the fitness function: the weakest (least fit) solutions are discarded while the good ones are kept for the i+1th generation. The evolution phase consists of three main parts: selection of parents, application of genetic operators and creation of a new population by evaluation of the offsprings. If during the selection phase two identical parents are chosen, the recombination process may result in duplication of chromosomes which may decrease the heterogeneity of the population. This could lead to the quick reduction of the coverage of the search space and the consequently fast and irreversible convergence towards local minima far away from the optimal solution.This premature convergence is not desirable and different methods have been devised to get around this problem. For example, in the random offspring generation technique [51] the genetic operators are applied only if the genetic materials of the parents are different, otherwise at least one of the offsprings is randomly generated. Other, even more drastic, solutions have been proposed. In [53] the social disasters technique is applied to the TSP in order to maintain the genetic diversity of the population. This method checks the heterogeneity of the population and, if necessary, replaces a number of selected chromosomes by randomly generated ones.To counter the effect of premature convergence, we decided to maintain heterogeneity of the populations by introducing what we call asingular mating pool. This pool is created at each generation step from the population by removing all duplicates. Consequently, if the population has n individuals, the singular mating pool is always composed of nSMP≤n solutions. With this method, the probability of mating identical chromosomes is reduced. However, note that an individual can be selected and mated more than once. The singular mating pool does not preclude the duplication of individuals, it only reduces its frequency, resulting in a higher diversity of the solutions and avoiding premature convergence.For the selection phase the Tournament Selection method [38, 54] is adopted. A subset of the nSMP chromosomes is randomly chosen from the Singular Mating Pool and the best chromosome is selected for the so-called mating pool. This process is repeated until a predefined number of individuals, ntournament, is reached (in our simulations ntournament=nSMP/2).From the mating pool two parents are randomly selected, and to these, the genetic operators are applied with some predefined probability (see Section6.3). This process is repeated until nnew offsprings have been generated. These new chromosomes are then added to the singular mating pool (of size nSMP), returning a new temporary population of size ntemp=nSMP+nnew. In this work, nnew is chosen such that ntemp=1.5n. Since the required number of chromosomes in a population is n, the ntemp-n=n/2 weakest individuals (the ones with the highest cost c, c.f. (5.1)) are discarded. The adopted schema is shown in Figure 8.Figure 8
Genetic algorithm schema with the singular mating pool technique and the application of the genetic operators. Note that given two parents, first the crossover operator is applied, followed by the mutation. The offsprings are then “boosted” with the 2-opt method.


## 6.3. Genetic Operators

Genetic operators combine existing solutions into new ones (crossover) or introduce random variations (mutation) to maintain genetic diversity. These operators are applied in a fixed order (shown in Figure8) with a priori assigned probabilities. In addition to these operators, the heuristic 2-opt method to directly improve the fitness of the offsprings is used (see Section 6.3.4).Different crossover typologies have been developed for solving the classic TSP, including the partially matched crossover, order crossover, and cycle crossover operators [38]. These operators are all based on the constraint that TSP solutions include all the targets. Since this is not the case for the Subtour Problem, these operators cannot be directly applied. To overcome these limitations, we modified the classic operators according to the new problem constraints. In particular, we decided to use a standard genes recombination mechanism, while changing the rules for keeping the feasibility of the solutions.


### 6.3.1. Single Cutting-Point Crossover

With the single cutting-point crossover (applied with probabilitypXO), both parents are halved at the same gene, the cutting point (see Figure 9).Figure 9
Single cutting-point crossover: parents are halved at the same gene.The cutting point is chosen either randomly or to break the longest edge in the parents (withplong-cut probability). Once the parents have been halved, two offsprings are created combining the first (second) half of the first parent with the second (first) half of the second parent, respectively. Care is taken to avoid duplication of genes (as every target should only be visited once) and the length of the chromosomes is kept constant. See Appendix A for an illustrative example.


### 6.3.2. Double Cutting-Point Crossover

The double cutting-point crossover operator cuts the parents at two different genes (see Figure10), with probability pDXO.  The locations of the cutting points are chosen either randomly or to cut the longest edge in the parents (with plong-cut probability). The latter introduces an improvement over the single cutting-point operator, where only one parent was cut along its longest edge and this point was also used for the other parent. An important consequence of having two different cutting points is that the halves will in general have different number of genes. A simple recombination would thus lead to two offsprings with different lengths. The technique to maintain the original size of the chromosomes (which is necessary for producing feasible solutions) is described in Appendix B.Figure 10
Double cutting-point crossover: parents are cut at two different genes.


### 6.3.3. Mutation Operator

After the application of the crossover operator, the mutation operator is applied to the new chromosomes withpmutation. The mutation operator generates a new offspring by randomly swapping genes (Figure 11) and/or randomly changing a gene to another one that is not already present in the chromosome (Figure 12). Note that with the simple TSP, this second type of mutation would not be possible, because there a chromosome already contains all possible genes. The probability of the mutation is a parameter of the genetic algorithm.Given a chromosomes1=(a,t1,t4,t3,t2,t5) (shown in (a)), (b) shows the chromosome s2=(a,t1,t2,t3,t4,t5) resulting after genes t4 and t2 are swapped.
(a)
Before gene swapping(b)
After gene swappingGiven a chromosomes1=(a,t1,t2,t3) (shown in (a)), (b) shows the chromosome s2=(a,t1,t4,t3) after t2 mutated into t4.
(a)
Before gene mutation(b)
After gene mutation


### 6.3.4. Improving Offsprings

A common approach for improving the TSP solutions is the coupling of the genetic algorithm with a heuristic boosting technique. The local search method adopted here is the 2-opt method [55–57] that replaces solutions with better ones from their “neighborhood”.Let us consider a setT of n targets and the corresponding complete and weighted graph Kn+1(V) (V=T∪a with a being the agent). Let us consider a subtour P∈𝒫k(Kn+1), with 1≤k≤n, coded in the chromosome s=(x1,…,xk). The 2-opt method determines whether the inequality(6.1)w(xi,xi+1)+w(xj,xj+1)>w(xi,xj)+w(xi+1,xj+1),
between the four vertices xi, xi+1, xj and xj+1 of P holds, in which case edges (xi,xi+1) and (xj,xj+1) are replaced with the edges (xi,xj) and (xi+1,xj+1), respectively. This method provides a shorter path without intersecting edges. Consequently, the order of genes in the chromosome changes [58] (see Figure 13). This operator is applied with p2-opt probability.In this example the effects of the application of the 2-opt method are illustrated. In (a) chromosomes2=(a,t1,t2,t3,t4,t5,t6,t7) is shown. Since edge (t1,t2) crosses (t5,t6), (6.1) is satisfied and (b) shows chromosome s2=(a,t1,t5,t4,t3,t2,t6,t7) after edges (t1,t5) and (t2,t6) have been replaced by edges (t1,t2) and (t5,t6), respectively.
(a)
Before the application of the 2-opt method(b)
After the application of the 2-opt method


## 6.3.1. Single Cutting-Point Crossover

With the single cutting-point crossover (applied with probabilitypXO), both parents are halved at the same gene, the cutting point (see Figure 9).Figure 9
Single cutting-point crossover: parents are halved at the same gene.The cutting point is chosen either randomly or to break the longest edge in the parents (withplong-cut probability). Once the parents have been halved, two offsprings are created combining the first (second) half of the first parent with the second (first) half of the second parent, respectively. Care is taken to avoid duplication of genes (as every target should only be visited once) and the length of the chromosomes is kept constant. See Appendix A for an illustrative example.


## 6.3.2. Double Cutting-Point Crossover

The double cutting-point crossover operator cuts the parents at two different genes (see Figure10), with probability pDXO.  The locations of the cutting points are chosen either randomly or to cut the longest edge in the parents (with plong-cut probability). The latter introduces an improvement over the single cutting-point operator, where only one parent was cut along its longest edge and this point was also used for the other parent. An important consequence of having two different cutting points is that the halves will in general have different number of genes. A simple recombination would thus lead to two offsprings with different lengths. The technique to maintain the original size of the chromosomes (which is necessary for producing feasible solutions) is described in Appendix B.Figure 10
Double cutting-point crossover: parents are cut at two different genes.


## 6.3.3. Mutation Operator

After the application of the crossover operator, the mutation operator is applied to the new chromosomes withpmutation. The mutation operator generates a new offspring by randomly swapping genes (Figure 11) and/or randomly changing a gene to another one that is not already present in the chromosome (Figure 12). Note that with the simple TSP, this second type of mutation would not be possible, because there a chromosome already contains all possible genes. The probability of the mutation is a parameter of the genetic algorithm.Given a chromosomes1=(a,t1,t4,t3,t2,t5) (shown in (a)), (b) shows the chromosome s2=(a,t1,t2,t3,t4,t5) resulting after genes t4 and t2 are swapped.
(a)
Before gene swapping(b)
After gene swappingGiven a chromosomes1=(a,t1,t2,t3) (shown in (a)), (b) shows the chromosome s2=(a,t1,t4,t3) after t2 mutated into t4.
(a)
Before gene mutation(b)
After gene mutation


## 6.3.4. Improving Offsprings

A common approach for improving the TSP solutions is the coupling of the genetic algorithm with a heuristic boosting technique. The local search method adopted here is the 2-opt method [55–57] that replaces solutions with better ones from their “neighborhood”.Let us consider a setT of n targets and the corresponding complete and weighted graph Kn+1(V) (V=T∪a with a being the agent). Let us consider a subtour P∈𝒫k(Kn+1), with 1≤k≤n, coded in the chromosome s=(x1,…,xk). The 2-opt method determines whether the inequality(6.1)w(xi,xi+1)+w(xj,xj+1)>w(xi,xj)+w(xi+1,xj+1),
between the four vertices xi, xi+1, xj and xj+1 of P holds, in which case edges (xi,xi+1) and (xj,xj+1) are replaced with the edges (xi,xj) and (xi+1,xj+1), respectively. This method provides a shorter path without intersecting edges. Consequently, the order of genes in the chromosome changes [58] (see Figure 13). This operator is applied with p2-opt probability.In this example the effects of the application of the 2-opt method are illustrated. In (a) chromosomes2=(a,t1,t2,t3,t4,t5,t6,t7) is shown. Since edge (t1,t2) crosses (t5,t6), (6.1) is satisfied and (b) shows chromosome s2=(a,t1,t5,t4,t3,t2,t6,t7) after edges (t1,t5) and (t2,t6) have been replaced by edges (t1,t2) and (t5,t6), respectively.
(a)
Before the application of the 2-opt method(b)
After the application of the 2-opt method


## 7. Results

A large number of simulations have been performed to test the performance of the implemented genetic algorithm. In order to evaluate the proposed method and provide statistically significant results, different problem configurations have been considered, including randomly generated problems and problems with known optimal solutions. Unless otherwise specified, the tests described here are all run for 250 generations with a population size of 200 chromosomes. The crossover, mutation, and boosting (2-opt) operators are applied with apXO=pDXO=70%, pmutation=20%, and p2-opt=50% probability, respectively. Table 1 summarizes the parameters and their default values adopted for the simulations.Table 1
Simulation parameters.
ParameterSymbolValuePopulation sizen200 chromosomesTemporary population sizentemp300 chromosomesSingle cutting point crossover probabilitypXO70%Double cutting point crossover probabilitypDXO70%Mutation probabilitypmutation20%2-opt method probabilityp2-opt50%Probability of cutting the longest edgeplong-cut50%The speed and optimality of any genetic algorithm depend on many parameters and the stopping criterion. The below results will demonstrate the efficacy of the proposed algorithm even without excessive tweaking of the parameters. In addition, it is important to note that due to the stochastic nature of the GA, convergence to optimal solutions can not be guaranteed. The fact that for many test problems with known optimal solution, these solutions were reached lends credence to our approach.


### 7.1. Avoiding Premature Convergence

Premature convergence was defined previously as fast convergence of the genetic algorithm towards a local minimum in the search space. Tests have been conducted to illustrate how the implementation of the singular mating pool technique described in Section6.2 prevents premature convergence. All the tests in this Section have been performed on a TSP with 600 targets randomly distributed over the unit square. The GA parameters are reported in Table 1.The maximum and the minimum fitness values are plotted as the function of the population age (generation number) in Figure14(a) for a simulation where duplicates are not removed from the populations (i.e., without using the singular mating pool technique). It can be observed that the range of fitness values (the width between the lines corresponding to the extrema) rapidly approaches zero as the consequence of the decreasing heterogeneity of successive populations, leading to a final population composed of identical chromosomes. Moreover, this is a local minimum, since none of the resulting solutions is optimal. It is also interesting to note what happens when a new, better solution is introduced into a stagnant genetic pool. In Figure 14(a),  solutions seem to have reached a constant fitness value (the plateau around the 80th generation), when a better chromosome randomly appears in the population around the 120th generation.(a) Simulation without using the singular mating pool. The duplicated chromosomes lead to premature convergence. (b) Simulation with the singular mating pool technique. With duplicate chromosomes removed from the populations, the diversity of solutions is maintained.
(a)
The singular mating pool is not used(b)
The singular mating pool is usedSince during the evolution the duplicates of this chromosome are not discarded (its fitness value is better than those of the other solutions), in a small number of generations they replicate and replace all other individuals.Figure14(b) shows the extremal values of fitness in a simulation where the duplicates are constantly removed from the mating pool; that is, where the singular mating pool method is used. As a result of this strategy the diversity of the populations is maintained with an increased coverage of the search space. This makes it more likely for the algorithm to reach a near-optimal solution (in this case, the optimal result is reached).To characterize the heterogeneity/diversity of a population, a pairwise comparison of chromosome edges can be used. Let us consider two chromosomes of lengthk, si, and sj, with edge sets Ei and Ej, respectively (|Ei|=|Ej|). One possible measure of diversity can be defined as(7.1)di,j=1-|Ei∩Ej||Ei|.Thisedge diversity quantifies how much two chromosomes differ. The exact locations of identical edges do not influence this diversity measure. The edge diversity of the entire population Sp is the averaged edge diversities for all pairs(7.2)DSp=1n(n-1)∑i=1p-1∑j=i+1pdi,j.
Clearly, 0≤DSp≤1. We also introduce a “Boolean” diversity. The diversity of two chromosomes are equal if and only if they have identical edges. The Boolean diversity for population Sp is defined as(7.3)BSp=∑i=1p-1∑j=i+1p{0ifdi,j=0,1ifdi,j≠0.Figure15 shows the average edge and boolean diversity at every generation step for the simulations used for Figure 14 (with or without the use of the singular mating pool technique).How the application of the singular mating pool technique affects the edge (a) and boolean (b) diversity (%) of the population.
(a)
Edge diversity(b)
Boolean diversityThe decrease of the edge diversity can be explained by the reduction of the coverage of the search space: many costly edges are discarded early in the evolution and only considered again during the search process with low probability. This is why at later generations many solutions differ only by few edges, but still the population maintains its heterogeneity (as shown in Figure15(b)).In conclusion, to avoid premature convergence it is important to ensure that the evolving population contains a variety of chromosomes (representing different strategies for the agent to reach a set of targets). In our work on distributed planning (published in the sequel), the availability of these different strategies will have special significance.


### 7.2. Influence of the 2-opt Method on the Performance of Genetic Operators

To evaluate the performance of the different genetic operators and the 2-opt method, various tests have been performed. A target configuration forn=100 targets randomly and uniformly distributed over the unit square is generated. This configuration is kept fixed for all tests in this section to make comparisons meaningful. The 30-from-100 subtour problem is then solved with different combinations of the genetic operators, 100 times for each combination. The application probabilities of the operators are reported in Table 1. To assess the influence of the various genetic operators, their performances are directly compared and tested without the 2-opt method. The mean values and the variances of the distribution of the best (highest) fitness values of the final populations are shown in Table 2.Table 2
Simulation cases to test efficiency of different genetic operators. The 2-opt method is not applied.
Crossover typeMutationMean fitnessVariance of fitnessDouble pointApplied11Single pointApplied0.931.32Double pointNot applied0.921.47Single pointNot applied0.692.12Since the optimal solution is not known, the mean fitness values and the variances of fitness are normalized by the best result (the highest for the fitness values and the lowest for the variances of fitness). The comparison of the quantities in Table2 shows that the combined application of the double cutting-point crossover and the mutation operator yields the maximum fitness value and the minimum variance of the solutions. On the other hand, the worst solutions are obtained with the standalone application of the single cutting point crossover operator. These results not only demonstrate the improvement introduced by the double cutting point crossover, but also clearly highlight the importance of the mutation operator.With the application of the 2-opt method, the results change, as shown in Table3.Table 3
Simulation cases to test efficiency of different genetic operators together with the 2-opt method.
Crossover typeMutationMean fitnessVariance of fitnessDouble pointApplied0.9933.12Single pointApplied11Double pointNot applied0.9942.62Single pointNot applied0.9981.31In this case, the performance of the single cutting-point crossover operator coupled with mutations is the best. It would be tempting to conclude that this configuration of the genetic operators is the best; however, in the next section it is demonstrated that the speed of convergence for this configuration of operators is significantly worse than for the double cutting-point crossover/mutation combo (here, this fact is hidden as the genetic algorithm is run for a fixed number of generations).


### 7.3. Speed of Convergence and Genetic Operators

The results of the previous section clearly demonstrate the efficiency of coupling the genetic operators with the 2-opt method. The most important improvement introduced by the 2-opt method is in the speed of convergence that is here intended as the number of generation the algorithm requires for converging (it is not related to time). In fact, because of its capability of detecting new local minima at each generation step, the application of the 2-opt method together with the double cutting-point crossover and the mutation operators helps the GA to converge faster than without [56]. To quantify the speed of convergence with various genetic operators and the 2-opt method, the required number of generations for the convergence of the genetic algorithm is calculated. To facilitate this test, a 100-target TSP with known exact solution was solved (KroA-100 TSP [59], with optimal path-length of 21282). For different combinations of the genetic operators, Table 4 reports the number of generations (and its variance) necessary to reach a solution within 1% of the optimal length. For each case, 500 simulations have been performed and the variance of the final results is normalized with respect to the minimum obtained value. From these results, we conclude that the GA with double cutting-point crossover coupled with the mutation operator needs the least number of generations to reach a near-optimal solution (for this example, the local boosting technique yielded a 25-fold increase in computational speed to reach populations with the same fitness). Results on the runtime performance for the method were published in [60].Table 4
GA solution of the KroA100 problem [59]. The 2-opt method is always applied and the number of generations necessary for the convergence of the full population within 1% of the optimal solution is evaluated with respect to different configurations of genetic operators.
Crossover typeMutationNumber of generationsVarianceDoubleApplied7.71DoubleNot applied8.71.14SingleApplied14.31.86SingleNot applied15.81.93


### 7.4. TSP Tests

Since the TSP is a limiting case of the subtour problem (one agent visiting all the targets, that is,m=1, k=n, with the restriction on returning to the starting position) the proposed algorithm can also be used to solve this classic problem.The algorithm has been tested with different TSPs from the well-known TSPLIB95 library [59]. This library includes different target configurations for the TSP and many related problems (Hamiltonian cycle problem, sequential ordering problem, etc.) together with their exact solutions. We note that the TSPs in the TSPLIB95 library are solved with a cost function based on rounded distances between targets. In order to have meaningful comparisons with the TSPLIB95 problems, our cost function was modified to round off distances.For every TSPLIB95 instances considered here, 100 simulations have been performed and the operators are applied with the probabilities reported in Table1. The results are shown in Table 5 and demonstrate the suitability of our approach.Table 5
Comparison of the proposed method with benchmarked solutions of the traveling salesman problem. Results are averaged over 100 simulations. Rounded distances are used.
Problem TSPLIBNumber of targetsOptimal tourGenetic algorithm errorLengthMinimumMeanMaximumStdBerlin525275420%0%0%0Eil76765380%0.02%1.4%0.8KroA100100212820%0%0%0lin105105143790%0%0%0ch13013061100%0.2%0.9%15.9a28028025790%0.2%1%8.5pcb442442507780.3%0.9%1.5%148.6att532532867290.4%1.1%2%340.07The att532 problem (532 cities in America) has been a popular benchmark for testing TSP-solvers. The optimal solution of length 86729 (shown in Figure18(a)) was found by Padberg and Rinaldi [61]. Yoshiyuki and Yoshiki [62] consider a real space renormalization approach for this problem, which provides solutions 37% longer than optimal on the average. Merz and Freisleben [63] show that while a simple memetic algorithm produces solutions that are about 20% longer than the optimal one, a recombination-based version of the memetic algorithm can find the optimal solution! Tsai et al. [64] introduce a smart combination of local and global search operators (called neighbor-join and edge assembly crossover) and this method is shown to find the optimal solution to the att532 problem in more than 75% of the simulations. A moving-frame renormalization group approach by Ugajin [65] yields a solution that is 17% longer than the optimal one. Yi et al. [66] present a parallel tabu search algorithm for this TSP and find solutions 6% longer than the optimal on the average (their best solution is only 3.85% longer than optimal). Chen and Zhang [50] report an enhanced annealing algorithm utilizing nth-nearest-neighbor distributions of optimal TSP solutions to solve the att532 benchmark problem, finding solutions that are 28% longer than optimal. Our GA reaches within 2% of the optimal solution in all simulations. The best solution we found (only 0.3% longer than optimal) differs from the optimal one in the “dense” region of the map as illustrated in Figures 16(b) and 16(c).att532 TSP: comparison between the optimal solution (of length 86729) and the one computed by our GA (of length 87075, 0.4% longer than the optimal solution).
(a)
att532 problem: optimal solution(b)
Optimal solution(c)
GA solutionOptimal TSP solutions for targets uniformly distributed over the unit square were obtained using CONCORDE [67] (also using rounded distances). Table 6 summarizes the results.Table 6
Comparison of the proposed method with different TSPs solved using the CONCORDE algorithm. For each case, 100 simulations have been run. Rounded distances are used.
Number of targetsOptimal tourGenetic algorithm errorLengthMinimumMeanMaximumStd60018120.7%1.3%2.2%5.670019460.9%2%2.8%7.680020871.3%2.1%2.8%9.1100022974.2%5.3%6.7%11.1Once again, the GA-based approach seems to perform well. The sudden increase in the errors for the 1000-target problem can be attributed to the relatively low size of the populations and to the fact that the number of the generations (250) used in these simulations is fixed (note that the objective of these tests was not to reach the best possible solutions).Finally, to quantify the influence of the singular mating pool technique, Table7 shows the different results obtained with or without its application. These simulations illustrate that avoiding the replication of the individuals through the application of the singular mating pool (slightly) improves the solutions. Note that the main purpose of the Singular Mating Pool is to maintain diversity of possible subtours. This has special significance for building near-optimal multiagent plans.Table 7
Efficacy of the singular mating pool. Results are averaged over 100 simulations. Considered problem: TSP of 600 cities with optimal tour length equal to 1812.
Singular mating poolGenetic algorithm errorMinimumMeanMaximumStdApplied0.5%1.3%2.3%7.01Not applied1.1%2.1%3.6%7.8The results of this section strengthen our claim that the implemented genetic algorithm is successful in finding near-optimal solutions for this type of combinatorial problems.


### 7.5. Subtour Tests

The genetic planner has also been statistically tested in order to demonstrate its capability to generate near-optimal subtours. To provide reliable averages, for a given configuration 100 simulations have been performed. All the subtour tests have been conducted on the unit square with a given target configuration and using the cost function (2.4). The double cutting-point crossover, the mutation operator, and the 2-opt method have been used (with the probabilities reported in Table 1).In order to evaluate the optimality of the subtours generated by our genetic algorithm, a comparison with known optimal solutions is needed. To our knowledge, no benchmark solutions exist for the subtour problem, so we introduced test cases with regular and random point configurations on the unit square to evaluate the algorithm.The first set of tests have been conducted by generating maps of targets with a trivial unique optimal solution. In these tests,n2 targets were selected with constant spacing of 1/n on the unit square (a uniform grid) with l extra points added between two points of the grid, following vertical, horizontal or diagonal directions. Figure 17 shows an example depicting the optimal 11-from-58 solution (n=7, l=9).Figure 17
Example of a subtour problem generated by a7×7 grid (circles), with 9 more added targets (squares).The convergence of the 50-from-489 Subtour Problem is shown. Subtour lengths are normalized with the optimal one (length = 0.0707). In (a) the speed of converge is shown. Note that the last simulation converges after 2045 generations. (b) Shows the distribution of the subtour lengths after 250 generations, considering 100 simulations.
(a)
Speed of convergence(b)
Distributions of subtour lengths after 250 generationsDifferent problems have been generated and the results are shown in Table8.Table 8
Comparison between exact and GA solutions for different Subtour Problems based on 100 simulations.
nlNumber of targetsSubtourOptimal tourGenetic algorithm errorn2+l(l+2)-from-(n2+l)LengthMinimumMeanMaximumStd795811-from-580.2360%0%0%0111513617-from-1360.1410%0.2%12.5%0.002214848950-from-4890.070%656.6%2883.4%0.43We note that the proposed method converges to the optimal solution in almost all the performed simulations. In few cases (the results of the 50-from-489 subtour), however, only very costly solutions (with high length) are found. This can be attributed to the slow convergence of the stochastic optimization process. In fact, all the reported tests are run with a fixed number of 250 generations which is in some cases not enough to ensure the convergence of the GA to an optimal (or near-optimal) solution.To elucidate this point, Figure18(a) shows the percentage of simulations reaching the optimal solution of the 50-from-489 problem as the function of population age (number of generations), while Figure 18(b) shows the distribution of subtour lengths after 250 generations. Note that only few of them are very costly solutions.The speed of convergence of the algorithm strongly depends on the GA parameters. In particular, it is influenced by the application of the 2-opt method.To provide numerical evidence for this claim, 100 simulations have been run on the 17-from-133 targets problem shown in Figure19 with different application probabilities of the 2-opt method. Note that in this case, the l points are added between more than two neighboring points.Figure 19
Example of a subtour problem generated by a grid of 112 targets (circles), with 12 more added points (squares).Results are reported in Table9, while Figure 20 shows the convergence speeds for different values of the 2-opt application probability.Table 9
Convergence results for the 17-from-133 problem with different 2-opt method probabilities.
2-opt probabilitySimulations converged after 250 generationsNumber of generations for full convergence0.0515%431480.234%121800.584%728194%1233Figure 20
Convergence for the GA solution of a 17-from-133 subtour problem with different application probabilities of the 2-opt method.In general, the frequent use of the 2-opt method restricts the random wandering of the genetic algorithm over the search space, thereby severely restricting the set of reachable solutions. If the 2-opt method is only applied with a given probability, much like the other operators, the results greatly improve and the number of necessary generations are strongly reduced.Note also (see Table9) that if the 2-opt method is always applied, the number of generations needed for full convergence can be very high.Another set of tests have been devised to compare GA subtour solutions to exact ones in random configurations of targets in the unit square. To find the exact solutions for these tests, the simplest brute force approach (exhaustive evaluation of combinations) was used. Figure21 shows an optimal 7-from-30 subtour with specified starting point (the depot) and the solution found by the GA. Table 10 summarizes the results for different subtour problems.Table 10
Comparison between exact and GA solutions for different subtour problems based on 100 simulations.
SubtourOptimal lengthGA solution lengthMean error7-from-300.710.721.4%6-from-300.6280.630.3%6-from-400.530.565.6%5-from-500.4460.4470.4%Figure 21
Comparison between the exact 6-from-40 subtour (length = 0.53) and the GA solution (length = 0.58). The fixed starting point (depot) isa.Figure22 shows a sample subtour for a problem, where the total number of targets is n=100 and the shortest path is sought connecting anyk=20 targets (a no depot problem).Figure 22
GA-generated 20-from-100 subtour solution of length 1.16. Optimal solution is not known.As previously described, the Subtour solutions can be used as a starting set of solutions for solving the more challenging multiagent planning problem. In Figure23, few preliminary examples are shown from our work on the multiagent planning problem.MAPP examples.
(a)
76 cities and 5 agents(b)
100 cities and 5 agents


## 7.1. Avoiding Premature Convergence

Premature convergence was defined previously as fast convergence of the genetic algorithm towards a local minimum in the search space. Tests have been conducted to illustrate how the implementation of the singular mating pool technique described in Section6.2 prevents premature convergence. All the tests in this Section have been performed on a TSP with 600 targets randomly distributed over the unit square. The GA parameters are reported in Table 1.The maximum and the minimum fitness values are plotted as the function of the population age (generation number) in Figure14(a) for a simulation where duplicates are not removed from the populations (i.e., without using the singular mating pool technique). It can be observed that the range of fitness values (the width between the lines corresponding to the extrema) rapidly approaches zero as the consequence of the decreasing heterogeneity of successive populations, leading to a final population composed of identical chromosomes. Moreover, this is a local minimum, since none of the resulting solutions is optimal. It is also interesting to note what happens when a new, better solution is introduced into a stagnant genetic pool. In Figure 14(a),  solutions seem to have reached a constant fitness value (the plateau around the 80th generation), when a better chromosome randomly appears in the population around the 120th generation.(a) Simulation without using the singular mating pool. The duplicated chromosomes lead to premature convergence. (b) Simulation with the singular mating pool technique. With duplicate chromosomes removed from the populations, the diversity of solutions is maintained.
(a)
The singular mating pool is not used(b)
The singular mating pool is usedSince during the evolution the duplicates of this chromosome are not discarded (its fitness value is better than those of the other solutions), in a small number of generations they replicate and replace all other individuals.Figure14(b) shows the extremal values of fitness in a simulation where the duplicates are constantly removed from the mating pool; that is, where the singular mating pool method is used. As a result of this strategy the diversity of the populations is maintained with an increased coverage of the search space. This makes it more likely for the algorithm to reach a near-optimal solution (in this case, the optimal result is reached).To characterize the heterogeneity/diversity of a population, a pairwise comparison of chromosome edges can be used. Let us consider two chromosomes of lengthk, si, and sj, with edge sets Ei and Ej, respectively (|Ei|=|Ej|). One possible measure of diversity can be defined as(7.1)di,j=1-|Ei∩Ej||Ei|.Thisedge diversity quantifies how much two chromosomes differ. The exact locations of identical edges do not influence this diversity measure. The edge diversity of the entire population Sp is the averaged edge diversities for all pairs(7.2)DSp=1n(n-1)∑i=1p-1∑j=i+1pdi,j.
Clearly, 0≤DSp≤1. We also introduce a “Boolean” diversity. The diversity of two chromosomes are equal if and only if they have identical edges. The Boolean diversity for population Sp is defined as(7.3)BSp=∑i=1p-1∑j=i+1p{0ifdi,j=0,1ifdi,j≠0.Figure15 shows the average edge and boolean diversity at every generation step for the simulations used for Figure 14 (with or without the use of the singular mating pool technique).How the application of the singular mating pool technique affects the edge (a) and boolean (b) diversity (%) of the population.
(a)
Edge diversity(b)
Boolean diversityThe decrease of the edge diversity can be explained by the reduction of the coverage of the search space: many costly edges are discarded early in the evolution and only considered again during the search process with low probability. This is why at later generations many solutions differ only by few edges, but still the population maintains its heterogeneity (as shown in Figure15(b)).In conclusion, to avoid premature convergence it is important to ensure that the evolving population contains a variety of chromosomes (representing different strategies for the agent to reach a set of targets). In our work on distributed planning (published in the sequel), the availability of these different strategies will have special significance.


## 7.2. Influence of the 2-opt Method on the Performance of Genetic Operators

To evaluate the performance of the different genetic operators and the 2-opt method, various tests have been performed. A target configuration forn=100 targets randomly and uniformly distributed over the unit square is generated. This configuration is kept fixed for all tests in this section to make comparisons meaningful. The 30-from-100 subtour problem is then solved with different combinations of the genetic operators, 100 times for each combination. The application probabilities of the operators are reported in Table 1. To assess the influence of the various genetic operators, their performances are directly compared and tested without the 2-opt method. The mean values and the variances of the distribution of the best (highest) fitness values of the final populations are shown in Table 2.Table 2
Simulation cases to test efficiency of different genetic operators. The 2-opt method is not applied.
Crossover typeMutationMean fitnessVariance of fitnessDouble pointApplied11Single pointApplied0.931.32Double pointNot applied0.921.47Single pointNot applied0.692.12Since the optimal solution is not known, the mean fitness values and the variances of fitness are normalized by the best result (the highest for the fitness values and the lowest for the variances of fitness). The comparison of the quantities in Table2 shows that the combined application of the double cutting-point crossover and the mutation operator yields the maximum fitness value and the minimum variance of the solutions. On the other hand, the worst solutions are obtained with the standalone application of the single cutting point crossover operator. These results not only demonstrate the improvement introduced by the double cutting point crossover, but also clearly highlight the importance of the mutation operator.With the application of the 2-opt method, the results change, as shown in Table3.Table 3
Simulation cases to test efficiency of different genetic operators together with the 2-opt method.
Crossover typeMutationMean fitnessVariance of fitnessDouble pointApplied0.9933.12Single pointApplied11Double pointNot applied0.9942.62Single pointNot applied0.9981.31In this case, the performance of the single cutting-point crossover operator coupled with mutations is the best. It would be tempting to conclude that this configuration of the genetic operators is the best; however, in the next section it is demonstrated that the speed of convergence for this configuration of operators is significantly worse than for the double cutting-point crossover/mutation combo (here, this fact is hidden as the genetic algorithm is run for a fixed number of generations).


## 7.3. Speed of Convergence and Genetic Operators

The results of the previous section clearly demonstrate the efficiency of coupling the genetic operators with the 2-opt method. The most important improvement introduced by the 2-opt method is in the speed of convergence that is here intended as the number of generation the algorithm requires for converging (it is not related to time). In fact, because of its capability of detecting new local minima at each generation step, the application of the 2-opt method together with the double cutting-point crossover and the mutation operators helps the GA to converge faster than without [56]. To quantify the speed of convergence with various genetic operators and the 2-opt method, the required number of generations for the convergence of the genetic algorithm is calculated. To facilitate this test, a 100-target TSP with known exact solution was solved (KroA-100 TSP [59], with optimal path-length of 21282). For different combinations of the genetic operators, Table 4 reports the number of generations (and its variance) necessary to reach a solution within 1% of the optimal length. For each case, 500 simulations have been performed and the variance of the final results is normalized with respect to the minimum obtained value. From these results, we conclude that the GA with double cutting-point crossover coupled with the mutation operator needs the least number of generations to reach a near-optimal solution (for this example, the local boosting technique yielded a 25-fold increase in computational speed to reach populations with the same fitness). Results on the runtime performance for the method were published in [60].Table 4
GA solution of the KroA100 problem [59]. The 2-opt method is always applied and the number of generations necessary for the convergence of the full population within 1% of the optimal solution is evaluated with respect to different configurations of genetic operators.
Crossover typeMutationNumber of generationsVarianceDoubleApplied7.71DoubleNot applied8.71.14SingleApplied14.31.86SingleNot applied15.81.93


## 7.4. TSP Tests

Since the TSP is a limiting case of the subtour problem (one agent visiting all the targets, that is,m=1, k=n, with the restriction on returning to the starting position) the proposed algorithm can also be used to solve this classic problem.The algorithm has been tested with different TSPs from the well-known TSPLIB95 library [59]. This library includes different target configurations for the TSP and many related problems (Hamiltonian cycle problem, sequential ordering problem, etc.) together with their exact solutions. We note that the TSPs in the TSPLIB95 library are solved with a cost function based on rounded distances between targets. In order to have meaningful comparisons with the TSPLIB95 problems, our cost function was modified to round off distances.For every TSPLIB95 instances considered here, 100 simulations have been performed and the operators are applied with the probabilities reported in Table1. The results are shown in Table 5 and demonstrate the suitability of our approach.Table 5
Comparison of the proposed method with benchmarked solutions of the traveling salesman problem. Results are averaged over 100 simulations. Rounded distances are used.
Problem TSPLIBNumber of targetsOptimal tourGenetic algorithm errorLengthMinimumMeanMaximumStdBerlin525275420%0%0%0Eil76765380%0.02%1.4%0.8KroA100100212820%0%0%0lin105105143790%0%0%0ch13013061100%0.2%0.9%15.9a28028025790%0.2%1%8.5pcb442442507780.3%0.9%1.5%148.6att532532867290.4%1.1%2%340.07The att532 problem (532 cities in America) has been a popular benchmark for testing TSP-solvers. The optimal solution of length 86729 (shown in Figure18(a)) was found by Padberg and Rinaldi [61]. Yoshiyuki and Yoshiki [62] consider a real space renormalization approach for this problem, which provides solutions 37% longer than optimal on the average. Merz and Freisleben [63] show that while a simple memetic algorithm produces solutions that are about 20% longer than the optimal one, a recombination-based version of the memetic algorithm can find the optimal solution! Tsai et al. [64] introduce a smart combination of local and global search operators (called neighbor-join and edge assembly crossover) and this method is shown to find the optimal solution to the att532 problem in more than 75% of the simulations. A moving-frame renormalization group approach by Ugajin [65] yields a solution that is 17% longer than the optimal one. Yi et al. [66] present a parallel tabu search algorithm for this TSP and find solutions 6% longer than the optimal on the average (their best solution is only 3.85% longer than optimal). Chen and Zhang [50] report an enhanced annealing algorithm utilizing nth-nearest-neighbor distributions of optimal TSP solutions to solve the att532 benchmark problem, finding solutions that are 28% longer than optimal. Our GA reaches within 2% of the optimal solution in all simulations. The best solution we found (only 0.3% longer than optimal) differs from the optimal one in the “dense” region of the map as illustrated in Figures 16(b) and 16(c).att532 TSP: comparison between the optimal solution (of length 86729) and the one computed by our GA (of length 87075, 0.4% longer than the optimal solution).
(a)
att532 problem: optimal solution(b)
Optimal solution(c)
GA solutionOptimal TSP solutions for targets uniformly distributed over the unit square were obtained using CONCORDE [67] (also using rounded distances). Table 6 summarizes the results.Table 6
Comparison of the proposed method with different TSPs solved using the CONCORDE algorithm. For each case, 100 simulations have been run. Rounded distances are used.
Number of targetsOptimal tourGenetic algorithm errorLengthMinimumMeanMaximumStd60018120.7%1.3%2.2%5.670019460.9%2%2.8%7.680020871.3%2.1%2.8%9.1100022974.2%5.3%6.7%11.1Once again, the GA-based approach seems to perform well. The sudden increase in the errors for the 1000-target problem can be attributed to the relatively low size of the populations and to the fact that the number of the generations (250) used in these simulations is fixed (note that the objective of these tests was not to reach the best possible solutions).Finally, to quantify the influence of the singular mating pool technique, Table7 shows the different results obtained with or without its application. These simulations illustrate that avoiding the replication of the individuals through the application of the singular mating pool (slightly) improves the solutions. Note that the main purpose of the Singular Mating Pool is to maintain diversity of possible subtours. This has special significance for building near-optimal multiagent plans.Table 7
Efficacy of the singular mating pool. Results are averaged over 100 simulations. Considered problem: TSP of 600 cities with optimal tour length equal to 1812.
Singular mating poolGenetic algorithm errorMinimumMeanMaximumStdApplied0.5%1.3%2.3%7.01Not applied1.1%2.1%3.6%7.8The results of this section strengthen our claim that the implemented genetic algorithm is successful in finding near-optimal solutions for this type of combinatorial problems.


## 7.5. Subtour Tests

The genetic planner has also been statistically tested in order to demonstrate its capability to generate near-optimal subtours. To provide reliable averages, for a given configuration 100 simulations have been performed. All the subtour tests have been conducted on the unit square with a given target configuration and using the cost function (2.4). The double cutting-point crossover, the mutation operator, and the 2-opt method have been used (with the probabilities reported in Table 1).In order to evaluate the optimality of the subtours generated by our genetic algorithm, a comparison with known optimal solutions is needed. To our knowledge, no benchmark solutions exist for the subtour problem, so we introduced test cases with regular and random point configurations on the unit square to evaluate the algorithm.The first set of tests have been conducted by generating maps of targets with a trivial unique optimal solution. In these tests,n2 targets were selected with constant spacing of 1/n on the unit square (a uniform grid) with l extra points added between two points of the grid, following vertical, horizontal or diagonal directions. Figure 17 shows an example depicting the optimal 11-from-58 solution (n=7, l=9).Figure 17
Example of a subtour problem generated by a7×7 grid (circles), with 9 more added targets (squares).The convergence of the 50-from-489 Subtour Problem is shown. Subtour lengths are normalized with the optimal one (length = 0.0707). In (a) the speed of converge is shown. Note that the last simulation converges after 2045 generations. (b) Shows the distribution of the subtour lengths after 250 generations, considering 100 simulations.
(a)
Speed of convergence(b)
Distributions of subtour lengths after 250 generationsDifferent problems have been generated and the results are shown in Table8.Table 8
Comparison between exact and GA solutions for different Subtour Problems based on 100 simulations.
nlNumber of targetsSubtourOptimal tourGenetic algorithm errorn2+l(l+2)-from-(n2+l)LengthMinimumMeanMaximumStd795811-from-580.2360%0%0%0111513617-from-1360.1410%0.2%12.5%0.002214848950-from-4890.070%656.6%2883.4%0.43We note that the proposed method converges to the optimal solution in almost all the performed simulations. In few cases (the results of the 50-from-489 subtour), however, only very costly solutions (with high length) are found. This can be attributed to the slow convergence of the stochastic optimization process. In fact, all the reported tests are run with a fixed number of 250 generations which is in some cases not enough to ensure the convergence of the GA to an optimal (or near-optimal) solution.To elucidate this point, Figure18(a) shows the percentage of simulations reaching the optimal solution of the 50-from-489 problem as the function of population age (number of generations), while Figure 18(b) shows the distribution of subtour lengths after 250 generations. Note that only few of them are very costly solutions.The speed of convergence of the algorithm strongly depends on the GA parameters. In particular, it is influenced by the application of the 2-opt method.To provide numerical evidence for this claim, 100 simulations have been run on the 17-from-133 targets problem shown in Figure19 with different application probabilities of the 2-opt method. Note that in this case, the l points are added between more than two neighboring points.Figure 19
Example of a subtour problem generated by a grid of 112 targets (circles), with 12 more added points (squares).Results are reported in Table9, while Figure 20 shows the convergence speeds for different values of the 2-opt application probability.Table 9
Convergence results for the 17-from-133 problem with different 2-opt method probabilities.
2-opt probabilitySimulations converged after 250 generationsNumber of generations for full convergence0.0515%431480.234%121800.584%728194%1233Figure 20
Convergence for the GA solution of a 17-from-133 subtour problem with different application probabilities of the 2-opt method.In general, the frequent use of the 2-opt method restricts the random wandering of the genetic algorithm over the search space, thereby severely restricting the set of reachable solutions. If the 2-opt method is only applied with a given probability, much like the other operators, the results greatly improve and the number of necessary generations are strongly reduced.Note also (see Table9) that if the 2-opt method is always applied, the number of generations needed for full convergence can be very high.Another set of tests have been devised to compare GA subtour solutions to exact ones in random configurations of targets in the unit square. To find the exact solutions for these tests, the simplest brute force approach (exhaustive evaluation of combinations) was used. Figure21 shows an optimal 7-from-30 subtour with specified starting point (the depot) and the solution found by the GA. Table 10 summarizes the results for different subtour problems.Table 10
Comparison between exact and GA solutions for different subtour problems based on 100 simulations.
SubtourOptimal lengthGA solution lengthMean error7-from-300.710.721.4%6-from-300.6280.630.3%6-from-400.530.565.6%5-from-500.4460.4470.4%Figure 21
Comparison between the exact 6-from-40 subtour (length = 0.53) and the GA solution (length = 0.58). The fixed starting point (depot) isa.Figure22 shows a sample subtour for a problem, where the total number of targets is n=100 and the shortest path is sought connecting anyk=20 targets (a no depot problem).Figure 22
GA-generated 20-from-100 subtour solution of length 1.16. Optimal solution is not known.As previously described, the Subtour solutions can be used as a starting set of solutions for solving the more challenging multiagent planning problem. In Figure23, few preliminary examples are shown from our work on the multiagent planning problem.MAPP examples.
(a)
76 cities and 5 agents(b)
100 cities and 5 agents


## 8. Conclusions

This paper describes a genetic goal planner for generating a near-optimal strategy, a subtour, for visiting a subset of known targets/goals. The importance of this work is to provide the ability to a single agent to plan a strategy—a subtour—by organizing a sequence of targets autonomously. This planning capability is a starting step toward a multiagent planning system, where agents are able to collectively decide on the overall mission strategy, allocating and sharing a given number of tasks/goals, with important applications in problems where there is limited/no human feedback (like planetary space exploration or search and rescue in collapsed buildings).The results presented here show the success of the implemented genetic algorithm. In particular, we demonstrated that the proposed combination of genetic operators (double crossover with mutation) and local boosting technique (the 2-opt method) provides an efficient solver for otherwise hard combinatorial problems (TSP, subtour problem).



---

*Source: 483643-2011-05-02.xml*