Python 遗传算法入门 - Hello World!
4.47/5 (18投票s)
使用 Python 逐步实践遗传算法的机器学习入门。
你好世界！
猜我的数字
我们先来简单了解一下遗传算法。回想一下我们小时候玩过的一个游戏。这是一个简单的两人游戏，一个人选择一个 1 到 10 之间的秘密数字，另一个人必须猜出这个数字。
Is it 2? No Is it 3? No Is it 7? No Is it 1? Yes
对于 1..10 来说，这还算合理，但当我们把范围扩大到 1..100 或 1..1000 时，很快就会变得令人沮丧或无聊。为什么？因为我们无法改进我们的猜测。没有挑战。猜测要么正确要么错误，所以很快就变成了一个机械过程。
Is it 1? No Is it 2? No Is it 3? No Is it 4? No Is it 5? No ...
所以，为了让它更有趣，我们不说“不”，而是说“更高”或“更低”。
1? Higher 7? Lower 6? Lower 5? Lower 4? Correct
对于 1..10 来说，这可能在一段时间内还算有趣，但很快你就会把范围扩大到 1..100。因为人们有竞争性，下一个修改是看谁是更好的猜测者，通过尝试用最少的猜测次数找到数字。此时，进化出最有效猜测策略的人获胜。
然而，我们在玩游戏时会自动做的一件事是利用领域知识。例如，在以下序列之后
1? Higher 7? Lower
我们为什么不猜 8、9 或 10 呢？原因当然是，我们知道这些数字不比 7 低。我们为什么不猜 1 呢？因为我们已经试过了。我们利用我们尝试过的记忆、我们的成功和失败，以及我们的领域知识、数字关系来改进我们的猜测。
遗传算法不知道“更低”是什么意思。它没有智能。它不会学习。它每次都会犯同样的错误。它解决问题的能力只取决于编写代码的人。然而，它却可以用来解决人类难以解决或根本无法解决的问题。这怎么可能呢？在玩纸牌游戏时，经验不足的玩家会利用手中的牌和桌面上的牌建立心理地图。经验更丰富的玩家还会利用他们对问题空间（牌组中的所有牌）的知识。这意味着他们也可能会跟踪尚未打出的牌，并且可能知道他们可以在不必打出所有牌的情况下赢得其余的回合。经验丰富的纸牌玩家也知道各种获胜组合的概率。以玩游戏谋生的专业玩家还会关注竞争对手的打法……例如他们在某些情况下是否虚张声势，或者在认为手牌好时是否玩弄筹码等。
遗传算法结合了对问题空间的随机探索和突变、交叉（遗传信息交换）等进化过程来改进猜测。但也因为它们在问题领域没有经验，它们会尝试人类从未想过要尝试的事情。因此，使用遗传算法的人可能会对问题空间和潜在解决方案了解更多。这使他们能够改进算法，形成良性循环。
我们能从中学到什么？
技巧：遗传算法应该做出明智的猜测。
猜密码
现在让我们看看这如何应用于猜密码。我们将从随机生成一个初始字母序列开始，然后一次突变/改变一个随机字母，直到字母序列是“Hello World!”。从概念上讲
伪代码
_letters = [a..zA..Z !] target = "Hello World!" guess = get 12 random letters from _letters while guess != target: index = get random value from [0..length of target] guess[index] = get 1 random value from _letters
如果你用你喜欢的编程语言尝试这个，你会发现它的表现比玩只有“是”和“否”答案的猜数字游戏还要差，因为它无法判断哪个猜测比另一个更好。
因此，让我们通过告诉它猜测中有多少字母在正确位置来帮助它做出明智的猜测。例如，“World!Hello?”会得到 2，因为每个单词中只有第四个字母是正确的。2 表示答案与正确答案的接近程度。这称为适应度值。“hello world?”会得到 9 的适应度值，因为有 9 个字母是正确的。只有 h、w 和问号是错误的。
第一个程序
现在我们准备好编写一些 Python 代码了。
基因
我们从一组通用基因字母和一个目标密码开始
guessPassword.py
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
target = "Hello World!"
生成一个猜测
接下来我们需要一种方法来从基因集中生成一个随机字符串。
import random
...
def generate_parent(length):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
return ''.join(genes)
random.sample 从输入中抽取 sampleSize 个值，不进行替换。这意味着除非 geneSet 包含重复项，或者 length 大于 len(geneSet)，否则生成的父代中不会有重复项。上面的实现允许我们使用少量基因生成一个长字符串，同时尽可能多地使用独特的基因。
适应度
遗传算法提供的 fitness 值是引导引擎找到解决方案的**唯一**反馈。在这个问题中，我们的 fitness 值是猜测中与密码相同位置的字母匹配的字母总数。
def get_fitness(guess):
return sum(1 for expected, actual in zip(target, guess)
if expected == actual)
突变
我们还需要一种方法通过改变当前猜测来产生新的猜测。以下实现将父字符串转换为数组 list(parent)，然后用从 geneSet 中随机选择的字母替换数组中的一个字母，然后使用 ''.join(genes) 将结果重新组合成字符串。
def mutate(parent):
index = random.randrange(0, len(parent))
childGenes = list(parent)
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate \
if newGene == childGenes[index] \
else newGene
return ''.join(childGenes)
如果随机选择的 newGene 与要替换的基因相同，此实现会使用替代替换，这可以节省大量的开销。
显示
接下来，监控正在发生的事情很重要，这样我们就可以在引擎卡住时停止它。它还允许我们了解哪些有效，哪些无效，从而改进算法。
我们将显示基因序列的视觉表示，这可能不是字面上的基因序列、它的适应度值以及经过了多长时间。
import datetime
...
def display(guess):
timeDiff = datetime.datetime.now() - startTime
fitness = get_fitness(guess)
print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff)))
Main
现在我们准备好编写主程序了。我们首先将 bestParent 初始化为随机的字母序列。
random.seed()
startTime = datetime.datetime.now()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
display(bestParent)
然后我们添加遗传引擎的核心。它是一个循环，生成一个猜测，请求该猜测的 fitness，然后将其与之前最佳猜测的 fitness 进行比较，并保留两者中较好的一个。这个循环重复进行，直到所有字母都与目标中的字母匹配。
while True:
child = mutate(bestParent)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
display(child)
if childFitness >= len(bestParent):
break
bestFitness = childFitness
bestParent = child
Run
现在运行它。
样本输出
ftljCDPvhasn 1 0:00:00
ftljC Pvhasn 2 0:00:00
ftljC Pohasn 3 0:00:00.001000
HtljC Pohasn 4 0:00:00.002000
HtljC Wohasn 5 0:00:00.004000
Htljo Wohasn 6 0:00:00.005000
Htljo Wohas! 7 0:00:00.008000
Htljo Wohls! 8 0:00:00.010000
Heljo Wohls! 9 0:00:00.013000
Hello Wohls! 10 0:00:00.013000
Hello Wohld! 11 0:00:00.013000
Hello World! 12 0:00:00.015000
成功！你已经用 Python 编写了一个遗传算法！
提取一个可重用的引擎
现在我们已经解决了这个问题，我们将从密码问题特定的代码中提取遗传引擎代码，以便我们可以重用它来解决其他问题。我们将首先创建一个名为 genetic.py 的新文件。
接下来，我们将 mutate 和 generate_parent 函数移动到新文件并将其重命名为 _mutate 和 _generate_parent。这就是 Python 中受保护函数的命名方式。它们对 genetic 库的用户将不可见。
生成与突变
由于我们希望能够在未来的问题中自定义使用的基因集，因此我们需要将其作为参数传递给 _generate_parent
import random
def _generate_parent(length, geneSet):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
return ''.join(genes)
以及 _mutate。
def _mutate(parent, geneSet):
index = random.randrange(0, len(parent))
childGenes = list(parent)
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate \
if newGene == childGenes[index] \
else newGene
return ''.join(childGenes)
get_best
接下来，我们将把主循环移动到 genetic 库文件中的一个名为 get_best 的新函数中。它的参数将包括它应该用来请求猜测的适应度以及在找到新的最佳猜测时显示（或报告）它的函数，创建新序列时要使用的基因数量，最佳适应度，以及用于创建和突变基因序列的基因集。
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display):
random.seed()
bestParent = _generate_parent(targetLen, geneSet)
bestFitness = get_fitness(bestParent)
display(bestParent)
if bestFitness >= optimalFitness:
return bestParent
while True:
child = _mutate(bestParent, geneSet)
childFitness = get_fitness(child)
if bestFitness >= childFitness:
continue
display(child)
if childFitness >= optimalFitness:
return child
bestFitness = childFitness
bestParent = child
请注意，我们调用 display 和 get_fitness 时只有一个参数 - 子基因序列。这是因为我们不希望引擎访问目标值，而且它不关心我们是否正在计时运行，因此这些参数不会传递给函数。
我们现在拥有一个名为 genetic 的可重用库，我们可以通过 import genetic 在其他程序中访问它。
使用 genetic 库
回到 guessPassword.py，我们将定义一些函数，这些函数允许我们将 genetic 传递的候选基因序列作为参数，并根据需要调用带有额外所需参数的本地函数。
guessPassword.py
def test_Hello_World():
target = "Hello World!"
guess_password(target)
def guess_password(target):
geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
startTime = datetime.datetime.now()
def fnGetFitness(genes):
return get_fitness(genes, target)
def fnDisplay(genes):
display(genes, target, startTime)
optimalFitness = len(target)
genetic.get_best(fnGetFitness, len(target), optimalFitness, geneset, fnDisplay)
显示
请注意 display 现在如何将目标密码作为参数。我们可以将其保留为算法文件中的全局变量，但这允许我们根据需要尝试不同的密码。
def display(genes, target, startTime):
timeDiff = datetime.datetime.now() - startTime
fitness = get_fitness(genes, target)
print("{0}\t{1}\t{2}".format(genes, fitness, str(timeDiff)))
适应度
我们只需要添加 target 作为参数。
def get_fitness(genes, target):
return sum(1 for expected, actual in zip(target, genes)
if expected == actual)
Main
说到测试，让我们将 guessPassword.py 重命名为 guessPasswordTests.py。我们还需要导入 genetic 库。
guessPasswordTests.py
import datetime
import genetic
最后，我们将通过添加以下代码来确保从命令行执行 guessPasswordTests 时会运行测试函数：
if __name__ == '__main__':
test_Hello_World()
如果您正在 repl.it 等编辑器中操作，请务必运行测试以验证您的代码是否仍然有效。
使用 Python 的 unittest 框架
接下来，我们将使 guessPasswordTests.py 与 Python 内置的测试框架兼容。
import unittest
为此，我们必须将至少主测试函数移动到一个继承自 unittest.TestCase 的类中。我们还需要将 self 添加为我们想要作为实例方法访问的任何函数的第一个参数，因为它现在属于测试类。
class GuessPasswordTests(unittest.TestCase):
geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,"
def test_Hello_World(self):
target = "Hello World!"
self.guess_password(target)
def guess_password(self, target):
...
optimalFitness = len(target)
best = genetic.get_best(fnGetFitness, len(target),
optimalFitness, self.geneset,
fnDisplay)
self.assertEqual(best.Genes, target)
只要我们调用其 main 函数，unittest 库就会自动执行每个名称以“test”开头的函数。
if __name__ == '__main__':
unittest.main()
这允许我们从命令行运行测试，并且不显示输出。
python -m unittest -b guessPasswordTests
.
----------------------------------------
Ran 1 test in 0.020s
好的
如果您收到类似 'module' object has no attribute 'py' 的错误，则表示您使用了文件名 guessPasswordTests.py 而不是模块名 guessPasswordTests。
一个更长的密码
“Hello World!”不足以展示我们引擎的强大功能。让我们尝试一个更长的密码
def test_For_I_am_fearfully_and_wonderfully_made(self):
target = "For I am fearfully and wonderfully made."
self.guess_password(target)
Run
...
ForMI am feabaully and wWndNyfulll made. 33 0:00:00.047094
For I am feabaully and wWndNyfulll made. 34 0:00:00.047094
For I am feabfully and wWndNyfulll made. 35 0:00:00.053111
For I am feabfully and wondNyfulll made. 36 0:00:00.064140
For I am feabfully and wondNyfully made. 37 0:00:00.067148
For I am feabfully and wondeyfully made. 38 0:00:00.095228
For I am feabfully and wonderfully made. 39 0:00:00.100236
For I am fearfully and wonderfully made. 40 0:00:00.195524
太棒了。
引入 Chromosome 对象
接下来，我们将引入一个具有 Genes 和 Fitness 属性的 Chromosome 对象。
genetic.py
class Chromosome:
Genes = None
Fitness = None
def __init__(self, genes, fitness):
self.Genes = genes
self.Fitness = fitness
这使得可以将这些值作为一个单元传递。
def _mutate(parent, geneSet, get_fitness):
index = random.randrange(0, len(parent.Genes))
childGenes = list(parent.Genes)
...
genes = ''.join(childGenes)
fitness = get_fitness(genes)
return Chromosome(genes, fitness)
def _generate_parent(length, geneSet, get_fitness):
...
genes = ''.join(genes)
fitness = get_fitness(genes)
return Chromosome(genes, fitness)
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display):
random.seed()
bestParent = _generate_parent(targetLen, geneSet, get_fitness)
display(bestParent)
if bestParent.Fitness >= optimalFitness:
return bestParent
while True:
child = _mutate(bestParent, geneSet, get_fitness)
if bestParent.Fitness >= child.Fitness:
continue
display(child)
if child.Fitness >= optimalFitness:
return child
bestParent = child
我们还对算法文件函数进行了相应的更改。
guessPasswordTests.py
def display(candidate, startTime):
timeDiff = datetime.datetime.now() - startTime
print("{0}\t{1}\t{2}".format(
candidate.Genes, candidate.Fitness, str(timeDiff)))
这减少了显示函数中的一些重复工作。
class GuessPasswordTests(unittest.TestCase):
...
def guess_password(self, target):
...
def fnDisplay(candidate):
display(candidate, startTime)
optimalFitness = len(target)
best = genetic.get_best(fnGetFitness, len(target),
optimalFitness, self.geneset,
fnDisplay)
self.assertEqual(best.Genes, target)
基准测试
接下来，我们需要为 genetic 添加基准测试支持，因为了解引擎平均需要多长时间才能找到解决方案以及标准差是很有用的。我们可以通过以下方式使用另一个类来做到这一点。
genetic.py
class Benchmark:
@staticmethod
def run(function):
timings = []
for i in range(100):
startTime = time.time()
function()
seconds = time.time() - startTime
timings.append(seconds)
mean = statistics.mean(timings)
print("{0} {1:3.2f} {2:3.2f}".format(
1 + i, mean,
statistics.stdev(timings, mean)
if i > 1 else 0))
这需要以下导入
genetic.py
import statistics
import time
您可能需要在系统上通过以下方式安装 statistics 模块：
python -m pip install statistics现在我们需要添加一个测试来传递我们想要进行基准测试的函数。
guessPasswordTests.py
def test_benchmark(self):
genetic.Benchmark.run(lambda: self.test_For_I_am_fearfully_and_wonderfully_made())
这个基准测试效果很好，但有点啰嗦，因为它还显示了所有 100 次运行的 display 输出。我们可以通过在基准函数中将输出重定向到空来解决这个问题。
genetic.py
import sys
...
class Benchmark:
@staticmethod
def run(function):
...
timings = []
stdout = sys.stdout
for i in range(100):
sys.stdout = None
startTime = time.time()
function()
seconds = time.time() - startTime
sys.stdout = stdout
timings.append(seconds)
...
另外，我们不需要它输出每次运行，所以不如只输出前十次，然后每第十次输出一次。
genetic.py
...
timings.append(seconds)
mean = statistics.mean(timings)
if i < 10 or i % 10 == 9:
print("{0} {1:3.2f} {2:3.2f}".format(
1 + i, mean,
statistics.stdev(timings, mean)
if i > 1 else 0))
现在，当我们运行基准测试时，我们会得到如下输出。
样本输出
1 0.19 0.00
2 0.17 0.00
3 0.18 0.02
...
9 0.17 0.03
10 0.17 0.03
20 0.18 0.04
...
90 0.16 0.05
100 0.16 0.05
这意味着，平均 100 次运行，猜密码需要 0.16 秒，其中 68% 的时间（一个标准差）在 0.11（0.16 - 0.05）到 0.21（0.16 + 0.05）秒之间。不幸的是，这可能太快了，我们无法判断变化是由于代码改进还是由于计算机上运行的其他程序造成的。所以我们要将其更改为一个需要 1-2 秒的随机序列。您的处理器可能与我的不同，因此请根据需要调整长度。
guessPasswordTests.py
import random
...
def test_Random(self):
length = 150
target = ''.join(random.choice(self.geneset) for _ in range(length))
self.guess_password(target)
def test_benchmark(self):
genetic.Benchmark.run(lambda: self.test_Random())
在我的系统上，结果是
|
平均（秒） |
标准差 |
|
1.46 |
0.35 |
摘要
我们构建了一个简单的遗传引擎，它利用随机突变来产生更好的结果。这个引擎能够猜出秘密密码，只给出其长度、可能在密码中的字符集以及一个返回猜测中与秘密匹配的字符数量的适应度函数。这是一个很好的引擎基准问题，因为随着目标字符串变得更长，引擎会浪费越来越多的猜测来尝试改变已经正确的位置。
最终代码
最终代码可在 zip 文件中获取。