AI ninja project [day 10] 基因演算法

这一篇介绍，将使用DEAP这个套件，
其实，现在比较红及使用上比较简便的套件应该是PyGAD，
但是，由於目前PyGAD还无法以比较简单的方法解决旅行推销员问题(需要自己改写突变、配对等等的机制，)。
所以下面采用DEAP来说明，这里附上两个套件的官方文件:

https://pygad.readthedocs.io/en/latest/

https://deap.readthedocs.io/en/master/index.html

这里要解决的问题是旅行推销员问题，
假设要经过所有城市，并且最终要回到起始城市，计算出最短的路径。

安装:

pip install deap

我使用官网的范例:
https://github.com/DEAP/deap/blob/master/examples/ga/tsp.py

gr17.json

{
    "TourSize" : 17,
    "OptTour" : [15, 11, 8, 4, 1, 9, 10, 2, 14, 13, 16, 5, 7, 6, 12, 3, 0],
    "OptDistance" : 2085,
    "DistanceMatrix" :
        [[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121],
        [633, 0, 390, 661, 227, 488, 572, 530, 555, 289, 282, 638, 567, 466, 420, 745, 518],
        [257, 390, 0, 228, 169, 112, 196, 154, 372, 262, 110, 437, 191, 74, 53, 472, 142],
        [91, 661, 228, 0, 383, 120, 77, 105, 175, 476, 324, 240, 27, 182, 239, 237, 84],
        [412, 227, 169, 383, 0, 267, 351, 309, 338, 196, 61, 421, 346, 243, 199, 528, 297],
        [150, 488, 112, 120, 267, 0, 63, 34, 264, 360, 208, 329, 83, 105, 123, 364, 35],
        [80, 572, 196, 77, 351, 63, 0, 29, 232, 444, 292, 297, 47, 150, 207, 332, 29],
        [134, 530, 154, 105, 309, 34, 29, 0, 249, 402, 250, 314, 68, 108, 165, 349, 36],
        [259, 555, 372, 175, 338, 264, 232, 249, 0, 495, 352, 95, 189, 326, 383, 202, 236],
        [505, 289, 262, 476, 196, 360, 444, 402, 495, 0, 154, 578, 439, 336, 240, 685, 390],
        [353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0, 435, 287, 184, 140, 542, 238],
        [324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0, 254, 391, 448, 157, 301],
        [70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0, 145, 202, 289, 55],
        [211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0, 57, 426, 96],
        [268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0, 483, 153],
        [246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0, 336],
        [121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0]]
    }

可以发现有17座城市，DistanceMatrix每一个元素的array为第几个城市到其他城市的距离。

tsp.py

import array
import random
import json
import matplotlib.pyplot as plt
import numpy

from deap import algorithms
from deap import base
from deap import creator
from deap import tools

with open("gr17.json", "r") as tsp_data:
    tsp = json.load(tsp_data)

distance_map = tsp["DistanceMatrix"]
IND_SIZE = tsp["TourSize"]

引入模组，查看刚才json中的距离矩阵及城市数量。

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", array.array, typecode='i', fitness=creator.FitnessMin)

须找的解答是最小值，weights的参数放-1(寻找最大值FitnessMax)。
再来创建每一个染色体个体为一个array，typecode的对照可以由array模组来查看，
https://docs.python.org/zh-tw/3.8/library/array.html

toolbox = base.Toolbox()

建立工具箱，演算法的流程使用这个工具箱来建立注册与操作。

toolbox.register("indices", random.sample, range(IND_SIZE), IND_SIZE)

# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

这里要建立染色体池，将每一条染色体以乱数生成
([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]可能的染色体范例)，
放入染色体池。

def evalTSP(individual):
    distance = distance_map[individual[-1]][individual[0]]
    for gene1, gene2 in zip(individual[0:-1], individual[1:]):
        distance += distance_map[gene1][gene2]
    return distance,

这个function就是我们要解决的问题，每条染色体代表一个路径行走城市的顺序，
那回传该路径所要行走的距离。(值得注意的是评估函数回传的格式为Tuple，所以有那个逗点的存在)

toolbox.register("mate", tools.cxPartialyMatched)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evalTSP)

最後一项评估evaluate 的流程，采用了我们上面的function evalTSP来评估路径的距离，
配对采用套件预设的流程，mate的流程为染色体与染色体之间交换基因，
突变为该染色体基因上变异，选择从染色体池中去掉一些回传距离太长的染色体。

def main():

    pop = toolbox.population(n=300)

    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean)
    stats.register("std", numpy.std)
    stats.register("min", numpy.min)
    stats.register("max", numpy.max)
    
    algorithms.eaSimple(pop, toolbox, 0.7, 0.2, 40, stats=stats, 
                        halloffame=hof)
    best = hof.items[0]
    print('Best Individual = ', best)                    

    return pop, stats, hof

if __name__ == "__main__":
    main()

执行之後，可以查看迭代的统计状况，以及最後演化出来的最佳路径。
值得注意的是这一行:
algorithms.eaSimple(pop, toolbox, 0.7, 0.2, 40, stats=stats, halloffame=hof)

• pop :染色体池数目
• toolbox: 演算法流程
• 0.7: 两个染色体发生交叉配对的机率
• 0.2: 染色体发生突变的机率
• hof: 列出演算过程中，表现不错的染色体

我会认为，这个演算法对物流业应该是有帮助的，
如果再多将上一些加油站交通位置或是交通现况的帮助下。

参考资料:https://brucehan.top/2020/02/13/deap/