A survey of repair methods used as constraint handling techniques in evolutionary algorithms

Goldberg, 1989 Michalewicz, 1996 Bäck, 1996 Fogel, 1994, An introduction to simulated evolutionary optimization, IEEE Transactions on Neural Networks, 5, 3, 10.1109/72.265956 Fogel, 1966 Holland, 1975 Schwefel, 1981 Yao, 1999, Evolutionary programming made faster, IEEE Transactions on Evolutionary Computation, 3, 82, 10.1109/4235.771163 Lee, 2004, Evolutionary programming using mutations based on the Levy Probability distribution, IEEE Transactions on Evolutionary Computation, 8, 1, 10.1109/TEVC.2003.816583 Bäck, 1993, An overview of evolutionary algorithms for parameter optimization, Evolutionary Computation, 1, 1, 10.1162/evco.1993.1.1.1 Beyer, 2002, Evolution strategies — A comprehensive introduction, Natural Computing, 1, 3, 10.1023/A:1015059928466 Krasnogor, 2005, A tutorial for competent memetic algorithms: Model, taxonomy, and design issues, IEEE Transactions on Evolutionary Computation, 9, 474, 10.1109/TEVC.2005.850260 Talbi, 2002, A taxonomy of hybrid metaheuristics, Journal of Heuristics, 8, 541, 10.1023/A:1016540724870 Coello-Coello, 2002, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art, Computational Methods and Applications in Mechanical Engineering, 191, 1245, 10.1016/S0045-7825(01)00323-1 Blum, 2003, Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Computing Surveys, 35, 268, 10.1145/937503.937505 Whitley, 1994, Lamarckian evolution, the Badwin effect and function optimization, Lecture Notes in Computer Science, 866, 6, 10.1007/3-540-58484-6_245 Joines, 2002, Utilizing hybrid genetic algorithms, 199 Tsang, 1993 A. Eiben, P. Rause, Z. Ruttkay, GA-easy and GA-hard constraint satisfaction problems, in: Proceedings of the ECAI’94 Workshop on Constraint Processing, 1995, pp. 267–284 C. Coello-Coello, E. Mezura-Montes, Handling constraints in genetic algorithms using dominance-based tournaments, in: Proceedings of the 5th International Conference on Adaptive Computing Design and Manufacturing, 2002 G. Gréwal, S. Coros, D. Banerji, A. Morton, Comparing a genetic algorithm penalty function and repair heuristic in the DSP application domain, in: Proceedings of IASTED Conference on Artificial Intelligence and Applications, 2006 Kumar, 1992, Algorithms for constraint-satisfaction problems: A survey, Artificial Intelligence Magazine, 13, 32 Milton, 1992, Minimizing conflicts: A heuristic repair method for constraint-satisfaction and scheduling problems, Artificial Intelligence, 58, 161, 10.1016/0004-3702(92)90007-K Vouduris, 1999, Guided local search, European Journal of Operational Research, 113, 469, 10.1016/S0377-2217(98)00099-X Lau, 2001, Guided genetic algorithm and its application to radio link frequency assignment problems, Constraints, 6, 373, 10.1023/A:1011406425471 Craenen, 2003, Comparing evolutionary algorithms on binary constraint satisfaction problems, IEEE Transactions on Evolutionary Computation, 7, 424, 10.1109/TEVC.2003.816584 Eiben, 2001, Evolutionary algorithms and constraint satisfaction: Definitions, survey, methodology, and research directions, 13 Deb, 1999, An efficient constrained handling method for genetic algorithms Craenen, 2001, vol. 1, 341 Chootinan, 2006, Constraint handling in genetic algorithms using a gradient-based repair method, Computers & Operations Research, 4, 2263, 10.1016/j.cor.2005.02.002 Wu, 2005, Solving optimum TDMA broadcast scheduling in mobile ad hoc networks: A competent permutation genetic algorithm approach, IEE Proceedings, 152, 780, 10.1049/ip-com:20045188 Ngo, 2003, Centralized broadcast scheduling in packet radio networks via genetic-fix algorithms, IEEE Transactions on Communications, 51, 1439, 10.1109/TCOMM.2003.816950 Ngo, 1998, Fixed channel assignment in cellular radio networks using a modified genetic algorithm, IEEE Transactions on Vehicular Technology, 47, 163, 10.1109/25.661043 Salcedo-Sanz, 2004, Enhancing genetic feature selection through restricted search and Walsh analysis, IEEE Transactions on Systems, Man and Cybernetics, Part C, 34, 398, 10.1109/TSMCC.2004.833301 Salcedo-Sanz, 2002, vol. 2415 Alexandre, 2007, Feature selection for sound classification in hearing aids through restricted search driven by genetic algorithms, IEEE Transactions on Audio, Speech and Audio Processing, 15, 2249, 10.1109/TASL.2007.905139 A. Webb, B. Turton, J. Brown, Application of genetic algorithm to a network optimization problem, in: Proc. of IEE Telecommunications Conference, 451, 1998, pp. 62–66 Saez-Landete, 2005, Optimal design of optical reference signals using a genetic algorithm, Optics Letters, 30, 2734, 10.1364/OL.30.002724 Saez-Landete, 2006, Design of two dimensional zero reference codes with a genetic algorithm, Optics Letters, 31, 1648, 10.1364/OL.31.001648 Whitley, 2000, 274 Poon, 1995, Genetic algorithm crossover operators for ordering applications, Computers & Operations Research, 22, 135, 10.1016/0305-0548(93)E0024-N Lai, 1996, Channel assignment through evolutionary optimization, IEEE Transactions on Vehicular Technology, 45, 91, 10.1109/25.481825 Choi, 2003, A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem, Computers & Operations Research, 30, 773, 10.1016/S0305-0548(02)00050-3 Ruiz, 2006, Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 461, 10.1016/j.omega.2004.12.006 R. Nakano, Conventional genetic algorithm for job shop problems, in: Proc. of the 4th International Conference on Genetic Algorithms, 1991, pp. 474–479 Carter, 2006, A new approach to solving the multiple traveling salesperson problem using genetic algorithms, European Journal of Operational Research, 175, 246, 10.1016/j.ejor.2005.04.027 Wiese, 2003, A permutation-based genetic algorithm for the RNA folding problem: A critical look at selection strategies, crossover operators, and representation issues, Biosystems, 72, 29, 10.1016/S0303-2647(03)00133-3 G.G. Mitchell, D. O’Donoghue, D. Barnes, M. McCarville, GeneRepair — a repair operator for genetic algorithms, in: Proc. of the Genetic and Evolutionary Computation Conference, 1999, pp. 212–219 J. Gottlieb, G. Raidl, The effects of locality on the dynamics of decoder-based evolutionary search, in: Proc. of the Genetic and Evolutionary Computation Conference, 2000, pp. 283-290 Hopfield, 1982, Neurons and physical systems with emergent collective computational abilities, Proceedings of the National Academy of Sciencies USA, 79, 2554, 10.1073/pnas.79.8.2554 Smith, 1998, Neural techniques for combinatorial optimization with applications, IEEE Transactions on Neural Networks, 9, 1301, 10.1109/72.728380 Salcedo-Sanz, 2003, A mixed neural-genetic algorithm for the broadcast scheduling problem, IEEE Transactions on Wireless Communications, 2, 277, 10.1109/TWC.2003.808967 Salcedo-Sanz, 2004, A hybrid Hopfield network genetic algorithm approach for the terminal assignment problem, IEEE Transactions on Systems Man Cybernatics, 34, 2343, 10.1109/TSMCB.2004.836471 Yao, 2005, Hybrid evolutionary approaches to terminal assignment in communication networks, Recent Advances in Memetic Algorithms, 129, 10.1007/3-540-32363-5_7 Shrivastava, 1992, Guaranteed convergence in a class of Hopfield networks, IEEE Transactions Neural Networks, 3, 951, 10.1109/72.165596 Huang, 1997, Object recognition using genetic algorithms with Hopfield’s neural model, Expert Systems with Applications, 13, 191, 10.1016/S0957-4174(97)00024-9 Salcedo-Sanz, 2005, A hybrid neural-genetic algorithm for the frequency assignment problem in satellite communications, Applied Intelligence, 22, 207, 10.1007/s10791-005-6619-y M. Hadam, M. El-Hawary, Hopfield-genetic approach for solving the routing problem in computers networks, in: Proceedings IEEE Canadian Conference on Electrical & Computing Engineering, 2002, pp. 823–827 Megala, 2006, Genetic algorithm and Hopfield neural network for a dynamic lot sizing problem, International Journal of Advanced Manufacturing Technology, 27, 1178, 10.1007/s00170-004-2306-1 S. De, A. Ghosh, S. Pal, An application of genetic algorithms to evolve Hopfield type optimum network architectures for object extraction, in: Proceedings of the IEEE Conference on Evolutionary Computation, 1995, pp. 504–508 H. Shirai, A. Ishigame, S. Kawamoto, T. Taniguchi, A solution of combinatorial optimization problem by uniting genetic algorithms with Hopfield’s model, in: Proceedings of the IEEE International Conference on Neural Networks, 1994, pp. 4704–4709 Xia, 2005, A binary Hopfield neural network with hysteresis for large crossbar packet switches, Neurocomputing, 67, 417, 10.1016/j.neucom.2004.09.004 Balicki, 1997, Genetic algorithms and Hopfield neural networks to solve combinatorial optimization problems, Applied Mathematics and Computer Science, 10, 568 Watanabe, 1998, Solving optimization problems by using a Hopfield neural network and genetic algorithm combination, Systems and Computers in Japan, 29, 68, 10.1002/(SICI)1520-684X(199810)29:10<68::AID-SCJ7>3.0.CO;2-I Salcedo-Sanz, 2005, A portable and scalable algorithm for a class of constrained combinatorial optimization problems, Computers & Operations Research, 32, 2671, 10.1016/j.cor.2004.03.020 Calderón-Macías, 1997, Hopfield neural networks, and mean field annealing for seismic deconvolution and multiple attenuation, Geophysics, 62, 992, 10.1190/1.1444205 Ansari, 1995, A new method to optimizate the satellite broadcast schedules using the mean field annealing of a Hopfield neural network, IEEE Transactions on Neural Networks, 6, 470, 10.1109/72.363481 E.G. Ortiz-García, S. Salcedo-Sanz, A.M. Pérez-Bellido, J.A. Portilla-Figueras, A hybrid Hopfield network genetic algorithm approach for the lights-up puzzle, in: IEEE Conference on Evolutionary Computation, Singapur, 2007 Chou, 2001, Genetic algorithms for communications network design–an empirical study of the factors that influence performance, IEEE Transactions on Evolutionary Computation, 5, 236, 10.1109/4235.930313 Dengiz, 1995, A genetic algorithm approach to optimal topological design of all terminal networks, vol. 5 Dengiz, 1997, Local search genetic algorithm for optimal design of reliable networks, IEEE Transactions on Evolutionary Computation, 1, 179, 10.1109/4235.661548 Esbensen, 1995, Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm, Networks, 26, 173, 10.1002/net.3230260403 H. Christensen, R. Wainwright, D. Schoenefeld, A hybrid algorithm for the point to multipoint routing problem, in: Proceedings of the ACM Symposium on Applied Computing, 1997, pp. 263–268 Kou, 1981, A fast algorithm for Steiner trees, Acta Informatica, 15, 141, 10.1007/BF00288961 Paulden, 2006, From the Dandelion code to the rainbow code: A class of bijective spanning tree representation with linear complexity and bounded locality, IEEE Transactions on Evolutionary Computation, 10, 108, 10.1109/TEVC.2006.871249 Thompson, 2007, The Dandelion code: A new coding of spanning trees for genetic algorithms, IEEE Transactions on Evolutionary Computation, 11, 91, 10.1109/TEVC.2006.880730 Soak, 2006, The edge-window-decoder representation for tree-based problems, IEEE Transactions on Evolutionary Computation, 10, 124, 10.1109/TEVC.2006.871250 Choi, 2005, A graph-based Lamarckian–Baldwinian hybrid for the sorting network problem, IEEE Transactions on Evolutionary Computation, 10, 105, 10.1109/TEVC.2004.841682 Lo, 2000, A multiobjective hybrid genetic algorithm for the capacitated multipoint network design problem, IEEE Transactions on Systems, Man and Cybernetics, part B, 30, 461, 10.1109/3477.846234 Bui, 1996, Genetic algorithms and graph partitioning, IEEE Transactions on Computers, 45, 841, 10.1109/12.508322 I. Ljubic, J. Kratica, A genetic algorithm for the biconnectivity augmentation problem, in: Proceedings of the IEEE Congress on Evolutionary Computation, 2000, pp. 89–95 Dozier, 1998, Solving constraint satisfaction problems using hybrid evolutionary search, IEEE Transactions on Evolutionary Computation, 2, 23, 10.1109/4235.728211 M. Cebrian, I. Dotú, GRASP-evolution for constraint satisfaction problems, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2006, pp. 531–538 Falkenauer, 1992, The grouping genetic algorithm–widening the scope of the GAs, Proceedings of the Belgian Journal of Operations Research, Statistics and Computer Science, 33, 79 Falkenauer, 1998 James, 2007, A hybrid grouping genetic algorithm for the cell formation problem, Computers & Operations Research, 34, 2059, 10.1016/j.cor.2005.08.010 Brown, 2001, CF-GGA: A grouping genetic algorithm for the cell formation problem, International Journal of Production Research, 36 Hung, 2003, CPGEA: A grouping genetic algorithm for material cutting plan generation, Computers & Industrial Engineering, 44, 651, 10.1016/S0360-8352(03)00004-4 James, 2007, A hybrid grouping genetic algorithm for the registration area planning problem, Computer Communications, 30, 2180, 10.1016/j.comcom.2007.04.018 Brown, 2004, A grouping genetic algorithm for the microcell sectorization problem, Engineering Applications of Artificial Intelligence, 17, 589, 10.1016/S0952-1976(04)00085-5 Vroblefski, 2006, A grouping genetic algorithm for registration area planning, Omega, 34, 220, 10.1016/j.omega.2004.10.005 L.E. Agustín-Blas, S. Salcedo-Sanz, P. Vidales, G. Urueta, A. Portilla-Figueras, A hybrid grouping genetic algorithm for citywide ubiquitous WiFi access deployment, in: Proceedings of the IEEE Conference on Evolutionary Computation, 2009 Agustín-Blas, 2009, A hybrid grouping genetic algorithm for assigning students to preferred laboratory groups, Expert Systems with Applications, 36, 7234, 10.1016/j.eswa.2008.09.020 M. Sinclair, Minimum network wavelength requirement design using a genetic-algorithm/heuristic hybrid, Electronic Letters 34(4), 388–389 Kassotakis, 2000, A hybrid genetic approach for channel reuse in multiple access telecommunication networks, IEEE Journal of Selected Areas in Communications, 18, 179, 10.1109/49.824804 F. Abuali, R. Wainwright, D. Schoenefeld, Determinant factorization: A new encoding scheme for spanning trees applied to the probabilistic minimum spanning tree problem, in: Proceedings of the 6th International Conference on Genetic Algorithms, 1995, pp. 470–477 Sayoud, 2001, A genetic local tuning algorithm for a class of combinatorial networks design problems, IEEE Communications Letters, 5, 322, 10.1109/4234.935756 Alabau, 2002, New hybrid genetic algorithms for the frequency assignment problem, IEEE Transactions on Broadcasting, 48, 27, 10.1109/11.992851 Chakraborty, 2004, Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks, IEEE Transactions on Communications, 52, 765, 10.1109/TCOMM.2004.826234 Xu, 2002, Traffic grooming in unidirectional WDM ring networks using genetic algorithms, Computer Communications, 25, 1185, 10.1016/S0140-3664(02)00007-5 Gen, 2001, Network design techniques using adapted genetic algorithms, Advances in Engineering Software, 32, 731, 10.1016/S0965-9978(01)00007-2 Gen, 2005, Recent network design techniques using evolutionary algorithms, International Journal of Production Economics, 98, 251, 10.1016/j.ijpe.2004.05.026 Mutafungwa, 2002, GORA: An algorithm for designing optical cross-connect nodes with improved dependability, Computer Communications, 25, 1454, 10.1016/S0140-3664(02)00046-4 Chan, 2002, Hard handoff minimization using genetic algorithms, Signal Processing, 82, 1047, 10.1016/S0165-1684(02)00213-X Pierre, 1998, A genetic algorithm for designing distributed computer network topologies, IEEE Transactions on System, Man and Cybernetics, Part B, 28, 249, 10.1109/3477.662766 He, 2000, Hybrid genetic algorithms for telecommunications network back-up routering, BT Technology Journal, 18, 42, 10.1023/A:1026702624501 Buriol, 2005, A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing, Networks, 46, 36, 10.1002/net.20070 P. Galiasso, R. Wainwright, A hybrid algorithm for the point to multipoint problem with single split paths, in: Proceedings of the ACM Symposium on Applied Computing, 2001, pp. 327–332 Y. Zhong, J. Yang, H. Qi, A hybrid genetic algorithm for tasks scheduling in heterogeneous computing systems, in: Proceedings of the 3rd International Conference on Machine Learning and Cybernetics, 2004, pp. 2463–2468 Reichelt, 2006, Reliable communication network design with evolutionary algorithms, International Journal of Computational Intelligence and Applications, 5, 251, 10.1142/S146902680500160X Xiao, 1997, Adaptive evolutionary planner/navigator for mobile robots, IEEE Transactions on Evolutionary Computation, 1, 67 Liepins, 1991, A genetic algorithm approach to multiple-fault diagnosis, Handbook of genetic algorithms, 237 Liepins, 1990, Representational issues in genetic optimization, Journal of Experimental and Theoretical Artificial Intelligence, 2, 101, 10.1080/09528139008953717 Mühlenbein, 1992, Parallel genetic algorithms in combinatorial optimization, Computer Science and Operations Research, 441, 10.1016/B978-0-08-040806-4.50034-4 Wilke, 2002, A hybrid genetic algorithm for school timetabling, vol. 2557, 455 R. Weare, E. Burke, D. Elliman, A hybrid genetic algorithm for highly constrained timetabling problems, in: Proceedings of the 6th International Conference on Genetic Algorithms, 1995, pp. 605–610 Santiago-Mozos, 2005, A two-phase heuristic evolutionary algorithm for personalizing course timetables: A case study in a Spanish university, Computers & Operations Research, 32, 1761, 10.1016/j.cor.2003.11.030 C. Di Stefano, A. Tettamanzi, An evolutionary algorithm for solving the school timetabling problem, in: Proceedings of the 14th Annual ACM Symposium on Applied Computing, 1999 de Werra, 1985, An introduction to timetabling, European Journal of Operational Research, 19, 151, 10.1016/0377-2217(85)90167-5 Burke, 2002, Recent research directions in automated timetabling, European Journal of Operational Research, 140, 260, 10.1016/S0377-2217(02)00069-3 Schaerf, 1999, A survey of automated timetabling, Artificial Intelligence Review, 13, 87, 10.1023/A:1006576209967 Carter, 1998, vol. 1408, 3 Burbidge, 1979 D. Orvosh, L. Davis, Using a genetic algorithm to optimize problems with feasibility constraints, in: Proceedings of the 1st IEEE Conference on Evolutionary Computation, 1994, pp. 548–552 D. Orvosh, L. Davis, Shall we repair? genetic algorithms, combinatorial optimization and feasibility, in: Proceedings of the 5th International Conference on Genetic Algorithms, 1993 Runarsson, 2000, Stochastic ranking for constrained evolutionary optimization, IEEE Transactions on Evolutionary Computation, 4, 284, 10.1109/4235.873238 Bäck, 1995, A comparative study of a penalty function, a repair heuristic and stochastic operators with the set-covering problem, Artificial Evolution, 320 Homaifar, 1994, Constrained optimization via genetic algorithms, Simulation, 62, 242, 10.1177/003754979406200405 Michalewicz, 1996, Evolutionary algorithms for constrained parameter optimization, Evolutionary Computation, 4, 1, 10.1162/evco.1996.4.1.1 Runarsson, 2005, Search biases in constrained evolutionary optimization, IEEE Transactions on Systems, Man and Cybernetics, Part C, 35, 233, 10.1109/TSMCC.2004.841906 Wang, 2005, An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme, IEEE Transactions on Systems, Man and Cybernetics, Part C, 35, 221, 10.1109/TSMCC.2004.841908 Coello-Coello, 2000, Treating constraints as objectives for single-objective evolutionary optimization, Engineering Optimization, 32, 275, 10.1080/03052150008941301 T. Ray, K. Tai, K. Seow, An evolutionary algorithm for constrained optimization, in: Proceedings Genetic and Evolutionary Computing Conference, 2000 Koziel, 1999, Evolutionary algorithms, homeomorphous mappings, and constrained parameter optimization, Evolutionary Computation, 7, 19, 10.1162/evco.1999.7.1.19 Sarker, 2002, Constrained evolutionary optimization: The penalty function approach, 87 Z. Michalewicz, J. Xiao, Evaluation of paths in evolutionary planner/navigator, in: Proceedings of the International Workshop on Biologically Inspired Evolutionary Systems, 1995, pp. 45–52 Tate, 1995, A genetic approach to the quadratic assignment problem, Computers & Operations Research, 22, 73, 10.1016/0305-0548(93)E0020-T