Epistasis in Genetic Algorithms: An Experimental Design Perspective
Epistasis in Genetic Algorithms: An Experimental Design Perspective
复制标题
DOI：
--
复制
发表时间：
1995-07
期刊：
影响因子：
--
通讯作者：
C. Reeves;C. C. Wright-C.
中科院分区：
文献类型：
--
作者：
C. Reeves;C. C. Wright-C.
在之前的一篇论文中，我们研究了遗传算法（GA）和传统实验设计方法之间的关系。这是由于对遗传算法在优化问题的实施和应用中上位性引起的问题的调查而产生的。我们展示了这种观点如何使我们能够进一步深入了解上位效应的确定，以及针对 GA 解决方案编码问题的不同形式的价值。我们还证明了这种方法与沃尔什变换分析的等价性。在本文中，我们进一步考虑上位度量是否实际上能够很好地预测 GA 解决给定问题的难易程度。与其他相关文献一样，我们最初的分析假设了解完整的解决方案空间。在实践中，我们只对所有可能的解决方案中的一小部分进行了采样，这提出了一些重要的问题，这些问题也是本文第二部分的主题。为了分析这些问题，我们引入了别名集的概念，并通过讨论对 GA 如何工作的传统理解的一些影响来结束。
In an earlier paper we examined the relationship between genetic algorithms (GAs) and traditional methods of experimental design. This was motivated by an investigation into the problems caused by epistasis in the implementation and application of GAs to optimization problems. We showed how this viewpoint enables us to gain further insights into the determination of epistatic effects , and into the value of diierent forms of encoding a problem for a GA solution. We also demonstrated the equivalence of this approach toWalsh transform analysis. In this paper we consider further the question of whether the epistasis metric actually gives a good prediction of the ease or dii-culty of solution of a given problem by a GA. Our original analysis assumed, as does the rest of the related literature, knowledge of the complete solution space. In practice, we only ever sample a fraction of all possible solutions , and this raises signiicant questions which are the subject of the second part of this paper. In order to analyse these questions , we introduce the concept of alias sets, and conclude by discussing some implications for the traditional understanding of how GAs work.