Arnaud Liefooghe
ABSTRACT
Real-world optimization problems frequently have constraints that define feasible and infeasible combinations of decision variables. Evolutionary algorithms do not inherently work with constraints, so they must be modified to include a suitable constraint handling technique (CHT) before they can be used to solve such problems. A range of different approaches to handling constraints have been used effectively with evolutionary algorithms, such as penalty-based, repair, feasibility rules, and bi-objective approaches. In this study we investigate different CHTs with an evolutionary algorithm on the 0/1 knapsack problem. We present results to show that performance complementarity exists between different CHTs on the knapsack problem. Landscape analysis is then used to characterize the search space of a large number of knapsack instances, and decision tree induction is used to derive rules for selecting the most appropriate CHT and switching it adaptively based on landscape features. We finally implement a landscape-aware CHT approach and show that it out-performs the constituent CHT approaches.
- Hernán Aguirre and Kiyoshi Tanaka. 2007. Working principles, behavior, and performance of MOEAs on MNK-landscapes. European Journal of Operational Research 181, 3 (2007), 1670--1690.Google Scholar
Cross Ref
- BBOB. 2022. GECCO Workshop on Black-Box Optimization Benchmarking (BBOB 2022). https://numbbo.github.io/workshops/BBOB-2022/index.html.Google Scholar
- Andrea Bettinelli, Valentina Cacchiani, and Enrico Malaguti. 2017. A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph. INFORMS Journal on Computing 29, 3 (2017), 457--473.Google ScholarDigital Library
- Carlos A. Coello Coello. 1999. A Survey of Constraint Handling Techniques used with Evolutionary Algorithms. Technical Report. Laboratorio Nacional de Informática Avanzada.Google Scholar
- Kalyanmoy Deb. 2000. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering 186, 2 (2000), 311 -- 338.Google ScholarCross Ref
- Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.Google ScholarDigital Library
- Arnaud Fréville. 2004. The multidimensional 0--1 knapsack problem: An overview. European Journal of Operational Research 155, 1 (2004), 1--21.Google ScholarCross Ref
- Guanqiang Gao, Bin Xin, Yi Mei, Shengyu Lu, and Shuxin Ding. 2022. A multiobjective evolutionary algorithm with new reproduction and decomposition mechanisms for the multi-point dynamic aggregation problem. In Proceedings of the Genetic and Evolutionary Computation Conference. ACM.Google ScholarDigital Library
- Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. 2009. The WEKA Data Mining Software: An Update. SIGKDD Explor. Newsl. 11, 1 (2009), 10--18.Google ScholarDigital Library
- Felipe Honjo Ide, Hernan Aguirre, Minami Miyakawa, and Darrell Whitley. 2021. A Generator for Scalable SAT Constrained Multi-Objective Optimization Benchmark Problems. In 2021 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE.Google ScholarCross Ref
- Stuart A. Kauffman. 1993. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, USA.Google Scholar
- Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (March 2019), 3--45.Google ScholarDigital Library
- Katherine M. Malan. 2018. Landscape-Aware Constraint Handling Applied to Differential Evolution. In Theory and Practice of Natural Computing (Lecture Notes in Computer Science, Vol. 11324). Springer International Publishing, 176--187.Google ScholarDigital Library
- Katherine M. Malan and Andries P. Engelbrecht. 2013. A survey of techniques for characterising fitness landscapes and some possible ways forward. Information Sciences 241 (2013), 148--163.Google ScholarDigital Library
- Katherine M. Malan and I. Moser. 2019. Constraint Handling Guided by Landscape Analysis in Combinatorial and Continuous Search Spaces. Evolutionary Computation 27, 2 (2019), 267--289.Google ScholarDigital Library
- K. M. Malan, J. F. Oberholzer, and A. P. Engelbrecht. 2015. Characterising constrained continuous optimisation problems. In 2015 IEEE Congress on Evolutionary Computation (CEC). 1351--1358.Google Scholar
- R. Mallipeddi and P. N. Suganthan. 2010. Ensemble of Constraint Handling Techniques. IEEE Transactions on Evolutionary Computation 14, 4 (2010), 561--579.Google ScholarDigital Library
- Rammohan Mallipeddi and Ponnuthurai Nagaratnam Suganthan. 2010. Problem definitions and evaluation criteria for the CEC 2010 competition on constrained real-parameter optimization. Technical Report. Nanyang Technological University, Singapore.Google Scholar
- Silvano Martello, David Pisinger, and Paolo Toth. 1999. Dynamic Programming and Strong Bounds for the 0--1 Knapsack Problem. Management Science 45, 3 (1999), 414--424.Google ScholarDigital Library
- Efrén Mezura-Montes and Carlos A. Coello Coello. 2011. Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation 1, 4 (2011), 173--194.Google ScholarCross Ref
- Zbigniew Michalewicz. 1995. A Survey of Constraint Handling Techniques in Evolutionary Computation Methods. Evolutionary Programming 4 (1995), 135--155.Google Scholar
- Zbigniew Michalewicz and Jarosław Arabas. 1994. Genetic algorithms for the 0/1 knapsack problem. In Methodologies for Intelligent Systems, Zbigniew W. Raś and Maria Zemankova (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 134--143.Google Scholar
- J. Ross Quinlan. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Google ScholarDigital Library
- P.N. Suganthan. 2010. Comparison of Results on the 2010 CEC Benchmark Function Set. Technical Report. Nanyang Technological University, Singapore. http://www3.ntu.edu.sg/home/epnsugan/index_files/CEC10-Const/CEC2010_COMPARISON2.pdfGoogle Scholar
Index Terms
- Adaptive Landscape-aware Constraint Handling with Application to Binary Knapsack Problem
Recommendations
Landscape-Aware Constraint Handling Applied to Differential Evolution
Theory and Practice of Natural ComputingAbstractIn real-world contexts optimisation problems frequently have constraints. Evolutionary algorithms do not naturally handle constrained spaces, so require constraint handling techniques to modify the search process. Based on the thesis that ...
Hybrid differential evolution for knapsack problem
ICSI'10: Proceedings of the First international conference on Advances in Swarm Intelligence - Volume Part IA hybrid Differential Evolution algorithm with double population was proposed for 0-1 knapsack problem The two populations play different roles during the process of evolution with the floating-point population as an engine while the binary population ...
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints
AbstractEvolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. Recent results in the area of runtime analysis have pointed out that algorithms such as the (1 + 1) EA and Global SEMO can efficiently ...
Highlights- We design a benchmark for the knapsack problem with dynamically changing constraints.
Comments