American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar

[6]

, Genetic Algorithm and Direct Search Toolbox,, MATLAB., ().   Google Scholar

[7]

A. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.  Google Scholar

[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.  Google Scholar

[9]

A. Hedar and M. Fukuhima, Evolution strategies learned with automatic termination criteria, Proceedings of SCIS & ISIS 2006, Tokyo, Japan, September 20-24, 2006. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), 1-25. doi: 10.1137/S1052623493250780.  Google Scholar

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.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar

[6]

, Genetic Algorithm and Direct Search Toolbox,, MATLAB., ().   Google Scholar

[7]

A. Hedar and M. Fukushima, Minimizing multimodal functions by simplex coding genetic algorithm, Optimization Methods and Software, 18 (2003), 265-282.  Google Scholar

[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.  Google Scholar

[9]

A. Hedar and M. Fukuhima, Evolution strategies learned with automatic termination criteria, Proceedings of SCIS & ISIS 2006, Tokyo, Japan, September 20-24, 2006. Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), 1-25. doi: 10.1137/S1052623493250780.  Google Scholar

[1]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & 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 & 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 & 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 & 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 & 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]

Hai Huyen Dam, Kok Lay Teo. Variable fractional delay filter design with discrete coefficients. Journal of Industrial & Management Optimization, 2016, 12 (3) : 819-831. doi: 10.3934/jimo.2016.12.819
[9]

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 & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134
[10]

Ying Hao, Fanwen Meng. A new method on gene selection for tissue classification. Journal of Industrial & Management Optimization, 2007, 3 (4) : 739-748. doi: 10.3934/jimo.2007.3.739
[11]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[12]

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 & Heterogeneous Media, 2008, 3 (2) : 333-343. doi: 10.3934/nhm.2008.3.333
[13]

Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial & Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875
[14]

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
[15]

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 & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[16]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020140
[17]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[18]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[19]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[20]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

 Impact Factor: 

Tools

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences