21

我目前正在尝试设计一种遗传编程算法来分析一系列字符为这些字符分配一个值。下面我做了一个示例集。每条线代表一个数据点。训练的值是实值。示例:对于单词ABCDE,算法应返回 1.0。

示例数据集:

ABCDE : 1

ABCDEF : 10

ABCDEGH : 3

ABCDELKA : 50

AASD : 3

数据集可以根据需要尽可能大,因为这一切都是虚构的。让我们假设 GP 应该弄清楚的规则并不太复杂,并且由数据解释。

我希望算法做的是在给定输入序列时从我的数据集中近似值。我现在的问题是每个序列可以包含不同数量的字符。如果可能的话,我宁愿不需要自己写一些花哨的描述符。

如何训练我的 GP(最好使用tinyGP或 python)来构建这个模型?

由于这里有很多讨论 - 一张图表说了一千个字: 原理图 我想做的只是放入一个数据点并将其放入一个函数中。然后我得到一个值,这是我的结果。不幸的是我不知道这个函数,我只有一个包含一些示例的数据集(也许 1000 个示例只是一个示例)。现在我使用遗传编程算法来找到能够将我的数据点转换为结果的算法。这是我的模型。在这种情况下,我遇到的问题是数据点的长度不同。对于设定的长度,我可以将字符串中的每个字符指定为输入参数。但是如果我有不同数量的输入参数,我该怎么办。

免责声明:我在学习期间多次遇到这个问题,但我们永远无法找到一个很好的解决方案(比如使用窗口、描述符等)。我想使用 GP,因为我喜欢这项技术并想尝试一下,但在 Uni 期间我们也尝试过使用 ANN 等,但无济于事。可变输入大小的问题仍然存在。

4

2 回答 2

9

由于您没有适应度函数,因此您需要将遗传算法视为分类器。因此,您需要想出一种方法来评估单个染色体。正如其他人所建议的那样,这是一个纯粹的分类问题,而不是优化问题,但是,如果您仍想继续使用 GA,您可以在这里尝试一些初始方法:

你会需要:

  1. 有效染色体的描述(如何编码)

要使用遗传算法,所有解决方案必须具有相同的长度(有更高级的可变长度编码方法,但我不会进入那里)。因此,有了它,您将需要找到一种最佳编码方法。知道您的输入是一个可变长度的字符串,您可以将您的染色体编码为您的字母表的查找表(python 中的字典)。但是,当您尝试应用交叉或变异操作时,字典会给您带来一些问题,因此最好将字母表和染色体编码分开。参考语言模型,您可以检查 n-gram,并且您的染色体将具有与字母表长度相同的长度:

..一元组

alphabet = "ABCDE"
chromosome1 = [1, 2, 3, 4, 5]
chromosome2 = [1, 1, 2, 1, 0]

..二元组

alphabet = ["AB", "AC", "AD", "AE", "BC", "BD", "BE", "CD", "CE", "DE"]
chromosome = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

..八卦

alphabet = ["ABC", "ABD", "ABE"...]
chromosome = as above, a value for each combination

2. 解码染色体以评估单个输入

您的染色体将代表字母表中每个元素的整数值。因此,如果您想知道具有染色体的输入(可变长度字符串)之一的值,您将需要尝试一些评估函数,最简单的一个是每个字母值的总和。

alphabet = "ABC"
chromosome = [1, 2, 1]
input = "ABBBC"

# acc = accumulated value
value = reduce(lambda acc, x: acc + chromosme[alphabet.index(x)], input, 0)
# Will return ABBBC = 1+2+2+2+1 = 8

3. 健身功能

您的适应度函数只是一个简单的误差函数。您可以使用简单的误差总和、平方误差... 单代的简单评估函数:

def fitnessFunction(inputs, results, alphabet, chromosome):
    error = 0

    for i in range(len(inputs)):
        value = reduce(lambda acc, x: acc + chromosome[alphabet.index(x)], inputs[i], 0) 
        diff = abs(results[i] - value)
        error += diff # or diff**2 if you want squared error

    return error

# A simple call -> INPUTS, EXPECTED RESULTS, ALPHABET, CURRENT CHROMOSOME
fitnessFunction(["ABC", "ABB", "ABBC"], [1,2,3], "ABC", [1, 1, 0])
# returned error will be:
# A+B+C = 1 + 1 + 0 -- expected value = 1 --> error += 1
# A+B+B = 1 + 1 + 1 -- expected value = 2 --> error += 1
# A+B+C = 1 + 1 + 1 + 0 -- expected value = 3 --> error += 0
# This chromosome has error of 2

现在,使用您想要的任何交叉和变异算子(例如:一点交叉和位翻转变异),找到最小化该错误的染色体。

您可以尝试改进算法模型的事情:

  • 使用二元组或三元组
  • 更改评估方法(目前是查找表值的总和,可以是产品或更复杂的东西)
  • 尝试在染色体中使用实数值,而不仅仅是整数
于 2013-05-20T19:27:03.100 回答
5

传统的遗传编程不适合可变长度输入。

在我看来,问题中预设了某种评估模型。

例如,考虑将可变长度输入编码为单个任意精度值,例如 10 个符号的字母表:

ABCD = 1234; ABCDEF = 123456

或者

ABCD = 0.1234; ABCDEF = 0.123456

然而,如果这种编码对于问题域来说不是自然的,那么开发一个能够很好地处理这种输入的程序将是相当困难的。

您还可以假设该问题可以由遗传衍生的有限状态机充分表示:

F(F(F(F(init(), A), B), C), D) = 1234

这是一个与基因编程不同的研究领域,谷歌周围,阅读研究论文,也许你可以找到一个包,为你做你想做的事。

然后你的问题可能最好用另一个变换来表示,例如二元组的频率——这种变换是有限长度的:

# bigrams
# ABCDE => 1
"AA": 0
"AB": 0.25
"AC": 0
"AD": 0
"AE": 0
"BA": 0
"BC": 0.25
"BD": 0
#... up to end of alphabet ...

(0, 0.25, 0, 0, 0, 0, 0.25, 0, ...., 0, ...) => 1      # ABCDE
(0, 0.20, 0, 0, 0, 0, 0.20, 0, ...., 0.20, ...) => 10  # ABCDEF
# input length N^2

# trigrams
(0, 0.33, 0, 0, ..., 0, ...) => 1      # ABCDE
(0, 0.25, 0, 0, ..., 0.25, ...) => 10  # ABCDEF
# input length N^3

二元组、三元组等是非常好的预测指标:

  • 捕获马尔可夫信息(“ab”与“ac”)
  • 捕获相对位置(“ab”&&“bc”与“ed”&&“bc”)
  • 捕获非线性语义 ("abab" != "ab" * 2)
  • 抗洗牌输入(“购买新垃圾邮件”与“购买垃圾邮件它是新的”)

这些常用于自然语言问题,例如文本主题检测、作者检测、垃圾邮件保护;生物技术,如 dna 和 rna 序列等。

但是,不能保证这种方法适用于您的问题。它确实取决于您的问题域,例如考虑10+算术域中的字母表,以下两个输入变得无法区分,但产生不同的结果:

10000+10000 = 20000
1000+100000 = 101000

在这种情况下,您需要注册机之类的东西:

init: tmp = 0; res = 0
"0": tmp *= 10
"1": tmp *= 10; tmp += 1
"+": res += tmp; tmp = 0
end: res += tmp
于 2013-05-19T13:29:14.937 回答