Information Technology Reference
In-Depth Information
100
90
80
Restricted
Generalized
70
60
50
40
30
20
10
0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Permutation rate
Figure 11.5.
Comparison of restricted permutation with generalized permutation on
the traveling salesperson problem with 13 cities. For this analysis,
P
= 100 and
G
=
200. The success rate was evaluated over 100 identical runs.
11.3 Two Scheduling Problems
The first problem of this section is the already explored traveling salesperson
problem with 19 cities. And we have already seen that this problem requires
only a multigene family consisting of the genes representing the 19 cities the
salesperson should visit.
The second problem is a task assignment problem that requires two differ-
ent multigene families: one containing the agents and the other the tasks
assigned to the agents.
11.3.1 The Traveling Salesperson Problem
The TSP represents a classical optimization problem and good, traditional
approximation algorithms have been developed to tackle it down (see, e.g.,
Papadimitriou and Steiglitz 1982 for a review). However, to evolutionary
computists, the TSP serves as the simplest case of a variety of combinatorial
problems which are of enormous relevance to industrial scheduling prob-
lems (Bonachea et al. 2000; Hsu and Hsu 2001; Johnson and McGeoch 1997;
Katayama and Narihisa 1999; Merz and Freisleben 1997; Reinelt 1994).
