You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
Publisher: World Scientific Publishing Co. Pte. Ltd.
Languages: English
Types: Article
Subjects:QA76
The need for 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.
1. Porter, S. and Mirmehdi, M. and Thomas, B.: A shortest path representation for video summarization, Proceedings of International Conference on Image Analysis and Processing, 2003, pp. 460-465.
2. Chen, Y.L. and Yang, H.H.: Finding the first K shortest paths in a time-window network, Computers and Operations Research 31, 2004, pp. 499-513.
3. Xiao, Y., Thulasiraman, K. and Xue, G.: Constrained shortest link-disjoint paths selection: a network programming based approach, IEEE Transactions on Circuits and Systems I: Regular Papers, 53, 2006, pp. 1174-1187.
4. Sun, X., You, X. and Liu, S.: Multi-objective ant colony optimization algorithm for shortest route problem, International Conference on Machine Vision and Human-Machine Interface, 2010, pp. 796-798.
5. Davies, C. and Lingras, P.: Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks. European Journal of Operational Research, 144, 2003, pp. 27-38.
6. Marinakis, Y. and Marinaki, M.: A hybrid genetic Particle Swarm Optimization Algorithm for the vehicle routing problem, Expert Systems with Applications, 37, 2010, pp. 1446-1455.
8. Awerbuch, B.: Distributed shortest paths algorithms, Proceedings of 21st Annual ACM Symposium on Theory of Computing (STOC), 1998, pp. 490-500.
9. Bellman, R. E.: On a routing problem, Quarterly of Applied Mathematics, 1958, pp. 87-90.
10. Ahn, C. W. and Ramakrishna, R.S.: A genetic algorithm for shortest path routing problem and the sizing of populations, IEEE Transactions on Evolutionary Computation, 6, 2002, pp. 566- 579.
11. Ahn, C.W., Ramakrishna, R.S., Kang, C.G. and Choi, I.C.: Shortest path routing algorithm using Hopfield neural networ, Electronics Letters, 37, 2001, pp. 1176-1178.
12. Juang, C.-F.: A hybrid of genetic algorithm and particle swarm optimization for recurrent network design, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 34, 2004, pp. 997-1006.
13. Isaacs, A. and Ray, T. and Smith, W.: A Hybrid Evolutionary Algorithm With Simplex Local Search, IEEE Congress on Evolutionary Computation, 2007, pp. 1701-1708.
14. Queiroz, L.M.O. and Lyra, C.: Adaptive Hybrid Genetic Algorithm for Technical Loss Reduction in Distribution Networks Under Variable Demands,IEEE Transactions on Power Systems, 24, 2009, pp. 326-335.
15. Ezeldin, A. S. and Soliman, A.: Hybrid time-cost optimization of nonserial repetitive construction projects, Journal of Construction Engineering and Management, 135, 2009, pp. 42-55.
16. Choi, S.S. and Moon, B.R.: A graph-based Lamarckian-Baldwinian hybrid for the sorting network problem, IEEE Transactions on Evolutionary Computation, 9, 2005, pp. 105-114.
17. Yan, G.: Design of qos anycast network cluster balance based on genetic algorithm, Proceedings of International Conference on Signal Processing Systems, 2009, pp. 610-614.
18. Arabas, J. and Kozdrowski, S.: Applying an evolutionary algorithm to telecommunication network design, IEEE Transactions on Evolutionary Computation, 5, 2001, pp. 309-322.
19. Ji, X.: Models and algorithm for stochastic shortest path problem, Applied Mathematics and Computation, 170, 2005, pp. 503-514.
20. Vijayalakshmi, K. and Radhakrishnan, S.: Artificial immune based hybrid GA for QoS based multicast routing in large scale networks (AISMR), Computer Communications, 31, 2005, pp. 3984-3994.
21. Wang, J. and Wang, M. and Huang, M.: A hybrid intelligent qos multicast routing algorithm in ngi, International Conference on Communication Technology, 2006, pp. 1-4.
22. El-Mihoub, T. and Hopgood, A. A. and Nolle, L. and Battersby, A., K.: Performance of hybrid genetic algorithms incorporating local search, 18th European Simulation Multiconference, 2004, pp. 154 -160.
23. Potter, C. and Venayagamoorthy, G.K. and Kosbar, K.: MIMO beam-forming with neural network channel prediction trained by a novel PSO-EA-DEPSO algorithm, IEEE International Joint Conference on Neural Networks, 2008, pp. 3338-3344.
24. Yang, S., Cheng, H. and Wang, F.: Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks, IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 40, 2010, pp. 52-63.
25. Zhang, X. and Tang, L.: A new hybrid ant colony optimization algorithm for the vehicle routing problem, Pattern Recognition Letters, 30, 2009, pp. 848-855.
26. Ali, M.K.M. and Kamoun, F.: Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks, IEEE Transactions on Neural Networks, 4, 1993, pp. 941-954.
27. Park, D.C. and Choi, S.E.: A neural network based multi-destination routing algorithm for communication network, International Joint Conference on Neural Networks, 1998, pp. 1673-1678.
28. Kennedy, J. and Eberhart, R.: Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, 1995, pp. 1942-1948.
29. Mohemmed, A. W. and Sahoo, N. C. and Geok, T. K.: Solving shortest path problem using particle swarm optimization, Applied Soft Computing, 8, 2008, pp. 1643-1653.
30. Das, S. and Abraham, A. and Chakraborty, U.K. and Konar, A.: Differential Evolution Using a Neighborhood-Based Mutation Operator, IEEE Transactions on Evolutionary Computation, 13, 2009, pp. 526-553.
31. Zhang, J. and Sanderson, A.C.: JADE: Adaptive Differential Evolution With Optional External Archive, IEEE Transactions on Evolutionary Computation, 13, 2009, pp. 945-958.
32. Fakcharoemphol, J. and Rao, S.: Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proc. 42nd IEEE Ann. Symp. Foundations of Computer Science (FOCS'01), 2001, pp. 232-241.
33. Gao et al.: Dynamic Shortest Path Algorithms for Hypergraphs, 10th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2012, pp. 238-245.
34. Klein, P. and Rao, S. and Rauch, M. and Subramanian, S.: Faster Shortest Path Algorithms for Planar Graphs, Proc. 26th Ann. ACM Symp. Theory of Computing (STOC'94), 1994, pp. 27- 37.
35. Baswana, S. and Hariharan, R. and Sen, S.: Improved Decremental Algorithms for Maintaining Transitive Closure and All-Pairs Shortest Paths, Proc. 34th Ann. ACM Symp. Theory of Computing (STOC'02), 2002 pp. 113-127.
36. Ausiello, G. and Italiano, G.F. and Marchetti-Spaccamela, A. and Nanni, U.: Incremental Algorithms for Minimal Length Paths, J. Algorithms, 12, 1991, pp. 615-638.
37. King, V.: Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs, Proc. 40th IEEE Symp. Foundations of Computer Science (FOCS'99), 1999, pp. 81-91.
39. Buriol, L.S. and Resende, M.G.C. and Thorup, M.: Speeding Up Dynamic Shortest Path Algorithms, TR TD-5RJ8B, AT&T Labs Research, Sept. 2003.
40. Xiao, B. and Cao, J. and Shao, Z. and Sha, E.H.M.: An Efficient Algorithm for Dynamic Shortest Path Tree Update in Network Routing, Journal of Communications and Networks, 9, 2007, pp. 499-510.
41. Demetrescu, C. and Frigioni, D. and Marchetti-Spaccamela, A. and Nanni, U.: Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study, Proc. 4th Int. Workshop Algorithm Eng. (WAE'01), 2001, pp. 218-229.
42. Frigioni,D. and Ioffreda, M. and Nanni, U. and Pasquale, G.: Experimental Analysis of Dynamic Algorithms for the Single-Source ShortestPath Problem, ACM J. Experimental Algorithms, 3, 1998, pp. 5.
44. Jaynes, E.T.: Information theory and statistical mechanics, Physical Review, 106, 1957, pp. 620- 630.
45. Sharif, M.H. and Djeraba, C.: An entropy approach for abnormal activities detection in video streams, Pattern Recognition, 45, 2012, pp. 2543-2561.
46. Zhang, J. and Chung, H. S.H. and Lo, W.L.: Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms, IEEE Transactions on Evolutionary Computation, 22, 2007, pp. 326-335.
47. Sharif, M.H.: High-performance mathematical functions for single-core architectures, Journal of Circuits, Systems and Computers, 23, 2014, pp. 1450051.
50. Gen, M. and Cheng, R. and Wang, D.: Genetic algorithms for solving shortest path problems, IEEE International Conference on Evolutionary Computation, 1997, pp. 401-406.
51. Sinalgo: a simulation framework for manets. Availaible on : dcg.ethz.ch/projects/sinalgo.
52. Leesutthipornchai, P. and Charnsripinyo, C. and Wattanapongsakorn, N.: Solving multiobjective routing and wavelength assignment in WDM network using hybrid evolutionary computation approach, Computer Communications, 33, 2010, pp. 2246 - 2259.
53. Goodman, S.N.: Toward Evidence-Based Medical Statistics. 1: The P Value Fallacy, Annals of Internal Medicine, 130, 1999, pp. 995-1004.
54. Trawinski, B. and Smetek, M. and Telec, Z. and Lasota, T.: Nonparametric statistical analysis for multiple comparison of machine learning regression algorithms, International Journal of Applied Mathematics and Computer Science, 22, 2012, pp. 867-881.
55. Sellke, T. and Bayarri, M.J. and Berger, J.O.: Calibration of p Values for Testing Precise Null Hypotheses, The American Statistician, 55, 2001, pp. 6271.
56. Friedman, M.: The use of ranks to avoid the assumption of normality implicit in the analysis of variance, J. of the American Statistical Assoc., 32:200, 1937, pp. 675-701.
57. Iman, R.L. and Davenport, J.M.: Approximations of the critical region of the Friedman statistic, Communications in Statistics, 18, 1980, pp. 571-595.
59. Quade D.: Using weighted rankings in the analysis of complete blocks with additive block effects, Journal of the American Statistical Association, 74, 1979, pp. 680-683.
60. Dunn, O.: Multiple comparisons among means, Journal of the American Statistical Association, 56,1961, pp. 52-64.
61. Holm, S.: A simple sequentially rejective multiple test procedure, Scandinavian Journal of Statistics, 6, 1979, pp. 65-70.
62. Hochberg,Y.: A sharper Bonferroni procedure for multiple tests of significance, Biometrika, 75, 1988, pp. 800-803.
63. Hommel, G.: A stagewise rejective multiple test procedure based on a modified Bonferroni test, Biometrika, 75, 1988, pp. 383-386.
64. Hommel, G., Bernhard, G.: A rapid algorithm and a computer program for multiple test procedures using procedures using logical structures of hypotheses. Computer Methods and Programs in Biomedicine, 1994, 43, pp. 213-216.
65. Holland, M.C.B.S.: An improved sequentially rejective Bonferroni test procedure, Biometrics, 43, 1987, pp. 417-423.
66. Rom, D.: A sequentially rejective test procedure based on a modified Bonferroni inequality, Biometrika, 77, 1990, pp. 663-665.
67. Finner, H.: On a monotonicity problem in step-down multiple test procedures, Journal of the American Statistical Association, 88, 1993, pp. 920-923.
68. Li, J.: A two-step rejection procedure for testing multiple hypotheses, Journal of Statistical Planning and Inference, 138, 2008, pp. 1521-1527.
70. Shaffer, J.: Modified sequentially rejective multiple test procedures, Journal of American Statistical Association, 81, 1986, pp. 826-831.
71. Bergmann, G. and Hommel, G.: Improvements of general multiple test proceduresfor redundant systems of hypotheses, in: P. Bauer, G. Hommel, E. Sonnemann (Eds.), Multiple Hypotheses Testing, Springer, 1988, pp. 100-115.
72. Garca, S. and Herrera, F.: An extension on ”Statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons, Journal of Machine Learning Research, 2008, 9, pp. 2677-2694.