Page 186 - Biomimetics : Biologically Inspired Technologies

Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c005 Final Proof page 172 6.9.2005 12:11pm

172 Biomimetics: Biologically Inspired Technologies

Table 5.5 Results for Non-Genetic Heuristics
Time per 10,000
Heuristic Minimum Average Maximum runs (sec)
Steepest descent 1362 þ588.59 þ25,500 0.57
0 Levels 1462 þ148.86 þ25,358 3.71
5 Levels 1460 24.36 þ13,200 18.92
10 Levels 1456 58.39 þ10,532 33.75
15 Levels 1452 80.51 þ11,910 48.54
20 Levels 1464 93.11 þ40,182 62.66
25 Levels 1468 104.07 þ13,162 77.19

We solved the QAP problem using a Fortran code compiled by Microsoft PowerStation 4.0 for
Windows. The code uses integer values for the parameters. The experiments were performed on a
desktop PC with 2.8 GHz CPU and 256 MB RAM.
To demonstrate the effectiveness of the genetic algorithm, we first report in Table 5.5 the results
of the steepest descent and the Ring Moves (RM) (Drezner, 2005b) for various levels without using
any evolution. Each algorithm was run 10,000,000 (ten million) times. The best solution, average
solution, and time in seconds for 10,000 runs are reported. The best solution, found with hybrid
genetic algorithms reported below of 1,550, has never been found by any of these 10,000,000
experiments. The quality of the solution increases as the number of levels increases, but it does not
seem to merit the extra computer time.
For the genetic algorithms we employ the hybrid genetic algorithm described in Drezner
(2005b) using the steepest descent, and RM with 10 and 25 levels. The population size is 100,
with 10,000 generations for each solution. Each replication is run 1,000 times thus a total
of 10,000,000 offspring are generated. In Table 5.6 we report the number of times the best
known solution ( 1550) was found, the average solution, the maximum solution, and the
run time required for one run. To demonstrate some of the modifications, we repeated the runs
with the gender-specific modification (Drezner and Drezner, 2005) and the distance modification
using K ¼ 1, 2, . . . , 5, for a total of 30 experiments. The results of the experiments are depicted
in Table 5.6.
A comparison of Tables 5.5 and 5.6 clearly shows the benefit derived from employing the
evolutionary process. The average result obtained with the evolutionary process is about the same
as the best results obtained in 10,000,000 runs without evolution and in most cases in a shorter
computer time. For example, the ten-levels case required about 9.4 h to evaluate all 10,000,000
replications without evolution. The best solution of –1,550 was never found in 10,000,000 repli-
cations. However, using a genetic algorithm with a K ¼ 3 distance modification and no gender
modification required a total of only 7.9 h for 1,000 replications and the best known solution was
found in 63.1% of those replications. Even the steepest descent version with K ¼ 2 found the best-
known solution in 12.5% of the replications in a total run time of 9.5 min.

5.6 DISCUSSION

In this chapter we describe genetic algorithms for solving optimization problems. These algorithms
mimic natural selection and the survival of the fittest principles. Modifications of the ‘‘standard’’
genetic algorithm are also presented.
Genetic algorithms are based on evolutionary premises, and attempt to simulate natural selec-
tion and survival of the fittest. To survive, species must reproduce and regenerate. This requires new
members of the population to be fit and adaptable to changing environmental conditions. Only the
fittest individuals survive while the weak members perish or are killed by their natural enemies.
Inherent to this theory is, therefore, the definition of what constitutes the ‘‘fittest.’’ In nature, the