理解

遗传算法思路来源于基因进化。即基因会随机突变，复制（生出新个体），最终适应的种群将会繁衍（找到最优解）。本质上是一种并行的搜索算法，可以自适应的得到最优解。

因此遗传算法的几个关键点是定义突变，复制过程，定义搜索空间和如何选择优良个体（定义适应度）

过程

  1. 随机的创建种群（例如二维搜索中随机的创建搜索点）
  2. 定义适应函数（二维搜索中和终点的距离）
  3. 选择出适应的个体作为父母进行繁衍
  4. 通过交叉和复制产生后代：从父亲和母亲中抽取一部分特征作为子集并合并，另一部分直接复制优秀的父亲和母亲
  5. 对一些个体进行变异
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

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