Maesani Andrea, Fernando Pradeep Ruben, Floreano Dario
Laboratory of Intelligent Systems (LIS), Ecole Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland.
PLoS One. 2014 Jan 29;9(1):e86831. doi: 10.1371/journal.pone.0086831. eCollection 2014.
Evolutionary algorithms are widespread heuristic methods inspired by natural evolution to solve difficult problems for which analytical approaches are not suitable. In many domains experimenters are not only interested in discovering optimal solutions, but also in finding the largest number of different solutions satisfying minimal requirements. However, the formulation of an effective performance measure describing these requirements, also known as fitness function, represents a major challenge. The difficulty of combining and weighting multiple problem objectives and constraints of possibly varying nature and scale into a single fitness function often leads to unsatisfactory solutions. Furthermore, selective reproduction of the fittest solutions, which is inspired by competition-based selection in nature, leads to loss of diversity within the evolving population and premature convergence of the algorithm, hindering the discovery of many different solutions. Here we present an alternative abstraction of artificial evolution, which does not require the formulation of a composite fitness function. Inspired from viability theory in dynamical systems, natural evolution and ethology, the proposed method puts emphasis on the elimination of individuals that do not meet a set of changing criteria, which are defined on the problem objectives and constraints. Experimental results show that the proposed method maintains higher diversity in the evolving population and generates more unique solutions when compared to classical competition-based evolutionary algorithms. Our findings suggest that incorporating viability principles into evolutionary algorithms can significantly improve the applicability and effectiveness of evolutionary methods to numerous complex problems of science and engineering, ranging from protein structure prediction to aircraft wing design.
进化算法是受自然进化启发而广泛应用的启发式方法，用于解决分析方法不适用的难题。在许多领域，实验者不仅对发现最优解感兴趣，还对找到满足最低要求的大量不同解感兴趣。然而，制定一个描述这些要求的有效性能度量（也称为适应度函数）是一项重大挑战。将多个性质和规模可能不同的问题目标和约束组合并加权到一个单一的适应度函数中存在困难，这常常导致不尽人意的解决方案。此外，受自然界基于竞争的选择启发，对最适应解的选择性繁殖会导致进化种群内多样性的丧失以及算法的过早收敛，从而阻碍许多不同解的发现。在此，我们提出一种人工进化的替代抽象方法，它不需要制定复合适应度函数。该方法受动力系统中的生存能力理论、自然进化和动物行为学启发，强调淘汰那些不符合一组根据问题目标和约束定义的不断变化标准的个体。实验结果表明，与传统的基于竞争的进化算法相比，该方法在进化种群中保持了更高的多样性，并生成了更多独特的解。我们的研究结果表明，将生存能力原则纳入进化算法可以显著提高进化方法对众多科学和工程复杂问题的适用性和有效性，从蛋白质结构预测到飞机机翼设计等问题均适用。
