4

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

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

Q1：在遗传算法中，给定两个父母 A 和 B 的染色体分别为 001110 和 101101，以下哪个后代可能是由单点交叉产生的？

一个：001101

乙：001110

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

请指教。

4

3 回答 3

7

如果您不知道逆交叉函数（因此 AxB => (a,b) & (any a) => (A,B)），则无法找到父代。

通常1点交叉函数为：

a = A1 + B2
b = B1 + A2

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

如果您知道任何 A 或/和 B 的任何 2 个部分，那么它可以被求解（具有 2 个变量的 2 个方程的系统）。当您提供 A 和 B 时，您的问题就是这种情况。

通常交叉函数没有反函数，你只需要在逻辑上找到解决方案，或者如果你知道父母，执行交叉和比较。

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

  1. 交叉功能。
  2. 逆交叉函数。

第二个通常不用于 GA，因为它不是必需的。

现在，我只回答你的问题。

Q1：在遗传算法中，给定两个父母 A 和 B 的染色体分别为 001110 和 101101，以下哪个后代可能是由单点交叉产生的？

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

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

通常使用这个公式完成交叉：

a = A1 + B2
b = B1 + A2

所以可能的孩子是：

a: 00 | 1101
b: 10 | 1110

从问题中排除选项 b。
所以 Q1 的答案是结果 child is a: 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）进行比较，我们可以说出答案：

Q2。A： 根据给定的交叉函数， a或b都不是与AxB的 2 点交叉的结果。

同样，如果不知道交叉功能，就不可能回答您的问题。

我提供的功能在 GA 中很常见，但您可以发明很多功能，以便他们回答问题（请参阅下面的评论）：

于 2009-12-09T00:51:36.037 回答
2

一点交叉是当您从每个父级进行一次连接时，两点交叉是当您进行两次连接时。即两个来自一个父母，一个来自其他人。

有关更多信息，请参阅交叉（维基百科）。

于 2009-12-09T00:25:07.313 回答
2

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

关于 Q2，(a) 和 (b) 都是可能的。有几个组合需要测试；写起来太乏味了，但是你可以用笔和纸来做。:-)

于 2009-12-09T00:26:20.270 回答