zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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:
90C27Combinatorial optimization
90C59Approximation methods and heuristics
Software:
Genocop
WorldCat.org
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 · doi:10.1007/BF02823145
[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. · doi:10.1016/j.engappai.2003.09.001
[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. · doi:10.1109/4235.771166
[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 · doi:10.1016/j.ejor.2004.06.038
[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. · doi:10.1016/j.omega.2004.12.006
[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. · doi:10.1109/4235.918434
[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. · doi:10.1109/TEVC.2004.831262
[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. · doi:10.1016/j.compchemeng.2005.08.005
[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. · doi:10.1016/j.ces.2007.03.042
[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 · doi:10.1016/0045-7949(91)90402-8
[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 · doi:10.1887/0750308958
[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 · doi:10.1007/BF01530777
[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. · doi:10.1111/j.1540-5915.1980.tb01142.x
[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 · doi:10.1016/0165-0114(87)90111-4
[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 · doi:10.1057/jors.1996.79
[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. · doi:10.1109/5326.740669
[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 · doi:10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C
[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 · doi:10.1023/A:1010949931021
[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 · doi:10.1016/j.ejor.2006.06.074
[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 · doi:10.1016/j.amc.2006.05.118
[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 · doi:10.1016/j.cor.2009.01.016