M. Ponjavic *, Z. Avdagic ** and A. Karabegovic*
*Gauss, Geo Information Systems, Tuzla, BiH
**Faculty of Electrical Engineering, Sarajevo, BiH
mirza @gauss.ba, firstname.lastname@example.org, almir @gauss.ba
Abstract— This paper shows how to apply genetic algorithm (GA) in optimization of spatial valorization multicriterial model during the regional urban planning process. The matter exposured in the work, describes both the problem of multicriterial spatial valorization from land use aspect and finding the optimal model methodology. The crucial points of the research are the following: possibility of multicriterial valorization of the land from the GA use perspective, how to utilize the capacity of the GA optimization techniques in the frame of decision support system and with usage of the GIS tools and how to apply the GA in the field of genotype presentation in spatial modeling. The paper is illustrated by actual examples taken from the spatial planning area and available existing studies in this field.
One of the key products in urban spatial planning is digital land use map, that with a system of settlements and traffic infrastructure plan, describes spatial organization. Using the optimal model of multicriterial land use valorization with Geographic Information System (GIS), this map could be generated automatically. The model requests a methodology built on existing principals of spatial planning and based on both GIS and multicriterial spatial analysis applications. In this work it has being developed a methodology for finding the optimal model of multicriterial land use valorization by means of genetic algorithm (GA). The methodology could be used for development of decision support system in spatial planning.
II. MULTICRITERIAL OPTIMIZATION PROBLEM IN SPATIAL PLANNING
The optimization problem always exists when there are more alternatives in space, among which the most acceptable should be selected. So, problem is related to multicriterial optimization. In synthesis phase of planning, typically, opposed alternatives for spatial organization are presented by synthesis models. Due to environmental trend in urban spatial planning it is defined a, so called, environmental model based on protection of environment, and as such favors criteria which guarantee an environmental values continuity. Another one is functional, based on aspect of as more as possible land exploitation for settling, not seeing the environmental consequences. Simulating these variants by adjusting the criterial weights it is possible to search for optimal model of spatial organization. This fact designates to possibility of genetic algorithm application in multicritrial optimization process.
III. SPATIAL REPRESENTATION BY LAND UNITS
For an example is used region of Tuzla Canton enclosing 13 municipalities with total area of 2700 km2. For spatial representation of the region of interest is used 2-dimensional grid of cells (land units), arranged in rows and columns, and with resolution of 100mx100m. To each of land units, it is added a database record, i.e. a set of attributes related to the unit properties in sense of its accessibility. By these attributes, during the multicriterial analysis it is performed scoring and classification of the units. Optimal model of land valorization is result of processing of data related to specific criteria. For realization of 2-dimensional grid, its integration with criterial database and geographic thematic representation of results is used GIS.
IV. CRITERIAL FACTORS AND CATEGORIES USED FOR LAND USE VALORIZATION
For land use valorization, the following criterial factors are used: land accessibility (related to the center of settlement), slope of terrain, relative height (above lowest point) of terrain, aspect of terrain, value of land usable for agriculture and forestry (according to adopted soil classification) and environmental value of vegetation coverage (estimated according to basic topographic classification). For synthesis models (functional and environmental) are introduced the following four categories of land use: extraordinary suitable, very suitable, suitable and unsuitable. Extraordinary suitable category is related to area for reconstruction, and basic use is mixed: collective and individual dwellings with central functions (e.g. services, administration etc.). Very suitable category is related to area of intensive urbanization with collective and individual dwelling units, industrial and recreation zones.
Suitable one is related to area of extensive urbanization with mostly individual dwelling units, rural agricultural production and small business. Unsuitable category includes two sub-categories. One is related to area mostly intended for agricultural production, and only exceptional for other uses. Another, which is related to area reserved only for forestry and agriculture, is not considered here.
V. APPLICATION OF GISIN DATA PREPARING FOR MULTICRITERIAL ANALYSIS
Fig. 1 shows 3D model of Tuzla Canton that enables classification of heights, aspects and slopes of terrain. By defined parameters for every class of aspect and slope it is possible to create thematic map in GIS. Assignment of criterial valuesto classes is realized by selection of objects belonging to specific class and by attachment of common attribute values in database. Five classes are defined for aspects: east, west, north, south and horizontal. Slopes are divided into five classes: flat, small inclination, inclined, steep and very steep. During the classification of relative heights, three zones are used for scoring: plain, hill and mountain land. To classify usability, here are used three categories of land bonity, and classification of land accessibility is based on chronometric analysis realized in GIS. By CORINE methodology is provided classification of environmental value of land. All classes are scored in scope from 1 to 5 points. Land for reconstruction is determined by analysis of existing construction areas, as it is shown in Table I.
VI. REPRESENTATION OF ALTERNATIVES BY SYNTHESIS MODELS
Weights of criteria are defined according to differences in their importance. Behavior of the model, in functional and environmental sense, is possible to describe by the following set of linear equations:
p1= -2,5 tgα+ 3,5
p2= -1,5 tgα+ 3,5
p3= -0,5 tgα+ 3,5
p4= 0,5 tgα+ 3,5
p5= 1,5 tgα+ 3,5
p6= 2,5 tgα+ 3,5 (1)
where p1, p2… p6 denote weights of specific criteria, and α is angle of model gravitation that represents how much the model gravitates to some of the alternatives (synthesis models).
VII. OPTIMIZATION OF MODEL
If coefficient of direction, tangαi, vary from -1 to 1, then angle of gravitation, αi ,takes values from – 4 / π to 4 / π . Optimum model is characterized by total suitable area P depending on the angle α.
If existing land for construction is adopted as extraordinary suitable category, than the condition for model optimization can be described by expression:
where Pr is extraordinary suitable area for optimum model, and PO is existing land for construction.
In order to make description of the problem easier, function Pr(α) is presented by appropriate polynomial ψr, and expression (2) can be transformed into:
which represents objective function for model optimization.
VIII. FITNESS FUNCTION
According to expression (3) fitness function Ff can be described as:
where n is total number of enclosed municipalities.
The expression (4) is used for evaluation of fitness values needful for creation of each next generation of potential solutions (chromosomes).
Fitness function is defined in M-file (Matlab) by calculated polynomial coefficients and balance of areas from Table I.
IX. REPRESENTATION OF CHROMOSOME
For representation of chromosome it is used binary string λ. Variable is encoded so that it presents real values of the angle of gravitation in radians. Domain of searching is defined with adopted precision of 0.01 radian. By this way, the solutions are presented by chromosomes (104 bits strings) consisting of 13 genes. Each of the gene (8 bits string) represents model (by angle of gravitation) of specific municipality.
X. PARAMETERIZATION OF GAAND RESULTS
After the testing, the parameters which gave acceptable results of optimization are determined as: roulette wheel selection, 100 chromosomes in population, elite count 2, crossover fraction 0.25, mutation with gaussian distribution, single point crossover and stopping after 500 generation. Final value of fitness obtained in the last generation is 0,24 ha, while predefined value of tolerance is 2 ha (Fig.3). Angles of model gravitation obtained by GA optimization are given in Table II.
XI. LAND USE CLASSIFICATION AND THEMATIC PRESENTATION IN GIS
Applying the genetic algorithm for searching the optimum model for land use classification are determined values of the angles of gravitation enough close to optimum. In order to achieve final objective of multicriterial analysis, it is necessary to perform aggregation, i.e. summing the factorized criterial values and classifying the areas according to the land use (already described). Total value of a land unit is calculated as:
where: wik are normalized weights from equations (1), for criteria i=1…6 and municipalities k=1…13,
f i is assigned scores for specific criteria, and υmax i υmin are maximal and minimal value of land unit (υmax =3.276, υmin =-3.276).
Table III shows ranked values used for classification of land use. Based on the ranked values is made thematic visualization in GIS of total land units values. To each of
the ranks (classes) is assigned a corresponding color (Fig.4).
As one of the approaches for finding a methodology for multicriterial land use valorization, application of genetic algorithm gave acceptable results. Weights pi, used in initial equations of mathematical presentation, are indirectly optimized by modified objective function applied in GA during fitness values evaluation.
Populations of binary vector strings which indirectly represent solutions for criterial weights, are maintained by unique mechanism of GA. By this way is enabled searching the alternatives of spatial organization for given land use categories and finding the optimum alternative. The optimum can be searched for various given parameters influencing the objective function. Due to its general application, genetic algorithm could have key role for development of a decision support system for spatial multicriterial analysis.
 Z. Avdagic, Vještačka inteligencija & fuzzy-neuro-genetika, 2003.
 Z. Avdagic, Metode i primjena vještačke inteligencije, 2004.
 M. Bublin, Prostorno planiranje, Univerzitetska knjiga, Sarajevo, Studentska štamparija, 2000.
 P. Longley, M. Goodchild, D. Maguire, and D. Rhind, Geographic Information Systems and Science, John Wiley&Sons, Ltd. England, 2002.
 MatLAB 7, Genetic Algorithm and Direct Search Toolbox , User’s Guide for Use with Matlab
 M. Ponjavic, A. Lojo, GIS u gazdovanju prirodnim resursima, Gauss d.o.o. Tuzla, 2004..
 S. Alert, Information Systems, The Foundation of E-Business, Prentice Hall, New Jersey, USA, 2002.
 T.J. Stewart, R. Janssen, M. van Herwijnen, “A genetic algorithm approach to multiobjective land use planning”, University of Cape Town, University for Environmental Studies, Vrije Universiteit Amsterdam, 2004.
 K.B. Matthews, S.Craw, I. MacKenzie, S. Elder and A.R. Sibbald, “Applying Genetic Algorithms to Land Use Planning”, Proceedings of 18th Annual Conference of the BCS Planning and Scheduling SIG, ISSN 1368-5708, 1999..
 M. Ponjavic, “GIS Application in Implementation of Spatial Plan”, IV Conference of Urbanism in BH, Tuzla, 2002.
 M. Ponjavić, A. Karabegović, “Land Inventory System and Valorization of Agricultural Areas”, Progis International Conference “IT in Rural Areas”, 2004.
 L. Biggiero, D. Laise, “Organizational Behavior and Multicriterial Decision Aid”, 2nd Annual Conference of Innovative Research in Management, Stockholm, 2002.