遗传算法--基础VRP--白话文版笔记（附逐句详细解释）_vrp问题归一化

#随机选择一段路径，并把路径移到最左边
 
def moveRandSubPathLeft(gene):
    import random
    path = random.randrange(k)  # 选择路径索引，随机分成k段
    print('path:',path)
    try:
        index = gene.index(CENTER, path+1) #移动到所选索引
       
        # 移动第一个配送中心
        locToInsert = 0
        gene.insert(locToInsert, gene.pop(index))
        index += 1
        locToInsert += 1
       
        # 移动此配送中心后的数据
        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

try:
    # 尝试执行的代码块
except ExceptionType:
    # 当发生指定类型的异常时执行的代码块
finally:
    # 无论是否发生异常，都会执行的代码块（可选）

# 创建一个列表
my_list = [1, 2, 3, 4, 5]
 
# 获取元素3的索引位置
index = my_list.index(3)
print(index)  # 输出：2
 
# 获取元素6的索引位置（不存在）
try:
    index = my_list.index(6)
    print(index)
except ValueError:
    print("元素6不存在于列表中")  # 输出："元素6不存在于列表中"

def choose(pop):
    num = int(geneNum/6) * 2             # 选择偶数个，方便下一步交叉
    key = lambda gene: getfit(gene)      # 获得个体的适应度值记作key
    pop.sort(reverse=True, key=key)      # 把pop用sort()函数降序排序, 按可选参数key排序
   # return shuffled top 1/3   
    return pop[0:num]

##交叉一对
def crossPair(i,gene1, gene2, crossedGenes):
    gene1 = moveRandSubPathLeft(gene1)    #这是已经处理好的个体
    gene2 = moveRandSubPathLeft(gene2)
    newGene1 = []
    newGene2 = []
 
   # copy first paths
    centers = 0                     # 记录中心点的数量
    firstPos1 = 1                   # 记录中心点的位置
    
# 遍历gene1，将前两个中心点及其之间的元素添加到newGene1中，并更新centers和firstPos1的值。
    for pos in gene1:
        firstPos1 += 1         #firstPos1表示当前处理的中心点的位置
        centers += (pos == CENTER)  #如果pos等于CENTER，则 centers的值增加 1；否则不变。
        newGene1.append(pos)
        if centers >= 2:
            break
# 同理处理gene2中的数据
    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:                   #如果possible2列表为空，说明没有找到合适的新基因序列。
            crossedGenes.append(newGene2)         #将原始基因序列添加到crossedGenes列表中
        else:
            possible2.sort(reverse=True, key=key2)#根据适应度对possible2列表进行降序排序。
            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

# 变异一个
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:            # 以PM的概率变异
            genes[index] = varyOne(gene)     # 更新
    return genes                             # 返回变异后的基因
 

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)
print('\r\n')
print('data:', pop[0])
print('fit:', 1/getfit(pop[0]))
plt.plot(J,min_cost, color='r')
plt.show()