04
is
ital
yes
V5,
rial
288.
NO.
kis,
for
nal
pp.
ure
sed
nal
| of
lis,
and
ing
/ol.
ing
py &
of
OM
ted
use
[lite
of
B3,
ted
and
ing,
ced
ery.
No.
AN EFFICIENT AND ROBUST GENETIC ALGORITHM APPROACH FOR
AUTOMATED MAP LABELING
Fan Hong!* Liu Kaijun? Zhang Zuxun'
(1 National Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing of Wuhan University,
No.129 Luoyu Road, Wuhan, China, Zip code:430079)
(2 Management college of Huazhong University of Science and Technology, Luoyu Road, Zip code: 430070)
Keywords: genetic algorithm, label placement, optimal combination problem, mutate on conflict gene,
comparison experiment
ABSTRACT:
This paper put forward an new solution, which adopted the genetic algorithm to obtain the global optimal solution (approximate) of
automated label placement of point feature. In the paper, the basic thought and design framework of using genetic algorithm to solve
point feature labelling was firstly introduced, then, some practical technique and new improved method during the experiment
procedure of genetic algorithm adopted by the author were presented in detail. Finally, in order to prove the advantage of genetic
algorithm, some experiment were conducted which compare the efficiency of genetic algorithm with hill climbing algorithm,
simulated annealing, neural network, etc. The result of comparison experiment was given out, which has proved the superiority of
genetic algorithm, especially proved the genetic algorithm is a kind of high-efficient, robust, all-purpose algorithm with well-
expansibility, and is the most promising solution for automated map labelling.
I. INTRODUCTION
Label is an important component of a map, with the aid of map
label user can recognize the important objects and obtain its
relevant information of objects. However for a long time, map
label has been a time-consuming manual work. So the automated
map label has been always one of the important study contents of
computer-aided cartography all the time. On the other hand, the
automated map label is one artificial intelligence puzzle. It has
been already proved that finding the optimal solution of
automated map label is a NP-hard problem [Marks, 1991].
This paper put forward one new approach to find the global
optimal solution of automated map labeling with genetic
algorithm. Genetic algorithm is a kind of method with global
searching characteristic. It originates from simulating the
biological evolution course of nature, and possesses many merits
including high-parallel, self-organization, self-adaptation, self-
learning and high efficiency, etc. Besides, genetic algorithm is
simple, easy to operate and expand. Through plenty of
experiments, we think genetic algorithm is a potential solution
for automated map labeling.
IIl. TRADITIONAL METHOD'S DISADVANTAGES
It has gone nearly thirty years since Yoeli began to study point
feature labeling, and many scholars have put forward various
method to solve point feature labeling problem [Yoeli, 1972;
Imhof , 1975; Ahn Freeman, 1984; Langran and Poilker, 1986;
Zoraster, 1991; Christensen ef.al, 1995, 1997 ]. In the eighties of
20" century, a lot of automated labeling expert system were
developed [Zoraster, 1991] that includes NAMAX, AutoNap,etc.
The disadvantages of expert systems is low-efficiency and great
developing cost. Another routine algorithm is exhausted
searching algorithm [Jones, 1989; Cook and Jones, 1990; Ebinge
and Goulette, 1990; Doerschler and Freeman, 1992]. These
algorithm can be expressed as searching in digraph or direction
fh@mail.liesmars.wtusm.edu.en
tree, which might cause concatenate backtracking and even
deadlock, So its severest problem is low efficient, therefore it is
only fit to small-scale problem. Another kind of important
algorithm is a kind of searching strategy based on the problem
solution space. Representative examples include the energy
minimization algorithm put forward by Hiersch [Hiesh, 1982]
and the discrete gradient descent algorithm [Christensen ef.al,
1995, 1997], etc. There possibly appear two kinds of problems in
these local search algorithms. First, they do not accept
degenerated solution, therefore unable to jump out the “local
minimum" trap; second, it may fall into dead loop.
ITI. POINT LABELING RULES
Consider point labeling, according to the common labeling
principles, combining Chinese topographic map plotting pattern
and regulations, in the labeling experiment of the residence
topographic map with the scale 1:250000, our research will focus
on the following three important principles especially:
I. The candidate positions and their priority: generally the
candidate position of point feature labeling has four kinds of
situations including — four-candidate-position, | five-candidate-
position, eight-candidate-position and n-candidate-position.
Four-candidate-position, as indicated in figure 1(a), regard the
right as first, top, left and bottom followed respectively in
succession, these labeling positions can be marked with priorities
from 0 to 3. Five-candidate-position, as indicated in figure 1(b),
similarly regard the right as first, the next are top, left, bottom,
right-vertical respectively in succession, these labeling positions
are expressed with priorities from 0 to 4. Eight-candidate-
position, as indicated in figure l(c), regard the right as first, the
next are top, left, bottom, right-top, left-top, left-bottom, right-
bottom respectively in succession, these labeling positions are
expressed with priorities from 0 to 7. The n-candidate-position is
illustrated in figure 1(d).
2. Forbid conflict: the labels of point features can't overlap
(conflict ) with one another.
617
