由于您没有适应度函数,因此您需要将遗传算法视为分类器。因此,您需要想出一种方法来评估单个染色体。正如其他人所建议的那样,这是一个纯粹的分类问题,而不是优化问题,但是,如果您仍想继续使用 GA,您可以在这里尝试一些初始方法:
你会需要:
有效染色体的描述(如何编码)
要使用遗传算法,所有解决方案必须具有相同的长度(有更高级的可变长度编码方法,但我不会进入那里)。因此,有了它,您将需要找到一种最佳编码方法。知道您的输入是一个可变长度的字符串,您可以将您的染色体编码为您的字母表的查找表(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
现在,使用您想要的任何交叉和变异算子(例如:一点交叉和位翻转变异),找到最小化该错误的染色体。
您可以尝试改进算法模型的事情:
- 使用二元组或三元组
- 更改评估方法(目前是查找表值的总和,可以是产品或更复杂的东西)
- 尝试在染色体中使用实数值,而不仅仅是整数