Misplaced Pages

Genotypic and phenotypic repair

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

This is an old revision of this page, as edited by Studi90 (talk | contribs) at 15:26, 28 December 2024 (A new article on geno- and phenotypic repair in the context of evolutionary algorithms for dealing with constraints.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 15:26, 28 December 2024 by Studi90 (talk | contribs) (A new article on geno- and phenotypic repair in the context of evolutionary algorithms for dealing with constraints.)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff) Genetic and phenotypic repair in evolutionary algorithms as a method for dealing with constrains
Part of a series on the
Evolutionary algorithm
Genetic algorithm (GA)
Genetic programming (GP)
Differential evolution
Evolution strategy
Evolutionary programming
Related topics

Genotypic and phenotypic repair are optional parts of an evolutionary algorithm that repairs or compensates for errors in the genome of an offspring caused by crossover and/or mutation. Genotypic repair, also known as genetic repair, is the removal or correction of impermissible entries in the chromosome that violate restrictions. In phenotypic repair, the corrections are only made in the genotype-phenotype mapping and the chromosome remains unchanged. Michalewicz wrote about the importance of restrictions in real-world applications: "In general, constraints are an integral part of the formulation of any problem".

Restriction violations are application-specific and therefore it depends on the current problem whether and which type of repair is useful. It should be noted that restriction violations can usually also be treated by a correspondingly extended evaluation and it depends on the problem which measures are possible and which is the most suitable. If a phenotypic repair is feasible, then it is usually the most efficient compared to the other measures. A survey on repair methods used as constraint handling techniques can be found in .

Violations of the range limits of genes should be avoided as far as possible by the formulation of the genome. If this is not possible or if restrictions within the search space defined by the genome are involved, their violations are usually handled by the evaluation. This can be done, for example, by penalty functions that lower the fitness.

Repair is often also required for combinatorial tasks. The application of a 1- or n-point crossover operator can, for example, lead to genes being missing in one of the child genomes that are present in duplicate in the other. In this case, a suitable genotypic repair measure is to move the surplus genes to the other genome in a positional manner. The use of the aforementioned operators in combinatorial tasks has also proven to be useful in combination with crossover types specially developed for permutations, at least for certain problems.

Particularly in combinatorial problems, it has been observed that genotypic repair can promote premature convergence to a suboptimum, but can also significantly accelerate a successful search. Studies on various tasks have shown that this is application-dependent. An effective measure to avoid premature convergence is generally the use of structured populations instead of the usual panmictic ones.

Sequence restrictions play a role in many scheduling tasks, for example when it comes to planning workflows. If, for example, it is specified that step A must be carried out before step B and the gene of step B is located before the gene of A in the chromosome, then there is an impermissible gene sequence. This is because the scheduling operation of step B requires the planned end of step A for correct scheduling, but this is not yet scheduled at the time gene B is processed. The problem can be solved in two ways:

  1. The scheduling operation of step B is postponed until the gene from step A has been processed. The genome remains unchanged and the repair only influences the genotype-phenotype mapping. Since only the phenotype is changed, this is referred to as phenotypic repair.
  2. If, on the other hand, the gene of step B is moved behind the gene of step A, this is a genotypic repair. The same applies to the alternative shift of gene A in front of gene B.

In this case, genotypic repair has the disadvantage that it prevents a meaningful restructuring of the gene sequence in the chromosome if this requires several intermediate steps (mutations) that at least partially violate restrictions.

References

  1. ^ Eiben, A.E.; Smith, J.E. (2015). "Approaches to Handling Constraints". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 204–211. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  2. ^ Michalewicz, Zbigniew (2000-11-20). "Introduction to Constraint-handling Techniques". In Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew (eds.). Evolutionary Computation 2: Advanced Algorithms and Operators. Taylor & Francis. pp. 38–40. doi:10.1201/9781420034349. ISBN 978-0-7503-0665-2.
  3. Michalewicz, Zbigniew (2000-11-20). "Part 2: Constraint-handling Techniques". In Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew (eds.). Evolutionary Computation 2: Advanced Algorithms and Operators. Taylor & Francis. pp. 38–86. doi:10.1201/9781420034349. ISBN 978-0-7503-0665-2.
  4. ^ Eiben, A.E.; Smith, J.E. (2015). "Penalty Functions". Introduction to Evolutionary Computing. Natural Computing Series (2nd ed.). Berlin, Heidelberg: Springer. pp. 206–208. doi:10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1.
  5. ^ Smith, Alice E.; Coit, David W. (2000-11-20). "Penalty Functions". In Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew (eds.). Evolutionary Computation 2: Advanced Algorithms and Operators. Taylor & Francis. pp. 41–48. doi:10.1201/9781420034349. ISBN 978-0-7503-0665-2.
  6. ^ Salcedo-Sanz, Sancho (2009). "A survey of repair methods used as constraint handling techniques in evolutionary algorithms". Computer Science Review. 3 (3): 175–192. doi:10.1016/j.cosrev.2009.07.001.
  7. Michalewicz, Zbigniew; Schoenauer, Marc (1996). "Evolutionary Algorithms for Constrained Parameter Optimization Problems". Evolutionary Computation. 4 (1): 1–32. doi:10.1162/evco.1996.4.1.1. ISSN 1063-6560.
  8. Kramer, Oliver (2010). "A Review of Constraint-Handling Techniques for Evolution Strategies". Applied Computational Intelligence and Soft Computing. 2010: 1–11. doi:10.1155/2010/185063. ISSN 1687-9724.
  9. Jakob, Wilfried (2021), Applying Evolutionary Algorithms Successfully: A Guide Gained from Real-world Applications, KIT Scientific Working Papers, Nr. 170, Karlsruhe, FRG: KIT Scientific Publishing, arXiv:2107.11300, doi:10.5445/ir/1000135763
  10. Yu, Xinjie; Gen, Mitsuo (2010). "Penalty Function". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 143–150. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
  11. ^ Michalewicz, Zbigniew (2000-11-20). "Repair Algorithms". In Bäck, Thomas; Fogel, David; Michalewicz, Zbigniew (eds.). Evolutionary Computation 2: Advanced Algorithms and Operators. Taylor & Francis. pp. 56–61. doi:10.1201/9781420034349. ISBN 978-0-7503-0665-2.
  12. ^ Jakob, Wilfried; Quinte, Alexander; Stucky, Karl-Uwe; Süß, Wolfgang (2008), Rudolph, Günter; Jansen, Thomas; Beume, Nicola; Lucas, Simon (eds.), "Fast Multi-objective Scheduling of Jobs to Constrained Resources Using a Hybrid Evolutionary Algorithm", Parallel Problem Solving from Nature – PPSN X, LNCS, vol. 5199, Berlin, Heidelberg: Springer, pp. 1031–1040, doi:10.1007/978-3-540-87700-4_102, ISBN 978-3-540-87699-1
  13. Yu, Xinjie; Gen, Mitsuo (2010). "Evolutionary Algorithms for Combinatorial Optimization". Introduction to Evolutionary Algorithms. Decision Engineering. London: Springer. pp. 267–269. doi:10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
  14. Coello Coello, Carlos A. (1999). A Survey of Constraint Handling Techniques Used with Evolutionary Algorithms (PDF). Veracruz, México: Laboratorio Nacional de Informática Avanzada.
  15. Gorges-Schleuter, Martina (1998), Eiben, Agoston E.; Bäck, Thomas; Schoenauer, Marc; Schwefel, Hans-Paul (eds.), "A comparative study of global and local selection in evolution strategies", Parallel Problem Solving from Nature — PPSN V, vol. 1498, Berlin, Heidelberg: Springer, pp. 367–377, doi:10.1007/bfb0056879, ISBN 978-3-540-65078-2
  16. Cantú-Paz, Erick (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
  17. Alba, Enrique; Dorronsoro, Bernabé (2008). Cellular genetic algorithms. Operations research/computer science interfaces series (ORCS 42). New York: Springer. ISBN 978-0-387-77610-1.
  18. ^ Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). "Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing". Algorithms. 6 (2): 245–277. doi:10.3390/a6020245. ISSN 1999-4893.