介绍

在我们开始之前，我们需要了解遗传算法的真正遗传。基于自然选择和进化的现象，遗传算法试图利用遗传交叉，突变等过程来高度优化进化过程，在计算机科学的情况下，这是一个解决问题的过程。

过程

遗传算法的逐步过程受自然进化的高度影响。它经历了一系列事件，每个事件都依赖于前一个事件的成功，为更老的种群补充更新的，希望有更好的种群。在这里，更好意味着具有更好DNA的新种群的实体。种群，其实体和DNA的确切定义非常模糊，并且取决于手头的问题。步骤是，

1. 初始化:第一步包括创建第一个种群，定义其大小、包含的实体、适应度参数等。在真正开始之前，可以把这看作是一个预处理步骤。
2. 适应度计算：这需要计算每个实体的适应度。现在，适应度是一个得分，它定义了当前实体与所需最终/完美实体之间距离，距离越近，其得分越高。
3. 选择：在这里，我们从我们的人口中选择获得交配许可的实体。完美的是需要只选择最好的个体，一个更现实的方法是将随机选择。
4. 交叉：这里选择的实体繁殖产生他们的后代，最重要的是我们如何结合父母的DNA来创造孩子的DNA。
5. 变异：孩子并不总是父母的完美副本，有时甚至表现出其中任何一个都没有的行为。在这里，我们尝试制定突变的可能性以及它如何影响孩子的DNA。

问题

为了更好地理解逻辑，让我们举一个例子问题并尝试用遗传算法解决它。如何教代理人猜测密码。对于每个猜测，我们提供其正确性的分数，这可能只是代理正确的字母数量。密码可以是任意长度，为简单起见，我们只使用英文字母和空格。现在为什么这个问题很难？在英文字母中有26个字母，考虑到大写和小写，我们得到52，加上空格，我们有53个可能的字符作为一个位置。假设密码是“The pen is mightier than the sword”，我们有53个字母争夺34个位置（短语的长度）。那是53 * 53 * 53 .... 共34次，这是一个超级大的组合（有58个零）。现在想象一下有人试图猜测它。即使是速度最快的超级计算机也需要数年时间来解决它。首先，我们可以选择较小的密码，但问题仍然存在，随着角色的每次增加，复杂性呈指数级增长。

第1步：初始化

在这里我们定义种群，假设它是当前对密码可能的猜测的个数，这使得每个这样的猜测都是一个实体。现在实体(猜测)的DNA将是猜测的密码，在我们的例子中是一个N长度的字符序列。让我们把它进行Python编码，

class Population:
 def __init__(self, pop_size, dna_size, target, mutate_prob = 0.01):
 self.pop_size = pop_size
 self.dna_size = dna_size
 self.entities = [Entity(dna_size) for x in range(pop_size)]
 self.mutate_prob = mutate_prob
 self.target = target
class Entity:
 def __init__(self, dna_size = None, dna = None):
 self.dna_size = dna_size
 if dna:
 self.dna = dna
 self.dna_size = len(dna)
 else:
 self.dna = choose_random_alphabets(dna_size)
 self.fitness = 0.01
 
 def __str__(self):
 return "".join(self.dna)
def choose_random_alphabets(size):
 relevant_characters = string.ascii_letters + ' '
 return random.sample(relevant_characters, size)

还允许初始化种群大小为150，每个实体将是字符的随机序列，

target = "aeiou"
pop = Population(150, len(target), list(target))

第2步：适应度计算

密码的适用度应该是多少呢？显然正确位置的正确字符数。因此，对于每个猜测，我们将逐个字符地比较它并计算我们找到相似字符的次数。最后除以密码的长度，我们有一个有限的相似度得分，即所选猜测的得分或适合度。（将这些添加到Entity类），Python代码如下：

def calculate_fitness(self, target):
 self.fitness = max(self.compare(target), 0.01)
def compare(self, another_dna_value):
 matched_count = 0
 for x,y in zip(self.dna, another_dna_value):
 if x == y:
 matched_count += 1
 return matched_count/self.dna_size

第3步：选择

我们有一大堆猜测，我们知道它们的适应度，现在我们需要确定有资格的候选人，这些候选人有资格将他们的信息传递给下一代猜测。一种经过试验和测试的方法是基于其适应度分数提供猜测的重要概率，即，猜测的适应度得分越高，其获得选择的机会越大。为此，我们通过将每个实体的适应度除以所有适应度值的总和来对其进行归一化。这为我们提供了每个实体重要性的概率。现在我们只需强制执行这种重要性的逻辑，这可以通过Python（将这些添加到Population类）来实现。

def create_mating_pool(self):
 # calculate the fitness
 ttl_fitness = 0
 for x in self.entities:
 x.calculate_fitness(self.target)
 ttl_fitness += x.fitness
 # normalize the fitness
 normalized_fitness = []
 entities = []
 for x in self.entities:
 x.fitness = x.fitness/ttl_fitness
 normalized_fitness.append(x.fitness)
 entities.append(x)
 # create a mating pool
 for x in range(self.pop_size):
 yield np.random.choice(entities, 2, p = normalized_fitness)

第4步：交叉

在达到这一部分时，我们得到一对父母（较老的猜测种群），我们试图制定如何将他们的信息（他们的密码字符）传递给下一代（新的种群）。让我们看一个简单的单点交叉逻辑，它表示，孩子DNA的一半来自不同的父母。现在，这一半可能具有字面意义，因为它是DNA的中点，或者我们可以随机选择切割点。按照后一种逻辑，我们有，（将这些添加到Population类）

def crossover_random_single_point(self, first_parent, second_parent):
 # get random index
 index = np.random.choice(len(first_parent.dna), 1)[0]
 # crossover by the index
 part_one = first_parent.dna[:index]
 part_two = second_parent.dna[index:]
 # combine
 part_one.extend(part_two)
 modified_gene_value = part_one
 # return
 return modified_gene_value

第五步：突变

在我们的例子中，我们随机浏览孩子猜测密码（DNA）的每个字符（基因），并根据概率查询是否需要修改（变异）此字符。如果不是，我们继续前进，如果是，我们用另一个随机字符替换它。通常我们将这种突变率保持在低水平，否则它将掩盖进化的进程。（将这些添加到Population 类）

def breed(self):
 # till we have populated same size
 new_population = []
 for first_parent, second_parent in self.create_mating_pool():
 # crossover logic
 modified_gene_value = self.crossover_random_single_point(first_parent, second_parent)
 # mutate; if you are unlucky...or lucky?
 for index in range(len(modified_gene_value)):
 # check if mutate probability is satisfied
 if np.random.random() <= self.mutate_prob:
 modified_gene_value[index] = choose_random_alphabets(1)[0]
 # create new entity with the parent's combined genes
 new_population.append(Entity(dna = modified_gene_value))
 # when done replace the population
 self.entities = list(new_population)

解

将各个部分连接在一起并重复几代的步骤，让我们看看我们的population 需要多长时间才能正确猜出不同的密码。

遗传算法解决密码破解问题

对于每个单独的密码，我们还绘制了几代种群平均适应度的进度图。

密码：“aeiou”

密码：“qwertyuiop”

密码：“You cant crack it”

有一件事是显而易见的，随着代的增加，种群的适应性增加。当然，由于突变会产生一些振荡，但从更大的角度来看，人口会随着更新的实体而发展，并且我们有机会找到更好的解决方案。

结论

我们采用了密码破解的经典例子，遗传算法可以用于各种问题。一些广泛的例子可能是旅行推荐，特征优化，多对象优化，游戏代理等。同时，我们保持了大量的参数不变，如突变率、种群大小、适应度得分等，并对选择不同逻辑进行交叉、突变和选择的效果进行了深入的研究。