Pareto-Based Genetic Algorithm in Multi-Objective Geospatial Analysis

Mirza Ponjavić, Almir Karabegović,
Department of Geodesy, Faculty of Civil Engineering
University of Sarajevo
Patriotske lige 30, 71000 Sarajevo, Bosnia and Herzegovina
Phone: (+387) 33 27 84 00 Fax: (+387) 33 20 01 58 E-mail: ab.signull@azrim

Abstract – This work studies the application of the multiobjective genetic algorithm based on the Pareto approach, as a tool for the decision making support in the geospatial analysis. Pareto-based evolutionary mechanism developed as an approach to multi-objective geospatial optimization operates with fixed parameters of genetic operators. It can be used as efficient tool for multi-objective planning both for their power and flexibility and the fact that they generate a whole set of good solutions rather than just one “optimal” solution. Within the studies it is tested and suggested an adaptive mechanism for mutation parameter based on the deterministic approach. The application of the suggested multi-objective Pareto based genetic algorithm over selected location problems demonstrates its ability of the discovery of multiple compromise solutions in a real spatial problem domain.

1. INTRODUCTION

     Generally, real geospatial optimization problems are characterized with two types of complexity: the existence of multiple conflict objectives and the large space of searching. Multi-objective genetic algorithms have the properties that address their complexity in both meanings. Furthermore, their ability of generating set of the noninferior solutions enables planners to explore the options and effects of the alternative solutions, as a compromise between different objectives [1]. 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 multi-objective approach, since it enables the planner to manipulate with spatial data and to create new information [2].

     This work studies the application of potential techniques of the artificial evolution in the geospatial analysis. The research objective is the development of modified multiobjective genetic algorithm 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.

2. MULTI-OBJECTIVE OPTIMIZATION PROBLEM AND

PARETO APPROACH

     Multi-objective optimization problem includes finding a set of values for decision-making variables that satisfies inequations and/or equations of constraints (i.e. environmental characteristics) and (globally) gives optimal values for all objective functions (i.e. criteria) [3]. However, when there are several objective functions, which are (usually) in a mutual conflict, it happens that  optimal solution for one function excludes optimal solutions for all other objective functions. In this case, the meaning of “optimum” is changed and the objective is to find good compromises rather than a single solution as it is case in global optimization [4]. This kind of comprehension of “optimum” is most frequently called Pareto optimum. A solution (i.e. a set of values of decisionmaking variables) is said to be Pareto optimum if there is no other feasible solution that would minimize some criteria (i.e. value of some objective function), without causing a simultaneous increase in at least one of other criteria (in the case of minimization of objectives). Region (set) of Pareto optimal points in the objective space forms the Pareto front (Fig. 1.).

3. THE ALGORITHM WORKFLOW

     In the sequence of its operations, Pareto-based multiobjective genetic algorithm (PBMOGA) corresponds to a simple evolutionary algorithm used for single-objective optimization. After the creation of initial population by generation of random number, the algorithm approaches to fitness valuation that is in this case realized through tasks of sorting and ranking based on the Pareto domination (Fig. 2.). After selection of chromosomes, it approaches to the application of genetic operators responsible for searching and exploitation of information in multi-objective searching space. Operator elitism maintains a stable convergence and solution diversity along the current (primary) Pareto front (PF_current) [5].

     The basic criterion for termination of algorithm is a given resolution (between solutions) along the known (secondary) Pareto front (PF_known). Verification of achieved resolution is performed based on solutions realized for secondary population (from the buffer).

     The whole mechanism is based on the paradigm of primary and secondary population, which is characteristic for the group of algorithms (with Pareto approach) of the latest generation, which are researched intensively (e.g. SPEA, PAES, PESA, micro GA etc.) [6].

4.  MODIFICATION PBMOGA WITH ADAPTIVE MUTATION

MECHANISM

     The paper also examines the possibility of modification of the algorithm in terms of introducing a mechanism for adaptive mutation operator with a deterministic approach. This approach is based on a deterministic expression that contains the values of which describe the relation between the position of the population in the objective space and the current Pareto front. The basic principle applied in this case is that the mutation probability increases for worse chromosomes (by comparison with the better ones), with an exponential dependence. In this way increases the chance to preserve the better chromosomes unchanged, and to improve the worse ones by mutation. By applying this approach it is created a modified multi-objective Pareto based genetic algorithm (mPBMOGA), which is treated as a separate instance of the Pareto-based GA.

     The adaptive mechanism is based on the simultaneous use of two deterministic expression for calculating the  probability of mutations: one for parents and another one for offspring chromosomes.

A. Determining the probability of mutation for parents

     After the crossover, the population is composed of parent chromosomes, who largely represent the current Pareto front, and offspring chromosomes, who are spatially distributed around them (in the objective space).

     To determine the probability of mutation for parents it is used the following expression:

where:

• 
  p^m_p is probability of mutation for parents (who constituted Pareto front),
•  a_i is difference between the average length of segments of the Pareto front (D_p) and length of the corresponding i-th segment of the point p_i (parent in the objective space), which is calculated on the basis of expression:

• d_p,min and d_p,max are minimum and maximum length of segment and
• 
  s_p is real parameter of exponential dependence for parents (s_p=s)

     The average length of a segment Pareto front is defined as the average of all distances between adjacent points (parents) in the Pareto front:

where n is the number of parents, and d_pi are the corresponding distances between points of Pareto front in the objective space.

B. Determining the probability of mutation for offspring

     Previous expression (1) can not be used for part of the population which refers to the offspring, because they are mainly deployed around the current Pareto front. Therefore, a deterministic expression which defines the probability of mutation of offspring is based on the mutual relations of their shortest distances from the actual Pareto front.

     All solutions (offspring), which fall into the space ahead of the current Pareto front, as well as those who lie in the Pareto front, are the non-dominated solutions in the current Pareto set P_current, and therefore have a high probability that dominate in the new (updated) buffer P_{known (t +1)}. As such, it is desirable that they remain unchanged and to provide further convergence of secondary Pareto front PF_known. In this case, these solutions has a probability of mutation p^m_c =0.

     Furthermore, the mutation probability for offspring, which lie in the space behind the Pareto front is determined by the following expression:

where:

• p^m_c is probability of mutation for offspring who lie in the space behind the Pareto front,
• 
  b_i is the variance of offspring in the objective space, which is calculated by the expression:

• 
  d_c,min and d_c,max are minimum and maximum length of segment to Pareto front and
• 
  s_c is real parameter of exponential dependence for offspring (s_c=s).

The average length D_c is defined as the average value of all shortest distances offspring to the Pareto front:

where m is number of offspring, and d_ci are shortest distances offspring to the Pareto front in the objective space.

5.  IMPLEMENTATION OF THE ALGORITHM IN

GEOSPATIAL ENVIRONMENT

     The implementation of the PBMOGA for the application in the multi-objective spatial location domain is established on the paradigm of layered grid model of data, where the spatial information (address of the grid cell) is represented by the continuous (decimal) values in the PBMOGA. The utilization of data layers, where each layer represents a particular spatial aspect (e.g. land use, population distribution, resource allocation) is a typical form of the representation of the spatial information in the GIS. In the evolutionary spatial model (PBMOGA application domain), the layers represent the sets of attribute information specifying the quality and/or quantity characteristics of the spatial phenomena (e.g. population density, attractiveness of sale facilities, land value) [7]. 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 [8]. A set of objective functions is represented by the grid model, where particular objectives are represented by the layers.

     In the context of the described approach, the implementation of the Pareto-based GA in the geospatial optimization means the representation of the solutions in three spatial domains: objective space, space of decision variables and geographic space. In the objective space (Fig. 3.), a set of non-dominated solutions forms a Pareto front, corresponding to the Pareto set in the space of decision variables (Fig. 4.), i.e. a set of items defined by the variable values (of cell addresses). In the geographic space (Fig. 5.) the cell addresses are mapped 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 according to their preferences [9].

A. 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 the east.

For the purpose of the implementation of the algorithm, the objective functions (for all test problems) are given in a matrix form:

where r is a total number of rows, while k is a total number of matrix columns [10].

     The optimal coverage of the town space from one place (new fire station) can be incorporated within the objective function minimizing a total distance (of the passed route) from the required location to potential dangerous facilities:

where:

• 
  i=1…n, where n is a number of locations of dangerous facilities,
• 
  j=1…m, where m is a number of alternative locations for the fire station (a total number of cells in the network, m=rxk),

• 
  w_i is a weight that is assigned to the i-th potential dangerous facility, and

• 
  d_ij is a length of the route from the j-th alternative location to the i-th potential dangerous facility.

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 (8)[11]:

and

where:

• 
  i_s=1…n_s, where n_s is a number of locations of residential facilities,
• 
  i_k=1…n_k, where n_k is a number of locations of business (commercial/industrial) facilities,
• 
  j=1…m, where m is a number of alternative locations for the fire station (a total number of cells in the grid, m=rxk),
  
• w^S_is  is a weight that is assigned to the i location of the residential facility,
• 
  w^K_ik  is a weight that is assigned to the i location of the business facility,
• 
  d^S_is,j  is a length of the route from the j alternative location for the fire station to the i_s location of the residential facility, and
• 
  d^K_ik,j  is a length of the route from the j alternative location for fire station to the i_k location of the business facility.

     These objective functions present two interests (for the decision makers) that can be more or less conflict depending on the spatial arrangement of the facilities from the sets S and K. The first objective is a minimization of the average distance between the fire station and the residential facilities, while the second one is a minimization of the average distance between the fire station and the commercial/industrial facilities.

B. Application of the PBMOGA in the fire station problem

     Fig. 5. give an overview of the alternative locations for the fire station, obtained by the application of the PBMOGA. Labels (from 0.69 to 1.39) with circles (Fig. 5.) are describing the ratio of objective values o1/o2 for given alternative solutions. The solutions (locations) with smaller ratio are more preferable for the first objective regarding the population protection, while the ones with higher ratio are more preferable for the second objective regarding the business facilities protection. An important indicator for the multi-objective decisions 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 [9]. The compromise cost is here presented in the graphics (Fig. 3.), 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 the multi-objective analysis.

     The obtained results demonstrate practical implications of the application of the multi-objective analytic approach. Namely, the significance of the approach is reflected in the situation shown in Fig. 5. 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. 3. 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.

6. TESTING OF ALGORITHM INSTANCES IN REAL PROBLEM DOMAIN

     To examine and compare the algorithm instances PBMOGA and mPBMOGA it is performed a set of tests over selected location problems using specific metrics and appropriate statistical approach.

Metrics identified for testing PBMOGA and mPBMOGA measure their performance related to the generation of Pareto front in the objective space. These metrics include the Error Ratio (ER), Generational Distance (GD), Hyper-area and Hyper-area Ratio (H, HR), Spacing (S) and Overall Non-dominated Vector Generation and Ratio (ONVG and ONVGR [3].

     Some of these metrics (ER, GD, HR, ONVGR) require knowledge of the true (ideal) Pareto front (PF_true), which can be determined by theoretical or comprehensive search (using multiple running of algorithm under circumstances of high resolution along the Pareto front and the large number of iterations).

    ER metric reports the number of vectors in Pareto front that are not members of true Pareto front. So when ER=0, the PF_known is the same as PF_true, but when ER=1, this inidicates that none of the points in PF_known, are in PF_true. GD metric reports how far, on average, PF_known is from PF_true. When GD=0, then PF_known = PF_true.

     H and HR metrics define the area of coverage that PFknown has with respect to the objective space.

     This would equate to the summation of all the areas of rectangles, bounded by the origin and points which are members of Pareto front (for a two-objective GA). Ratio of the PF_known hyper-area and PF_true hyper-area is 1 if PF_known = PF_true.

     S metric measures the distance variance of neighboring vectors in PF_known. When S=0, all members are spaced evently apart [3].

      ONVGR metric measures the total number of nondominated vectors during algorithm execution and divides it by the number of vectors in PF_true. When ONVGR =1 this states only that the same number of points have been found in both PF_true and PF_known. This metric shows the efficiency of generating non-dominated vectors in the secondary set of solutions (in buffer) in relation to the number of nondominated vectors of the PF_true.

     For each test, which involved the application of instances of the algorithm (PBMOGA and mPBMOGA) over selected multi-objective optimization problem (LOP1), it is performed the appropriate number of repeats (20 repeats), with their identical parameter settings and the number of iterations (200 iterations). Table 1 shows the metric values for the algorithm instances which are collected at 200-th iteration.

     The obtained results (Tab. 1) showed that instance of modified algorithm (mPBMOGA) have better performances both in terms of achieved final metric values (after 200 iterations), so in terms of their behavior (convergence speed) during the execution.

     Before the testing of the algorithm in real problem domain, the instances are also carefully tested with the pedagogical problems under identical conditions (same metrics, statistical and genetic parameters). Here were used bi-objective test functions (multi-objective problems) MOP2, MOP3, MOP4. MOP6 [3] proposed by Fonseca, Poloni, Kursawa, Deb, and Haupt & Haupt [5]. Comparing the results obtained using the test functions and real problems (LOP1), the analysis confirmed similar behavior and performances of individual instances of the algorithm.

7. CONCLUSION

     This paper presents the development of Pareto based evolutionary mechanism (as the multi-objective geospatial optimization approach) in the form of the initial (PBMOGA) and modified (mPBMOGA) instances. The first instance operates with fixed parameters multiobjective genetic operators, and the other uses adaptive mechanism with a deterministic approach to determining the parameters of mutation. The analysis of experimental results has been found that the introduction of a mechanism adaptation provides certain performance improvements of the algorithm. However, both instances can be used as an effective tool for multi-objective planning, both because of its strength and flexibility, and the fact that generate a whole set of good (sub-optimal) solutions, instead of just one “optimal” solution.

     The application of the multi-objective Pareto based GA over the real optimization problems demonstrates the ability of discovery of multiple compromise solutions (in geospatial problem domain) through one running of the algorithm. The obtained results imply the great potential and efficiency of the implemented optimization mechanism, as well as the possibility of its further application in solving this type of problems.

REFERENCES

[1] Z. Avdagic, A. Karabegovic, M. Ponjavic: Section 12: Fuzzy Logic and Genetic Algorithm Application for Multi Criteria Land Valorization in Spatial Planning, Artificial Intelligence Technices for Computer Graphics, Series: Studies in Computational Intelligence, Vol.159, D. Plemenos & G. Miaoulis (Eds.), Special Springer Volume, 2009

[2] P. A. Burrough, R. A. McDonnel: Principles of Geographical Information Systems, Spatial Information Systems and Geostatistics, 2000

[3] C. A. Coello Coello, D. A. Veldhuizen, G. B. Lamont: Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic / Plenum Publishers, New York, 2002

[4] D. A. Van Veldhuizen, G. B. Lamont: Multi-Objective Evolutionary Algorithms: Analyzing the State-of-the-Art, Air Force Institute of Technology, Ohio, 2001

[5] R.L. Haupt, S.E. Haupt: Practical Genetic Algorithms, John Wiley & Sons, Inc., Hoboken, New Jersey, 2004

[6] E. Zitzler, M. Laumanns, S. Bleuer: A Tutorial on Evolutionary Multi-objective Optimization, , Swiss Federal Institute of Technology Zurich, 2003

[7] R. Krzanowski, J. Raper: Spatial Evolutionary modeling, Oxford University Press, Inc. NewYork, 2001

[8] A. Abraham, L. Jain, R.Goldberg: Evolutionary Multiobjective Optimization, Theoretical Advances and Applications, Springer-Verlag London Ltd., 2005

[9] J. L. Cohon: Multiobjective Programming and Planning, Dover Publications Inc., Mineola, New York, 2004

[10] M. Ponjavic, Z. Avdagic, A. Karabegovic: Geographic Information System and Genetic Algorithm Application for Multi-criteria Land Valorization in Spatial Planning, CORP2006 – Competence Center of Urban and Regional Planning: 11th International Conference on Urban Planning & Regional Development -Vienna, Austria, 2006

[11] L. Pitaksringkarn, M. 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