遗传算法理论问题

Question

我目前正在阅读《人工智能：一种现代方法》（Russell+Norvig）和《机器学习》（Mitchell），并尝试学习AINN的基础知识。

为了理解一些基本概念，我有两个“新手”问题：

问题1：在遗传算法中，给定染色体001110和101101的两个父母A和B，以下哪个后代可能是单点交叉的结果？

a: 001101

b: 001110

问题2：上述哪个后代可能是双点交叉的结果？为什么？

请给予建议。

- mandelart

---

重要的是要理解一点交叉和两点交叉并不是什么神奇不同的算法，只是用不同的方式交换信息，并具有不同程度的协调性。许多遗传算法甚至不会使用像这样的位流，因此重要的是深入挖掘正在传输的信息以及原因，而不是陷入实现细节中。 - Kylotan

Answer 1

如果你不知道逆交叉函数（AxB => (a,b) &(任何a) => (A,B)），那么就无法找到父母。

通常的单点交叉函数为:

a = A1 + B2
b = B1 + A2

即使您知道a和b，也无法解决系统（具有4个变量的2个方程组）。

如果您知道A或/和B的任何2个部分，则可以解决它（具有2个变量的2个方程组）。对于您的问题，情况就是这样，因为您提供了A和B。

通常交叉函数没有反函数，您只需要逻辑地找到解决方案，或者如果您知道父母，请执行交叉并进行比较。

因此，为您制作通用公式，我们应该知道两件事：

1.交叉功能。

2.反交叉功能。

通常不使用第二个功能，因为GAs不需要它。

现在，我将回答您的问题。

Q1：在遗传算法中，给定带有染色体001110和101101的两个父母A和B，以下哪种后代可能是由单点交叉导致的？

查看a和b，我可以看到交叉点在这里：

    1    2
A: 00 | 1110
B: 10 | 1101

通常使用这个公式来进行交叉处理：

a = A1 + B2
b = B1 + A2

因此可能的子项是：

a: 00 | 1101
b: 10 | 1110

这里需要排除选项b。
所以Q1的答案是：根据给定的交叉函数，结果为001101。

Q2：哪些后代可能是由两点交叉产生的？为什么？

从a和b中可以看出，交叉点可能在这里：

    1   2    3
A: 00 | 11 | 10
B: 10 | 11 | 01

常规的2点交叉公式为：

a = A1 + B2 + A3
b = B1 + A2 + B3

那么孩子们就会是：

a = 00 | 11 | 10
b = 10 | 11 | 01

与您提出的选项（小写字母a和b）相比，我们可以得出答案：

问题2. A: 根据给定的交叉函数，不能通过2点交叉获得AxB的a或b。

再次强调，在不知道交叉函数的情况下无法回答您的问题。

我提供的函数在GA中很常见，但是您可以发明许多其他函数来回答这个问题（请参见下面的评论）。

- Dmytrii Nagirniak

---

哎呀，难道不能由A1 + B2 + A3生成吗？00 11 10 - Jean Azzopardi

在我提供的定义中，它是做不到的。我在答案中明确说明了这一点，并加粗了它。你定义了一个新函数可以做到这一点。 - Dmytrii Nagirniak

Answer 2

一点交叉是指从每个父代中各选一个位置进行交叉，而两点交叉则是选择两个位置进行交叉，即一个来自一个父代，一个来自另一个父代。

详见交叉（维基百科）。

- Dan Midwood

Answer 3

关于Q1，(a)可能是通过单点交叉产生的，从父本A中取位0-4和父本B中的位5。(b)除非你的交叉算法允许空贡献，即父本的贡献为零。在这种情况下，父本A可以贡献其完整染色体（位0-5），而父本B将不产生贡献，得到(b)。

关于Q2，(a)和(b)都是可能的。有几个组合需要测试;太繁琐了，但你可以用纸笔完成工作。 :-)

- CesarGon