CONSTRAINT HANDLING PROBLEMS BY USING GA
1
Author(s):
JUGMENDRA SINGH
Vol - 6, Issue- 11 ,
Page(s) : 59 - 74
(2015 )
DOI : https://doi.org/10.32804/CASIRJ
Abstract
Genetic Algorithm (GA) is part of a broader soft computing paradigm known as evolutionary computation. They attempt to arrive at optimal solutions through a process similar to biological evolution. This involves following the principles of survival of the fittest, and crossbreeding and mutation to generate better solutions from a pool of existing solutions. Genetic algorithm is a population-based search method. Genetic algorithms are acknowledged as good solvers for tough problems. However, no standard GA takes constraints into account. This paper describes how genetic algorithms can be used for solving constraint satisfaction problems.
- [Burk95] Burke, E. K., Elliman, D.G., Weave, R. F., A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems, Proc. of 6th International Conference on the Practice and Theory of Automated Timetabling, Napier University, Edinburgh, UK, 1995.
- [Holl92] J. H. Holland, “Adaption in natural and artificial systems”, MIT Press, 1992.
- [Mich96] Michalewicz, Z., Dasgupta, D., Le Riche, R.G., and Schoenauer, M., Evolutionary Algorithms for Constrained Engineering Problems, Computers & Industrial Engineering Journal, Vol.30, No.2, September 1996, pp.851-870.
- [Panw12]
- P. Panwar, A. K. Lal, and Jugmendra Singh. "A Genetic Algorithm Based Technique for Efficient Scheduling of Tasks on Multiprocessor System." In Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) December 20-22, 2011, pp. 911-919. Springer India, 2012.
- [Siva07] S. N. Sivanandam, and S. N. Deepa, “Introduction to genetic algorithms”, Springer Science & Business Media, 2007.
- [Trip00] A.K. Tripathi, B.K. Sarker and N. Kumar, “A GA based multiple task allocation considering load”, International Journal of High Speed Computing, Vol. 11, No. 4, pp. 203-214, 2000.
- [Tsuj95]
- Y. Tsujimura and M. Gen, “Genetic algorithms for solving multiprocessor scheduling problems”, Simulated Evolution and Learning, Heidelberg: Springer, pp.106-15. 1995.
- [Wang97] L. Wang, H. J. Siegel, V. P. Roychowdhury and A. A. Maciejewski. “Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach”. Journal of Parallel and Distributed Computing, Vol.47, pp. 8-22, 1997.
- [Wu04] A. S. Wu, H. Yu, S. Jin, K.-C. Lin, and G. Schiavone, “An incremental genetic algorithm approach to multiprocessor scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol. 15, pp. 824-834, 2004.
- [Yang87] X.L. Yang and X.D. Zhang, “A general heuristic algorithm of task allocation in distributed systems”, Proceeding of the 2nd International Conference on Computers and Applications, China, pp. 689-693, 1987.
- [Yumi14]
- X. Yuming, Kenli Li, Jingtong Hu, and Keqin Li. "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues." Information Sciences 270 (2014): 255-287.
|