I 
es 
1 
1al is calculated 
st individual is 
scheme. 
mates newly 
ien it randomly 
of individuals. 
he window are 
S). 
  
  
  
ry role in the 
in a individual 
  
  
lual 
IN Gas 
e efficiency of 
em resolutions 
ntly conflicting 
rently available 
ker, GA&SA). 
1 class general 
onable balance 
power of these 
iple heuristic 
ound in regions 
   
of the search space containing relatively high proportions 
of good solutions. The problem is that, if the complex space 
of problem resolutions become larger and larger, the 
population size and the generation size have to be increased 
at same time. Therefore, the efficiency of GA is one of 
obstacles to apply GA in reality. 
Hill climbing is a good example of a search strategy 
that exploits the best among known possibilities for finding 
an improved solution. Although Hill-Climbing strategies is 
easy to trap in one of local maxima more far away from the 
optimal solution, it is a very good search strategy that 
exploits the best among known possibilities for finding an 
improved solution. So in our research we try to combine 
the Hill-Climbing strategy with GA. 
4.2 Maintenance of Population Diversity 
Estimates based on finite samples in GA inevitably 
have a sample error associated with them. Repeated 
iterations of algorithm compound the sample error and lead 
to search trajectories much different from those theoretically 
predicted. The most serious phenomenon is the premature 
convergence. The premature convergence is caused by early 
emergence of an individual that is better than the others in 
the population, although far form optimal. Copies of this 
structure may quickly dominate the population. Search 
continues then but is concentrated in the vicinity of this 
structure and may miss much better solutions elsewhere in 
the search space. 
To avoid the premature convergence, one has to 
maintain population diversity or to reduce the different of 
best fitness with others. Althou gh, to reduce the reproduction 
number can not eliminate the premature convergence, it can 
be used as a simple way to reduce the rapid convergence. 
Therefore, in our research, we limited the duplicated number 
of individuals less than two. It means that if individual's 
expected duplicated number is larger than two, we will force 
it to equal two. To do so, the premature convergence speed 
can be reduced. 
5. EXPERIMENTS 
The test program of GA/HC for spatio-temporal 
interpolation of pixel based landuse data was coded with C 
language and was run on SPARC/station2. Several simple 
landuse class variable data had been used to test program. 
Small spatio-temporal datasets are used in the experiment 
to check the behavior of the GA/HC based interpolation 
under different conditions. The test data size of individual 
had been defined with 20 pixels * 6 time-slices for two 
dimensional case, while 1 lines * 11 columns * 6 time slices 
for three dimensional case. The first and last time-slice in 
~~ Boundary condition - 
22222200222112222222 Space 
20000000222111111122 
Boundary condition 
Estimated 
class values 
Time 
Figure.7 a) Result of GA/HC (2D case) 
Time 
Time 
  
    
      
     
Observational Data 
    
  
7 / 
^ € 7 ; - 
ToL Oly 
7 
^ 
fL 
  
51111111111 o] Observational Data 
Y Observational Data / Y 
Figure.7 b) Result of GA/HC (3D case) 
the individual are supposed to be sample (observational) 
data and all middle time-slices should be estimated by the 
interpolation. In these experiments, we set the generation 
size of GA/HC to 2000, which was large enough to get stable 
results. The probability of crossover operation was defined 
as 0.7, while the probability of mutation operation was 
relative small in natural population, so that we used 0.01 as 
the probability of mutation. Figure.7 is two dimensional 
and three dimensional experiment results of GA/HC, in 
which the individual has largest fitness value. With the 
assumed model, smooth transition/expansion has the largest 
fitness or likelihood. 
In Figure 8, observed location of class '0' in the 
first time slice and the last time slice are overlapping 
spatially. The Interpolation result naturally connect class '0' 
together, forming a band of class '0'. On the other hand in 
Figure 9, while class '0' is not overlapping, it is demonstrated 
that the most likely interpolation do not connect class '0’ 
together, and that a case forming a band of class '0' apparently 
have lower likelihood, though it looks natural. InFigure.10, 
another observational data is given at the middle. In this 
case, the most likely spatio-temporal pattern of class changes 
has a band of class '0'. It is concluded that the interpolation 
method integrating observational data and behavioral 
models/rules can estimate the most likely voxel field under 
different conditions. 
  
  
  
  
11d 1000011 
| 1111000011 
  
  
  
  
  
TimW Observational data Time) Interpolation result 
Figure. 8 Interpolation Result (Overlapping case) 
807 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996