I have learned the previous two genetic algorithms , but they are all aimed at solving abstract mathematical problems, so how do we apply genetic algorithms to practical problems in reality, and then the first problem I came into contact with It is the vehicle routing optimization problem VRP. Of course, I also found a good article, Logistics Management Paper Implementation: Vehicle Routing Optimization with Time Window and Load Constraints Based on Genetic Algorithms.
This blogger's code is very good, because I There is no error when copying and running, but it is more difficult to read, because this blogger is more powerful, he defines a class class in it, and then there will be a lot of self, which is slightly different from ordinary definition functions , which caused my novice to look very uncomfortable. I don’t know how to realize the specific selection, crossover and mutation operations, so I re-wrote the code based on the study of the previous two articles and my own understanding. Among them, the objective function is relatively complicated, but I also simplified it. It only needs to require the shortest distance, because I just want to see how this genetic algorithm looks like in a practical problem. Of course, the simpler the better, I think I can understand it. , most people should be fine.
And in this process, I also learned a skill. When an error occurs and the operation cannot continue, add a try, except, skip the error, continue to run, and the result will be obtained.
First define the conditions given in the question and initialize the parameters

geneNum = 100  # 种群数量
generationNum = 300  # 迭代次数


CENTER = 0  # 配送中心

# HUGE = 9999999
# PC = 1   #交叉率,没有定义交叉率，也就是说全部都要交叉，也就是1
PM = 0.1  # 变异率   以前是用的vary

n = 25  # 客户点数量
m = 2  # 换电站数量
k = 3  # 车辆数量
Q = 5  # 额定载重量, t
# dis = 160  # 续航里程, km
length = n+m+1

# 坐标   第0个是配送中心   1-25是顾客      26和27是换电站          一共28个位置    行驶距离要通过这个坐标自己来算
X = [56, 66, 56, 88, 88, 24, 40, 32, 16, 88, 48, 32, 80, 48, 23, 48, 16, 8, 32, 24, 72, 72, 72, 88, 104, 104, 83,32]
Y = [56, 78, 27, 72, 32, 48, 48, 80, 69, 96, 96, 104, 56, 40, 16, 8, 32, 48, 64, 96, 104, 32, 16, 8, 56, 32, 45, 40]
# 需求量
t = [0, 0.2, 0.3, 0.3, 0.3, 0.3, 0.5, 0.8, 0.4, 0.5, 0.7, 0.7, 0.6, 0.2, 0.2, 0.4, 0.1, 0.1, 0.2, 0.5, 0.2, 0.7,0.2,0.7, 0.1, 0.5, 0.4, 0.4]

Coding: Coding according to the actual problem, then use real number coding. The content that needs to be obtained is placed in the chromosome
in two steps to generate an initial individual that meets the conditions. First, an unordered list is generated, and the distribution center 0 is inserted at the first and last positions. , and then according to the sum of the transport demand of a car does not exceed the load of the car, randomly insert 0 into this unordered list as a new start from the distribution center, which means that there are several cars Note: the initial population here is
generated It is not as simple as the pure mathematics problems in the previous two articles, and it needs to be written as a function to produce an initial solution that meets the requirements, that is, the initial population.

def getGene(length):   
    ##先产生一个无序的列表
    data = list(range(1,length))  ##先产生一个有序的列表
    np.random.shuffle(data)   ##有序列表打乱成无序列表
    data.insert(0, CENTER)    ##在开始插入0
    data.append(CENTER)       ##在结尾插入0

    #再插入车
    sum = 0
    newData = []
    for index, pos in enumerate(data):
        sum += t[pos]
        if sum > Q:
            newData.append(CENTER)
            sum = t[pos]
        newData.append(pos)

    return newData
def getpop(length,geneNum):
    pop = []
    for i in range(geneNum):
        gene = getGene(length)
        pop.append(gene)
    return pop

Calculate the fitness value, calculate the fitness value of an individual, and then get the fitness list of the entire population
Note: the fitness value is a distance function, which needs to be expressed according to the coordinates of each point

##计算一个个体的适应度值
def getfit(gene):
    distCost = 0
    dist = []  # from this to next
    # 计算距离
    i = 1
    while i < len(gene):
        calculateDist = lambda x1, y1, x2, y2: math.sqrt(((x1 - x2) ** 2) + ((y1 - y2) ** 2))
        dist.append(calculateDist(X[gene[i]], Y[gene[i]], X[gene[i - 1]], Y[gene[i - 1]]))
        i += 1
    # 距离成本
    distCost = sum(dist)     #总行驶距离
    fit = 1/distCost   ##fitness越小表示越优秀，被选中的概率越大，
    return fit
##得到整个种群的适应度列表
def getfitness(pop):
    fitness = []
    for gene in pop:
        fit = getfit(gene)
        fitness.append(fit)
    return np.array(fitness)

Selection, using roulette, the greater the fitness value, the more likely it will be selected to the next generation

def select(pop,fitness):
    fitness = fitness / fitness.sum()  # 归一化
    idx = np.array(list(range(geneNum)))
    pop_idx = np.random.choice(idx, size=geneNum, p=fitness)  # 根据概率选择
    for i in range(geneNum):
        pop[i] = pop[pop_idx[i]]
    return pop

The crossover here is also more troublesome, because you can’t crossover casually in this problem, because if you use 5 crossover to exchange for a 6, but in fact there are already 6 in this individual, and each customer can only visit once, which does not meet the problem It is stipulated, so some operations need to be done
to pave the way. The effect of selecting the path is as follows:

Then the intersection of two individuals, the effect is as follows:

Take gene1 as an example, it is to add the numbers that are in gene2 but not in the path in front of gene1 Go to the back of gene1, get newgene1, newgene2 is the same, and then the crossover is over.

And only the first 1/3 population with high fitness is selected for crossover. If there is no crossover probability, all must be crossover, but the population obtained after crossover is only 1/3 of individuals, so the 1/3 Individuals are replaced to the last part of the original population with lower fitness, and finally merged into a complete population.

#选择路径
def moveRandSubPathLeft(gene):
    import random
    path = random.randrange(k)  # 选择路径索引，随机分成k段
    print('path:',path)
    try:
        index = gene.index(CENTER, path+1) #移动到所选索引
        # move first CENTER
        locToInsert = 0
        gene.insert(locToInsert, gene.pop(index))
        index += 1
        locToInsert += 1
        # move data after CENTER
        print('index:',index)
        try:
            print('len(gene):',len(gene))
            while gene[index] != CENTER:
                gene.insert(locToInsert, gene.pop(index))
                index += 1
                print('执行完index+1,index=',index)
                locToInsert += 1
            return gene
            # assert(length+k == len(gene))
        except:
            print('出错啦，index:',index)
            return gene
    except:
        print('0 is not in list',gene)
        return gene

# 选择复制，选择适应度最高的前 1/3，进行后面的交叉
def choose(pop):
    num = int(geneNum/6) * 2    # 选择偶数个，方便下一步交叉
    # sort genes with respect to chooseProb
    key = lambda gene: getfit(gene)
    pop.sort(reverse=True, key=key)      ##那就是说按照适应度函数降序排序,选了适应度值最高的那1/3
    # return shuffled top 1/3   
    return pop[0:num]

For crossover, the probability of crossover is not considered, because all of them will cross in turn, but the code first writes a pair of crossover, and then crossover the first 1/3 population with higher fitness selected earlier

##交叉一对
def crossPair(i,gene1, gene2, crossedGenes):
    gene1 = moveRandSubPathLeft(gene1)
    gene2 = moveRandSubPathLeft(gene2)
    newGene1 = []
    newGene2 = []
    # copy first paths
    centers = 0
    firstPos1 = 1
    for pos in gene1:
        firstPos1 += 1
        centers += (pos == CENTER)
        newGene1.append(pos)
        if centers >= 2:
            break
    centers = 0
    firstPos2 = 1
    for pos in gene2:
        firstPos2 += 1
        centers += (pos == CENTER)
        newGene2.append(pos)
        if centers >= 2:
            break
    # copy data not exits in father gene
    for pos in gene2:
        if pos not in newGene1:
            newGene1.append(pos)
    for pos in gene1:
        if pos not in newGene2:
            newGene2.append(pos)
    # add center at end
    newGene1.append(CENTER)
    newGene2.append(CENTER)
    # 计算适应度最高的
    key1 = lambda gene1: getfit(gene1)
    possible1 = []
    try:
        while gene1[firstPos1] != CENTER:
            newGene = newGene1.copy()
            newGene.insert(firstPos1, CENTER)
            possible1.append(newGene)
            firstPos1 += 1
        print('第{}位置:{}'.format(i,len(possible1)))
        if len(possible1) == 0:
            crossedGenes.append(newGene1)
        else:
            possible1.sort(reverse=True, key=key1)
            crossedGenes.append(possible1[0])
    except:
        print('交叉出错啦：firstPos1', firstPos1)

    key2 = lambda gene2: getfit(gene2)
    possible2 = []
    try:
        while gene2[firstPos2] != CENTER:
            newGene = newGene2.copy()
            newGene.insert(firstPos2, CENTER)
            possible2.append(newGene)
            firstPos2 += 1
        print('第{}:{}'.format(i,len(possible2)))
        if len(possible2) == 0:
            crossedGenes.append(newGene2)
        else:
            possible2.sort(reverse=True, key=key2)
            crossedGenes.append(possible2[0])
        print('交叉完成第：', i)
    except:
        print('交叉出错啦：',i)

# 交叉
def cross(genes):
    crossedGenes = []
    for i in range(0, len(genes), 2):
        # print('gene[i]:',genes[i])
        # print('gene[i+1]:', genes[i])
        crossPair(i,genes[i], genes[i+1], crossedGenes)
        print('交叉完成')
    return crossedGenes

# 合并
def mergeGenes(genes, crossedGenes):
    # sort genes with respect to chooseProb
    key = lambda gene: getfit(gene)
    genes.sort(reverse=True, key=key)    ##先把原来的种群100按照适应度降序排列，然后，将交叉得到的32个个体替换到种群的最后32个
    pos = geneNum - 1
    for gene in crossedGenes:
        genes[pos] = gene
        pos -= 1
    return  genes

Mutation, first write how the individual mutates, and then mutate the entire crossed population according to the mutation probability.
Note: The mutation here is very simple, and a new individual is directly generated by the method of generating individuals in the initial population, but here also uses The method of generating a few more individuals and selecting the individual with the highest fitness to reduce the error.

# 变异一个
def varyOne(gene):
    varyNum = 10    
    variedGenes = []
    for i in range(varyNum):       # 先按照这种方法变异10个，选择适应度最高的那个作为变异完的子代
        p1, p2 = random.choices(list(range(1,len(gene)-2)), k=2)
        newGene = gene.copy()
        newGene[p1], newGene[p2] = newGene[p2], newGene[p1] # 交换
        variedGenes.append(newGene)
    key = lambda gene: getfit(gene)
    variedGenes.sort(reverse=True, key=key)
    return variedGenes[0]

# 变异
def vary(genes):
    for index, gene in enumerate(genes):
        # 精英主义，保留前三十，这个意思就是前三十个一定不变异，到后面的个体才按照变异概率来变异
        if index < 30:
            continue
        if np.random.rand() < PM:
            genes[index] = varyOne(gene)
    return genes

Genetic Algorithm Subject

import numpy as np
import random
from tqdm import *  # 进度条
import matplotlib.pyplot as plt
from pylab import *
mpl.rcParams['font.sans-serif'] = ['SimHei']
mpl.rcParams['axes.unicode_minus'] = False

best_fitness = []
min_cost = []
J = []
pop = getpop(length, geneNum)  # 初始种群
# 迭代
for j in tqdm(range(generationNum)):
    print('j=',j)
    chosen_pop = choose(pop)   # 选择   选择适应度值最高的前三分之一，也就是32个种群，进行下一步的交叉
    crossed_pop = cross(chosen_pop)   # 交叉
    pop = mergeGenes(pop, crossed_pop) # 复制交叉至子代种群
    pop = vary(pop) # under construction
    key = lambda gene: getfit(gene)
    pop.sort(reverse=True, key=key)  # 以fit对种群排序
    cost = 1/getfit(pop[0])
    print(cost)
    min_cost.append(cost)
    J.append(j)
print(J)
print(min_cost)


# key = lambda gene: getfit(gene)
# pop.sort(reverse=True, key=key)   # 以fit对种群排序
print('\r\n')
print('data:', pop[0])
print('fit:', 1/getfit(pop[0]))
plt.plot(J,min_cost, color='r')
plt.show()