×

Hybrid genetic algorithm for optimization problems with permutation property. (English) Zbl 1067.90147

Summary: The permutation property has been recognized as a common but challenging feature in combinatorial problems. Because of their complexity, recent research has turned to genetic algorithms to address such problems. Although genetic algorithms have been proven to facilitate the entire space search, they lack in fine-tuning capability for obtaining the global optimum. Therefore, in this study a hybrid genetic algorithm was developed by integrating both the evolutional and the neighborhood search for permutation optimization.
Experimental results of a production scheduling problem indicate that the hybrid genetic algorithm outperforms the other methods, in particular for larger problems. Numerical evidence also shows that different input data from the initial, transient and steady states influence computation efficiency in different ways. Therefore, their properties have been investigated to facilitate the measure of the performance and the estimation of the accuracy.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research

Software:

CPLEX; Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0469.90052
[2] Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[3] Houck, C. R.; Joines, J. A.; Kay, M. G., Comparison of genetic algorithms, random restart, and two-opt switching for solving large location-allocation problems, Computers & Operations Research, 23, 6, 587-596 (1996) · Zbl 0847.90091
[4] Kirkpatrick S, Gelatt Jr CD, Vecchi MP. Optimization by simulated annealing. IBM Research Report RC 9355, 1982.; Kirkpatrick S, Gelatt Jr CD, Vecchi MP. Optimization by simulated annealing. IBM Research Report RC 9355, 1982.
[5] Glover, F., A user’s guide to tabu search, Annals of Operations Research, 41, 3-28 (1993) · Zbl 0772.90063
[6] Holland JH. Adaptation in natural and artificial systems, 2nd ed. Ann Arbor: University of Michigan Press; 1975. Cambridge: MIT Press; 1992.; Holland JH. Adaptation in natural and artificial systems, 2nd ed. Ann Arbor: University of Michigan Press; 1975. Cambridge: MIT Press; 1992.
[7] Mitchell, M., An introduction to genetic algorithm (1996), MIT Press: MIT Press Cambridge
[8] Gen, M.; Cheng, R., Genetic algorithms and engineering optimization (1997), Wiley: Wiley New York
[9] Reeves, C. R., Modern heuristic techniques for combinatorial problems (1993), Blackwell: Blackwell Oxford · Zbl 0942.90500
[10] Aarts E, Lenstra JK, editors. Local search in combinatorial optimization. Chichester: Wiley; 1997.; Aarts E, Lenstra JK, editors. Local search in combinatorial optimization. Chichester: Wiley; 1997. · Zbl 0869.00019
[11] Tian, P.; Ma, J.; Zhang, D.-. M., Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation propertyan investigation of generation mechanism, European Journal of Operational Research, 118, 81-94 (1999) · Zbl 0945.90051
[12] Djerid, L.; Portmann, M.-. C., How to keep good schemata using cross-over operators for permutation problems, International Transactions in Operational Research, 7, 637-651 (2000)
[13] Renders, J.-. M.; Flasse, S., Hybrid methods using genetic algorithms for global optimization, IEEE Transactions on Systems, Man and Cybernetics Part B, 26, 2, 243-258 (1996)
[14] Chu, P. C.; Beasley, J. E., A genetic algorithm for the generalized assignment problem, Computers & Operations Research, 24, 1, 17-23 (1997) · Zbl 0881.90070
[15] Yagiura, M.; Ibaraki, T., The use of dynamic programming in genetic algorithms for permutation problems, European Journal of Operational Research, 92, 387-401 (1996) · Zbl 0912.90242
[16] Joines, J. A.; Kay, M. G.; King, R. E.; Culbreth, C. T., A hybrid genetic algorithm for manufacturing cell design, Journal of Chinese Institute of Industrial Engineers, 17, 5, 549-564 (2000)
[17] Whitley D, Gordan V, Mathias K. Lamarckian evolution, the Baldwin effect and function optimization. In: Davidor et al., editors. Parallel problem solving from nature: PPSN III. Berlin: Springer-Verlag; 1994. p. 6-15.; Whitley D, Gordan V, Mathias K. Lamarckian evolution, the Baldwin effect and function optimization. In: Davidor et al., editors. Parallel problem solving from nature: PPSN III. Berlin: Springer-Verlag; 1994. p. 6-15.
[18] Bean, J., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 2, 154-160 (1994) · Zbl 0807.90060
[19] Hansen P, Mladenović N. First improvement may be better than best improvement: an empirical study. Les Cahiers du GERAD G-99-40, Montréal, Canada, 1999.; Hansen P, Mladenović N. First improvement may be better than best improvement: an empirical study. Les Cahiers du GERAD G-99-40, Montréal, Canada, 1999.
[20] Johnson DS, Bentley JL, McGeoch LA, Rothberg EE. Near-optimal solutions to very large traveling salesman problems. Monograph 2003, to be published.; Johnson DS, Bentley JL, McGeoch LA, Rothberg EE. Near-optimal solutions to very large traveling salesman problems. Monograph 2003, to be published.
[21] Poon, P. W.; Carter, J. N., Genetic algorithm crossover operators for ordering applications, Computers & Operations Research, 22, 1, 135-147 (1995) · Zbl 0813.90098
[22] Murata, T.; Ishibuchi, H.; Tanaka, H., Genetic algorithms for flowshop scheduling problems, Computers & Industrial Engineering, 30, 4, 1061-1071 (1996)
[23] Wang, H. F.; Wu, K. Y., Modeling and analysis for multi-period, multi-product and multi-resource production scheduling, Journal of Intelligent Manufacturing, 14, 3, 297-309 (2003)
[24] ILOG. Using the CPLEX Callable Library. ILOG CPLEX Division, 1997.; ILOG. Using the CPLEX Callable Library. ILOG CPLEX Division, 1997.
[25] Ho, Y. C., On the numerical solution of stochastic optimization problem, IEEE Transactions on Automatic Control, 42, 5, 727-729 (1997) · Zbl 1078.93576
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.