Mayer H A
Department of Computer Science, University of Salzburg, Austria.
Evol Comput. 1998 Winter;6(4):361-86.
In this article we present work on chromosome structures for genetic algorithms (GAs) based on biological principles. Mainly, the influence of noncoding segments on GA behavior and performance is investigated. We compare representations with noncoding sequences at predefined, fixed locations with "junk" code induced by the use of promoter/terminator sequences (ptGAs) that define start and end of a coding sequence, respectively. As one of the advantages of noncoding segments a few researchers have identified the reduction of the disruptive effects of crossover, and we solidify this argument by a formal analysis of crossover disruption probabilities for noncoding segments at fixed locations. The additional use of promoter/terminator sequences not only enables evolution of parameter values, but also allows for adaptation of number, size, and location of genes (problem parameters) on an artificial chromosome. Randomly generated chromosomes of fixed length carry different numbers of promoter/terminator sequences resulting in genes of varying size and location. Evolution of these ptGA chromosomes drives the number of parameters and their values to (sub)optimal solutions. Moreover, the formation of tightly linked building blocks is enhanced by self-organization of gene locations. We also introduce a new, nondisruptive crossover operator emerging from the ptGA gene structure with adaptive crossover rate, location, and number of crossover sites. For experimental comparisons of this genetic operator to conventional crossover in GAs, as well as properties of different ptGA chromosome structures, an artificial problem from the literature is utilized. Finally, the potential of ptGA is demonstrated on an NP-complete combinatorial optimization problem.
在本文中，我们展示了基于生物学原理的遗传算法（GA）染色体结构方面的工作。主要研究了非编码片段对遗传算法行为和性能的影响。我们将在预定义的固定位置具有非编码序列的表示与通过使用分别定义编码序列起始和结束的启动子/终止子序列（ptGA）诱导的“垃圾”代码进行比较。作为非编码片段的优势之一，一些研究人员已经确定其减少了交叉的破坏作用，并且我们通过对固定位置非编码片段的交叉破坏概率进行形式化分析来巩固这一论点。启动子/终止子序列的额外使用不仅能够实现参数值的进化，还允许人工染色体上基因（问题参数）的数量、大小和位置进行自适应调整。固定长度的随机生成染色体携带不同数量的启动子/终止子序列，从而产生大小和位置各异的基因。这些ptGA染色体的进化将参数数量及其值驱动至（次）最优解。此外，基因位置的自组织增强了紧密连锁积木块的形成。我们还引入了一种新的、无破坏作用的交叉算子，它源自ptGA基因结构，具有自适应交叉率、交叉位点的位置和数量。为了将这种遗传算子与遗传算法中的传统交叉进行实验比较，以及研究不同ptGA染色体结构的特性，我们利用了文献中的一个人工问题。最后，在一个NP完全组合优化问题上展示了ptGA的潜力。
