Robustness and Evolvability of Evolutionary Algorithms

进化算法的鲁棒性和可进化性

• 批准号: RGPIN-2016-04699
• 负责人: Hu, Ting
• 金额: $ 1.97万
• 依托单位: Queen's University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708396
• 关键词: Robustness; Evolvability; Evolutionary; Algorithms

Evolutionary algorithms draw inspiration from natural evolution. A population of diverse candidate solutions is generated and compared to a desired outcome. Then, through multiple generations of variation, selection, and reproduction, such a population adapts to the selection criteria, i.e. relative distance from the desired outcome, and produces fitter solutions. Evolutionary algorithms have seen enormous progress since they were founded in the 1970s. The knowledge of natural evolution has improved profoundly in biology in the past decades. This progress has, to a large degree, not yet been incorporated into computational models of evolution and, therefore, cannot be harvested for applications. My research program investigates new developments in biological evolution and incorporates them into designing more intelligent algorithms for more ambitious application problems. Some fundamental questions on biological evolution seem particularly interesting to me. Why are living organisms evolvable? Why isn't random variation always harmful, and how can it be the driving force for adaptive evolution? Natural evolutionary systems show tremendous resilience to genetic and environmental perturbations, as well as great capabilities in generating adaptive new phenotypes. Robustness and evolvability are fundamental properties of living systems, and investigating their relationship is key to understanding core mechanisms of evolution. These have been the focus of numerous theoretical and empirical studies in biology. However, they have not yet received adequate attention in evolutionary computing, and hold great potential in advancing our algorithm design. I propose to quantitatively characterize robustness and evolvability in evolutionary algorithms. Robustness is a result of the redundant genotype-to-phenotype mapping, where different genotypes can encode the same phenotype. That is, mutations can yield both a neutral and an observable phenotypic outcome. Investigating the relationship of robustness and evolvability can inspire the design of a new algorithm with a better representation scheme that enables both high tolerance to random variations and high adaptivity to explore novel phenotypes. This can improve the search efficiency of algorithms and advance the field of evolutionary computing profoundly. The new algorithm will then be applied to complex biomedical knowledge mining problems. Meanwhile, the findings of this research can help elucidate core mechanisms of evolution in biological systems. Evolutionary algorithms provide the possibility of studying natural evolution very differently from traditional biology. In computational evolution, up to millions of generations are allowed in a practical timeline, and the evolution process is fully controllable, tractable, and repeatable. These features go far beyond experimental studies in biology.

进化算法从自然进化中获得灵感。生成一组不同的候选解决方案，并将其与期望的结果进行比较。然后，通过多代的变异、选择和繁殖，这样的种群适应选择标准，即与期望结果的相对距离，并产生更合适的解决方案。 进化算法自20世纪70年代创立以来，取得了巨大的进步。在过去的几十年里，关于自然进化的知识在生物学上有了很大的提高。这一进展在很大程度上还没有被纳入进化的计算模型，因此不能用于应用。 我的研究计划调查生物进化的新发展，并将其纳入为更雄心勃勃的应用问题设计更智能的算法。 对我来说，关于生物进化的一些基本问题似乎特别有趣。为什么生物是可以进化的？为什么随机变异并不总是有害的，它如何成为适应性进化的驱动力？自然进化系统表现出对遗传和环境扰动的巨大韧性，以及产生适应性新表型的巨大能力。稳健性和可进化性是生命系统的基本属性，研究它们之间的关系是理解进化核心机制的关键。这些一直是生物学中众多理论和实证研究的焦点。然而，它们在进化计算中还没有得到足够的重视，在推进我们的算法设计方面具有很大的潜力。 我建议对进化算法的稳健性和可进化性进行定量表征。稳健性是多余的基因型到表型映射的结果，在这种映射中，不同的基因型可以编码相同的表型。也就是说，突变既可以产生中性的结果，也可以产生明显的表型结果。研究健壮性和可进化性的关系可以启发设计一种新的算法，该算法具有更好的表示方案，能够同时具有对随机变化的高耐受性和对探索新表型的高适应性。这可以提高算法的搜索效率，深刻推进进化计算领域的发展。然后，新算法将被应用于复杂的生物医学知识挖掘问题。 同时，这项研究的发现有助于阐明生物系统进化的核心机制。进化算法为研究自然进化提供了与传统生物学截然不同的可能性。在计算进化中，在一个实际的时间轴上允许多达数百万代，并且进化过程是完全可控的、可驯服的和可重复的。这些特征远远超出了生物学实验研究的范畴。