Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy
Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy
复制标题
DOI：
--
复制
发表时间：
1987-10
期刊：
影响因子：
--
通讯作者：
D. Goldberg;R. Smith
中科院分区：
文献类型：
--
作者：
D. Goldberg;R. Smith
具体地说，我们将包含二倍体基因和显性算子的遗传算法应用于函数优化中一个简单的非平稳问题：振荡盲背包问题。在这样做的过程中，我们发现二倍体和支配导致了一种长期分布式记忆的形式，这种记忆存储并偶尔记住曾经想要的好的部分解决方案。与没有增加的结构和运算符相比，这种存储器允许更快地适应剧烈的环境变化。研究了二倍体表示和优势算子在遗传算法中的应用，以提高在随时间变化的环境中的性能。简要讨论了自然遗传学中的二倍体和显性机制，并对这些结构和算子在其他遗传算法研究中的应用进行了综述。发展了模式定理的一个推广，它说明了具有显性的二倍体GA搁置替代等位基因的能力。单倍体和二倍体遗传算法都适用于一个简单的时变问题：一个振荡的盲背包问题。仿真结果表明，具有进化优势图的二倍体遗传算法比具有固定优势图的单倍体遗传算法和二倍体遗传算法能更快地适应问题环境的突变。这些原理证明结果表明，二倍体和显性可以用来在一群结构中诱导一种形式的长期分布式记忆。在本文的剩余部分，我们将探讨人工遗传搜索中显性和二倍体的机制、理论和实现。我们首先研究二倍体和显性在自然遗传学中的作用，并简要回顾它们在遗传算法领域的应用实例。我们推广了图式定理来分析这些结构和机制的影响。我们给出了一个17个目标，振荡，盲0-1背包问题的计算实验结果。使用自适应显性图和二倍体的模拟比具有固定显性图的单倍体遗传算法或二倍体遗传算法能够更快地适应环境的突然变化。这些结果是令人鼓舞的，并表明在搜索和机器学习中的其他遗传算法应用中的显性和二倍体的调查。
Specifically, we apply genetic algorithms that include diploid genotypes and dominance operators to a simple nonstationary problem in function optimization: an oscillating, blind knapsack problem. In doing this, we find that diploidy and dominance induce a form of long term distributed memory that stores and occasionally remembers good partial solutions that were once desirable. This memory permits faster adaptation to drastic environmental shifts than is possible without the added structures and operators. This paper investigates the use of diploid representations and dominance operators in genetic algorithms (GAs) to improve performance in environments that vary with time. The mechanics of diploidy and dominance in natural genetics are briefly discussed, and the usage of these structures and operators in other GA investigations is reviewed. An extension of the schema theorem is developed which illustrates the ability of diploid GAs with dominance to hold alternative alleles in abeyance. Both haploid and diploid GAs are applied to a simple time varying problem: an oscillating, blind knapsack problem. Simulation results show that a diploid GA with an evolving dominance map adapts more quickly to the sudden changes in this problem environment than either a haploid GA or a diploid GA with a fixed dominance map. These proof-of-principle results indicate that diploidy and dominance can be used to induce a form of long term distributed memory within a population of structures. In the remainder of this paper, we explore the mechanism, theory, and implementation of dominance and diploidy in artificial genetic search. We start by examining the role of diploidy and dominance in natural genetics, and we briefly review examples of their usage in genetic algorithm circles. We extend the schema theorem to analyze the effect of these structures and mechanisms. We present results from computational experiments on a 17-object, oscillating, blind 0-1 knapsack problem. Simulations with adaptive dominance maps and diploidy are able to adapt more quickly to sudden environmental shifts than either a haploid genetic algorithm or a diploid genetic algorithm with fixed dominance map. These results are encouraging and suggest the investigation of dominance and diploidy in other GA applications in search and machine learning.