Abstract: It is mostly believed that raster maps are not practically useful for finding shortest path and generally vector approaches are more prevalent. But any raster approach can open new horizons. Among various approaches, Genetic Algorithm (GA) can contribute effectively in solving lots of problems including shortest path problem in raster maps where other algorithms are inefficient. In this research a novel Genetic Algorithm (GA) will be presented for solving shortest path on a raster map. In a raster map, each road is shown by a specific color. A few pre-processes are performed on raster map based on the color attributes then all parameters of Genetic Algorithm will be defined. In order to evaluate the proposed algorithm, a raster map as an urban road map is selected. In the case study, the algorithm was successful in determining the shortest path.
INTRODUCTION
As an important branch of graph and network analysis, the traditional shortest path problem has extensive applications. That is to say, the SPP is a classical research topic (Cherkassky et al., 1996; Thorup, 2000; Shi, 1999; Heide and Vocking, 1999; Goldfarb, 1999). With the development of communications, computer science, traffic and transportation systems and so on, derivative problems from the traditional shortest path problems are becoming more and more important in real life. For instance, in the communication networks, the nodes and the edges have costs (Li et al., 2006). There are many methods to solve shortest path in a network. The differences among these algorithms are related to their being precise and fast. The similarity between most of these algorithms is that they are performed on the vector graphs. Genetic algorithm is a kind of algorithm that is used to solve many problems. As mentioned before, the vector is an essential part of finding shortest path, but the raster maps are more available and cheaper than the vector maps. In this study, a new genetic algorithm is presented to solve shortest path on the raster map. In the raster map, each road is shown by a specific color. Finding shortest path is solved by using the color map and a little information about the type of colored road.
GENETIC ALGORITHM
The Genetic Algorithm (GA) is an optimization and search technique (Horowitch and Sahani, 1978; Horst and Pardalos, 1995; Haupt and Haupt, 2004) based on the principles of genetics and natural selection (Goldberg, 1989; Srinivas and Patnaik, 1994; Bandyopadhyay and Maulik, 2001; Maulik and Bandyopadhyay, 2003; Sarkar et al., 2003; Saha Misra et al., 2001; Mukhopadhyay et al., 2000, 2005; Naskar et al., 2002). The method was developed by John Holland (Holland, 1975) and his colleagues. Genetic algorithms have been theoretically and empirically proven to be robust search techniques (Goldberg, 1989).
Genetic algorithm starts with a random population of encoded candidate solutions, called chromosomes. Through a recombination process and mutation operators, it evolves the population towards an optimal solution. The first step is typically to evaluate the fitness of each candidate solution in the current population and to select the fittest candidate solutions to act as parents of the next generation of candidate solutions. After being selected for reproduction, parents are recombined (using a crossover operator) and mutated (using a mutation operator) to generate offspring (Holland, 1975; Whitley, 1994). The fittest parents and the new offspring form a new population, from which the process is repeated to create new populations (Hosseinali and Alesheikh, 2008; Godefroid and Khurshid, 2004).
The steps of a GA are (Ericsson et al., 2002):
| • | Randomly create an initial population of individuals |
| • | Iteratively perform the following sub steps on the current generation of the population until the termination criterion has been satisfied |
| • | Assign fitness value to each individual using the fitness function |
| • | Select parents to mate |
| • | Create children from selected parents by crossover and mutation |
| • | Identify the best-so-far individual for this iteration of the GA |
PRE-PROCESSING
In this step, some processes are performed on a raster map to be used by genetic algorithm. At first the area is rotated as the start and end points are located with an equal row. In the raster map each pixel has a value which shows the type of pixel as a block or road. Each map has many types of roads and the speed of passing vehicles in each type of road is approximately equal. At the second step, the value of each pixel is changed to an integer value (Walter et al., 2006) depending on the vehicle speed on the road. The road in which the vehicle can move faster is represented by a smaller value. For example in a raster map which has two kinds of roads as highway and street the value of highway is considered 1 and the value of street is represented by 4. It shows that the speed in highway is four time faster than the speed on the street.
| Fig. 1: | (a) Rotated map base on the start and end points (b) respective DNAs |
In this case the value of blocks of buildings is considered ′0`. This process is shown in Fig. 1.
IMPLEMENTATION
Each pixel in the map has a value that is obtained from the pre-processing stage. The length of the individual is selected to be equal to the number of horizontal pixels that are located between the start and end points. For example the length of the individual for a sample map that was shown in Fig. 1 is 22.
Coding: In this problem, permutation encoding is used. In permutation encoding, each gene is considered by an integer number and a set of these numbers is considered as a chromosome (Ling and Meng, 2006). The value of each gene is corresponding to the number of pixels that are between the selected point and the connected line between the start and end points. For example [3 5 -2] as an encoding which corresponds to the chromosome in Fig. 2. The pre-processing and this encoding method are able to generate all feasible individuals through genetic operation such as crossover or mutation.
Initial population: In this problem, the initial population is generated randomly (Duan and Yu, 2003). It means that the genes of each chromosome are defined by choosing a random number between Lmin and Lmax, where Lmin and Lmax are the numbers of pixels which exist under and above the connecting line between start and end point respectively in the same column. The number of columns is equal to the position of selected gene.
| Fig. 2: | An example of encoding |
Fitness function: The fitness function in this research is defined as:
(1) |
| n | = | The length of the chromosome |
| Row (gene (i)) | = | The value of the row of the gene (i) |
| Row (Start pixel) | = | The value of the row of the start pixel |
| Row (gene (i)) | = | The value of pixel which is defined in pre-processing step |
Fitness scaling: Fitness scaling converts the raw fitness scores that are returned by the fitness function to the values in a range that are suitable for the selecting parents to generate offspring. In this research, proportional scaling is used to make the scaled value of an individual proportional to its raw fitness score.
Genetic operator: The most important part of genetic algorithm is genetic operators: crossover and mutation. The efficiency and the speed of solving the problem depend on the definition of these parameters. In this problem, mutation and crossover operators are not performed at the same time. At first mutation operator is performed on the map to create real segments of road then the complete roads are made by using crossover operators.
Mutation operator: At first, the connected line between start and end point is divided to m parts where m is a random number smaller than the number of pixels between start and end points. For each part, from the first random gene to the last gene, each pixel is sequentially mutated to another pixel which locates in the same column and the distance between currently getting mutated pixel and the previously mutated pixel must be less than two pixels. The value of the mutated gene that is calculated in the pre-processing step must not be ′0`. This kind of mutation is shown in Fig. 3.
Crossover operator: In this research, n-points crossover operator is used to create complete road as the solution for the problem where n is a random number between 1 to m−1 (m is a number that is defined in the mutation operator). For example if n equals 2 then 2-points crossover is used.
| Fig. 3: | Mutation operator |
| Fig. 4: | Two-point crossover on a raster map |
In two-point crossover, 2 points are selected, the genes from the beginning of the chromosome to the first crossover point is copied from first parent, the part from the first to the second crossover point is copied from the second parent and the rest is copied from the first parent (Davies and Lingras, 2003; Yen et al., 2007). Two-point crossover is shown in Fig. 4.
RESULTS AND DISCUSSION
In order to illustrate the result of proposed method, the actual colored raster map of a part of Tehran, the capital city of Iran is used. The object was to find the path with minimum time. The result of the experiment is shown in Fig. 5.
| Fig. 5: | (a) A part of the tested raster map (b) finding shortest path on the raster map |
Genetic algorithm is an efficient algorithm that is used to solve many problems. This algorithm is a general algorithm and each problem can be solved by this algorithm. Finding the best path is a kind of problem that needs a vector graph to be solved. A lot of algorithms are designed for this problem and the basic platform of most of them is a vector graph. In this paper, as it mentioned above, there are some restrictions in using vector maps. Therefore a raster map was used for this problem. Using GA, it was tried to find the shortest path on a raster map. At first a few pre-processing were performed on the map including changing the value of all pixels in the map based on the information about the color of roads and rotating the area based on the start and end points. In this study, a raster map was only used. We can use a raster and a vector map simultaneously. In this case, new operators must be defined based on the new problem or the vector map can be changed to raster map. In this case, we have only a raster map then the shortest path is solved by the proposed method.