Geoscience Reference
In-Depth Information
Fig. 2.6
Errors due to using
various heuristic algorithms
Percent Error for Various Algorithms
16%
14%
12%
10%
8%
6%
4%
2%
0%
0
5
10
15
20
25
Number of Medians
GA
GAS -- Every
Neighborhood -- Every
GAS -- Last
Neighborhood -- Last
We next consider the impact of using different construction and improvement
algorithms to solve the problem. Five different algorithms were tested: the greedy
adding or myopic algorithm (GA), the greedy adding algorithm with the node
exchange algorithm applied after every median is added (GAS-Every), the greedy
adding algorithm with the neighborhood algorithm applied after every median
is added (Neighborhood-Every), the greedy adding algorithm with the exchange
algorithm applied after all nodes have been added (GAS-Last), and the greedy
adding algorithm using the neighborhood algorithm only after all nodes have been
added to the solution (Neighborhood-Last).
Figure
2.6
plots the results. Both the greedy adding algorithm (GA) and the
Neighborhood algorithm applied after all nodes have been added to the solution
(Neighborhood-Last) result in large errors, often exceeding 10 %. The other three
algorithms perform much better and result in errors that are under 4 % and often
under 2 %.
Figure
2.7
plots the results of using a genetic algorithm similar to that proposed
by Alp et al. (
2003
). The variant employs a standard crossover operator. To ensure
feasibility of the solution generated by the crossover operator, we randomly drop
nodes from any solution that has more than
p
facilities (always retaining facilities
that are in both parent's solutions) and randomly add facilities from the parents
when the operator results in fewer than
p
facilities being selected. The standard
genetic algorithm can result in large errors and the errors seem to grow with the
number of medians. However, if the final genetic algorithm solutions are subject to
an exchange algorithm, the errors are under 1 % and average under 0.1 % for the 25
cases.
