基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进

1147-柳同学

发表文章数:593

热门标签

,
首页 » 算法 » 正文

前言

前面一节我们尝试用GA求解TSP问题,简单遗传算法总是不能很好收敛到一个较优的解,在用时和求解精度上都被贪心算法吊打。末尾我们总结了三个可能的改进方向,这一次我们沿着这三个方向试着改进简单遗传算法,以提升其性能。

一.精英保留策略

1.精英保留策略

在简单遗传算法中,我们总是用产生的育种后代族群完全取代父代族群。在真实的生物进化中,总是会有一部分后代由于不能适应环境而夭折,留下来的后代往往是相对来说更加优秀的个体。仿照这个原理,我们可以在SGA中加入自然选择,用精英保存策略(Eliteness preservation strategy)来筛选产生的育种后代并保留其中较为优秀的个体,这样可以使得算法更快收敛。
精英保留策略如下:

  • 在选择育种后代时,选择出比原始族群更大的一个育种族群,
  • 对该育种族群进行变异操作-交叉与突变
  • 对变异后的育种族群进行自然选择,只取其中n_pop个个体以保持族群规模。
    精英保留策略代码实现
    为了获取更大的自由度,此处不再调用DEAP内置的eaSimple函数,而是自行用注册的工具箱实现
'''
    精英保留策略
'''
from scipy.spatial import distance
import numpy as np
import matplotlib.pyplot as plt
from deap import creator,tools,base
import random
# 生成城市坐标
def genCity(n,lb = 100,ub = 999):
    return np.random.randint(low=lb,high=ub,size=(n,2))

# 生成城市距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,metric='euclidean')

# 补全路线
def completeRoute(individual):
    return individual + [individual[0]]  # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i, j in zip(route[0::], route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i, j]
    return (routeDist),

# 精英保留策略一遗传算法
def GA_improved(cities,nCities,npop = 100,cxpb = 0.5,mutpb = 0.2,ngen = 200):
    global cityDist
    # 定义问题
    creator.create('FitnessMin',base.Fitness,weights=(-1.0,))   # 单目标优化最小值
    creator.create('Individual',list,fitness = creator.FitnessMin)

    # 定义个体编码
    toolbox = base.Toolbox()
    toolbox.register('Indices',np.random.permutation,range(nCities))    # 创建序列
    toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Indices)

    # 创建族群
    toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)
    pop = toolbox.Population(npop)

    # 注册所需工具
    cityDist = cityDistance(cities)
    toolbox.register('evaluate',routeDistance)
    toolbox.register('select',tools.selTournament,tournsize=2)
    toolbox.register('mate',tools.cxOrdered)
    toolbox.register('mutate',tools.mutShuffleIndexes,indpb=0.2)

    # 数据记录
    stats = tools.Statistics(key= lambda ind : ind.fitness.values)
    stats.register('avg',np.mean)
    stats.register('std',np.std)
    stats.register('min',np.min)
    stats.register('max',np.max)
    logbook = tools.Logbook()
    logbook.header = 'gen','nevals','avg','std','min','max'

    # 实现遗传算法
    for gen in range(1,ngen+1):
        # 配种选择
        offspring = toolbox.select(pop,2*npop)
        # 复制,否则在交叉和突变这样的原位操作中,会改变所有select出来的同个体副本
        offspring_copy = list(map(toolbox.clone,offspring))

        # 变异操作-交叉
        for child1,child2 in zip(offspring_copy[::2],offspring_copy[1::2]):
            if random.random() < cxpb:
                toolbox.mate(child1,child2)
                del child1.fitness.values
                del child2.fitness.values

        # 变异操作-突变
        for mutant in offspring_copy:
            if random.random() < mutpb:
                toolbox.mutate(mutant)
                del mutant.fitness.values

        # 对于被改变的个体,重新计算其适应度
        invalid_ind = [ind for ind in offspring_copy if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate,invalid_ind)

        for ind,fit in zip(invalid_ind,fitnesses):
            ind.fitness.values = fit

        # 环境选择-保留精英,保持种群规模
        pop = tools.selBest(offspring_copy,npop,fit_attr='fitness')

        # 记录数据
        # compile(sequence)# 将每个注册功能应用于输入序列数据,并将结果作为字典返回
        record = stats.compile(pop)
        logbook.record(gen=gen,nevals=len(invalid_ind),**record)

    return pop,logbook


# 可视化
def plotTour(logbookGA_improved):
    gen = logbookGA_improved.select('gen')
    min = logbookGA_improved.select('min')
    avg = logbookGA_improved.select('avg')
    plt.plot(gen,min,'r-',label='Minimum Fitness')
    plt.plot(gen,avg,'b-',label='Average Fitness')
    plt.xlabel('Iteration')
    plt.ylabel('Fitness')
    plt.legend(loc='upper right')
    plt.title('GA with eliteness preservation strategy iterations, Problem size:{nCities}',fontsize = 20)
    plt.tight_layout()


nCities = 30
# 随机生成30个城市坐标
cities = genCity(nCities)
resultPopGA_improved,logbookGA_improved = GA_improved(cities,nCities)
print(logbookGA_improved)
plotTour(logbookGA_improved)

改进后的GA迭代过程如下
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
相比于SGA的过程有很大改进
可以看到加入精英保存策略之后,遗传算法的收敛速度大大加快了,遗传算法寻优能力得到了提升。

2.精英策略结合局部搜索算法

遗传算法依靠较大的种群数和变异操作,能够在很大的空间内寻找最优解,它的一个重要优点时不需要问题的具体信息。但是正由于没有利用问题的具体信息,导致GA的局部搜索能力差,在解空间较大的优化问题中,往往需要“人海战术”,产生很大的族群来尝试寻找最优解。

在上一篇文章中我们已经知道2-OPT这种局部搜索方法能够通过uncross路径来改善解的质量,我们可以在变异操作之后,用2-OPT改善族群中的优秀个体,提高搜索效率。

代码实现如下

from scipy.spatial import distance
import numpy as np
import matplotlib.pyplot as plt
from deap import creator,tools,base
import random
# 生成城市坐标
def genCity(n,lb = 100,ub = 999):
    return np.random.randint(low=lb,high=ub,size=(n,2))

# 生成城市距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,metric='euclidean')

# 补全路线
def completeRoute(individual):
    return individual + [individual[0]]  # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i, j in zip(route[0::], route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i, j]
    return (routeDist),

# 2-OPT优化算法
def opt(route,k=2):
    '''
    :param route: 路径
    :param k:
    :return: 返回优化后的路径及其路径长度
    '''
    nCities = len(route)
    optimizedRoute = route
    minDistance = routeDistance(route)
    for i in range(1,nCities-2):
        for j in range(i+k,nCities):
            if j - i <= 1:
                continue
            reversedRoute = route[:i] + route[i:j][::-1] + route[j:]
            reversedRouteDist = routeDistance(reversedRoute)
            # 如果翻转后的路径更优,则更新最优解
            if reversedRouteDist < minDistance:
                optimizedRoute = reversedRoute
                minDistance = reversedRouteDist

    return optimizedRoute,minDistance


# 精英保留策略一遗传算法
def GA_improved(cities,nCities,npop = 100,cxpb = 0.5,mutpb = 0.2,ngen = 200):
    global cityDist
    # 定义问题
    creator.create('FitnessMin',base.Fitness,weights=(-1.0,))   # 单目标优化最小值
    creator.create('Individual',list,fitness = creator.FitnessMin)

    # 定义个体编码
    toolbox = base.Toolbox()
    toolbox.register('Indices',np.random.permutation,range(nCities))    # 创建序列
    toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Indices)

    # 创建族群
    toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)
    pop = toolbox.Population(npop)

    # 注册所需工具
    cityDist = cityDistance(cities)
    toolbox.register('evaluate',routeDistance)
    toolbox.register('select',tools.selTournament,tournsize=2)
    toolbox.register('mate',tools.cxOrdered)
    toolbox.register('mutate',tools.mutShuffleIndexes,indpb=0.2)
    toolbox.register('localOpt',opt)    # 注册2-opt
    # 数据记录
    stats = tools.Statistics(key= lambda ind : ind.fitness.values)
    stats.register('avg',np.mean)
    stats.register('std',np.std)
    stats.register('min',np.min)
    stats.register('max',np.max)
    logbook = tools.Logbook()
    logbook.header = 'gen','nevals','avg','std','min','max'

    # 实现遗传算法
    for gen in range(1,ngen+1):
        # 配种选择
        offspring = toolbox.select(pop,2*npop)
        # 复制,否则在交叉和突变这样的原位操作中,会改变所有select出来的同个体副本
        offspring_copy = list(map(toolbox.clone,offspring))

        # 变异操作-交叉
        for child1,child2 in zip(offspring_copy[::2],offspring_copy[1::2]):
            if random.random() < cxpb:
                toolbox.mate(child1,child2)
                del child1.fitness.values
                del child2.fitness.values

        # 变异操作-突变
        for mutant in offspring_copy:
            if random.random() < mutpb:
                toolbox.mutate(mutant)
                del mutant.fitness.values

        # 对于被改变的个体,重新计算其适应度
        invalid_ind = [ind for ind in offspring_copy if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate,invalid_ind)
        for ind,fit in zip(invalid_ind,fitnesses):
            ind.fitness.values = fit

        # 环境选择-保留精英,保持种群规模
        pop = tools.selBest(offspring_copy,npop,fit_attr='fitness')

        # 对族群中的精英进行优化,也可以对全部个体进行优化
        nOpt = int(npop/10)
        pop_opt = tools.selBest(pop,nOpt)
        for ind in pop_opt:
            ind[:],ind.fitness.values = toolbox.localOpt(ind)

        # 记录数据
        # compile(sequence)# 将每个注册功能应用于输入序列数据,并将结果作为字典返回
        record = stats.compile(pop)
        logbook.record(gen=gen,nevals=len(invalid_ind),**record)

    return pop,logbook


# 可视化
def plot(logbookGA_improved):
    gen = logbookGA_improved.select('gen')
    min = logbookGA_improved.select('min')
    avg = logbookGA_improved.select('avg')
    fig = plt.figure()
    fig.add_subplot(111)
    plt.plot(gen,min,'r-',label='Minimum Fitness')
    plt.plot(gen,avg,'b-',label='Average Fitness')
    plt.xlabel('Iteration')
    plt.ylabel('Fitness')
    plt.legend(loc='upper right')
    plt.title('GA with eliteness preservation strategy iterations, Problem size:{%d}'%nCities,fontsize = 10)
    plt.tight_layout()
    plt.show()

#
# 路径可视化
def plotTour(tour, cities):
    start = tour[0:1]
    fig = plt.figure()
    fig.add_subplot(111)
    for i, j in zip(tour[0::], tour[1::]):
        plt.plot([cities[i, 0], cities[j, 0]], [cities[i, 1], cities[j, 1]],'bo-')
    plt.plot(cities[start, 0], cities[start, 1], 'rD-')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_GA_opt_TSP')
    plt.show()

nCities = 30
# 随机生成30个城市坐标
cities = genCity(nCities)
resultPopGA_improved,logbookGA_improved = GA_improved(cities,nCities)
print(logbookGA_improved)
plot(logbookGA_improved)
# 最优路径
tour = tools.selBest(resultPopGA_improved,k=1)[0]
print('最优路径为:'+str(tour)+'/n'+'最优路径距离为:'+str(routeDistance(tour)))
tour = completeRoute(tour)
plotTour(tour,cities)

运行结果

最优路径为:[22, 29, 1, 17, 9, 13, 10, 28, 14, 2, 12, 11, 24, 16, 6, 0, 3, 27, 7, 18, 5, 25, 20, 23, 15, 8, 21, 26, 4, 19]
最优路径距离为:(3776.4456973287165,)

可视化
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进

基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
可以看到,在加入局部搜索之后,获得的解质量大幅提升,已经超过repNNTSP+2-OPT的水平,另外迭代收敛所需的次数也大大减少了。

二.超参数调参

1.遗传算法中的超参数以及其一般取值

一般遗传算法中的超参数有:
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
通常来说这些超参数是通过经验和反复试错获得的,并且超参数的选择和问题的类型紧密相关。

除了这些一般超参数以外,各项操作–育种选择、变异和环境选择的方法选择也可以视为一些额外的超参数。

2.超参数寻优

迭代步数–停止原则

GA的停止准则通常包含以下几种:

  • 当适应度函数收敛到某个特定值:一般在对问题有深刻了解的情况下或者问题有特定约束时才能使用;
  • 当最佳适应度在较长时间内不再改变:这是一个常用的准则,但是如果以此作为准则,有在局部最优提前结束的可能;
  • 当族群没有进化潜力时:这也是较为普遍采用的准则,一般来说可以通过计算族群的variance来确定族群的多样性是否还能支持进一步进化。当variance小于某个值时,可以判定已经收敛。
  • 当迭代步数达到预设值:这是为了防止计算时间无限拖延的一个安全设定。迭代步数达到预设值并不能保证遗传算法收敛到最优,因此通常只是作为一个最后保险。
    此处,不妨采用第三种准则,当种群适应度的标准差小于1*10^(-9)时,结束运算
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 迭代停止-方差.py
@time: 2020/11/24 19:29
"""
from scipy.spatial import distance
import numpy as np
import matplotlib.pyplot as plt
from deap import creator,tools,base
import random
# 生成城市坐标
def genCity(n,lb = 100,ub = 999):
    return np.random.randint(low=lb,high=ub,size=(n,2))

# 生成城市距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,metric='euclidean')

# 补全路线
def completeRoute(individual):
    return individual + [individual[0]]  # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i, j in zip(route[0::], route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i, j]
    return (routeDist),

# 2-OPT优化算法
def opt(route,k=2):
    '''
    :param route: 路径
    :param k:
    :return: 返回优化后的路径及其路径长度
    '''
    nCities = len(route)
    optimizedRoute = route
    minDistance = routeDistance(route)
    for i in range(1,nCities-2):
        for j in range(i+k,nCities):
            if j - i <= 1:
                continue
            reversedRoute = route[:i] + route[i:j][::-1] + route[j:]
            reversedRouteDist = routeDistance(reversedRoute)
            # 如果翻转后的路径更优,则更新最优解
            if reversedRouteDist < minDistance:
                optimizedRoute = reversedRoute
                minDistance = reversedRouteDist

    return optimizedRoute,minDistance


# 精英保留策略一遗传算法
def GA_improved(cities,nCities,npop = 100,cxpb = 0.5,mutpb = 0.2,ngen = 200):
    global cityDist
    # 定义问题
    creator.create('FitnessMin',base.Fitness,weights=(-1.0,))   # 单目标优化最小值
    creator.create('Individual',list,fitness = creator.FitnessMin)

    # 定义个体编码
    toolbox = base.Toolbox()
    toolbox.register('Indices',np.random.permutation,range(nCities))    # 创建序列
    toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Indices)

    # 创建族群
    toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)
    pop = toolbox.Population(npop)

    # 注册所需工具
    cityDist = cityDistance(cities)
    toolbox.register('evaluate',routeDistance)
    toolbox.register('select',tools.selTournament,tournsize=2)
    toolbox.register('mate',tools.cxOrdered)
    toolbox.register('mutate',tools.mutShuffleIndexes,indpb=0.2)
    toolbox.register('localOpt',opt)    # 注册2-opt
    # 数据记录
    stats = tools.Statistics(key= lambda ind : ind.fitness.values)
    stats.register('avg',np.mean)
    stats.register('std',np.std)
    stats.register('min',np.min)
    stats.register('max',np.max)
    logbook = tools.Logbook()
    logbook.header = 'gen','nevals','avg','std','min','max'

    # 实现遗传算法
    for gen in range(1+ngen):
        # 配种选择
        offspring = toolbox.select(pop,2*npop)
        # 复制,否则在交叉和突变这样的原位操作中,会改变所有select出来的同个体副本
        offspring_copy = list(map(toolbox.clone,offspring))

        # 变异操作-交叉
        for child1,child2 in zip(offspring_copy[::2],offspring_copy[1::2]):
            if random.random() < cxpb:
                toolbox.mate(child1,child2)
                del child1.fitness.values
                del child2.fitness.values

        # 变异操作-突变
        for mutant in offspring_copy:
            if random.random() < mutpb:
                toolbox.mutate(mutant)
                del mutant.fitness.values

        # 对于被改变的个体,重新计算其适应度
        invalid_ind = [ind for ind in offspring_copy if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate,invalid_ind)
        for ind,fit in zip(invalid_ind,fitnesses):
            ind.fitness.values = fit

        # 环境选择-保留精英,保持种群规模
        pop = tools.selBest(offspring_copy,npop,fit_attr='fitness')

        # 对族群中的精英进行优化,也可以对全部个体进行优化
        nOpt = int(npop/10)
        pop_opt = tools.selBest(pop,nOpt)
        for ind in pop_opt:
            ind[:],ind.fitness.values = toolbox.localOpt(ind)

        # 记录数据
        # compile(sequence)# 将每个注册功能应用于输入序列数据,并将结果作为字典返回
        record = stats.compile(pop)
        logbook.record(gen=gen,nevals=len(invalid_ind),**record)
        # 当族群适应度的标准差小于1*10^(-9)时,结束运算
        if logbook.select('std')[gen - 1] < 1*10**(-9):
            break


    return pop, logbook


# 可视化
def plot(logbookGA_improved):
    gen = logbookGA_improved.select('gen')
    min = logbookGA_improved.select('min')
    avg = logbookGA_improved.select('avg')
    fig = plt.figure()
    fig.add_subplot(111)
    plt.plot(gen,min,'r-',label='Minimum Fitness')
    plt.plot(gen,avg,'b-',label='Average Fitness')
    plt.xlabel('Iteration')
    plt.ylabel('Fitness')
    plt.legend(loc='upper right')
    plt.title('GA with eliteness preservation strategy iterations, Problem size:{%d}'%nCities,fontsize = 10)
    plt.tight_layout()
    plt.show()

#
# 路径可视化
def plotTour(tour, cities):
    start = tour[0:1]
    fig = plt.figure()
    fig.add_subplot(111)
    for i, j in zip(tour[0::], tour[1::]):
        plt.plot([cities[i, 0], cities[j, 0]], [cities[i, 1], cities[j, 1]],'bo-')
    plt.plot(cities[start, 0], cities[start, 1], 'rD-')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_GA_opt_TSP')
    plt.show()

nCities = 30
# 随机生成30个城市坐标
cities = genCity(nCities)
resultPopGA_improved,logbookGA_improved = GA_improved(cities,nCities)
print(logbookGA_improved)
plot(logbookGA_improved)
# 最优路径
tour = tools.selBest(resultPopGA_improved,k=1)[0]
print('最优路径为:'+str(tour)+'/n'+'最优路径距离为:'+str(routeDistance(tour)))
tour = completeRoute(tour)
plotTour(tour,cities)

运行结果:

gen	nevals	avg    	std        	min    	max    
0  	200   	12144.7	879.238    	9419.18	13042.2
1  	111   	11062.3	1008.21    	8503.61	12066.8
2  	128   	10070.4	951.235    	6831.5 	11155.5
3  	130   	9171.87	948.409    	6425.84	10197  
4  	122   	8251.71	773.579    	6496.55	9161.14
5  	116   	7452.58	575.769    	6099   	8123.42
6  	127   	6965.9 	580.68     	5824.76	7668.22
7  	108   	6465.9 	510.499    	5559.95	7152.25
8  	123   	6104.74	366.592    	5362.46	6644.87
9  	124   	5788.35	315.654    	5154.55	6214.42
10 	121   	5501.77	307.906    	4990.17	5829.28
11 	123   	5259.16	214.875    	4857.05	5692.82
12 	111   	5063.11	188.04     	4642.45	5362.46
13 	137   	4912.4 	218.538    	4514.95	5154.55
14 	142   	4723.87	181.7      	4403.61	5033.61
15 	109   	4524.7 	117.827    	4326.45	4716.81
16 	112   	4406.41	65.1068    	4299.75	4514.95
17 	117   	4341.65	45.3688    	4285.86	4403.61
18 	137   	4299.54	12.8953    	4278.46	4326.45
19 	131   	4283.05	29.245     	4198.56	4299.75
20 	117   	4261.95	37.4632    	4198.56	4299.75
21 	103   	4233.86	39.5621    	4198.56	4278.46
22 	132   	4198.7 	1.38155    	4198.56	4212.45
23 	138   	4198.56	9.09495e-13	4198.56	4198.56
24 	120   	4198.56	9.09495e-13	4198.56	4198.56
最优路径为:[17, 12, 0, 20, 23, 11, 5, 27, 14, 25, 10, 6, 22, 9, 19, 13, 7, 24, 2, 15, 4, 28, 21, 18, 16, 26, 3, 8, 1, 29]
最优路径距离为:(4198.56280798808,)

可视化
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
可以看到对于规模为100的TSP问题,只用了不到50代就提前停止计算,省下了大量时间。并且,从获得的路线肉眼判定,它已经非常接近最优路径了。计算的提前结束并没有降低解的质量。

族群规模
各路论文中推荐的族群规模千差万别,从几十到几百,不一而足。有的研究者认为族群规模选定为问题维度的10倍。但是该规则并不能可扩展的。如果面对一个规模300的TSP问题,难道将族群规模设置为3000?这显然是一个非常过剩的数字,并且有研究者认为单纯增加族群规模未必有用。

在笔者的尝试下,对于一个规模100的TSP问题,将族群规模从100提升到1000,计算时间增加了13倍,但是解的质量没有明显提升。下面列出单纯改变族群规模对计算的影响,TSP问题规模为100:
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
考虑到用时和精度,100 应该是一个合理的取值,

变异概率-自适应遗传算法
在通常的遗传算法中,交叉概率和突变概率是固定的值,与个体以及迭代过程都没有关系。在M.Srinivas 和 L .M. Patnaik 1994年的一篇文章 Adaptive probabilities of crossover and mutation in genetic algorithms中,他们提出了一些不同的思考:

  • 不同适应度的个体不应该具有相同的交叉概率Pc与突变概率 Pm, 对于优秀的个体,应当降低变异概率使其能最大限度保留;而对于不良个体,则应当增大变异概率,使其能脱出不良状态。
  • 作为族群整体来说,在求解的前期需要较大变异概率以便将个体在解空间中扩散出去,帮助寻优;而在求解的后期则需要较小的变异概率,加速收敛。
    基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进
    自适应遗传算法代码实现
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 自适应遗传算法.py
@time: 2020/11/24 20:42
"""
from scipy.spatial import distance
import numpy as np
import matplotlib.pyplot as plt
from deap import creator,tools,base
import random
# 生成城市坐标
def genCity(n,lb = 100,ub = 999):
    return np.random.randint(low=lb,high=ub,size=(n,2))

# 生成城市距离矩阵
def cityDistance(cities):
    return distance.cdist(cities,cities,metric='euclidean')

# 补全路线
def completeRoute(individual):
    return individual + [individual[0]]  # 不要append

def routeDistance(route):
    '''
    :param route: 一条路线,一个序列
    :return: 路线长度
    '''
    if route[0] != route[-1]:
        route = completeRoute(route)
    # 存储路线长度
    routeDist = 0
    # i,j分别是相邻的坐标点
    for i, j in zip(route[0::], route[1::]):
        # 这里直接从CityDist变量中取值了
        routeDist += cityDist[i, j]
    return (routeDist),

# 2-OPT优化算法
def opt(route,k=2):
    '''
    :param route: 路径
    :param k:
    :return: 返回优化后的路径及其路径长度
    '''
    nCities = len(route)
    optimizedRoute = route
    minDistance = routeDistance(route)
    for i in range(1,nCities-2):
        for j in range(i+k,nCities):
            if j - i <= 1:
                continue
            reversedRoute = route[:i] + route[i:j][::-1] + route[j:]
            reversedRouteDist = routeDistance(reversedRoute)
            # 如果翻转后的路径更优,则更新最优解
            if reversedRouteDist < minDistance:
                optimizedRoute = reversedRoute
                minDistance = reversedRouteDist

    return optimizedRoute,minDistance

# 计算Pc
def PC(child1,child2,pop,k1=1.0,k3=1.0):
    f_ = max(routeDistance(child1),routeDistance(child2))[0]
    # print(f_[0])
    fitness = []
    for route in pop:
        fitness.append(routeDistance(route))
    f_max = np.max(fitness)
    # print(f_max)
    f_mean = np.mean(fitness)
    # print(f_mean)
    if f_ > f_mean:
        PC = k1*(f_max - f_) / (f_max - f_mean)
    else:
        PC = k3
    return PC

# 计算Pm
def PM(mutant,pop,k2=0.5,k4=0.5):
    f_ = routeDistance(mutant)[0]
    fitness = []
    for route in pop:
        fitness.append(routeDistance(route))
    f_max = np.max(fitness)
    f_mean = np.mean(fitness)
    if f_ > f_mean:
        # print(f_max)
        PM = k2*(f_max - f_) / (f_max - f_mean)
    else:
        PM = k4
    return PM


# 自适应遗传算法
def GA_improved(cities,nCities,npop = 100,ngen = 200):
    global cityDist
    # 定义问题
    creator.create('FitnessMin',base.Fitness,weights=(-1.0,))   # 单目标优化最小值
    creator.create('Individual',list,fitness = creator.FitnessMin)

    # 定义个体编码
    toolbox = base.Toolbox()
    toolbox.register('Indices',np.random.permutation,range(nCities))    # 创建序列
    toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Indices)

    # 创建族群
    toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)
    pop = toolbox.Population(npop)

    # 注册所需工具
    cityDist = cityDistance(cities)
    toolbox.register('evaluate',routeDistance)
    toolbox.register('select',tools.selTournament,tournsize=2)
    toolbox.register('mate',tools.cxUniform)        # 缺变异几率
    toolbox.register('mutate',tools.mutShuffleIndexes)  # 缺变异几率
    toolbox.register('localOpt',opt)    # 注册2-opt
    # 数据记录
    stats = tools.Statistics(key= lambda ind : ind.fitness.values)
    stats.register('avg',np.mean)
    stats.register('std',np.std)
    stats.register('min',np.min)
    stats.register('max',np.max)
    logbook = tools.Logbook()
    logbook.header = 'gen','nevals','avg','std','min','max'

    # 实现遗传算法
    for gen in range(1+ngen):
        # 配种选择
        offspring = toolbox.select(pop,2*npop)
        # 复制,否则在交叉和突变这样的原位操作中,会改变所有select出来的同个体副本
        offspring_copy = list(map(toolbox.clone,offspring))

        # 变异操作-交叉
        # 计算Pc
        for child1,child2 in zip(offspring_copy[::2],offspring_copy[1::2]):
            cxpb = PC(child1,child2,offspring_copy)
            if random.random() < cxpb:
                toolbox.mate(child1,child2,cxpb)
                del child1.fitness.values
                del child2.fitness.values

        # 变异操作-突变
        for mutant in offspring_copy:
            mutpb = PM(mutant,offspring_copy)
            if random.random() < mutpb:
                toolbox.mutate(mutant,mutpb)
                del mutant.fitness.values

        # 对于被改变的个体,重新计算其适应度
        invalid_ind = [ind for ind in offspring_copy if not ind.fitness.valid]
        fitnesses = map(toolbox.evaluate,invalid_ind)
        for ind,fit in zip(invalid_ind,fitnesses):
            ind.fitness.values = fit

        # 环境选择-保留精英,保持种群规模
        pop = tools.selBest(offspring_copy,npop,fit_attr='fitness')

        # 对族群中的精英进行优化,也可以对全部个体进行优化
        nOpt = int(npop/10)
        pop_opt = tools.selBest(pop,nOpt)
        for ind in pop_opt:
            ind[:],ind.fitness.values = toolbox.localOpt(ind)

        # 记录数据
        # compile(sequence)# 将每个注册功能应用于输入序列数据,并将结果作为字典返回
        record = stats.compile(pop)
        logbook.record(gen=gen,nevals=len(invalid_ind),**record)
        # 当族群适应度的标准差小于1*10^(-9)时,结束运算
        if logbook.select('std')[gen - 1] < 1*10**(-9):
            break

    return pop, logbook


# 可视化
def plot(logbookGA_improved):
    gen = logbookGA_improved.select('gen')
    min = logbookGA_improved.select('min')
    avg = logbookGA_improved.select('avg')
    fig = plt.figure()
    fig.add_subplot(111)
    plt.plot(gen,min,'r-',label='Minimum Fitness')
    plt.plot(gen,avg,'b-',label='Average Fitness')
    plt.xlabel('Iteration')
    plt.ylabel('Fitness')
    plt.legend(loc='upper right')
    plt.title('GA with eliteness preservation strategy iterations, Problem size:{%d}'%nCities,fontsize = 10)
    plt.tight_layout()
    plt.show()

#
# 路径可视化
def plotTour(tour, cities):
    start = tour[0:1]
    fig = plt.figure()
    fig.add_subplot(111)
    for i, j in zip(tour[0::], tour[1::]):
        plt.plot([cities[i, 0], cities[j, 0]], [cities[i, 1], cities[j, 1]],'bo-')
    plt.plot(cities[start, 0], cities[start, 1], 'rD-')
    plt.axis('scaled')
    plt.axis('off')
    plt.title('30cities_GA_opt_TSP')
    plt.show()

nCities = 30
# 随机生成30个城市坐标
cities = genCity(nCities)
resultPopGA_improved,logbookGA_improved = GA_improved(cities,nCities)
print(logbookGA_improved)
plot(logbookGA_improved)
# 最优路径
tour = tools.selBest(resultPopGA_improved,k=1)[0]
print('最优路径为:'+str(tour)+'/n'+'最优路径距离为:'+str(routeDistance(tour)))
tour = completeRoute(tour)
plotTour(tour,cities)


运行结果

gen	nevals	avg    	std        	min    	max    
0  	200   	11209.3	819.151    	8350.55	11980.7
1  	174   	10402.8	982.17     	7691.37	11374.9
2  	165   	9560.53	1026.49    	7096   	10712.1
3  	172   	8855.22	1020.16    	6699.99	10315.1
4  	189   	8409.38	930.383    	6352.36	9846.28
5  	186   	8038.99	993.161    	5952.9 	9511.67
6  	193   	7951.44	1114.98    	5654.22	9665.14
7  	180   	7826.13	1230.7     	5284.97	9850.02
8  	186   	7189.36	1157.52    	5009.87	9248.32
9  	172   	6310.11	874.519    	4676.99	7933.6 
10 	187   	5885.76	874.095    	4516.04	7899.19
11 	191   	5661.15	1074.13    	4383.73	8364.51
12 	191   	5101.44	737.958    	4137.57	7185.54
13 	196   	4914.45	785.055    	3950.49	7026   
14 	195   	4921.82	1379.81    	3864.89	9414.62
15 	190   	4569.21	969.753    	3717.26	8793.99
16 	194   	4330.21	582.766    	3518.74	7777.17
17 	194   	4474.44	1268.6     	3386.3 	9384.19
18 	195   	4302.5 	933.278    	3074.96	8918.04
19 	194   	4127.25	594.695    	3083.1 	6219.16
20 	196   	4224.75	1060.5     	2985.6 	8926.29
21 	189   	3857.39	656.194    	2946.38	6277.39
22 	193   	3656.72	617.201    	2918.47	5597.25
23 	193   	3325.66	394.094    	2909.08	4426.3 
24 	197   	3300.36	598.115    	2891.38	5818.67
25 	194   	3173.58	1045.13    	2732.57	9193.8 
26 	167   	2933.08	59.6176    	2840.79	3058.07
27 	187   	2894.57	31.1727    	2732.57	2964.86
28 	185   	3375.39	1675.31    	2700.88	9404.9 
29 	199   	3350.59	1574.53    	2700.88	9032.55
30 	148   	2828.3 	64.3639    	2732.57	2891.38
31 	156   	2907.72	769.554    	2699.78	8687.75
32 	172   	2775.94	64.4723    	2699.78	2942.56
33 	181   	2730.08	30.7126    	2699.78	2833.41
34 	188   	2893.75	1015.02    	2699.78	8715.81
35 	191   	2708.73	16.2796    	2699.78	2804.6 
36 	186   	2810.99	757.309    	2699.78	8260.6 
37 	198   	2700.39	0.546674   	2699.78	2700.88
38 	144   	2700.06	0.475819   	2699.78	2700.88
39 	192   	3451.76	2052.13    	2699.78	9665.07
40 	196   	3171.84	1591.62    	2699.78	9149.6 
41 	198   	2743.65	436.345    	2699.78	7085.23
42 	200   	4467.87	2917.51    	2699.78	10035.3
43 	179   	3237.57	1669.2     	2699.78	8892.51
44 	196   	2699.78	4.54747e-13	2699.78	2699.78
45 	200   	2699.78	4.54747e-13	2699.78	2699.78
最优路径为:[28, 28, 29, 9, 5, 5, 23, 4, 7, 22, 22, 22, 6, 6, 13, 24, 24, 24, 8, 8, 15, 15, 1, 25, 25, 25, 0, 26, 26, 19]
最优路径距离为:(2699.784713875705,)

可视化
基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进

基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进

3.算法测试-多核运行

遗传算法由于其较大的计算量,对于大规模问题通常来说需要很长的计算时间,为了减少等待时间,这里采用多核计算。
对于local parallelization(当地并行化),可以用python的multiprocessing模块或者concurrent.futures来实现;
对于cluster parallelization(集群并行化),可以用SCOOP来实现。

import multiprocessing

nbCpu = multiprocessing.cpu_count()
pool = multiprocessing.Pool(processes = nbCpu) # 调用所有CPU
print('Conducting calculation with %d workers'%nbCpu)
toolbox.register('map', pool.map)
# ....#
pool.close() # 运行完毕后记得关闭计算池

注意通过以上方式DEAP只会对评价进行并行计算,而其他操作如交叉和突变仍然按常规执行。如果评价函数非常简单,那么并行计算并不会节约太多时间。

如果是用控制台跑单独的python file,需要将multiprocess放在main中,参考这里

改进后的遗传算法精度远远超过之前,但耗时同样也变长了

小结

在本文中,我们从三个方面探索了GA的改进,使之在求解TSP时精度大幅提高:

  • 精英保存策略能使GA收敛速度大大加快,但是也有早熟,使得算法陷入局部最优的风险;

  • 结合局部搜索之后,GA从盲目搜索到能够利用问题的性质,解的质量得到大幅改善;

  • 结合了自适应算法之后,GA脱出局部最优的能力增强,但是迭代收敛需要的步数也增加了。

在进行了这三方面改善之后,GA求解TSP的能力大幅提高,从上一节的被各种吊打,已经超越了benchmark repNNTSP+2opt。

在问题规模继续扩大到300以上时,当前很难在较短时间内完成计算,需要尝试将选择、突变、评价操作进行并行计算,提高计算速度。

标签:

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《基于DEAP库的python进化算法-5.遗传算法求解TSP问题的改进》 发布于2020-11-25

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录