Implementation of Genetic Algorithm (GA)

This section introduces briefly the on going study on using genetics algorithm (GA) to automate the spatial and temporal rule calibration. GA as a heuristic optimisation technique can work over the search space to find the most suitable solution. GA improves the efficiency of rule calibration to select the best set of rule values for accurate modeling. GA was first introduced by Holland (1975) as computer programs to mimic the evolutionary process in nature. GA manipulates a set of feasible solutions to find an optimal solution and is able to find the global optimum solution (S. Alkheder and J. Shan, 2006). The following steps describe the design of the proposed GA-based transition rule calibration.

Step 1: Initial GA population generation: In this step, 30 set of rule values were randomly generated as an initial population for each direction over which GA module would work. Each rule value set was coded as a binary string and a string was designed as a combination of the rule values. Two rules were identified to be optimised using GA.

Rule 1: The number of neighbourhood urbanised (residential plus commercial) pixels, in the possible range of [0-8] integer values or in corresponding binary coding [0000 to 1000].

Rule 2: The population density threshold, continuous values represent the cut-off population density at a pixel. This rule was scaled by multiplying its value by 10 in the range of [0-10] possible values or in binary coding [0000 to 1010].

Step 2: Fitness function identification: Fitness function evaluates the performance of each string. The prediction accuracy was used as the fitness function.

Step 3: GA selection operation: Rank selection procedure was used here. All the strings were ordered based on their fitness values in descending order and the string with highest fitness value was given rank 30 then the second one 29 till lowest fitness value with rank 1. Rank was divided by the summation of all the ranks and the probability of selection for each string in next generation was identified.

Step 4: GA crossover and mutation parameters design: The crossover probability was selected to be 80%, 24 strings were selected for crossover, while the other 6 (the best 6 in terms of fitness values) were copied directly to the new generation (this process is known in GA as Elitism). Elitism can rapidly increase the performance of GA, because it prevents a loss of the best solution. A mutation rate of 1% was used. Once the crossover and mutation was done, the new generation of 30 strings was produced and the loop continued. This continued until the convergence criterion was met. The final output was the optimized CA rule values that model the temporal urban growth. The model is run over the western region of the city to project the growth in 2006 using 1992 data. The final result (figure 8) indicates good match (94 %) with the real 2006 classified image.

Figure 8: GA-CA calibrated results for the year 2006.