如何将遗传编程算法训练到可变的描述符序列上？

Question

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

示例数据集:

ABCDE : 1

ABCDEF : 10

ABCDEGH : 3

ABCDELKA : 50

AASD : 3

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

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

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

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

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

Answer 1

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

你会需要:

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

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

.. Unigrams

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

.. Bigrams

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

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

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

• 使用双字母或三卦
• 更改评估方法(当前是查找表值的总和,它可以是产品或更复杂的东西)
• 尝试在染色体中使用真实值,而不仅仅是整数

Answer 2

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

在我看来,一些评估模型是在问题中预先假定的.

例如,考虑将可变长度输入编码为单个任意精度值,例如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

Bigrams,trigrams等是令人惊讶的好预测者:

• 捕获马尔可夫信息("ab"vs"ac")
• 捕获相对位置("ab"&&"bc"vs"ed"&&"bc")
• 捕获非线性语义("abab"!="ab"*2)
• 抵制改组输入("购买新垃圾邮件"vs"购买垃圾邮件是新的")

这些通常用于自然语言问题,例如文本主题检测,作者检测,垃圾邮件保护; 生物技术,如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