iT邦幫忙

2021 iThome 鐵人賽

DAY 10
0
AI & Data

AI ninja project系列 第 10

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

https://ithelp.ithome.com.tw/upload/images/20210910/20122678SrWm1qOfXP.png

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()

https://ithelp.ithome.com.tw/upload/images/20210910/20122678jsjEnsIjqW.png

https://ithelp.ithome.com.tw/upload/images/20210910/20122678vSArGo1rme.png

執行之後,可以查看迭代的統計狀況,以及最後演化出來的最佳路徑。
值得注意的是這一行:
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/


上一篇
AI ninja project [day 9] 先驗演算法
下一篇
AI ninja project [day 11] 圖片分類(1)
系列文
AI ninja project30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言