×

zbMATH — the first resource for mathematics

Statistical design of genetic algorithms for combinatorial optimization problems. (English) Zbl 1235.90130
Summary: Many genetic algorithms (GA) have been applied to solve different NP-complete combinatorial optimization problems so far. The striking point of using GA refers to selecting a combination of appropriate patterns in crossover, mutation, and and so forth and fine tuning of some parameters such as crossover probability, mutation probability, and and so forth. One way to design a robust GA is to select an optimal pattern and then to search for its parameter values using a tuning procedure. This paper addresses a methodology to both optimal pattern selection and the tuning phases by taking advantage of design of experiments and response surface methodology. To show the performances of the proposed procedure and demonstrate its applications, it is employed to design a robust GA to solve a project scheduling problem. Through the statistical comparison analyses between the performances of the proposed method and an existing GA, the effectiveness of the methodology is shown.
MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
Genocop
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, Germany, 2003. · Zbl 1028.68022
[2] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Boston, Mass, USA, 1975. · Zbl 0429.03045
[3] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Boston, Mass, USA, 1989. · Zbl 0813.68072
[4] K. Deb, “An introduction to genetic algorithms,” S\Badhan\Ba. Academy Proceedings in Engineering Sciences, vol. 24, no. 4-5, pp. 293-315, 1999. · Zbl 1075.90565
[5] K. Deb, “Genetic algorithm in search and optimization: the technique and applications,” in Proceedings of the International Workshop on Soft Computing and Intelligent Systems, pp. 58-87, Calcutta, India, 1998.
[6] A. W. M. Ng and B. J. C. Perera, “Selection of genetic algorithm operators for river water quality model calibration,” Engineering Applications of Artificial Intelligence, vol. 16, no. 5-6, pp. 529-541, 2003.
[7] A. E. Eiben, R. Hinterding, and Z. Michalewicz, “Parameter control in evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 124-141, 1999. · Zbl 05451876
[8] H. P. Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, New York, NY, USA, 1981. · Zbl 0451.65043
[9] K. A. de Jong and W. M. Spears, “An analysis of the interacting roles of population size and crossover in genetic algorithms,” in Proceedings of the International Conference on Parallel Problems Solving from Nature, pp. 38-47, Springer, Berlin, Germany, 1990.
[10] B. Friesleben and M. Hartfelder, “Optimization of genetic algorithms by genetic algorithms,” in Artificial Neural Networks and Genetic Algorithms, R. F. Albrecht, C. R. Reeves, and N. C. Steele, Eds., pp. 392-399, Springer, Belin, Germany, 1993.
[11] M. E. Samples, M. J. Byom, and J. M. Daida, “Parameter sweeps for exploring parameter spaces of genetic and evolutionary algorithms,” in Parameter Setting in Evolutionary Algorithms, F. G. Lobo, C.F. Lima, and Z. Michalewicz, Eds., pp. 161-184, Springer, Berlin, Germany, 2007.
[12] M. Preuss and T. Bartz-Beielstein, “Sequential parameter optimization applied to self-adaptation for binary-coded evolutionary algorithms,” in Parameter Setting in Evolutionary Algorithms, F. G. Lobo, C.F. Lima, and Z. Michalewicz, Eds., pp. 91-119, Springer, Berlin, Germany, 2007.
[13] T. P. Bagchi and K. Deb, “Calibration of GA parameters: the design of experiments approach,” Computer Science and Informatics, vol. 26, no. 3, pp. 45-56, 1996.
[14] R. Ruiz and C. Maroto, “A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility,” European Journal of Operational Research, vol. 169, no. 3, pp. 781-800, 2006. · Zbl 1079.90061
[15] R. Ruiz, C. Maroto, and J. Alcaraz, “Two new robust genetic algorithms for the flowshop scheduling problem,” Omega, vol. 34, no. 5, pp. 461-476, 2006.
[16] A. Saremi, T. Y. ElMekkawy, and G. G. Wang, “Tuning the parameters of a memetic algorithm to solve vehicle routing problem with backhauls using design of experiments,” International Journal of Operations Research, vol. 4, pp. 206-219, 2007. · Zbl 1153.90329
[17] G. Taguchi and Y. Wu, Introduction to Off-Line Quality Control, Central Japan Quality Control Association, Nagoya, Japan, 1980.
[18] O. Fran\ccois and C. Lavergne, “Design of evolutionary algorithms-a statistical perspective,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 2, pp. 129-148, 2001. · Zbl 05451922
[19] A. Czarn, C. MacNish, K. Vijayan, B. Turlach, and R. Gupta, “Statistical exploratory analysis of genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 4, pp. 405-421, 2004. · Zbl 05451909
[20] C. B. B. Costa, M. R. W. Maciel, and R. M. Filho, “Factorial design technique applied to genetic algorithm parameters in a batch cooling crystallization optimisation,” Computers and Chemical Engineering, vol. 29, no. 10, pp. 2229-2241, 2005.
[21] C. B. B. Costa, E. A. Ccopa-Rivera, M. C. A. F. Rezende, M. R. W. Maciel, and R. M. Filho, “Prior detection of genetic algorithm significant parameters: coupling factorial design technique to genetic algorithm,” Chemical Engineering Science, vol. 62, no. 17, pp. 4780-4801, 2007.
[22] F. G. Lobo, C. F. Lima, and Z. Michalewicz, Parameter Setting in Evolutionary Algorithms, Springer, Berlin, Germany, 2007. · Zbl 1139.68047
[23] W. M. Jenkins, “Towards structural optimization via the genetic algorithm,” Computers and Structures, vol. 40, no. 5, pp. 1321-1327, 1991. · Zbl 0775.73035
[24] P. Hajela, “Stochastic search in discrete structural optimization simulated annealing, genetic algorithms and neural networks,” in Discrete Structural Optimization, W. Gutkowski, Ed., pp. 55-134, Springer, New York, NY, USA, 1997. · Zbl 0885.73052
[25] G. R. Reeves, Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, New York, NY, USA, 1993. · Zbl 0942.90500
[26] O. Andrzej, Evolutionary Algorithms for Single and Multicriteria Design Optimization, Physica, New York, NY, USA, 2002. · Zbl 0988.68207
[27] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, London, UK, 1996. · Zbl 0841.68047
[28] T. Back, D. B. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Institute of Physics Publishing, Bristol, UK, 1997. · Zbl 0883.68001
[29] D. E. Goldberg and K. Deb, “A comparative analysis of selection schemes used in genetic algorithms,” in Foundations of Genetic Algorithms, G. Rawlins, Ed., pp. 69-93, Morgan Kaufmann, San Mateo, Calif, USA, 1991.
[30] G. Syswerda, “Uniform crossover in genetic algorithms,” in Proceedings of the 3rd Conference on Genetic Algorithms, J. D. Schaffer, Ed., pp. 2-8, San Francisco, Calif, USA, 1989.
[31] L. Eshelman, R. Caruana, and D. Schaffer, “Biases in the crossover landscape,” in Proceedings of the 3rd Conference on Genetic Algorithms, J. D. Schaffer, Ed., pp. 10-19, San Francisco, Calif, USA, 1989. · Zbl 0709.68046
[32] W. M. Spears and K. A. de Jong, “On the virtues of parameterized uniform crossover,” in Proceedings of the 4rd Conference on Genetic Algorithms, J. D. Schaffer, Ed., pp. 230-236, San Francisco, Calif, USA, 1991.
[33] K. A. de Jong and W. M. Spears, “A formal analysis of the role of multi-point crossover in genetic algorithms,” Annals of Mathematics and Artificial Intelligence, vol. 5, no. 1, pp. 1-26, 1992. · Zbl 1004.68538
[34] D. C. Montgomery, Design and Analysis of Experiments, John Wiley & Sons, New York, NY, USA, 6th edition, 2005. · Zbl 1195.62128
[35] R. H. Myers and D. C. Montgomery, Response Surface Methodology: Process and Product Optimization Using Designed Experiments, John Wiley & Sons, New York, NY, USA, 2002. · Zbl 1161.62393
[36] R. Narasimhan, “Goal programming in a fuzzy environment,” Decision Sciences, vol. 11, pp. 325-336, 1980.
[37] R. N. Tiwari, S. Dharmar, and J. R. Rao, “Fuzzy goal programming-an additive model,” Fuzzy Sets and Systems, vol. 24, no. 1, pp. 27-34, 1987. · Zbl 0627.90073
[38] J. K. Lee and Y. D. Kim, “Search heuristics for resource constrained project scheduling,” Journal of the Operational Research Society, vol. 47, no. 5, pp. 678-689, 1996. · Zbl 0863.90090
[39] L. Ă–zdamar, “A genetic algorithm approach to a general category project scheduling problem,” IEEE Transactions on Systems, Man and Cybernetics Part C, vol. 29, no. 1, pp. 44-59, 1999.
[40] S. Hartmann, “A competitive genetic algorithm for resource-constrained project scheduling,” Naval Research Logistics, vol. 45, no. 7, pp. 733-750, 1998. · Zbl 0936.90024
[41] J. Alcaraz and C. Maroto, “A robust genetic algorithm for resource allocation in project scheduling,” Annals of Operations Research, vol. 102, pp. 83-109, 2001. · Zbl 1024.90036
[42] J. F. Gon\ccalves, J. J. M. Mendes, and M. G. C. Resende, “A genetic algorithm for the resource constrained multi-project scheduling problem,” European Journal of Operational Research, vol. 189, no. 3, pp. 1171-1190, 2008. · Zbl 1146.90412
[43] A. A. Najafi and S. T. A. Niaki, “A genetic algorithm for resource investment problem with discounted cash flows,” Applied Mathematics and Computation, vol. 183, no. 2, pp. 1057-1070, 2006. · Zbl 1112.90035
[44] A. A. Najafi, S. T. A. Niaki, and M. Shahsavar, “A parameter-tuned genetic algorithm for the resource investment problem with discounted cash flows and generalized precedence relations,” Computers and Operations Research, vol. 36, no. 11, pp. 2994-3001, 2009. · Zbl 1162.90464
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.