
Research Article


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

S. Behzadi,
Ali A. Alesheikh
and
E. Poorazizi



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 preprocesses
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 bestsofar individual for this iteration of the GA 
PREPROCESSING
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 preprocessing
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 preprocessing 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 L_{min}
and L_{max}, where L_{min} and L_{max} 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:
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 preprocessing 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 preprocessing step must not be ′0`. This kind of mutation
is shown in Fig. 3.
Crossover operator: In this research, npoints 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 2points crossover
is used.

Fig. 3: 
Mutation operator 

Fig. 4: 
Twopoint crossover on a raster map 
In twopoint 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). Twopoint
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
preprocessing 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. Nonparametric genetic clustering: Comparison of validity indices. IEEE Trans. Sys. Man and Cyb. PartC, 31: 120125. CrossRef  Direct Link 
2: Cherkassky, B., V. Andrew V. Goldberg and T. Radzik, 1996. Shortest paths algorithms: Theory and experimental evaluation. Math. Prog., 73: 129174. 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: 2728. CrossRef  Direct Link 
4: Duan, G. and Y. Yu, 2003. Power distribution system optimization by an algorithm for capacitated Steiner tree problems with complexflows and arbitrary cost functions. Elec. Power Eng. Syst., 25: 515523. 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: 299333. CrossRef  Direct Link 
6: Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. 1st Edn., AddisonWesley Publishing Company, New York, USA., ISBN: 0201157675, pp: 3690.
7: Srinivas, M. and L.M. Patnaik, 1994. Genetic algorithm: A survey. IEEE Comput. Mag., 2: 1726. CrossRef  Direct Link 
8: Goldfarb, D., 1999. An O(mn)time network simple algorithm for the shortest path problem. Operat. Res., 47: 445448.
9: Godefroid, P. and S. Khurshid, 2004. Exploring very large state spaces using genetic algorithms. Int. J. Software Tools Technol. Transfer, 6: 117127. 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: 105131. CrossRef  Direct Link 
12: Holland, J., 1975. Adaptatin in Natural and Artificial System 1st Edn. University of Michigan Press, Ann Arbor, MI., ISBN10:0262581116.
13: Horowitch, E. and S. Sahani, 1978. Fundamentals of Computer Algorithms. 1st Edn. Science Press, Maryland, ISBN0716780453.
14: Horst, R. and P.M. Pardalos, 1995. Handbook of Global Optimization. Kluwer Academic Publishers, The Netherlands, ISBN 1402007426 .
15: Hosseinali, F. and A.A. Alesheikh, 2008. Weighting spatial information in GIS for copper mining exploration. Am. J. Applied Sci., 5: 11871198. CrossRef  Direct Link 
16: Ling, Y. and Meng, D., 2006. A genetic optimization algorithm to solve the problem of the loadbalancing of network load. Int. J. Comp. Sci. Net. Sec., 6: 6368. 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: 10751081. 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: 207210.
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 highgrequencyperformance under hot electron condition. Phys. B (Elsevier), 32: 189194. CrossRef  Direct Link 
20: Shi, H., 1999. Time work tradeoffs of the single source shortest paths problem. J. Algor., 30: 1932. CrossRef  Direct Link 
21: Thorup, M., 2000. Floats, integers and single source shortest path. J. Algor., 35: 189201. Direct Link 
22: Whitley, D., 1994. A genetic algorithm tutorial. Statist. Comput., 4: 6585. CrossRef  Direct Link 
23: Yen, Y.S., Y.K. Chan, H.C. Chao and J.H. Park, 2007. A genetic algorithm for energyefficient based multicast routing on MANETs. Comput. Com., 31: 858869. 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 82, 2006, Xinjiang, China, pp: 380389.
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 ISBN10: 1584884754, pp: 209217.
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.unistuttgart.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



