Research PapersNo Access

A Reduced Uncertainty-Based Hybrid Evolutionary Algorithm for Solving Dynamic Shortest-Path Routing Problem

Huseyin Kusetogullari

Department of Computer Engineering, Gediz University, Seyrek, Izmir, Turkey

Search for more papers by this author

Md. Haidar Sharif

Department of Computer Engineering, Gediz University, Seyrek, Izmir, Turkey

Corresponding author.

Search for more papers by this author

Mark S. Leeson

The School of Engineering, Warwick University, Coventry, UK

Search for more papers by this author

, and

Turgay Celik

School of Computer Science, University of the Witwatersrand, Johannesburg, South Africa

Search for more papers by this author

https://doi.org/10.1142/S021812661550067XCited by:7 (Source: Crossref)

Abstract

The need of effective packet transmission to deliver advanced performance in wireless networks creates the need to find shortest network paths efficiently and quickly. This paper addresses a reduced uncertainty-based hybrid evolutionary algorithm (RUBHEA) to solve dynamic shortest path routing problem (DSPRP) effectively and rapidly. Genetic algorithm (GA) and particle swarm optimization (PSO) are integrated as a hybrid algorithm to find the best solution within the search space of dynamically changing networks. Both GA and PSO share context of individuals to reduce uncertainty in RUBHEA. Various regions of search space are explored and learned by RUBHEA. By employing a modified priority encoding method, each individual in both GA and PSO are represented as a potential solution for DSPRP. A complete statistical analysis has been performed to compare the performance of RUBHEA with various state-of-the-art algorithms. It shows that RUBHEA is considerably superior (reducing the failure rate by up to 50%) to similar approaches with increasing number of nodes encountered in the networks.

This paper was recommended by Regional Editor Kshirasagar Naik.

Keywords:

References

S. V. Porter, M. Mirmehdi and B. T. Thomas, A shortest path representation for video summarization, Proc. 12th Int. Conf. on Image Analysis and Processing (ICIAP) (2003) pp. 460–465. Google Scholar
Y. L. Chen and H. H. Yang , Comput. Oper. Res. 31 , 499 ( 2004 ) . Crossref, Web of Science, Google Scholar
Y. Xiao, K. Thulasiraman and G. Xue, Constrained shortest link-disjoint paths selection: A network programming based approach, IEEE Trans. Cir. and Syst. I: Regular Papers 53 (2006) 1174–1187 . Google Scholar
X. Sun, X. You and S. Liu, Multi-objective ant colony optimization algorithm for shortest route problem, Proc. Int. Conf. on Machine Vision and Human-Machine Interface (MVHI) (2010) pp. 796–798. Google Scholar
C. Davies and P. Lingras , Eur. J. Oper. Res. 144 , 27 ( 2003 ) . Crossref, Web of Science, Google Scholar
Y. Marinakis and M. Marinaki , Expert. Syst. Appl. 37 , 1446 ( 2010 ) . Crossref, Web of Science, Google Scholar
E. W. Dijkstra , Numer. Math. 1 , 269 ( 1959 ) . Crossref, Google Scholar
B. Awerbuch, Distributed shortest paths algorithms, Proc. 21st Annual ACM Symp. Theory of Computing (STOC) (1989) pp. 490–500. Google Scholar
R. E. Bellman , Q. Appl. Math. 16 , 87 ( 1958 ) . Crossref, Google Scholar
C. W. Ahn and R. S. Ramakrishna , IEEE Trans. Evolut. Comput. 6 , 566 ( 2002 ) . Crossref, Web of Science, Google Scholar
C. W. Ahn et al. , Electron. Lett. 37 , 1176 ( 2001 ) . Crossref, Web of Science, Google Scholar
C. F. Juang , IEEE Trans. Syst. Man. Cy. B 34 , 997 ( 2004 ) . Crossref, Web of Science, Google Scholar
A. Isaacs, T. Ray and W. Smith, A hybrid evolutionary algorithm with simplex local search, Proc. IEEE Cong. Evolutionary Computation (CEC) (2007) pp. 1701–1708. Google Scholar
L. M. O. Queiroz and C. Lyra , IEEE Trans. P. Syst. 24 , 445 ( 2009 ) . Crossref, Web of Science, Google Scholar
A. S. Ezeldin and A. Soliman , J. Constr. Eng. Manage. 135 , 42 ( 2009 ) . Crossref, Web of Science, Google Scholar
S. S. Choi and B. R. Moon , IEEE Trans. Evolut. Comput. 9 , 105 ( 2005 ) . Crossref, Web of Science, Google Scholar
G. Yan, Design of QoS anycast network cluster balance based on genetic algorithm, Proc. Int. Conf. Signal Processing Systems (ICSPS) (2009) pp. 610–614. Google Scholar
J. Arabas and S. Kozdrowski , IEEE Trans. Evolut. Comput. 5 , 309 ( 2001 ) . Crossref, Web of Science, Google Scholar
X. Ji , Appl. Math. Comput. 170 , 503 ( 2005 ) . Crossref, Web of Science, Google Scholar
K. Vijayalakshmi and S. Radhakrishnan , Comput. Commun. 31 , 3984 ( 2005 ) . Crossref, Web of Science, Google Scholar
J. Wang, M. Wang and M. Huang, A hybrid intelligent QoS multicast routing algorithm in NGI, Proc. Int. Conf. Parallel and Distributed Computing, Applications and Technologies (PDCAT) (2005) pp. 723–727. Google Scholar
T. El-Mihoubet al., Performance of hybrid genetic algorithms incorporating local search, Proc. 18th European Simulation Multiconference (ESM) (2004) pp. 154–160. Google Scholar
C. Potter, G. K. Venayagamoorthy and K. Kosbar, MIMO beam-forming with neural network channel prediction trained by a novel PSO-EA-DEPSO algorithm, Proc. Int. Joint Conf. Neural Networks (IJCNN) (2008) pp. 3338–3344. Google Scholar
S. Yang , H. Cheng and F. Wang , IEEE Trans. Syst. Man. Cy. C 40 , 52 ( 2010 ) . Crossref, Web of Science, Google Scholar
X. Zhang and L. Tang , Pattern Recogn. Lett. 30 , 848 ( 2009 ) . Crossref, Web of Science, Google Scholar
M. K. M. Ali and F. Kamoun , IEEE Trans. Neural Networ. 4 , 941 ( 1993 ) . Crossref, Web of Science, Google Scholar
D. C. Park and S. E. Choi, A neural network based multi-destination routing algorithm for communication network, Proc. Int. Joint Conf. on Neural Networks (IJCNN) (1998) pp. 1673–1678. Google Scholar
J. Kennedy and R. Eberhart, Particle swarm optimization, Proc. Int. Joint Conf. on Neural Networks (IJCNN) (1995) pp. 1942–1948. Google Scholar
A. W. Mohemmed , N. C. Sahoo and T. K. Geok , Appl. Soft. Comput. 8 , 1643 ( 2008 ) . Crossref, Web of Science, Google Scholar
S. Das et al. , IEEE Trans. Evolut. Comput. 13 , 526 ( 2009 ) . Crossref, Web of Science, Google Scholar
J. Zhang and A. C. Sanderson , IEEE Trans. Evolut. Comput. 13 , 945 ( 2009 ) . Crossref, Web of Science, Google Scholar
J. Fakcharoemphol and S. Rao , J. Comp. Syst. Sci. 72 , 868 ( 2006 ) . Crossref, Web of Science, Google Scholar
J. Gaoet al., Dynamic shortest path algorithms for hypergraphs, Proc. 10th Int. Symp. Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) (2012) pp. 238–245. Google Scholar
P. Klein et al. , J. Comp. Syst. Sci. 55 , 3 ( 1997 ) . Crossref, Web of Science, Google Scholar
S. Baswana, R. Hariharan and S. Sen, Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths, Proc. 34th Annual Symp. Theory of Computing (STOC) (2002) pp. 113–127. Google Scholar
G. Ausiello et al. , J. Algo. 12 , 615 ( 1991 ) . Crossref, Web of Science, Google Scholar
V. King, Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs, Proc. 40th Symp. Foundations of Computer Science (FOCS) (1999) pp. 81–91. Google Scholar
H. Kusetogullari et al. , Appl. Soft Comput. 14 , 536 ( 2014 ) . Crossref, Web of Science, Google Scholar
L. S. Buriol, M. G. C. Resende and M. Thorup, Speeding up dynamic shortest path algorithms, TR TD-5RJ8B, AT&T Labs Research, September 2003 . Google Scholar
B. Xiao et al. , J. Commun. Netw. 9 , 499 ( 2007 ) . Crossref, Web of Science, Google Scholar
C. Demetrescuet al., Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study, Proc. 4th Int. Workshop Algorithm Eng. (WAE) (2000) pp. 218–229. Google Scholar
D. Frigioni et al. , ACM J. Exper. Algo. 3 , 5 ( 1998 ) . Google Scholar
H. Kusetogullariet al., K-shortest path network problem solution with a hybrid Genetic algorithm: Particle swarm optimization algorithm, Proc. 13th Int. Conf. Transparent Optical Networks (ICTON) (2011) pp. 1–4. Google Scholar
E. T. Jaynes , Phys. Rev. 106 , 620 ( 1957 ) . Crossref, Web of Science, Google Scholar
M. H. Sharif and C. Djeraba , Pattern Recogn. 45 , 2543 ( 2012 ) . Crossref, Web of Science, Google Scholar
J. Zhang , H. S. H. Chung and W. L. Lo , IEEE Trans. Evolut. Comput. 11 , 326 ( 2007 ) . Crossref, Web of Science, Google Scholar
M. H. Sharif et al. , J. Syst. Architect. 54 , 638 ( 2008 ) . Crossref, Web of Science, Google Scholar
M. H. Sharif , J. Circuit Syst. Comp. 23 , 1450051 ( 2014 ) . Link, Web of Science, Google Scholar
Z. Michalewicz , Genetic Algorithms + Data Structure = Evolution Programs ( Springer , Berlin , 1996 ) . Crossref, Google Scholar
H. Sayoud , K. Takahashi and B. Vaillant , IEEE Commun. Lett. 5 , 113 ( 2001 ) . Crossref, Web of Science, Google Scholar
M. Gen, R. Cheng and D. Wang, Genetic algorithms for solving shortest path problems, Proc. Int. Conf. Evolutionary Computation (ICEC) (1997) pp. 401–406. Google Scholar
Sinalgo, A simulation framework for testing and validating network algorithms. Available from http://dcg.ethz.ch/projects/sinalgo, 2015 . Google Scholar
P. Leesutthipornchai , C. Charnsripinyo and N. Wattanapongsakorn , Comput. Commun. 33 , 2246 ( 2010 ) . Crossref, Web of Science, Google Scholar
S. N. Goodman , Ann. Intern. Med. 130 , 995 ( 1999 ) . Crossref, Web of Science, Google Scholar
B. Trawinski et al. , Int. J. Ap. Mat. Com. 22 , 867 ( 2012 ) . Web of Science, Google Scholar
T. Sellke , M. J. Bayarri and J. O. Berger , Am. Stat. 55 , 62 ( 2001 ) . Crossref, Web of Science, Google Scholar
M. Friedman , J. Am. Stat. Assoc. 32 , 675 ( 1937 ) . Crossref, Google Scholar
R. L. Iman and J. M. Davenport , Commun. Stat. Theor. M. 18 , 571 ( 1980 ) . Crossref, Web of Science, Google Scholar
J. L. Hodges and E. L. Lehmann , Ann. Stat. 33 , 482 ( 1962 ) . Crossref, Web of Science, Google Scholar
D. Quade , J. Am. Stat. Assoc. 74 , 680 ( 1979 ) . Crossref, Web of Science, Google Scholar
O. Dunn , J. Am. Stat. Assoc. 56 , 52 ( 1961 ) . Crossref, Web of Science, Google Scholar
S. Holm , Scand. J. Stat. 6 , 65 ( 1979 ) . Web of Science, Google Scholar
Y. Hochberg , Biometrika 75 , 800 ( 1988 ) . Crossref, Web of Science, Google Scholar
G. Hommel , Biometrika 75 , 383 ( 1988 ) . Crossref, Web of Science, Google Scholar
G. Hommel and G. Bernhard , Comput. Meth. Prog. Bio. 43 , 213 ( 1994 ) . Crossref, Web of Science, Google Scholar
M. C. B. S. Holland , Biometrics 43 , 417 ( 1987 ) . Crossref, Web of Science, Google Scholar
D. Rom , Biometrika 77 , 663 ( 1990 ) . Crossref, Web of Science, Google Scholar
H. Finner , J. Am. Stat. Assoc. 88 , 920 ( 1993 ) . Crossref, Web of Science, Google Scholar
J. Li , J. Stat. Plan. Infer. 138 , 1521 ( 2008 ) . Crossref, Web of Science, Google Scholar
P. B. Nemenyi, Distribution-free multiple comparisons, Ph.D. thesis, Princeton University (1963) . Google Scholar
J. Shaffer , J. Am. Stat. Assoc. 81 , 826 ( 1986 ) . Crossref, Web of Science, Google Scholar
G. Bergmann and G. Hommel, Multiple Hypotheses Testing, eds. P. Bauer, G. Hommel and E. Sonnemann (Springer, Berlin Hiedelberg, Germany, 1988) pp. 100–115. Crossref, Google Scholar
S. Garca and F. Herrera , J. Mach. Learn. Res. 9 , 2677 ( 2008 ) . Web of Science, Google Scholar
P. H. Westfall and S. S. Young , Resampling-based Multiple Testing: Examples and Methods for p-Value Adjustment ( John Wiley and Sons , New York, USA , 2004 ) . Google Scholar