A GENETIC ALGORITHM FOR AUTOMATIC MAP SYMBOLS PLACEMENT

Dalibor Bartoněk

ABSTRACT

Genetic algorithms represent an up-to-date method of process optimalization, where other solutions have failed or haven’t given any satisfactory results. One of these processes is automatic placement of map symbols in such a way so that no symbols should mutually overlay. A genetic algorithm solving this task including an exact formulation and a definition of the initial conditions has been described in this paper. The algorithm efficiency will be tested in diploma works in Institute of Geodesy, Faculty of Civil Engineering, Brno University of Technology.

Key words: Genetic algorithm, map, coordinate system, map element, optimalization, fitness function, overlay area, overlay code, geometric transformation..

INTRODUCTION

Genetic algorithms are general procedures with the help of which important natural processes, especially reproduction of population are controlled. The first one to notice the possibility of their making use of in technical spheres was D. E. Goldberg in his publication [1]. This method has enjoyed a great interest ever since. A couple of publications and conferences dealing with these problems can prove this fact. A coherent survey on current development in this branch is written in habilitation work [2]. Genetic algorithms are based on evolution mechanism which have been verified by our nature in the course of long period development. These are very effective optimalization methods that stem out of our knowledge of natural genetic and its laws. Their advantage consists in possibility of application even on technical problems especially those ones couldn’t be expressed mathematically. An example of such a problem can be a space arrangement of elements in a level the position of which has ce rtain conditions defined by the metric under a given coordinate system. Tasks like these make in many cases, class NP-completely problems. It is proved e. g. [3] that no exact algorithm can be made for these tasks and if so it either never ends or cycles. Therefore tasks like these are solved by heuristic methods. One of possible solutions of this problem with the help of genetic algorithm is described in this paper.

THE TASK FORMULATION

When creating maps we often come across problem with placing various elements (e.g. map symbols, descriptions etc.). The thing is, that during a certain concentration of elements on the map, the symbols can mutually overlay which is disturbing and lowers a well arrangement. Manual placing of symbols in graphic editor is very laborious and time consuming. An automatic way of solution is complicated when taking into consideration that the task is NP-completely problem. That is way the symbols are placed according to simple rules e.g. homogenously at a certain distance and direction from a given map point and the possibly overlaying of the symbols can be removed manually. All the present hypotheses enable to solve these problems with application of a suitable genetic algorithm. Let us form the task problem for this purpose.

There is a map in the coordinate system (for example SJTSK) with points that are supposed to be placed with elements. These elements can be for instance locality map symbols, areas outlined by cadastral or municipality boundaries etc. Our task consists in generating a map symbol to each element in such a way so that no elements and symbols should mutually overlay. The formulation of the task can be expressed by a table the header of which is in table 1. The individual columns of the table 1 have a following meaning:

N_e is the map element number, X_e or Y_e in the table 1 are coordinates of the reference point of described object, and the X_smin, Y_smin or X_smax, Y_smax, are coordinates of left lower or right upper corner limiting rectangle which defines the symbol dimension. Another part of the task formulation are X_min, Y_min, X_max, Y_max, coordinates

which determine the maximum distance of the point (X_e, Y_e) environs where the symbol can be placed - see Fig. 1. For the needs of the genetic algorithm we will create another table – the so called symbol overlay table (table 2). This table contains numbers of the individual map elements (columns denoted Ne₁, Ne₂) further the area in which the symbols of both elements overlay (column marked Overlay area) and overlay code. This code unambiguously sets the direction of area overlaying of element Ne₂ symbol (Symbol i) with reference to element Ne₁ symbol (Basic symbol). The introduction of this code makes geometric transformation easier within the algorithm – see another chapter. Fig. 2 shows the symbol overlay of two elements and their record in the symbol overlay table.

AN ALGORITHM FOR THE AUTOMATIC PLACEMENT OF MAP SYMBOLS

General scheme of genetic algorithm in Fig. 4 has according [2] following phases:

1. Creation of initial population and evaluation of the individuals.

2. Selection of the individuals out of population.

3. Crossing over of parents which results in creation of new descendants.

4. Mutation of newly born descendants according to the parents’ characters.

5. Evaluation of the descendants and their including in population.

6. The selection of new individuals as parents.

Steps 2 – 6 have to be repeated for such a long time until a final condition is completed. This condition can be either in the form of the fitness function test or in the form of the number of iteration steps – see as follows.

Algorithm for the automatic placement of map symbols - see Fig. 5 works on a similar principle like algorithm on Fig. 4. Its input is table 1. We can create the second table 2 from the first table 1 in this way: we gradually scan the individual elements and their limited coordinates of descriptions (X_smin, Y_smin, X_smax, Y_smax). The elements the symbols of which are mutually overlaying are written in second table 2. An area and overlay code are computed according to verified algorithms of computer graphic – see [4] or [5] When the second table 2 is created the purposeful function which is to be optimalized is set. It is a summary of all overlay areas in the table 2:

(1)

where k is number of rows of the table 2 and a_i is overlay area in i. row of the table 2. Due to task formulation it is necessary for the value F_o to be as low as possible most optimally equal to zero. As the optimalization with genetic algorithms is based on function computing whose optimal value equals 1 – see [2], it requires forming of the purpose function as follows:

(2)

This function is called fitness function – see [2]. Other inputs of algorithm are parameters which define final conditions. These are:

• Acceptable value of fitness function – F_opt Î < 0..1 >,

• Number of iteration steps – N.

The algorithm itself works in following phases - see Fig. 5:

1. The selection of table 2 rows according to the criterion:

   (3)

   which means that only those rows overlay area of which is greater or equal to a half of purpose function value are selected. This phase correspond to the selection – in Fig. 4, block 2.

2. A geometric transformation - the movement of the limiting rectangle of the symbol of the selected elements in such a way so that the overlay area shouldn’t be lowered and the element limiting rectangle of the given element shouldn’t be exceeded – see Fig. 1. The movement within the geometric transformation has to be done in an opposite sense than determines the overlay code in the table 2, see Fig. 2. The phase is analogical to crossing and mutation – in Fig. 4, block 3 and 4.

3. Depending on the geometric transformation data in the table 1 and table 2 are modified. The phase correspond to evaluation – block 5, Fig. 4.

4. The value of the fitness function is computed according to the formula (2).

5. If F_i ³ F_opt, the algorithm is completed, if this condition is not fulfilled it must be tested if the number of iteration steps reached maximum number N. If so, the computing is completed, if not it is continued by step 1 (rows selection in the table 2).

VERIFICATION OF THE METHOD

The above described method was verified by creating of the thematic map shown on Fig. 6. The text on this map was placed by using of the genetic algorithm. The overlay area (see Fig. 2) was in this case a rectangle outlining the text. Number of steps in the iteration process (see Fig. 5) was N=100. A special utility, which makes use of two databases, has been created by author for this purpose in Borland Delphi: 1) graphic, which contains cadastral boundaries, and 2) statistical, where the values of the socio-economic phenomenon in question are stored. The application works according to a DBF (dBase) control file. This file defines the extent of the territory with the aid of codes from a municipality code list. It further contains the values of the given socio-economic phenomenon. Based on the user’s, needs (the range of legend and type of hatching or filling), the application will generate a cartogram file in the standardized DXF (Data eXchange Format) graphic format. The file can be imported into any graphic system where relevant modifications can be completed before the final output.

CONCLUSIONS

The advantages of above described algorithm unlike other consist in selection of only such elements with the worst evaluation (the fitness function value). If all the elements were optimalized (in our case position of all symbols simultaneously) it could happen that under the influence of mutual shifting the whole value of the purposeful function would become worse – see the formula (1) and the iteration process would diverge. This is the most important contribution of genetic algorithms. The described method was used in special software for thematic map creation especially for the optimal text placement – see Fig. 6.

REFERENCES

1. Goldberg D. E., 1989. Genetic Algorithms in Search, Optimisation and Machine Learning. Addisson-Wesley.

2. Ošmera P., 2001. Genetic algorithms and theirs application. Habilitation thesis. Faculty of Mechanical Engineering, University of Technology Brno.

3. Manna Z., 1981. Mathematical theory of computation. SNTL Prague, 1981, 468 pp. [in Czech].

4. Žára J., Beneš B., Felkel P., 1998. Modern computer graphics. Computer Press Prague, 448 pp. [in Czech].

5. Hudec B., 1993. Basics of Computer Graphics. Scriptum CTU, Prague, 222 pp. [in Czech].

Responses to this article, comments are invited and should be submitted within three months of the publication of the article. If accepted for publication, they will be published in the chapter headed ‘Discussions’ in each series and hyperlinked to the article.