Page 178 - Biomimetics : Biologically Inspired Technologies

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

164 Biomimetics: Biologically Inspired Technologies

may be less suited to the local conditions and may be poorer competitors locally. Edmands (1999,
2002) observed that parental divergence (parents who are genetically distant) leads to less fit
offspring.
In genetic algorithms, if dissimilar individuals mate, the offspring is more genetically diverse
which is critical in maintaining a population’s genetic diversity. However, parents who are too
dissimilar produce less fit offspring. Using the distance criterion for parent selection, Drezner and
Marcoulides (2003) crafted a rule attempting to find dissimilar but not too distant parents.
A parameter K ¼ 1, 2, 3, . . . is used. The first parent is randomly selected and K candidates for
mating are then randomly selected. The distance (number of variables with different values, the
Hamming distance metric) between the first parent and all candidate mates is calculated. The
farthest mate among these K candidates is selected as the second parent. Note that K ¼ 1is
the ‘‘standard’’ parent selection. Drezner and Marcoulides (2003) found that the efficiency of the
modification for a set of test problems peaks for K ¼ 2,3. Selecting the farthest population member
as a mate does not work well. It was also found that run time increases with K which further reduces
the appeal of larger Ks.

5.3.8 Removal of Population Members

In most standard genetic algorithms, when an offspring is generated, it is compared with the worst
population member, and if the offspring is better than the worst population member, it replaces
it. Some genetic algorithms employ a rule according to which if the offspring is identical to an
existing population member, it is not considered for inclusion in the population. This precludes the
possibility of having two identical population members.
Drezner (2005c) suggested a different rule for the removal of population members. Two rules
for the removal of a population member, once a better offspring (who is not identical to an existing
population member) is found, are used. Rule 1 is the standard approach and Rule 2 is a new one.
Rule 1: Remove the worst population member.
Rule 2: Distances between all pairs of population members are calculated. Suppose that the shortest
distance among all pairs of population members is d. All existing population members who are at
distance d from another population member form a subset. This subset must have at least two members
(at least one pair of population members are at distance d from one another). Remove the worst
population member in this subset.

In the experiments performed in Drezner (2005c), it was found that Rule 2 is not necessarily
better than Rule 1. The suggested rule is to select Rule 2 with probability p, and to select Rule 1
otherwise. Note that p ¼ 0 is the standard rule (Rule 1), and p ¼ 1 is Rule 2. The mix between the
two rules by selecting 0 < p < 1 seems to work well.

5.4 AN ILLUSTRATION

Three facilities (such as post office branches) are to be constructed to serve 20 communities. For
simplicity, we assume that the communities have the same number of residents. Of the 20
communities, seven communities can house a branch and 13 communities cannot (for various
reasons). See Figure 5.1, where communities that can house a branch are denoted by black
circles and the rest by empty circles. Table 5.1 gives the x–y coordinates of the seven potential
facilities. Distances are straight-line (Euclidean) distances. Each community is served by the
closest branch. The objective is to locate the three branches so as to minimize the sum of
the service distances to all 20 communities thus providing the best overall service to all residents.
This problem is a p-median problem. For a discussion of p-median problems, see Current
et al. (2002).