• Previous Article
    Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints
  • NACO Home
  • This Issue
  • Next Article
    A derivative-free trust-region algorithm for unconstrained optimization with controlled error
2011, 1(1): 99-116. doi: 10.3934/naco.2011.1.99

Filter-based genetic algorithm for mixed variable programming

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.
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. doi: 10.1137/S1052623400378742.

[2]

J. E. Baker, Adaptive selection methods for genetic algorithms,, In, (1985), 101.

[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)., (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.

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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.

[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. 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, (2006), 20.

[10]

A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination,, Technical Report 2007-002, (2007), 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1016/0360-8352(96)00041-1.

[19]

V. Torczon, On the convergence of pattern search algorithms,, SIAM J. Optim., 7 (1997), 1. 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. doi: 10.1137/S1052623400378742.

[2]

J. E. Baker, Adaptive selection methods for genetic algorithms,, In, (1985), 101.

[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)., (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.

[5]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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.

[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. 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, (2006), 20.

[10]

A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms with automatic accelerated termination,, Technical Report 2007-002, (2007), 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1016/0360-8352(96)00041-1.

[19]

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

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

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

[3]

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

[4]

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

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

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic Sylvester matrix equations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1-13. doi: 10.3934/jimo.2017053

[14]

Qingzhi Yang. The revisit of a projection algorithm with variable steps for variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 211-217. doi: 10.3934/jimo.2005.1.211

[15]

Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059

[16]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[17]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[18]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367

[19]

Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059

[20]

Yaguang Huangfu, Guanqing Liang, Jiannong Cao. MatrixMap: Programming abstraction and implementation of matrix computation for big data analytics. Big Data & Information Analytics, 2016, 1 (4) : 349-376. doi: 10.3934/bdia.2016015

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]