Filter-based genetic algorithm for mixed variable programming

Previous Article
A derivative-free trust-region algorithm for unconstrained optimization with controlled error
NACO Home
This Issue
Next Article
Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints

2011, 1(1): 99-116. doi: 10.3934/naco.2011.1.99

Filter-based genetic algorithm for mixed variable programming

Abdel-Rahman Hedar ^1, and Alaa Fahim ^2,

1.	Dept. of Computer Science, Faculty of Computers and Information, Assiut University, Assiut 71526, Egypt
2.	Dept. of Mathematics, Faculty of Science, Assiut University, Assiut 71516, Egypt

Received October 2010 Revised November 2010 Published February 2011

Abstract
Related Papers

In this paper, Filter Genetic Algorithm (FGA) method is proposed to find the global optimal of the constrained mixed variable programming problem. The considered problem is reformulated to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the filter set methodology [5] is applied within a genetic algorithm framework to solve the reformulated problem. We use pattern search as local search to improve the obtained solutions. Moreover, the gene matrix criteria [10] has been applied to accelerated the search process and to terminate the algorithm. The proposed method FGA is promising compared with some other methods existing in the literature.

Keywords: filter method, Genetic algorithm, gene matrix., pattern search, mixed variable programming.

Mathematics Subject Classification: Primary: 90C11, 68T20, 68W20; Secondary: 68T0.

Citation: Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

References:

[1]	C. Audet and J. E. Dennis, Jr., Analysis of generalized pattern searches, SIAM Journal on Optimization, 13(3) (2003), 889-903. doi: 10.1137/S1052623400378742.
[2]	J. E. Baker, Adaptive selection methods for genetic algorithms, In "Proceedings of the First International Conference on Genetic Algorithms''(eds. J. J. Grefenstette), Lawrence Erlbaum Associates, Hillsdale, MA (1985), 101-111.
[3]	T. Butter, F. Rothlauf, J. Grahl, T. Hildenbrand and J. Arndt, Developing Genetic Algorithm and Mixed Integer Linear Programs for finding optimal strategies for a student's activity, (2006).
[4]	K. Deep, K. P. Singh, M. L. Kansal and C. Mohan, A real coded genetic algorithm for solving integer and mixed integer optimization problems, Mathematics and Computation, 212 (2009), 505-518.
[5]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.
[6]	, Genetic Algorithm and Direct Search Toolbox, MATLAB.
[7]	A. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.
[8]	A. Hedar and M. Fukuhima, Derivative-Free filter simulated annealing method for constrained continuous global optimization problems, Journal of Global Optimization, 35 (2006), 521-549. doi: 10.1007/s10898-005-3693-z.
[9]	A. Hedar and M. Fukuhima, Evolution strategies learned with automatic termination criteria, Proceedings of SCIS & ISIS 2006, Tokyo, Japan, September 20-24, 2006.
[10]	A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination, Technical Report 2007-002, Department of Applied Mathematics and Physics, Kyoto University (January 2007).
[11]	F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis, Artificial Intelligence Review, 12 (1998), 265-319. doi: 10.1023/A:1006504901164.
[12]	R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems, J. ACM, 8 (1961), 212-229. doi: 10.1145/321062.321069.
[13]	Z. Hua and F. Huang, An effective genetic algorithm approach to large scale mixed integer programming problems, Applied Mathematics and Computation, 174 (2006), 897-909. doi: 10.1016/j.amc.2005.05.017.
[14]	Y. C. Lin and K. S. Hwang, A mixed-coding scheme of evolutionary algorithms to solve mixed-integer nonlinear programming problems, Computers and Mathematics with Applications, 47 (2004), 1295-1307. doi: 10.1016/S0898-1221(04)90123-X.
[15]	A. K. Maiti, A. K. Bhunia and M. Maiti, An application of real-coded genetic algorithm (RCGA) for mixed integer non-linear programming in two stage multi-item inventory model with discount policy, Applied Mathematics and Computation, 183 (2006), 903-915. doi: 10.1016/j.amc.2006.05.141.
[16]	M. Schlutera, J. Egeab and J. Bangab, Extended ant colony optimization for non-convex mixed integer nonlinear programming. Computers and Operations Research, 36 (2009), 2217-2229. doi: 10.1016/j.cor.2008.08.015.
[17]	V. K. Srivastava and A. Fahim, An optimization method for solving mixed discrete-continuous programming problems, Computers and Mathematics with Applications, 53 (2007), 1481-1491. doi: 10.1016/j.camwa.2007.01.006.
[18]	T. Yokota, M. Gen and Y. X. Li, Genetic algorithm for nonlinear mixed integer programming problems and its application, Computers and Industrial Engineering, 30 (1996), 905-917. doi: 10.1016/0360-8352(96)00041-1.
[19]	V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), 1-25. doi: 10.1137/S1052623493250780.

show all references

References:

[1]	C. Audet and J. E. Dennis, Jr., Analysis of generalized pattern searches, SIAM Journal on Optimization, 13(3) (2003), 889-903. doi: 10.1137/S1052623400378742.
[2]	J. E. Baker, Adaptive selection methods for genetic algorithms, In "Proceedings of the First International Conference on Genetic Algorithms''(eds. J. J. Grefenstette), Lawrence Erlbaum Associates, Hillsdale, MA (1985), 101-111.
[3]	T. Butter, F. Rothlauf, J. Grahl, T. Hildenbrand and J. Arndt, Developing Genetic Algorithm and Mixed Integer Linear Programs for finding optimal strategies for a student's activity, (2006).
[4]	K. Deep, K. P. Singh, M. L. Kansal and C. Mohan, A real coded genetic algorithm for solving integer and mixed integer optimization problems, Mathematics and Computation, 212 (2009), 505-518.
[5]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.
[6]	, Genetic Algorithm and Direct Search Toolbox, MATLAB.
[7]	A. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.
[8]	A. Hedar and M. Fukuhima, Derivative-Free filter simulated annealing method for constrained continuous global optimization problems, Journal of Global Optimization, 35 (2006), 521-549. doi: 10.1007/s10898-005-3693-z.
[9]	A. Hedar and M. Fukuhima, Evolution strategies learned with automatic termination criteria, Proceedings of SCIS & ISIS 2006, Tokyo, Japan, September 20-24, 2006.
[10]	A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination, Technical Report 2007-002, Department of Applied Mathematics and Physics, Kyoto University (January 2007).
[11]	F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis, Artificial Intelligence Review, 12 (1998), 265-319. doi: 10.1023/A:1006504901164.
[12]	R. Hooke and T. A. Jeeves, Direct search solution of numerical and statistical problems, J. ACM, 8 (1961), 212-229. doi: 10.1145/321062.321069.
[13]	Z. Hua and F. Huang, An effective genetic algorithm approach to large scale mixed integer programming problems, Applied Mathematics and Computation, 174 (2006), 897-909. doi: 10.1016/j.amc.2005.05.017.
[14]	Y. C. Lin and K. S. Hwang, A mixed-coding scheme of evolutionary algorithms to solve mixed-integer nonlinear programming problems, Computers and Mathematics with Applications, 47 (2004), 1295-1307. doi: 10.1016/S0898-1221(04)90123-X.
[15]	A. K. Maiti, A. K. Bhunia and M. Maiti, An application of real-coded genetic algorithm (RCGA) for mixed integer non-linear programming in two stage multi-item inventory model with discount policy, Applied Mathematics and Computation, 183 (2006), 903-915. doi: 10.1016/j.amc.2006.05.141.
[16]	M. Schlutera, J. Egeab and J. Bangab, Extended ant colony optimization for non-convex mixed integer nonlinear programming. Computers and Operations Research, 36 (2009), 2217-2229. doi: 10.1016/j.cor.2008.08.015.
[17]	V. K. Srivastava and A. Fahim, An optimization method for solving mixed discrete-continuous programming problems, Computers and Mathematics with Applications, 53 (2007), 1481-1491. doi: 10.1016/j.camwa.2007.01.006.
[18]	T. Yokota, M. Gen and Y. X. Li, Genetic algorithm for nonlinear mixed integer programming problems and its application, Computers and Industrial Engineering, 30 (1996), 905-917. doi: 10.1016/0360-8352(96)00041-1.
[19]	V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), 1-25. doi: 10.1137/S1052623493250780.

[1]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[2]	Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[3]	Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[4]	Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279
[5]	T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial and Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53
[6]	William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041
[7]	Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009
[8]	Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial and Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[9]	Hai Huyen Dam, Kok Lay Teo. Variable fractional delay filter design with discrete coefficients. Journal of Industrial and Management Optimization, 2016, 12 (3) : 819-831. doi: 10.3934/jimo.2016.12.819
[10]	Ying Hao, Fanwen Meng. A new method on gene selection for tissue classification. Journal of Industrial and Management Optimization, 2007, 3 (4) : 739-748. doi: 10.3934/jimo.2007.3.739
[11]	Roberto Serra, Marco Villani, Alex Graudenzi, Annamaria Colacci, Stuart A. Kauffman. The simulation of gene knock-out in scale-free random Boolean models of genetic networks. Networks and Heterogeneous Media, 2008, 3 (2) : 333-343. doi: 10.3934/nhm.2008.3.333
[12]	Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[13]	Adrian Korban, Serap Sahinkaya, Deniz Ustun. New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022032
[14]	Adrian Korban, Serap Şahinkaya, Deniz Ustun. A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022033
[15]	Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240
[16]	Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[17]	Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[18]	Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140
[19]	Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial and Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875
[20]	Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Abdel-Rahman Hedar Alaa Fahim
on Google Scholar
Abdel-Rahman Hedar Alaa Fahim

[Back to Top]