×

A real coded genetic algorithm for solving integer and mixed integer optimization problems. (English) Zbl 1168.65353

Summary: A real coded genetic algorithm named MI-LXPM is proposed for solving integer and mixed integer constrained optimization problems. The proposed algorithm is a suitably modified and extended version of the real coded genetic algorithm, LXPM, of Deep and Thakur [K. Deep and M. Thakur, Appl. Math. Comput. 188, No. 1, 895–911 (2007; Zbl 1137.90726); Appl. Math. Comput. 193, No. 1, 211–230 (2007)]. The algorithm incorporates a special truncation procedure to handle integer restrictions on decision variables along with a parameter free penalty approach for handling constraints. The performance of the algorithm is tested on a set of twenty test problems selected from different sources in literature, and compared with the performance of an earlier application of a genetic algorithm and also with a random search based algorithm, RST2ANU, incorporating annealing concept. The proposed MI-LXPM outperforms both the algorithms in most of the cases which are considered.

MSC:

65K05 Numerical mathematical programming methods

Citations:

Zbl 1137.90726
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Deep, K.; Thakur, M., A new crossover operator for real coded genetic algorithms, Applied Mathematics and Computation, 188, 895-912 (2007) · Zbl 1137.90726
[2] Deep, K.; Thakur, M., A new mutation operator for real coded genetic algorithms, Applied Mathematics and Computation, 193, 211-230 (2007) · Zbl 1193.68209
[3] Cooper, M. W., Survey of methods for nonlinear integer programming, Management Science, 27, 353-361 (1981) · Zbl 0453.90067
[4] Salkin, H. M., Integer Programming (1975), Eddison Wesley Publishing Com.: Eddison Wesley Publishing Com. Amsterdam · Zbl 0319.90038
[5] Floudas, C. A., Nonlinear Mixed-integer Optimization. Fundamentals and Applications (1995), Oxford University Press: Oxford University Press New York, USA · Zbl 0886.90106
[6] Grossmann, I. E., Review of non-linear mixed integer and disjunctive programming techniques, Optimization and Engineering, 3, 227-252 (2002) · Zbl 1035.90050
[7] Marchand, H.; Martin, A.; Weismantel, R., Cutting planes in integer and mixed integer programming, Discrete Applied Mathematics, 123, 397-446 (2002) · Zbl 1130.90370
[8] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[9] Sonilah, A., Simulated anneling for manufacturing systems layout design, European Journal of Operational Research, 82, 592-614 (1995)
[10] Cardoso, M. F.; Salcedo, R. L.; Azevedo, S. F.; Barbosa, D., A simulated annealing approach to the solution of minlp problems, Computers and Chemical Engineering, 21, 1349-1364 (1997)
[11] B.V. Babu, R. Angira, A differential evolution approach for global optimization of minlp problems, in: Proceedings of Fourth Asia Pacific Conference on Simulated Evolution and Learning, Singapore, 2002, pp. 880-884.; B.V. Babu, R. Angira, A differential evolution approach for global optimization of minlp problems, in: Proceedings of Fourth Asia Pacific Conference on Simulated Evolution and Learning, Singapore, 2002, pp. 880-884.
[12] Yan, L.; Shen, K.; Hu, S., Solving mixed integer nonlinear programming problems with line-up competition algorithm, Computers and Chemical Engineering, 28, 2647-2657 (2004)
[13] Yiqing, L.; Xigang, Y.; Yongjian, L., An improved pso algorithm for solving non-convex nlp/minlp problems with equality constraints, Computers and Chemical Engineering, 31, 153-162 (2007)
[14] Price, W. L., Global optimization by controlled random search, Journal of Optimization: Theory and Applications, 40, 333-348 (1983) · Zbl 0494.90063
[15] Price, W. L., Global optimization algorithms for cad workstation, Journal of Optimization: Theory and Application, 55, 133-146 (1987) · Zbl 0622.90073
[16] Mohan, C.; Shanker, K., A controlled random search technique for global optimization using quadratic approximation, Asia-Pacific Journal of Operation Research, 11, 93-101 (1994) · Zbl 0807.90104
[17] Mohan, C.; Nguyen, H. T., A controlled random search technique incorporating the simulating annealing concept for solving integer and mixed integer global optimization problems, Computational Optimization and Applications, 14, 103-132 (1999) · Zbl 0970.90053
[18] Salcedo, R. L., Solving nonconvex nonlinear programming and mixed-integer non-linear programming problems with adaptive random search, Industrial & Engineering Chemistry Research, 31, 262-273 (1992)
[19] Holland, J. H., Adaptation in Natural and Artificial systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor
[20] K.A. De-Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. Thesis, University of Michigan, 1975.; K.A. De-Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. Thesis, University of Michigan, 1975.
[21] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley New York, USA · Zbl 0721.68056
[22] Deb, K., Multi-Objective Optimization using Evolutionary Algorithms (2001), John Wiley and Sons · Zbl 0970.90091
[23] Cheung, B. K.S.; Langevin, A.; Delmaire, H., Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems, Computers and Mathematics with Applications, 32, 13-23 (1997) · Zbl 0905.90126
[24] Luo, Y. C.; Guignard, M.; Chen, C. H., A hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization, Journal of Intelligent Manufacturing, 12, 509-519 (2001)
[25] Costa, L.; Oliveria, P., Evolutionary algorithms approach to the solution jof mixed integer non-linear programming problems, Computers and Chemical Engineering, 21, 257-266 (2001)
[26] Hua, Z.; Huang, F., An efficient genetic algorithm approach to large scale mixed integer programming problems, Applied Mathematics and Computation, 174, 897-907 (2006)
[27] Y.-X. Li, M. Gen, Nonlinear mixed integer programming problems using genetic algorithm and penalty function, in: Proceeding of the IEEE International Conference on Systems, Man and Cybernatics, vol. 4, 1996, pp. 2677-2682.; Y.-X. Li, M. Gen, Nonlinear mixed integer programming problems using genetic algorithm and penalty function, in: Proceeding of the IEEE International Conference on Systems, Man and Cybernatics, vol. 4, 1996, pp. 2677-2682.
[28] Yokota, T.; Gen, M.; Li, Y. X., Genetic algorithm for nonlinear mixed integer programming problems and its applications, Computers and Industrial Engineering, 30, 905-917 (1996)
[29] Maiti, A. K.; Bhunia, A. K.; Maiti, M., An application of real coded genetic algorithm (rcga) for mixed integer non-linear programming in two storage multi-item inventory model with discount policy, Applied Mathematics and Computation, 183, 903-915 (2006) · Zbl 1112.90103
[30] Ponsich, A.; Pantel, C. A.; Domenech, S.; Pibouleau, L., Mixed integer nonlinear programming optimization strategies for batch plant design problems, Industrial & Engineering Chemistry Research, 46, 854-863 (2007)
[31] D.E. Goldberg, K. Deb, A comparison of selection schemes used in genetic algorithms, in: Foundations of Genetic Algorithms 1, FOGA-1, vol. 1, 1991, pp. 69-93.; D.E. Goldberg, K. Deb, A comparison of selection schemes used in genetic algorithms, in: Foundations of Genetic Algorithms 1, FOGA-1, vol. 1, 1991, pp. 69-93.
[32] Deb, K., An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 311-338 (2000) · Zbl 1028.90533
[33] Bharti, Controlled Random Search Techniques and Their Applications, Ph.D. Thesis, Department of Mathematics, University of Roorkee, India, 1994.; Bharti, Controlled Random Search Techniques and Their Applications, Ph.D. Thesis, Department of Mathematics, University of Roorkee, India, 1994.
[34] Kocis, G. R.; Grossmann, I. E., Global optimazation of nonconvex mixed-integer nonlinear programming (minlp) problems in process synthesis, Industrial & Engineering Chemistry Research, 27, 1407-1421 (1988)
[35] H.T. Nguyen, Some Global Optimization Techniques and Their Use in Solving Optimization Problems in Crisp and Fuzzy Environments, Ph.D. Thesis, Department of Mathematics, University of Roorkee, Roorkee, India, 1996.; H.T. Nguyen, Some Global Optimization Techniques and Their Use in Solving Optimization Problems in Crisp and Fuzzy Environments, Ph.D. Thesis, Department of Mathematics, University of Roorkee, Roorkee, India, 1996.
[36] Yuan, X.; Zhang, S.; Pibouleau, L.; Domenech, S., une methode d’optimization nonlineaire en variables mixtes pour la conception de proceds, RAIRO Operations Research, 22, 131-146 (1988)
[37] Berman, O.; Ashrafi, N., Optimization models for reliability of modular software systems, IEEE Transactions on Software Engineering, 19, 11-19 (1993)
[38] Bazaraa, M. S.; Sherah, H. D.; Shetty, C. M., Nonlinear Programming: Theory and Algorithms (2004), John Wiley and Sons: John Wiley and Sons Asia
[39] Himmelblau, D. M., Applied Nonlinear Programing (1972), McGraw Hill: McGraw Hill New York, USA
[40] Conley, W., Computer Optimization Techniques (1984), Petrocelli Books: Petrocelli Books Newjersy, USA
[41] Dhingra, A. K., Optimal apportionment of reliability and redundancy in series systems under multiple objectives, IEEE Transactions on Reliability, 41, 576-582 (1992) · Zbl 0775.90182
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.