Reduction of Search Space by Applying Controlled Genetic Operators for Weight Constrained Shortest Path Problem

Authors: A.K.M. Khaled Ahsan Talukder, Taibun Nessa, Kaushik Roy

Abstract:

The weight constrained shortest path problem (WCSPP) is one of most several known basic problems in combinatorial optimization. Because of its importance in many areas of applications such as computer science, engineering and operations research, many researchers have extensively studied the WCSPP. This paper mainly concentrates on the reduction of total search space for finding WCSP using some existing Genetic Algorithm (GA). For this purpose, some controlled schemes of genetic operators are adopted on list chromosome representation. This approach gives a near optimum solution with smaller elapsed generation than classical GA technique. From further analysis on the matter, a new generalized schema theorem is also developed from the philosophy of Holland-s theorem.

Keywords: Genetic Algorithm, Evolutionary Optimization, Multi Objective Optimization, Non-linear Schema Theorem, WCSPP.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056218

References:

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco.
[2] G. Y. Handler and I. Zang, "Dual Algorithm for the Constrained Shortest Path Problem", in Networks 10, pp.293-309.
[3] Y. J. Yen, "Finding the k Shortest Loop-less Paths in a Network", in Management Science 17, pp.711-715.
[4] H. C. Joksch, "The Shortest Route Problem with Constraints", in Journal of Mathematical Analysis and Applications 14, pp.191-197.
[5] E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York..
[6] Y. P. Aneja, V. Aggarwal and K. P. K. Nair, "Shortest Chain Subject to Side Constraints", in Networks 13,pp.295-302.
[7] M. Desrochers and F. Soumis, "A Generalized Permanent Labeling Algorithm for the Shortest Path Problem with Time Windows", in INFOR 26, pp.191-212.
[8] I. Dumitrescu and N. Boland, Algorithms for the Weight Constrained Shortest Path Problem, Department of Mathematics and Statistics, University of Melbourne, Australia.
[9] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition, Springer - Verlag, Berlin, Germany, pp.209-237, 171-172.
[10] T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, Prentice-Hall of India Pvt. Ltd. New Delhi, India.
[11] D. E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning, Pearson Education Pvt. Ltd, Singapore, pp.170-174, 204-206.
[12] K. Deb, S. Agarwal, S. Pratap and T. Meyarivan, "A Fast Elitist Nondominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA - II", in Proceedings of the Parallel Problem Solving from Nature 6 Conference, pp.849-858.
[13] W. A. Greene, "A Non-linear Schema Theorem for Genetic Algorithm" in GECCO-2000, Las-Vegas, USA.