| 
| 
i 
i 
il 
I 
| 
| 
| 
  
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
  
E(L;)= E(L j) 
MI Wpositior position Li, j) IE Li j without conflicEO 
0 otherwise 
; N 
Ji(1)s Y EG) (7) 
i=] 
Where W esiti on l. 
Now consider the example in figure 2, the figure gives out its 
chromosome. Consider the targets of least conflict and most 
optimal position, adopt the fitness function (7), and calculate its 
fitness value: 
20 
fi(L) 2 X E(Lj) 2 99x10 98x44 97x3--96x3 —1961.0 
i-l 
4.4 design genetic operators 
4.4.1 Selection operators 
The labeling algorithm adopts roulette-wheel selection as 
selection method. When the population size is very large, can use 
elite strategy, namely retain the optimal individuals of the 
previous generation into the next generation's population. The 
implementation algorithm of roulette-wheel selection is as follow: 
(1) Calculate the fitness value of individual 
fit i =12,...,n); 
(2) Calculate the accumulative fitness value of individual 
Accfit(V, Yi = K2 m) and relative accumulative fitness 
value Re/Accfit(V, Xi = 1290). 
(3) Generate a random r in [0, 1], 
here suppose Re lAccfit(V,) zi, 
Re/Accfi(V, ,) « r x Reldccfi(V,) (i=12,.n), 
then select the individual i. 
4.4.2 Crossover operator 
(l)single-point-crossover: 
father string1  (0[1]2]3]0]1]0)2 
Iu NS poin exchange _ = 
father string2 TORENT 1J0|1]1]2|2]1]0 
offspring string? 
offspring stringl 
(Zymultipoint- crossover: 
father stringl O]1/2]5]0] 11012 : y Ont]1H1[2]1]0/2 
; er pointl Y T zm: point2 offspring stringl 
father string?  [1|0111]212]1|0 110121310121 110 
exchange offspring string? 
Figure 3 the example of point-crossover 
The integer vector generally adopts two kinds of crossover 
operators: point-crossover and even-crossover. The experiments 
have proved there is no too much difference between the 
influences of two kinds of crossover operators on the 
performance of labeling algorithm. Therefore the labeling 
algorithm adopts the point-crossover strategy. 
The point-crossover operator is divided into single-point- 
crossover and multipoint-crossover. The single-point-crossover 
randomly selects a cross point on two father strings and then 
exchanges the corresponding sub-strings of the two strings. The 
multipoint-crossover randomly generates several cross point 
every time, and then exchanges the corresponding sub-strings of 
father strings respectively [Pan Zhengjun, 1998]. Figure 3 gives a 
chromosome point-crossover example of two labeling place- 
ments with the string length 8 and the gene code set 10, 1, 2, 3}. 
4.4.3 Conflict gene mutate (namely mutate on conflict gene) 
For integer vector encoding, the common mutation includes 
point-mutation and even-mutation. The former selects single 
point, the latter selects point according to some template, and 
then randomly relocate the selected point. 
As for map labeling, we put forward a new mutation operator 
which is called conflict gene mutation to replace the routine 
point-mutation and even-mutation. The basic theory of conflict 
gene mutation is that: select the gene of conflict label, randomly 
generate a labeling code to replace the original gene. 
Experiments have proved the conflict gene mutation is very 
effective. Figure 4 shows the comparison result of the conflict 
gene mutation and even-mutation with the same genetic 
parameters (the number of iterations is 300, population size is 50, 
crossover probability is 0.75, mutation probability is 0.2). From 
figure 4 we can find that the conflict gene mutation is obviously 
superior to the even-mutation. The possible reasons are as 
follows: 
(1) The point-mutation and even-mutation are blind, and the 
conflict gene mutation utilizes the heuristic information of label 
conflict to improve the bad sub-solution, so the probability of 
obtaining good sub-solution is bigger. 
(2) In actual maps, there is little conflict in the area with sparse 
labeling point, the mutation probability should be smaller, 
however in the area with dense labeling point there is more 
conflict, and the mutation probability should be relatively larger. 
The conflict gene mutation meets this demand. 
  
  
1 — & E E e 
qd ptt "s 
o 0355! + 
5 | 
Ca — 09! + 
a | 
0.85: 
E à | e + 
= + Mutate on . | 
= 0.75 + Conflict Gene 
3, E : 5 
s ds | Even Mutate 
"rj & i + 
o 0.65 | 
E nl 
u i * 
5 0.55 
5S 09 
  
ü 200 400 600 200 1000 1200 1400 1600 
Labeling Poing Numbers 
Figure 4 compare conflict gene mutation with even mutate 
4.5 determine the important parameters of genetic algorithm 
According to references and experiment conclusion, there are the 
following principles in determining the genetic parameters of 
automated labeling: 
620 
Inter 
  
(1) 1 
algor 
doma 
(2) X 
Cross 
this p 
(3) M 
the d 
03.1 
(4) T: 
over 
termi 
guara 
to jud 
opera 
stably 
impro 
V. 
CON 
The e 
two p 
by the 
actual 
topogi 
1:250( 
layers 
The th 
and 27 
From | 
point | 
gradu: 
genetk 
has m 
popula 
point 
MILYSAE. 
‚#8 
ET 
su 
“14e 
vaux 
Figure 
The ex 
algoritl 
compar 
on the ¢ 
the pro 
parame 
populat 
increase