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

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.

Authors:

• A.K.M. Khaled Ahsan Talukder
• Taibun Nessa
• Kaushik Roy

Keywords:

• Genetic Algorithm
• Evolutionary Optimization
• Multi Objective Optimization
• Non-linear Schema Theorem
• WCSPP.

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.