遗传算法 （GA） 从自然选择中汲取灵感，是解决搜索和优化问题的一种引人入胜的方法。虽然已经写了很多关于 GA 的文章，但很少有人展示 Python 中针对更复杂问题的 GA 的分步实现。这就是本教程的用武之地！按照步骤操作到最后，您将完全了解如何从头开始部署 GA。

问题

在本教程中，我们将使用 GA 来查找旅行推销员问题 （TSP） 的解决方案。TSP描述如下：

“给定城市列表和每对城市之间的距离，访问每个城市并返回始发城市的最短路线是什么？”

鉴于此，有两条重要规则需要牢记：

（1）每个城市只需要访问一次

（2）我们必须返回起始城市，因此需要相应地计算我们的总距离

方法

让我们从几个定义开始，在 TSP 的上下文中重新表述：

● 基因：一个城市（表示为 （x， y） 坐标）

● 个体（又名“染色体”）：满足上述条件的单一途径

● 种群：可能路线的集合（即个体的集合）

● 父路由：将两条路由合并为创建新路由

● 交配池：用于创建下一个种群（从而创建下一代路线）的亲本集合

● 交叉：一个告诉我们每条路线有多好的函数（在我们的例子中，距离有多短）

● 突变：一种通过在一条路线中随机交换两个城市来引入人口变异的方法

● 精英主义：一种将最优秀的人带入下一代的方式

我们的 GA 将按以下步骤进行：

(1)创建种群

(2)确定适用性

(3)选择配对池

(4)繁殖

(5)变异

(6)重复

现在，让我们看看它的实际效果。

构建我们的遗传算法

虽然 GA 的每个部分都是从头开始构建的，但我们将使用一些标准包来简化操作：

import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt

创建两个类：城市和适应度

我们首先创建一个类，使我们能够创建和处理我们的城市。这些只是我们的 （x， y） 坐标。在 City 类中，我们在第 6 行添加了一个计算（利用勾股定理），并在第 12 行添加了一种更简洁的方式将城市输出为坐标。

Citydistance__repr__

class City:    
      def __init__(self, x, y):        
            self.x = x        
            self.y = y
     
      def distance(self, city):        
            xDis = abs(self.x - city.x)        
            yDis = abs(self.y - city.y)        
            distance = np.sqrt((xDis ** 2) + (yDis ** 2))        
            return distance
   
       def __repr__(self):       
             return "(" + str(self.x) + "," + str(self.y) + ")"

我们还将创建一个类。在我们的例子中，我们将适应度视为路线距离的倒数。我们希望最小化路线距离，因此体能分数越高越好。根据规则 #2，我们需要在同一个地方开始和结束，所以这个额外的计算在距离计算的第 13 行中考虑。

Fitness

class Fitness:    
       def __init__(self, route):        
             self.route = route        
             self.distance = 0        
             self.fitness= 0.0
    
       def routeDistance(self):        
             if self.distance ==0:            
                pathDistance = 0            
                for i in range(0, len(self.route)):                
                     fromCity = self.route                
                     toCity = None                
                     if i + 1 < len(self.route):                    
                         toCity = self.route[i + 1]                
                     else:                    
                           toCity = self.route[0]                
                     pathDistance += fromCity.distance(toCity)            
                self.distance = pathDistance        
          return self.distance

       def routeFitness(self):        
              if self.fitness == 0:            
                   self.fitness = 1 / float(self.routeDistance())        
              return self.fitness

创建种群

我们现在可以制作我们的初始种群（又名第一代）。为此，我们需要一种方法来创建一个函数来生成满足我们条件的路线（注意：我们将在本教程末尾实际运行 GA 时创建城市列表）。要创建一个个人，我们随机选择我们访问每个城市的顺序：

def createRoute(cityList):    
       route = random.sample(cityList, len(cityList))    
       return route

这会产生一个个体，但我们想要一个完整的种群，所以让我们在下一个函数中这样做。这就像循环访问函数一样简单，直到我们为我们的种群提供尽可能多的路由。

createRoute

def initialPopulation(popSize, cityList):    
       population = []
    
       for i in range(0, popSize):        
            population.append(createRoute(cityList))    
       return population

注意：我们只需要使用这些函数来创建初始种群。后代将通过育种和突变产生。

确定适应性

接下来，进化的乐趣开始了。为了模拟我们的“适者生存”，我们可以利用它来对种群中的每个人进行排名。我们的输出将是一个有序列表，其中包含路线 ID 和每个相关的交叉分数

Fitness

def rankRoutes(population):    
      fitnessResults = {}    
      for i in range(0,len(population)):        
           fitnessResults = Fitness(population).routeFitness()    
      return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)

选择配对池

有几个选项可以选择将用于创建下一代的父母。最常见的方法是适应度比例选择（又名“轮盘选择”）或锦标赛选择：

● 适应度比例选择（下面实现的版本）：每个个体相对于总体的适应度用于分配选择概率。将此视为被选中的适应度加权概率。

● 比赛选择：从人群中随机选择一定数量的个体，并选择组中体能最高的个体作为第一家长。重复此操作以选择第二个父项。

另一个需要考虑的设计特征是精英主义的使用。在精英主义中，种群中表现最好的人将自动传递给下一代，确保最成功的人坚持下去。

为了清楚起见，我们将分两步创建交配池。首先，我们将使用 from 的输出来确定要在函数中选择哪些路由。在第 3-5 行中，我们通过计算每个人的相对适应度权重来设置轮盘赌。在第 9 行中，我们将随机抽取的数字与这些权重进行比较，以选择我们的交配池。我们还想坚持我们最好的路线，所以我们在第 7 行引入了精英主义。最终，该函数返回一个路由 ID 列表，我们可以使用它在函数中创建配对池。

rankRoutesselectionselectionmatingPool

def selection(popRanked, eliteSize):    
       selectionResults = []    
       df = pd.DataFrame(np.array(popRanked), columns=["Index","Fitness"])    
       df['cum_sum'] = df.Fitness.cumsum()    
       df['cum_perc'] = 100*df.cum_sum/df.Fitness.sum()
 
       for i in range(0, eliteSize):        
             selectionResults.append(popRanked[0])    
       for i in range(0, len(popRanked) - eliteSize):        
             pick = 100*random.random()        
             for i in range(0, len(popRanked)):            
                  if pick <= df.iat[i,3]:                
                      selectionResults.append(popRanked[0])                
                      break    
       return selectionResults

现在，我们已经从函数中获得了构成交配池的路由的 ID，我们可以创建交配池。我们只是从我们的种群中提取选定的个体。

selection

def matingPool(population, selectionResults):    
      matingpool = []    
      for i in range(0, len(selectionResults)):        
            index = selectionResults        
            matingpool.append(population[index])    
      return matingpool

交叉

随着我们的交配池的创建，我们可以在称为交叉（又名“繁殖”）的过程中创造下一代。如果我们的个体是 0 和 1 的字符串，并且我们的两个规则不适用（例如，假设我们正在决定是否将一只股票包含在投资组合中），我们可以简单地选择一个交叉点并将两个字符串拼接在一起以产生后代。

但是，TSP 是独一无二的，因为我们需要一次准确地包含所有位置。为了遵守这个规则，我们可以使用一种特殊的育种函数，称为有序交叉。在有序交叉中，我们随机选择第一个亲本字符串的子集（参见下面函数中的第 12 行），然后按照它们出现的顺序用来自第二个亲本的基因填充路由的其余部分，而不会复制来自第一个亲本的选定子集中的任何基因（参见下面函数中的第 15 行）。

breedbreed

def breed(parent1, parent2):    
       child = []    
       childP1 = []    
       childP2 = []

       geneA = int(random.random() * len(parent1))    
       geneB = int(random.random() * len(parent1))

       startGene = min(geneA, geneB)    
       endGene = max(geneA, geneB)

       for i in range(startGene, endGene):        
             childP1.append(parent1)

      childP2 = [item for item in parent2 if item not in childP1]

      child = childP1 + childP2    
      return child

接下来，我们将对此进行推广，以创建我们的后代种群。在第 5 行中，我们使用精英主义来保留当前人口中的最佳路线。然后，在第 8 行中，我们使用该函数填写下一代的其余部分。

breed

def breedPopulation(matingpool, eliteSize):    
       children = []    
       length = len(matingpool) - eliteSize    
       pool = random.sample(matingpool, len(matingpool))
 
       for i in range(0,eliteSize):        
             children.append(matingpool)

       for i in range(0, length):        
            child = breed(pool, pool[len(matingpool)-i-1])        
            children.append(child)    
       return children

变异

突变在 GA 中发挥着重要作用，因为它通过引入新的路由来帮助避免局部收敛，这些路由将使我们能够探索解决方案空间的其他部分。与交叉类似，TSP在突变方面也有特殊的考虑。同样，如果我们的染色体是 0 和 1，突变只是意味着基因从 0 变为 1 的概率很低，反之亦然（继续之前的例子，现在不包括在后代投资组合中的股票）。

但是，由于我们需要遵守我们的规则，我们不能放弃城市。相反，我们将使用交换突变。这意味着，在指定的低概率下，两个城市将在我们的路线中交换位置。我们将为我们的职能中的一个人执行此操作：

mutate

def mutate(individual, mutationRate):    
      for swapped in range(len(individual)):        
            if(random.random() < mutationRate):            
                 swapWith = int(random.random() * len(individual))

                 city1 = individual[swapped]            
                 city2 = individual[swapWith]

                  individual[swapped] = city2            
                  individual[swapWith] = city1    
         return individual

接下来，我们可以扩展函数以遍历新的种群。

mutate

def mutatePopulation(population, mutationRate):    
       mutatedPop = []

       for ind in range(0, len(population)):        
            mutatedInd = mutate(population[ind], mutationRate)        
            mutatedPop.append(mutatedInd)    
       return mutatedPop

重复

我们快到了。让我们将这些部分组合在一起，创建一个产生新一代的函数。首先，我们使用对当前一代的路由进行排名。然后，我们通过运行该函数来确定我们的潜在父母，这使我们能够使用该函数创建交配池。最后，我们使用该函数创建新一代，然后使用该函数应用突变。

rankRoutesselectionmatingPoolbreedPopulationmutatePopulation

def nextGeneration(currentGen, eliteSize, mutationRate):    
      popRanked = rankRoutes(currentGen)    
      selectionResults = selection(popRanked, eliteSize)    
      matingpool = matingPool(currentGen, selectionResults)    
      children = breedPopulation(matingpool, eliteSize)    
      nextGeneration = mutatePopulation(children, mutationRate)    
      return nextGeneration

运动中的进化

我们终于准备好了创建我们的 GA 的所有部分！我们需要做的就是创建初始种群，然后我们可以根据需要循环多少代。当然，我们也希望看到最佳路线以及我们改进了多少，因此我们捕获了第 3 行的初始距离（请记住，距离是适应度的倒数）、第 8 行的最终距离和第 9 行的最佳路线。

def geneticAlgorithm(population, popSize, eliteSize, mutationRate, generations):    
      pop = initialPopulation(popSize, population)    
      print("Initial distance: " + str(1 / rankRoutes(pop)[0][1]))

      for i in range(0, generations):        
           pop = nextGeneration(pop, eliteSize, mutationRate)

      print("Final distance: " + str(1 / rankRoutes(pop)[0][1]))    
      bestRouteIndex = rankRoutes(pop)[0][0]    
      bestRoute = pop[bestRouteIndex]    
      return bestRoute

运行遗传算法

一切就绪后，解决 TSP 只需两个步骤：

首先，我们需要一个旅行城市列表。在这个演示中，我们将创建一个包含 25 个随机城市的列表（看似数量不多的城市，但蛮力必须测试超过 300 条六分路！

cityList = []

for i in range(0,25):    
      cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))

然后，运行遗传算法是一行简单的代码。这是艺术与科学相遇的地方;您应该了解哪些假设最适合您。在这个例子中，我们每代有 100 个个体，保留 20 个精英个体，对给定基因使用 1% 的突变率，并运行 500 代：

geneticAlgorithm(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

奖励功能：绘制改进

很高兴知道我们的起点和终点距离以及建议的路线，但如果不看看我们的距离如何随着时间的推移而改善，那就太失职了。通过对函数的简单调整，我们可以将每一代的最短距离存储在一个列表中，然后绘制结果。

geneticAlgorithmprogress

def geneticAlgorithmPlot(population, popSize, eliteSize, mutationRate, generations):    
      pop = initialPopulation(popSize, population)    
      progress = []    
      progress.append(1 / rankRoutes(pop)[0][1])

      for i in range(0, generations):        
            pop = nextGeneration(pop, eliteSize, mutationRate)        
            progress.append(1 / rankRoutes(pop)[0][1])

      plt.plot(progress)    
      plt.ylabel('Distance')    
      plt.xlabel('Generation')    
      plt.show()

与以前相同的方式运行 GA，但现在使用新创建的函数：

geneticAlgorithmPlot

geneticAlgorithmPlot(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

结论

自己尝试一下，看看你能走多短的路线。或者更进一步，尝试在另一个问题集上实现 GA;了解如何更改 AND 函数以处理其他类型的染色体！

---

本文转载自微信公众号：进修编程

遗传算法 （GA） 从自然选择中汲取灵感，是解决搜索和优化问题的一种引人入胜的方法。虽然已经写了很多关于 GA 的文章，但很少有人展示 Python 中针对更复杂问题的 GA 的分步实现。这就是本教程的用武之地！按照步骤操作到最后，您将完全了解如何从头开始部署 GA。

问题

在本教程中，我们将使用 GA 来查找旅行推销员问题 （TSP） 的解决方案。TSP描述如下：

“给定城市列表和每对城市之间的距离，访问每个城市并返回始发城市的最短路线是什么？”

鉴于此，有两条重要规则需要牢记：

（1）每个城市只需要访问一次

（2）我们必须返回起始城市，因此需要相应地计算我们的总距离

方法

让我们从几个定义开始，在 TSP 的上下文中重新表述：

● 基因：一个城市（表示为 （x， y） 坐标）

● 个体（又名“染色体”）：满足上述条件的单一途径

● 种群：可能路线的集合（即个体的集合）

● 父路由：将两条路由合并为创建新路由

● 交配池：用于创建下一个种群（从而创建下一代路线）的亲本集合

● 交叉：一个告诉我们每条路线有多好的函数（在我们的例子中，距离有多短）

● 突变：一种通过在一条路线中随机交换两个城市来引入人口变异的方法

● 精英主义：一种将最优秀的人带入下一代的方式

我们的 GA 将按以下步骤进行：

(1)创建种群

(2)确定适用性

(3)选择配对池

(4)繁殖

(5)变异

(6)重复

现在，让我们看看它的实际效果。

构建我们的遗传算法

虽然 GA 的每个部分都是从头开始构建的，但我们将使用一些标准包来简化操作：

import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt

创建两个类：城市和适应度

我们首先创建一个类，使我们能够创建和处理我们的城市。这些只是我们的 （x， y） 坐标。在 City 类中，我们在第 6 行添加了一个计算（利用勾股定理），并在第 12 行添加了一种更简洁的方式将城市输出为坐标。

Citydistance__repr__

class City:    
      def __init__(self, x, y):        
            self.x = x        
            self.y = y
     
      def distance(self, city):        
            xDis = abs(self.x - city.x)        
            yDis = abs(self.y - city.y)        
            distance = np.sqrt((xDis ** 2) + (yDis ** 2))        
            return distance
   
       def __repr__(self):       
             return "(" + str(self.x) + "," + str(self.y) + ")"

我们还将创建一个类。在我们的例子中，我们将适应度视为路线距离的倒数。我们希望最小化路线距离，因此体能分数越高越好。根据规则 #2，我们需要在同一个地方开始和结束，所以这个额外的计算在距离计算的第 13 行中考虑。

Fitness

class Fitness:    
       def __init__(self, route):        
             self.route = route        
             self.distance = 0        
             self.fitness= 0.0
    
       def routeDistance(self):        
             if self.distance ==0:            
                pathDistance = 0            
                for i in range(0, len(self.route)):                
                     fromCity = self.route                
                     toCity = None                
                     if i + 1 < len(self.route):                    
                         toCity = self.route[i + 1]                
                     else:                    
                           toCity = self.route[0]                
                     pathDistance += fromCity.distance(toCity)            
                self.distance = pathDistance        
          return self.distance

       def routeFitness(self):        
              if self.fitness == 0:            
                   self.fitness = 1 / float(self.routeDistance())        
              return self.fitness

创建种群

我们现在可以制作我们的初始种群（又名第一代）。为此，我们需要一种方法来创建一个函数来生成满足我们条件的路线（注意：我们将在本教程末尾实际运行 GA 时创建城市列表）。要创建一个个人，我们随机选择我们访问每个城市的顺序：

def createRoute(cityList):    
       route = random.sample(cityList, len(cityList))    
       return route

这会产生一个个体，但我们想要一个完整的种群，所以让我们在下一个函数中这样做。这就像循环访问函数一样简单，直到我们为我们的种群提供尽可能多的路由。

createRoute

def initialPopulation(popSize, cityList):    
       population = []
    
       for i in range(0, popSize):        
            population.append(createRoute(cityList))    
       return population

注意：我们只需要使用这些函数来创建初始种群。后代将通过育种和突变产生。

确定适应性

接下来，进化的乐趣开始了。为了模拟我们的“适者生存”，我们可以利用它来对种群中的每个人进行排名。我们的输出将是一个有序列表，其中包含路线 ID 和每个相关的交叉分数

Fitness

def rankRoutes(population):    
      fitnessResults = {}    
      for i in range(0,len(population)):        
           fitnessResults = Fitness(population).routeFitness()    
      return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)

选择配对池

有几个选项可以选择将用于创建下一代的父母。最常见的方法是适应度比例选择（又名“轮盘选择”）或锦标赛选择：

● 适应度比例选择（下面实现的版本）：每个个体相对于总体的适应度用于分配选择概率。将此视为被选中的适应度加权概率。

● 比赛选择：从人群中随机选择一定数量的个体，并选择组中体能最高的个体作为第一家长。重复此操作以选择第二个父项。

另一个需要考虑的设计特征是精英主义的使用。在精英主义中，种群中表现最好的人将自动传递给下一代，确保最成功的人坚持下去。

为了清楚起见，我们将分两步创建交配池。首先，我们将使用 from 的输出来确定要在函数中选择哪些路由。在第 3-5 行中，我们通过计算每个人的相对适应度权重来设置轮盘赌。在第 9 行中，我们将随机抽取的数字与这些权重进行比较，以选择我们的交配池。我们还想坚持我们最好的路线，所以我们在第 7 行引入了精英主义。最终，该函数返回一个路由 ID 列表，我们可以使用它在函数中创建配对池。

rankRoutesselectionselectionmatingPool

def selection(popRanked, eliteSize):    
       selectionResults = []    
       df = pd.DataFrame(np.array(popRanked), columns=["Index","Fitness"])    
       df['cum_sum'] = df.Fitness.cumsum()    
       df['cum_perc'] = 100*df.cum_sum/df.Fitness.sum()
 
       for i in range(0, eliteSize):        
             selectionResults.append(popRanked[0])    
       for i in range(0, len(popRanked) - eliteSize):        
             pick = 100*random.random()        
             for i in range(0, len(popRanked)):            
                  if pick <= df.iat[i,3]:                
                      selectionResults.append(popRanked[0])                
                      break    
       return selectionResults

现在，我们已经从函数中获得了构成交配池的路由的 ID，我们可以创建交配池。我们只是从我们的种群中提取选定的个体。

selection

def matingPool(population, selectionResults):    
      matingpool = []    
      for i in range(0, len(selectionResults)):        
            index = selectionResults        
            matingpool.append(population[index])    
      return matingpool

交叉

随着我们的交配池的创建，我们可以在称为交叉（又名“繁殖”）的过程中创造下一代。如果我们的个体是 0 和 1 的字符串，并且我们的两个规则不适用（例如，假设我们正在决定是否将一只股票包含在投资组合中），我们可以简单地选择一个交叉点并将两个字符串拼接在一起以产生后代。

但是，TSP 是独一无二的，因为我们需要一次准确地包含所有位置。为了遵守这个规则，我们可以使用一种特殊的育种函数，称为有序交叉。在有序交叉中，我们随机选择第一个亲本字符串的子集（参见下面函数中的第 12 行），然后按照它们出现的顺序用来自第二个亲本的基因填充路由的其余部分，而不会复制来自第一个亲本的选定子集中的任何基因（参见下面函数中的第 15 行）。

breedbreed

def breed(parent1, parent2):    
       child = []    
       childP1 = []    
       childP2 = []

       geneA = int(random.random() * len(parent1))    
       geneB = int(random.random() * len(parent1))

       startGene = min(geneA, geneB)    
       endGene = max(geneA, geneB)

       for i in range(startGene, endGene):        
             childP1.append(parent1)

      childP2 = [item for item in parent2 if item not in childP1]

      child = childP1 + childP2    
      return child

接下来，我们将对此进行推广，以创建我们的后代种群。在第 5 行中，我们使用精英主义来保留当前人口中的最佳路线。然后，在第 8 行中，我们使用该函数填写下一代的其余部分。

breed

def breedPopulation(matingpool, eliteSize):    
       children = []    
       length = len(matingpool) - eliteSize    
       pool = random.sample(matingpool, len(matingpool))
 
       for i in range(0,eliteSize):        
             children.append(matingpool)

       for i in range(0, length):        
            child = breed(pool, pool[len(matingpool)-i-1])        
            children.append(child)    
       return children

变异

突变在 GA 中发挥着重要作用，因为它通过引入新的路由来帮助避免局部收敛，这些路由将使我们能够探索解决方案空间的其他部分。与交叉类似，TSP在突变方面也有特殊的考虑。同样，如果我们的染色体是 0 和 1，突变只是意味着基因从 0 变为 1 的概率很低，反之亦然（继续之前的例子，现在不包括在后代投资组合中的股票）。

但是，由于我们需要遵守我们的规则，我们不能放弃城市。相反，我们将使用交换突变。这意味着，在指定的低概率下，两个城市将在我们的路线中交换位置。我们将为我们的职能中的一个人执行此操作：

mutate

def mutate(individual, mutationRate):    
      for swapped in range(len(individual)):        
            if(random.random() < mutationRate):            
                 swapWith = int(random.random() * len(individual))

                 city1 = individual[swapped]            
                 city2 = individual[swapWith]

                  individual[swapped] = city2            
                  individual[swapWith] = city1    
         return individual

接下来，我们可以扩展函数以遍历新的种群。

mutate

def mutatePopulation(population, mutationRate):    
       mutatedPop = []

       for ind in range(0, len(population)):        
            mutatedInd = mutate(population[ind], mutationRate)        
            mutatedPop.append(mutatedInd)    
       return mutatedPop

重复

我们快到了。让我们将这些部分组合在一起，创建一个产生新一代的函数。首先，我们使用对当前一代的路由进行排名。然后，我们通过运行该函数来确定我们的潜在父母，这使我们能够使用该函数创建交配池。最后，我们使用该函数创建新一代，然后使用该函数应用突变。

rankRoutesselectionmatingPoolbreedPopulationmutatePopulation

def nextGeneration(currentGen, eliteSize, mutationRate):    
      popRanked = rankRoutes(currentGen)    
      selectionResults = selection(popRanked, eliteSize)    
      matingpool = matingPool(currentGen, selectionResults)    
      children = breedPopulation(matingpool, eliteSize)    
      nextGeneration = mutatePopulation(children, mutationRate)    
      return nextGeneration

运动中的进化

我们终于准备好了创建我们的 GA 的所有部分！我们需要做的就是创建初始种群，然后我们可以根据需要循环多少代。当然，我们也希望看到最佳路线以及我们改进了多少，因此我们捕获了第 3 行的初始距离（请记住，距离是适应度的倒数）、第 8 行的最终距离和第 9 行的最佳路线。

def geneticAlgorithm(population, popSize, eliteSize, mutationRate, generations):    
      pop = initialPopulation(popSize, population)    
      print("Initial distance: " + str(1 / rankRoutes(pop)[0][1]))

      for i in range(0, generations):        
           pop = nextGeneration(pop, eliteSize, mutationRate)

      print("Final distance: " + str(1 / rankRoutes(pop)[0][1]))    
      bestRouteIndex = rankRoutes(pop)[0][0]    
      bestRoute = pop[bestRouteIndex]    
      return bestRoute

运行遗传算法

一切就绪后，解决 TSP 只需两个步骤：

首先，我们需要一个旅行城市列表。在这个演示中，我们将创建一个包含 25 个随机城市的列表（看似数量不多的城市，但蛮力必须测试超过 300 条六分路！

cityList = []

for i in range(0,25):    
      cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))

然后，运行遗传算法是一行简单的代码。这是艺术与科学相遇的地方;您应该了解哪些假设最适合您。在这个例子中，我们每代有 100 个个体，保留 20 个精英个体，对给定基因使用 1% 的突变率，并运行 500 代：

geneticAlgorithm(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

奖励功能：绘制改进

很高兴知道我们的起点和终点距离以及建议的路线，但如果不看看我们的距离如何随着时间的推移而改善，那就太失职了。通过对函数的简单调整，我们可以将每一代的最短距离存储在一个列表中，然后绘制结果。

geneticAlgorithmprogress

def geneticAlgorithmPlot(population, popSize, eliteSize, mutationRate, generations):    
      pop = initialPopulation(popSize, population)    
      progress = []    
      progress.append(1 / rankRoutes(pop)[0][1])

      for i in range(0, generations):        
            pop = nextGeneration(pop, eliteSize, mutationRate)        
            progress.append(1 / rankRoutes(pop)[0][1])

      plt.plot(progress)    
      plt.ylabel('Distance')    
      plt.xlabel('Generation')    
      plt.show()

与以前相同的方式运行 GA，但现在使用新创建的函数：

geneticAlgorithmPlot

geneticAlgorithmPlot(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

结论

自己尝试一下，看看你能走多短的路线。或者更进一步，尝试在另一个问题集上实现 GA;了解如何更改 AND 函数以处理其他类型的染色体！

---

本文转载自微信公众号：进修编程