)
des
ele
ind
tor
Ine
ict
ly
ery
lict
tic
50,
om
sly
as
m
the
of
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXX V, Part B4. Istanbul 2004
(1) The population size N: it affects the validity of genetic
algorithm, recommended it no more than 300. In this paper the
domain of N is [30, 300].
(2) Crossover probability P ,: it controls the frequency of
crossover operation. Generally it is between 0.25 and 0.85. In
this paper it is between 0.6 and 0.8.
(3) Mutation probability P ,,: it is the second factor in increasing
the diversity of population. Generally P ,, is between 0.01 and
0.2. This paper doesn't have to use this parameter.
(4) Terminating number of generation: when population evolves
over the specified largest evolution number of generation,
terminate the evolvement course, so this parameter should
guarantee the population has matured. There are two conditions
to judge whether the population has matured: (1) through several
operations, the approximate optimal individual can be gotten
stably; (2) continue evolving, the optimal individual is not
improved obviously again.
V. GENETIC ALGORITHM EXPERIMENTS AND
CONCLUSION
The experiment of genetic algorithm scheme is composed with
two parts of data. The first part is some random maps generated
by the algorithm developed by ourselves; the second part is the
actual topographic maps that includes three complete feature
topographic maps from National Topographic Map Database of
1:250000, among them every map is composed with nineteen
layers including hydrogen, road, vegetation, boundary, and so on.
The three topographic maps contain point residences 2511, 1651
and 2734 respectively.
From the evolvement experiment on the map containing 50-3000
point features, we can find that in the iteration course, with the
gradual increment of the fitness value of optimal individual,
genetic algorithm becomes steady, this indicates the population
has matured. The algorithm should be terminated after the
population has matured. Usually the map with no more than 3000
point features becomes matured within 300 generations.
EEE E OC BUR NE «us PA
* adu
sR EET wo tor La] woo I
)W AC C We
we : : --—
WEHEN | RT we M ras f TE ess
pe ; 6. jn 4 eon
* ru
> os ores ae “> san »
TU
. nte in a £8 "he xa
es ix "y vy - Fe
- ha "* NS us T n ten wi
> ! D 118 "aw ‘wad 4
n ees Ph i
as - 149
Ave x sma *
x fo - E
gui des Bi VK 1 ax
a^ sa té x
, > a. var wa
e - as. Cr ter ae”
ci oe 1 das s xw» HAM
/ u. Ag,
PHI wis #=n 113 * #44
*
am wt
e ws jan
a 7 feme W i -
Fa Lb de + LEE Br
fS agg t
dx TI
i-i 8 es ám LLL i
vo à # { ?
atom } ruse Ur ver — ^
- Py m = aux
ss t R -— sie ,
se — tmu ;
sas ue wry m
Ll LI me ^ of
ee $ i j^4" ag
- ehh + ;
: vom X em i «thi m
. vy
[rr . T
aes WEE GARE eae
Figure 5 the labeling result of H4810 using genetic algorithm
The experiments also include the comparison of using genetic
algorithm on maps with different complexities and the
comparison of using genetic algorithm with different parameters
on the same map. The experiments indicate that when processing
the problems of different complexities with the same genetic
parameters the results are different. When keeping certain
population size, the increment of evolvement generations will
increase the fitness of solution. But once reach certain degree,
when the population is matured, the solution will not be made
better. If the evolvement generations are very few, the simple
increment of population size is not very useful to improve the
solution.
The experiments include the experiment on three actual
topographic maps which belong to the problems of moderate
difficulty. Genetic algorithm can eliminate nearly all the conflicts
(only 1 or 2 are not eliminated) in 20~30 seconds. Figure 5 is a
part of the labeling result of H4810 (2511 point features).
VI COMPARISON EXPERIMENT AND CONCLUSION
In order to verify the performance of genetic algorithm
introduced in this paper, we compare genetic algorithm with
simple random algorithm, hill climbing algorithm, simulated
annealing and neural network algorithm.
The simple random algorithm is one of the simplest algorithms.
It specifies randomly a labeling position for every point feature,
but not implement any optimization, it's algorithm quality is the
lowest limit of labeling quality.
Hill climbing algorithm is a kind of simple local optimization
algorithms. It begins from an initial solution of randomly given
labeling placement (or be calculated by other methods or be
specified directly), search the n adjacent new solutions generated
randomly from the current solution, and select the optimal
solution and continue searching in new solutions until the
solution can't be improved again. In order to guarantee the
comparability, we set up the numbers of iterations as 200-300
generations in experiments, namely let the program start to
search in 200~30 different initial solutions, and search thirty
adjacent strings every iteration.
Christensen and his fellows have put forward a kind of point
feature labeling algorithm based on simulated annealing.
Simulated annealing algorithm is a kind of simple global
searching algorithm, and it is the improved hill climbing
algorithm, which adopts randomly relocating in labeling, but
allows the “degenerated solution” with certain probability in
order to jump out the local minimum. About the kernel algorithm
please refer to [Christensen, 1995]. Christensen has proved
simulated annealing algorithm possesss a lot of performance
superior to traditional algorithms. The simulated annealing in this
paper adopts the processing flow and parameters in Christensen’s
work. In order to guarantee the comparability, we set up the
number of iterations as 200~300.
Neural network algorithm adopts the model put forward by Fan
Hong and Zhang Zuxun [Fan Hong, Zhang Zuxun, 1997], after
setting up the neural network of solving point labeling problem,
let the network run iteratively, the running result is regarded as
the labeling placement. In order to guarantee the comparability,
we also set up the number of iterations as 200~300.
The experimented data is a group of point maps generated
randomly. The experiment methods are carried on based on the
same data background and subsidiary data conditions. Before
using algorithms we have set up the same conflict detection table
and overlap detection table.
The experiment compares the labeling qualities of different
algorithms mainly. In order to compare conveniently, all
consider the four-position labeling problem of point feature, and
consider the following two optimization targets: (1) only
621
