Page 179 - Biomimetics : Biologically Inspired Technologies

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

Genetic Algorithms in Optimization Models 165

6

5 6

4 1

3 3
y

2 5 2 7

1

0 4
0 1 2 3 4 5 6
x
Figure 5.1 The p-median problem.

This particular problem is very simple. There are only 35 possible combinations for
selecting three communities out of seven and thus total enumeration is straightforward. We
list all possible combinations in Table 5.2. A ‘‘1’’ indicates a community selected for a branch
and ‘‘0’’ indicates that it is not. To simplify the illustration, we calculate the objective function
values using an Excel spreadsheet. These values are depicted in the last column of Table 5.2. Since
the objective is the minimization of the sum of service distances to all communities, total
enumeration will find that the optimal solution is combination #27 (communities #1, #3, and #7,
see Figure 5.1) with a total service distance of 31.01. To illustrate the genetic algorithm, we
‘‘pretend’’ that the optimal solution is not known and whenever the value of the fit function
(objective function) is needed, it is calculated for that combination.

Table 5.1 Location of Candidate Communities

# x Y
1 5 4
2 2 2
3 1 3
4 5 0
5 0 2
6 0 5
7 4 2