Application of the Multi-Objective Pareto-based GA in Solving Geospatial Optimisation Problems
Mirza Ponjavic2, Zikrija Avdagic1, Almir Karabegovic2
1Faculty of Electrical Engineering, University of Sarajevo,
Zmaja od Bosne b.b., 71000 Sarajevo, Bosnia and Herzegovina,
Tel: (+387) 33 25 07 37, Fax: (+387) 33 25 07 25
2Faculty of Civil Engineering, Department of Geodesy, University of Sarajevo,
Patriotske lige 30, 71000 Sarajevo, Bosnia and Herzegovina,
Tel: (+387) 33 27 84 00, Fax: (+387) 33 20 01 58
Email: ab.ssuagnull@azrim , ab.ssuagnull@rimla
This work studies the development and application of the multi-objective genetic algorithms based on the Pareto approach, as a tool for the support in deciding in the geospatial analysis. The implementation of the suggested multi-objective Pareto based GA over selected instance of the location-allocation geospatial optimisation problem demonstrates its ability of the discovery of multiple compromise solutions in a real problem domain.
Multi-objective genetic algorithm – Geospatial analysis – Geoinformation system – Location-allocation problem
Generally, real geospatial problems of the optimization are characterized with two types of complexity: the existence of multiple conflict objectives and the great space of the research.
Multi-objective genetic algorithms have the properties that address their complexity in both meanings. Furthermore, their ability of generating set of the non-inferior solutions enables planners to explore the options and effects of the alternative solutions, as a compromise between different objectives. The exploration of such compromises in the spatial domain can be very complex. The application of the Geographical Information Systems (GIS) gives an additional dimension to the multiobjective approach, since it enables the planner to manipulate with spatial data and to create new information.
This work studies the application of potential techniques of the artificial evolution in the geospatial analysis. The research objective is the development of modified multi-objective genetic algorithms based on the Pareto approach as a tool for the support in the decision making process in the geospatial analysis, as well as the examination of its efficiency in the test and real problem environment. Within the realisation of this objective, the implementation of the PBMOGA is demonstrated in the geospatial multiobjective problem domain.
Implementation of the PBMOGA in geospatial environment
The implementation of the Pareto-based multiobjective genetic algorithms (PBMOGA) for the application in the domain of multi-objective spatial location is established on the paradigm of layered spatial network model of data, where the spatial information (location address of the network cell) in the PBMOGA is represented by the standardised continuous values.
The utilisation of data layers, where each layer represents a special spatial aspect (land use, population distribution, resource allocation) is a typical form of the representation of the spatial information in the GIS. This concept (a layered spatial model) is based on the information layering by types, whereof every type is abstracted by an individual layer. In the evolutionary spatial model, the layers represent the sets of attribute information specifying the quality and/or quantity characteristics of the spatial phenomena (population density, attractiveness of sale facilities, land value) and not just the phenomena (location, form and size of the spatial features) .
The main component in the evolutionary representation of the space is a chromosome that abstracts the spatial location. As the location is specified by the location coordinates in a reference system, the genes constituting the chromosome represent its (geographical) coordinates.
In this way, the population is represented by the collection (of predefined number) of individuals storing the genetic material that contain the information about locations relating to the corresponding spatial experience. The quality of the experience is measured by the fitness, which represents the value of objective function (measures of the location quality). A set of objective functions is represented by the network model, while individual objectives are represented in layers.
By the algorithm activation, the set of random locations (initialisation) is generated in the domain of the location search, which represents the initial solutions for the multi-objective problem. A simultaneous scanning of cell values for the specified objectives is performed during the initialisation.
After initialisation, the Pareto ranking of initial (evaluated) solutions (locations) is performed, which is analogous to local and focal operations of the cartographic algebra. Within this process, initial objective values are tested and sorted by their comparison for the whole set of cells referenced within the population.
After ranking, the algorithms proceed to the spatial selection of general solutions (locations) that belong to the Pareto set. By a crossing operator, the acquired spatial experience (the exploitation process) is exchanged through genetic material, while new spatial experience (the exploration process) is acquired through a mutation operator .
The mutation is realised by the random change of address values of the cells (that have locations in the reference system as mapping coordinates), that are obtained after the crossing, in this way exploring the spatial potential of locating. With the application of elitisms in algorithms, the locations with the best spatial experience are kept for their utilisation during generation of new offspring. After every application of the aforementioned operators, the obtained solutions are evaluated, i.e. the objective values are scanned (based on the cell addresses) from corresponding matrices (network layers) for every solution (location) of the existing population.
An adequate set of the specified PBMOGA parameters is applied for the aforementioned genetic operators, determining a level of their activity, i.e. their operating characteristics. A mechanism of buffering of the most quality locations generated during the iteration of Pareto-based algorithms is realised at the same time as the specified process.
In the context of the described approach, the implementation of the Pareto-based GA in the geospatial optimisation means the representation of the solutions in three spatial domains: objective space, space of decision variables and geographical space. In the objective space, a set of nondominated solutions forms a Pareto front, corresponding to the Pareto set in the space of decision variables, i.e. a set of items defined by the variable values (of cell addresses). In the geographical space, the cell addresses are copied (converted) to coordinates of suboptimal locations (for non-inferior solutions).
After the identification of the set of Pareto optimal solutions, the decision makers select the locations (offered solutions) from the Pareto front that best meet the specified objectives based on the acceptability of objective performances .
Multi-Objective Problems of the Spatial Locating
For the purpose of the representation of the set of location spatial problems, as an example we can observe a multi-objective location modelling of problem of selection of suitable location for a fire station, which is frequently presented in the example form in the literature of the multi-objective decision domain (Cohon, 2004.) . For the realisation of objective functions, an authentic geospatial data, including a demography and public infrastructure regarding the urban space of Tuzla town (in Bosnia and Hercegovina), will be used in the example.
Location Model of the Fire Station
The town space (6 by 3 km) is presented by the grid of 200×100 cells, whose dimensions are 30×30 meters. The grid is oriented along its longer side to the direction of the town spread, i.e. from the west to east.
For the purpose of the implementation of the Pareto-based algorithms, the objective functions, realised by the application of the tools for location profile, are given in a matrix form:
where r is a total number of rows while k is a total number of matrix columns.
The optimal coverage of the town space from one place can be incorporated with the objective function minimizing a total distance of the passed route from the required location to potential users:
• i=1…n, where n is a number of locations of potential users,
• j=1…m, where m is a number of potential alternative locations (a total number of cells in the network, m=rxk),
• wi is a weight that is assigned to the i potential user, and
• dij is a length of the route from the j alternative location to the i potential user.
Since, there are two sets of items: S – a set of all locations of residential facilities and K – a set of all locations of commercial-industrial facilities; two objective functions can be derived from the expression (2):
• is=1…ns, where ns is a number of locations of residential facilities,
• ik=1…nk, where nk is a number of locations of business (commercialindustrial) facilities,
• j=1…m, where m is a number of potential alternative locations (a total number of cells in the network, m=rxk),
• wSis is a weight that is assigned to the i location of the residential facility,
• wKik is a weight that is assigned to the i location of the business facility,
• dSis,j is a length of the route from the j alternative location to the is location of the residential facility, and
• dKik,j is a length of the route from the j alternative location to the ik location of the business facility.
These objective functions, for the decision makers and according to the problem description, present two interests that can be more or less conflict depending on the spatial arrangement of the locations of the facilities from the S and K.
The first objective (interest) is a minimization of the average distance between the fire station and the residential facilities, while the second objective (interest) is a minimization of the average distance between the fire station and the commercial and industrial facilities. The conflict of the objectives is reflected in the fact that the protection of public, commercial and economic capacities does not always include the best protection of the population.
Results of the Multi-Objective Location of the Fire Station
The Pareto-based multi-objective genetic algorithm (PBMOGA) is applied to the problem solving.
In the generation of alternative locations, the following parameter values are used for the PBMOGA: maxit=50 (for the iteration number), dmin=0.02 (for the resolution of the Pareto front), popsize=300 (for the population size), mutrate=0.01 (for the mutation probability) and elitrate=0.1 (for the elitism factor).
Fig.1 and Fig.3 give an overview of the alternative locations for the fire station, obtained by the application of the Pareto-based multi-objective genetic algorithm.
On the right of the Fig.1, there is a legend describing the ratio of objective values c1/c2 for given alternative solutions. Thus, a ratio for the regions indicated with blue (east part of the town) is c1/c2=0.64, a ratio for the regions indicated with shades of green (central part of the town) is in the range between 0.69 and 0.96 and ratios for the regions indicated with shades of red (west part of the town) are 1.28 and 1.39. The solutions (locations) with smaller ratio are more preferable for the first objective regarding the population protection, while the ratio increase is more preferable for the second objective, i.e., for the protection of business facilities.
An important indicator for the multi-objective decision presents a cost of the compromise, i.e. a value of one objective which must be sacrificed in order to obtain a specific increase in behalf of the second objective. The compromise cost is here presented in the graphics (Fig.2), where the form of the Pareto front reflects the change rate of one objective function with regard to the change of the second objective function. The connection of the spatial arrangement of solutions and the corresponding cost of the compromise presents an important quality parameter, which is used in their multi-objective analysis.
Eight solutions, which are presented in the objective space in Fig.2 and in the geographical space in the Fig.3, are obtained by the application of the Pareto-based multiobjective GA, with the specified parameters. The best compromise solution ad hoc is the solution with the ratio of objective values of 0.96, which is the middle between the highest and lowest ratio for the given set of solutions.
The obtained results demonstrate practical implications of the application of the multiobjective analytic approach. Namely, the value of multi-objective approach to the facility location can be considered through Fig.1. A line of items with the ratio of objective value from 0.69 to 0.96, arranged on a small spatial scope (middle part of the town), cover a very wide rank of alternatives. We can notice in the Fig.2 that a significant gain in the coverage of residential facilities can be obtained with a relatively small sacrifice of the coverage of business facilities, with some minor changes of geographical location. Real situations will not probably demonstrate such a wide rank in the compromise between the objectives. However, multi-objective approach will certainly be necessary in order to avoid the unbalanced solutions such as the items identified in the east and west of the town (Fig.3).
The implementation of the multi-objective Pareto based GA over the real optimisation problem of the spatial location of the fire station demonstrates the ability of discovery of multiple compromise solutions through one passage (activation) of the application. The approach generalization is realised by the choice of the examples addressing typical multi-objective applications in the locationallocation optimisation. The obtained results imply the great potential and satisfactory efficiency of the implemented optimisation mechanism, as well as the possibility of its further application in solving this type of problem.
 Carlos A. Coello Coello, David A. Veldhuizen, Gary B. Lamont: Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic / Plenum Publishers, New York, 2002
 A. Abraham, L. Jain, R.Goldberg: Evolutionary Multiobjective Optimization, Theoretical Advances and Applications, Springer-Verlag London Ltd. 2005
 Jared L. Cohon: Multiobjective Programming and Planning, Dover Publications Inc., Mineola, New York 2004
 T. Bäck, D.B. Fogel and Z. Michalewicz: Evolutionary Computation 2, Advanced Algorithms and Operators, Institute of Physics Publishing Bristol and Philadelphia 2000
 R.L. Haupt, S.E. Haupt: Practical Genetic Algorithms, John Wiley & Sons, Inc., Hoboken, New Jersey 2004
 Robert Haining: Spatial Data Analysis: Theory and Practice, Cambridge University Press 2003
 M. Batty, P.A. Longley: Advanced Spatial Analysis, ESRI Press 2003
 P.Longley, M.Goodchild, D.Maguire, D.Rhind: Geographic Information Systems and Science, John Wiley&Sons, Ltd. England 2002
 Roman Krzanowski, Jonathan Raper: Spatial Evolutionary modeling, Oxford University Press, Inc. NewYork 2001
 Mark Birkin, Graham Clarke, Martin Clarke, Alan Wilson: Intelligent GIS, Location decisions and strategic planning, GeoInformation International, Pearson Professional Ltd. Cambridge 1996
 Peter A. Burrough, Rachael A. McDonnel: Principles of Geographical Information Systems, Spatial Information Systems and Geostatistics, 2000
 Eckart Zitzler, Marco Laumanns, Stefan Bleuer: A Tutorial on Evolutionary Multiobjective Optimization , Swiss Federal Institute of Technology Zurich, 2003
 Samim Konjicija, Zikrija Avdagic, Bakir Lacevic: Performance of Genetic Algorithm with Adaptive Mutation Probability Dependant on Fitness in Dynamic Environments, Faculty of Electrical Engineering Sarajevo 2005
 P.A.N. Bosman and D. Thierens: The Balance Between Proximity and Diversity in Multiobjective Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 7. No. 2, April 2003
 Ladda Pitaksringkarn, Michael A.P. Taylor: Grouping Genetic Algorithm in GIS: A Facility Location Modelling, Journal of the Eastern Asia Society for Transportation Studies, Vol.6, pp. 2908-2920, 2005
 David A. Van Veldhuizen, Gary B. Lamont: Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art, Air Force Institute of Technology, Ohio, 2001
 Mirza Ponjavic, Zikrija Avdagic, Almir Karabegovic: Geographic Information System and Genetic Algorithm Application for Multicriterial Land Valorization in Spatial Planning, CORP2006: 11th International Conference on Urban Planning & Regional Development -Vienna, Austria, 2006