为什么每个解决方案(或基因型)多于一条染色体？

Question

我正在尝试开始使用Jenetics JAVA库进行遗传算法,而且我的GA有限背景中有一些我不理解的东西;

据我所知,GA生成了一组m元素阵列,其中每个数组都是一个可以评估的潜在解决方案,一旦评估,潜在的解决方案就会被排序,最好的选择是为了创建一个新的人口,等等.但我发现Jenetics中的解决方案(基因型)是一个数组列表,其中每个数组都是我理解的潜在解决方案,每个数组也可以有不同的长度,我不明白为什么要使用这个结构而不是基因载体.

参见手册第6页,第3.1.3节.

如果可能的话我想知道为什么会这样.我希望这个问题足够明确.

Answer 1

您所描述的是基本遗传算法中的种群。有很多技术可以改进它，其中之一就是自适应编码。

您正在寻找的术语是自适应编码技术下的（修改的）基因库重组。

基因库重组对整个种群而不是单个单位进行操作并进化种群。它可能会也可能不会保持相同的结构。

从生物学角度来看这个想法：

• 在自然界中，首先存在更简单的生物体，然后它们进化成更复杂的生物体。

同样的动机也可以用于遗传算法。首先，有一些更简单的单元可以随着时间的推移而演变——换句话说，解的长度和结构不必是恒定的。

没有简单的方法可以对遗传算法的信息进行通用编码，因此您必须针对手头的每个问题都考虑它。您可能需要也可能不需要基因库重组、基本二进制编码或基本比例选择。这些选项很大程度上取决于您要解决的问题，以及可接受的算法所花费的解决方案精度/时间。

表示基因向量的基本二进制编码很简单，但 GA 的缺点是在寻找最近邻居方面效率低下。

考虑以下示例：

• 有解 15 和 16 (01111, 10000)

• 这两个数字之间的汉明距离是 5

为了将 GA 从 15 更改为 16，所有 5 位都应更改。因此，遗传算法在处理邻近离散数方面存在问题。改善此问题的一种方法是使用格雷码，它可以让所有解决方案之间的距离为 1。