Evolutionary computation

From WFM Labs


Evolutionary computation is a family of population-based optimization and search algorithms whose design is inspired by the mechanisms of biological evolution, in particular natural selection, reproduction with variation, and survival of the fittest.[1] An evolutionary algorithm maintains a population of candidate solutions, evaluates each candidate with a problem-specific fitness function, and iteratively applies operators analogous to selection, recombination, and mutation so that the distribution of solutions is progressively biased toward regions of higher fitness.[1][2] Because these methods make few assumptions about the objective function—requiring neither differentiability nor convexity—they are classified as stochastic, derivative-free Metaheuristics and are widely used on problems for which exact or gradient-based methods are impractical.[3][2]

The principal historical strands of the field are the Genetic algorithm, the evolution strategy, evolutionary programming, and genetic programming; more recent developments include estimation-of-distribution algorithms and, within it, quality-diversity methods such as Novelty search, Quality-diversity optimization, and MAP-Elites.[1][2]

Common framework

Although individual paradigms differ in representation and operator design, most evolutionary algorithms share a common generational loop.[1] An initial population is generated, typically at random; each individual is assigned a fitness value; a selection step chooses parents with a probability that increases with fitness; variation operators (recombination, which combines material from two or more parents, and mutation, which introduces small random changes) produce offspring; and a replacement step forms the next generation from parents and offspring. The cycle repeats until a termination criterion—such as a fitness threshold or a fixed budget of evaluations—is met.[1][3]

Key design choices are the representation (the encoding of candidate solutions, for example binary strings, real-valued vectors, permutations, or program trees), the fitness function, and the balance between exploration of new regions and exploitation of known good regions of the search space.[1][2]

Major paradigms

Genetic algorithms

The genetic algorithm, introduced by John Holland and popularized by David Goldberg, traditionally encodes solutions as fixed-length binary strings and relies on crossover as its primary search operator, with mutation playing a secondary role.[4][3] Holland's schema theorem offered an early theoretical account of why short, low-order, above-average building blocks are propagated across generations.[4][3]

Evolution strategies

Evolution strategies, developed by Ingo Rechenberg and Hans-Paul Schwefel, operate on real-valued vectors and emphasize mutation, often self-adapting the mutation step sizes as part of the search; they are commonly denoted using the (μ/ρ,λ) and (μ/ρ+λ) notation that describes how parents and offspring are combined.[5][2] Modern variants such as the covariance-matrix adaptation evolution strategy are prominent for continuous black-box optimization.[1]

Genetic programming

Genetic programming, developed by John Koza, evolves computer programs—usually represented as syntax trees—so that the structure and size of a solution are themselves subject to evolution rather than fixed in advance.[6] It has been applied to symbolic regression, classifier induction, and automatic design tasks.[6]

Estimation-of-distribution algorithms

Estimation-of-distribution algorithms replace explicit recombination and mutation with an explicit probabilistic model: at each generation a statistical model is learned from the fittest individuals and new candidates are sampled from that model, allowing the algorithm to capture and exploit dependencies among decision variables.[7][1]

Theoretical considerations

Evolutionary algorithms are anytime, global search heuristics that provide no general guarantee of locating a global optimum in finite time; their behavior is analyzed through convergence theory, runtime analysis, and models of population dynamics.[1][2] The no free lunch theorems formalize a fundamental limit: averaged over all possible objective functions, no optimization algorithm outperforms any other, so the effectiveness of an evolutionary method depends on how well its operators and representation match the structure of the target problem.[8] This motivates careful problem-specific design of encodings, fitness functions, and variation operators.[1]

Applications in workforce management

Staff scheduling and rostering problems—assigning employees to shifts subject to coverage requirements, skills, labor rules, and fairness constraints—are typically NP-hard combinatorial problems for which metaheuristics, including evolutionary algorithms, are a well-established solution approach.[9] Reviews of the personnel-scheduling literature document the use of genetic algorithms and related evolutionary methods alongside integer programming, constraint programming, and other metaheuristics such as Simulated annealing and tabu search.[9] In a contact center context, the general workflow is illustrative: a candidate roster is encoded (for example as an assignment of agents to shift patterns), a fitness function penalizes under- and over-staffing relative to interval-level requirements together with rule violations, and evolutionary operators recombine and perturb rosters to search for schedules that reduce cost while meeting service-level targets.[9][1] Such formulations connect evolutionary computation to the broader operations-research treatment of scheduling under uncertainty and disruption.[9]

See also

References

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 Eiben, A. E., Smith, J. E. (2015). Introduction to Evolutionary Computing (2nd ed.). Natural Computing Series. Springer. ISBN 978-3-662-44873-1. doi:10.1007/978-3-662-44874-8.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 Bäck, T., Fogel, D. B., Michalewicz, Z. (eds.) (1997). Handbook of Evolutionary Computation. Institute of Physics Publishing and Oxford University Press. ISBN 978-0-7503-0392-7.
  3. ↑ 3.0 3.1 3.2 3.3 Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley. ISBN 978-0-201-15767-3.
  4. ↑ 4.0 4.1 Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 978-0-472-08460-9. (Reprinted MIT Press, 1992.)
  5. ↑ Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog. ISBN 978-3-7728-0373-4.
  6. ↑ 6.0 6.1 Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Complex Adaptive Systems. MIT Press. ISBN 978-0-262-11170-6.
  7. ↑ Larrañaga, P., Lozano, J. A. (eds.) (2002). Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Genetic Algorithms and Evolutionary Computation, vol. 2. Kluwer Academic Publishers. ISBN 978-0-7923-7466-4.
  8. ↑ Wolpert, D. H., Macready, W. G. (1997). "No Free Lunch Theorems for Optimization". IEEE Transactions on Evolutionary Computation 1 (1), 67–82. doi:10.1109/4235.585893.
  9. ↑ 9.0 9.1 9.2 9.3 Ernst, A. T., Jiang, H., Krishnamoorthy, M., Sier, D. (2004). "Staff scheduling and rostering: A review of applications, methods and models". European Journal of Operational Research 153 (1), 3–27. doi:10.1016/S0377-2217(03)00095-X.
Retrieved from "https://wiki.wfmlabs.org/w/index.php?title=Evolutionary_computation&oldid=3592"