Subscribe Now Subscribe Today
Research Article
 

Developing a Genetic Algorithm to Solve Shortest Path Problem on a Raster Data Model



S. Behzadi, Ali A. Alesheikh and E. Poorazizi
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
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.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

S. Behzadi, Ali A. Alesheikh and E. Poorazizi, 2008. Developing a Genetic Algorithm to Solve Shortest Path Problem on a Raster Data Model. Journal of Applied Sciences, 8: 3289-3293.

DOI: 10.3923/jas.2008.3289.3293

URL: https://scialert.net/abstract/?doi=jas.2008.3289.3293
 

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)
Where:
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.

REFERENCES
1:  Bandyopadhyay, S. and U. Maulik, 2001. Non-parametric genetic clustering: Comparison of validity indices. IEEE Trans. Sys. Man and Cyb. Part-C, 31: 120-125.
CrossRef  |  Direct Link  |  

2:  Cherkassky, B., V. Andrew V. Goldberg and T. Radzik, 1996. Shortest paths algorithms: Theory and experimental evaluation. Math. Prog., 73: 129-174.
CrossRef  |  Direct Link  |  

3:  Davies, C. and P. Lingras, 2003. Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks. Eur. J. Operat. Res., 144: 27-28.
CrossRef  |  Direct Link  |  

4:  Duan, G. and Y. Yu, 2003. Power distribution system optimization by an algorithm for capacitated Steiner tree problems with complex-flows and arbitrary cost functions. Elec. Power Eng. Syst., 25: 515-523.
CrossRef  |  Direct Link  |  

5:  Ericsson, M., M. Resende and P. Pardalos, 2002. A genetic algorithm for the weight setting problem in OSPF routing. J. Comb. Optim., 6: 299-333.
CrossRef  |  Direct Link  |  

6:  Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. 1st Edn., Addison-Wesley Publishing Company, New York, USA., ISBN: 0201157675, pp: 36-90.

7:  Srinivas, M. and L.M. Patnaik, 1994. Genetic algorithm: A survey. IEEE Comput. Mag., 2: 17-26.
CrossRef  |  Direct Link  |  

8:  Goldfarb, D., 1999. An O(mn)-time network simple algorithm for the shortest path problem. Operat. Res., 47: 445-448.

9:  Godefroid, P. and S. Khurshid, 2004. Exploring very large state spaces using genetic algorithms. Int. J. Software Tools Technol. Transfer, 6: 117-127.
CrossRef  |  

10:  Haupt, R.L. and S.E. Haupt, 2004. Practical Genetic Algorithms. 1st Edn. John Wiley and Sons, Inc., Hoboken, New Jersey, ISBN: 9780471455653.

11:  Heide, F.M. and B. Vocking, 1999. Shortest path routing in arbitrary networks. J. Algorithms, 31: 105-131.
CrossRef  |  Direct Link  |  

12:  Holland, J., 1975. Adaptatin in Natural and Artificial System 1st Edn. University of Michigan Press, Ann Arbor, MI., ISBN-10:0-262-58111-6.

13:  Horowitch, E. and S. Sahani, 1978. Fundamentals of Computer Algorithms. 1st Edn. Science Press, Maryland, ISBN-0716780453.

14:  Horst, R. and P.M. Pardalos, 1995. Handbook of Global Optimization. Kluwer Academic Publishers, The Netherlands, ISBN 1-4020-0742-6 .

15:  Hosseinali, F. and A.A. Alesheikh, 2008. Weighting spatial information in GIS for copper mining exploration. Am. J. Applied Sci., 5: 1187-1198.
CrossRef  |  Direct Link  |  

16:  Ling, Y. and Meng, D., 2006. A genetic optimization algorithm to solve the problem of the load-balancing of network load. Int. J. Comp. Sci. Net. Sec., 6: 63-68.
Direct Link  |  

17:  Maulik, U. and S. Bandyopadhyay, 2003. Fuzzy partitioning using real coded variable length genetic algorithm for pixel classification. IEEE Trans. Geosci. Remote Sensing, 41: 1075-1081.
CrossRef  |  Direct Link  |  

18:  Saha Misra, I., M. Chakraborty, M.K. Naskar, B. Banerjee and D. Dutta, 2001. Solution of unicast Qos routing using genetic algorithm. Proceedings of the 4th International Conference on Information Technology, (IT'01), NIST, Palur Hills, Beharampur, India, pp: 207-210.

19:  Sarkar, S.K., A. Moi, C. Puttamadappa, A.K. De and M.K. Naskar, 2003. Application of genetic algorithm to determine the optimized system parameters of GaAs quantum wells for better high-grequencyperformance under hot electron condition. Phys. B (Elsevier), 32: 189-194.
CrossRef  |  Direct Link  |  

20:  Shi, H., 1999. Time work tradeoffs of the single source shortest paths problem. J. Algor., 30: 19-32.
CrossRef  |  Direct Link  |  

21:  Thorup, M., 2000. Floats, integers and single source shortest path. J. Algor., 35: 189-201.
Direct Link  |  

22:  Whitley, D., 1994. A genetic algorithm tutorial. Statist. Comput., 4: 65-85.
CrossRef  |  Direct Link  |  

23:  Yen, Y.S., Y.K. Chan, H.C. Chao and J.H. Park, 2007. A genetic algorithm for energy-efficient based multicast routing on MANETs. Comput. Com., 31: 858-869.
CrossRef  |  Direct Link  |  

24:  Li, Y., R. He and Y. Guo, 2006. Faster genetic algorithm for network paths. Proceedings of the 6th International Symposium on Operations Research and Its Applications, August 8-2, 2006, Xinjiang, China, pp: 380-389.

25:  Mukhopadhyay, A., U. Biswas, M.K. Naskar, U. Maulik and S. Bandyopadhyay, 2005. Minimizationn of SADMs in Unifdirectional SONET/WDM Rings Using Genetic Algorithms. In: Handbook of Bioinspired Algorithms and Applications, Olariu, S. and A.Y. Zomaya (Eds.)., Chapman and Hall/CRC ISBN-10: 1584884754, pp: 209-217.

26:  Walter, V., M. Kada and H. Chen, 2006. Shortest path analyses in raster maps for pedestrian navigation in location based systems. Proceedings of the ISPRS, the Netherlands. www.ifp.uni-stuttgart.de/publications/2006/walter06_ISPRS_CommIV_Goa.pdf

27:  Naskar, M.K., B. Mukherjee, J.N. Majumder and S.K. Sarkar, 2002. A genetic approach for design protection in WDM optical networks. International Conf. PHOTONICS, Mumbai

©  2021 Science Alert. All Rights Reserved