On a Feasible–Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch
Open accessThe DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Abstract
We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No free lunch theorems for optimization
Wolpert, D. H., & Macready, W. G. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585893 · Cited by 14,237 · cited 6×
“Wolpert and Macready (1995, 1997) proved the following No Free Lunch theorem.”
BackgroundResultInfluential
Cited by
Search-Based Procedural Content Generation: A Taxonomy and Survey
Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011) · IEEE Transactions on Computational Intelligence and AI in Games · doi:10.1109/tciaig.2011.2148116 · Cited by 706
No Free Lunch Theorem: A Review
Adam, S. P., Alexandropoulos, S.-A. N., Pardalos, P. M., & Vrahatis, M. N. (2019) · Springer Optimization and Its Applications · doi:10.1007/978-3-030-12767-1_5 · Cited by 401
Mixed-initiative content creation
Liapis, A., Smith, G., & Shaker, N. (2016) · Computational Synthesis and Creative Systems · doi:10.1007/978-3-319-42716-4_11 · Cited by 71
Procedural Personas as Critics for Dungeon Generation
Liapis, A., Holmgård, C., Yannakakis, G. N., & Togelius, J. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-16549-3_27 · Cited by 50
(2013) · doi:10.1109/cig.2014.6932873 · Cited by 33
Metadata
- Authors
- Kimbrough, S. O., Koehler, G. J., Lu, M., & Wood, D. H.
- Venue
- European Journal of Operational Research
- Publisher
- Elsevier BV
- Published
- 2008-10
- Volume
- 190
- Issue
- 2
- Pages
- 310-327
- ISSN
- 0377-2217 (ISSN-L)
- OpenAlex
- W2001466640
- Cited by
- 145
- References
- 1
- FWCI
- 4.73
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.