【进化计算】遗传算法求解gr48数据集

rand50 : 5553
rand75 : 7054
rand100 : 7891
rand200 : 10649
rand300 : 11865
rand400 : 14722
rand400b : 144595
a280 : 2579 
ali535 : 202339 
att48 : 33522 
att532 : 86729 
bayg29 : 1610 
bays29 : 2020 
berlin52 : 7542 
bier127 : 118282 
brazil58 : 25395 
brd14051 : 469385 
brg180 : 1950 
burma14 : 3323
chn31 : 15377 
ch130 : 6110 
ch150 : 6528 
d198 : 15780 
d493 : 35002 
d657 : 48912 
d1291 : 50801 
d1655 : 62128 
d2103 : 80450 
d15112 : 1573084 
d18512 : 645238
dantzig42 : 699 
dsj1000 : 18659688
dsj1000 : 18660188
eil51 : 426 
eil76 : 538 
eil101 : 629 
fl417 : 11861 
fl1400 : 20127 
fl1577 : 22249 
fl3795 : 28772 
fnl4461 : 182566 
fri26 : 937 
gil262 : 2378 
gr17 : 2085 
gr21 : 2707 
gr24 : 1272 
gr48 : 5046 
gr96 : 55209 
gr120 : 6942 
gr137 : 69853 
gr202 : 40160 
gr229 : 134602 
gr431 : 171414 
gr666 : 294358 
hk48 : 11461 
kroA100 : 21282 
kroB100 : 22141 
kroC100 : 20749 
kroD100 : 21294 
kroE100 : 22068 
kroA150 : 26524 
kroB150 : 26130 
kroA200 : 29368 
kroB200 : 29437 
lin105 : 14379 
lin318 : 42029 
linhp318 : 41345 
nrw1379 : 56638 
oliver30 : 420
p654 : 34643 
pa561 : 2763 
pcb442 : 50778 
pcb1173 : 56892 
pcb3038 : 137694 
pla7397 : 23260728 
pla33810 : 66048945 
pla85900 : 142382641 
pr76 : 108159 
pr107 : 44303 
pr124 : 59030 
pr136 : 96772 
pr144 : 58537 
pr152 : 73682 
pr226 : 80369 
pr264 : 49135 
pr299 : 48191 
pr439 : 107217 
pr1002 : 259045 
pr2392 : 378032 
rat99 : 1211 
rat195 : 2323 
rat575 : 6773 
rat783 : 8806 
rd100 : 7910 
rd400 : 15281 
rl1304 : 252948 
rl1323 : 270199 
rl1889 : 316536 
rl5915 : 565530 
rl5934 : 556045 
rl11849 : 923288 
si175 : 21407 
si535 : 48450 
si1032 : 92650 
st70 : 675 
swiss42 : 1273 
ts225 : 126643 
tsp225 : 3916 
u159 : 42080 
u574 : 36905 
u724 : 41910 
u1060 : 224094 
u1432 : 152970 
u1817 : 57201 
u2152 : 64253 
u2319 : 234256 
ulysses16 : 72
ulysses22 : 74 
usa13509 : 19982859 
vm1084 : 239297 
vm1748 : 336556 

def load_data(cityNum, file_path):
    with open(file_path, 'r', encoding='utf-8') as f:
        context = f.read()
        # print(context)
        # 根据换行进行分隔
        row_list = context.splitlines()
        data_list = []
        for row in row_list:
            for i in row.strip().split(" "):
                data_list.append(int(i))
    distance = np.zeros([cityNum, cityNum])
    # 遍历data[]，填入distance[][]
    p = 0
    for i in range(cityNum):
        for j in range(cityNum):
            distance[i][j] = data_list[p]
            distance[j][i] = data_list[p]
            p += 1
            # 每行读到"0"跳出列循环，到下一行
            if data_list[p - 1] == 0:
                break
    return distance

import time
import numpy as np
import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif'] = ["SimHei"]

# 载入数据
def load_data(cityNum, file_path):
    with open(file_path, 'r', encoding='utf-8') as f:
        context = f.read()
        # print(context)
        # 根据换行进行分隔
        row_list = context.splitlines()
        data_list = []
        for row in row_list:
            for i in row.strip().split(" "):
                data_list.append(int(i))
    distance = np.zeros([cityNum, cityNum])
    # 遍历data[]，填入distance[][]
    p = 0
    for i in range(cityNum):
        for j in range(cityNum):
            distance[i][j] = data_list[p]
            distance[j][i] = data_list[p]
            p += 1
            # 每行读到"0"跳出列循环，到下一行
            if data_list[p - 1] == 0:
                break
    return distance

# 初始化种群
def rand_pop(city_num, pop_num, pop, distance, matrix_distance):
    rand_ch = np.array(range(city_num))
    for i in range(pop_num):
        np.random.shuffle(rand_ch)
        pop[i, :] = rand_ch
        distance[i] = comp_dis(city_num, matrix_distance, rand_ch)  # 这里的适应度其实是距离

# 计算每个个体的总距离
def comp_dis(city_num, matrix_distance, one_path):
    res = 0
    for i in range(city_num - 1):
        res += matrix_distance[one_path[i], one_path[i + 1]]
    res += matrix_distance[one_path[-1], one_path[0]]  # 最后一个城市和第一个城市的距离，需单独处理
    return res

# 打印最优城市编码
def print_path(city_num, one_path):
    bm = [str(one_path[0] + 1)]
    for i in range(1, city_num):
        bm.append(str(one_path[i] + 1))
    print("最优解城市编码为：")
    print(bm)

# 轮盘赌的方式选择子代
def select_sub(pop_num, pop, distance):
    fit = 1. / distance  # 适应度函数
    p = fit / sum(fit)
    q = p.cumsum()  # 累积概率
    select_id = []
    for i in range(pop_num):
        r = np.random.rand()  # 产生一个[0,1)的随机数
        for j in range(pop_num):
            if r < q[0]:
                select_id.append(0)
                break
            elif q[j] < r <= q[j + 1]:
                select_id.append(j + 1)
                break
    next_gen = pop[select_id, :]
    return next_gen

# 交叉操作-每个个体对的某一位置进行交叉
def cross_sub(city_num, pop_num, next_gen, cross_prob, evbest_path):
    for i in range(0, pop_num):
        best_gen = evbest_path.copy()
        if cross_prob >= np.random.rand():
            next_gen[i, :], best_gen = intercross(city_num, next_gen[i, :], best_gen)

# 具体的交叉方式：部分映射交叉(Partial-Mapped Crossover)
def intercross(city_num, ind_a, ind_b):
    r1 = np.random.randint(city_num)
    r2 = np.random.randint(city_num)
    while r2 == r1:
        r2 = np.random.randint(city_num)
    left, right = min(r1, r2), max(r1, r2)
    ind_a1 = ind_a.copy()
    ind_b1 = ind_b.copy()
    for i in range(left, right + 1):
        ind_a2 = ind_a.copy()
        ind_b2 = ind_b.copy()
        ind_a[i] = ind_b1[i]
        ind_b[i] = ind_a1[i]
        # 每个个体包含的城市序号是唯一的，因此交叉时若两个不相同，就会产生冲突
        x = np.argwhere(ind_a == ind_a[i])
        y = np.argwhere(ind_b == ind_b[i])
        # 产生冲突，将不是交叉区间的数据换成换出去的原数值，保证城市序号唯一
        if len(x) == 2:
            ind_a[x[x != i]] = ind_a2[i]
        if len(y) == 2:
            ind_b[y[y != i]] = ind_b2[i]
    return ind_a, ind_b

# 变异方式：翻转变异
def mutation_sub(city_num, pop_num, next_gen, mut_prob):
    for i in range(pop_num):
        if mut_prob >= np.random.rand():
            r1 = np.random.randint(city_num)
            r2 = np.random.randint(city_num)
            while r2 == r1:
                r2 = np.random.randint(city_num)
            if r1 > r2:
                temp = r1
                r1 = r2
                r2 = temp
            next_gen[i, r1:r2] = next_gen[i, r1:r2][::-1]

# 局部搜索:随机找两个点位交换
def local_search(city_num, pop_num, next_gen):
    for i in range(pop_num):
        r1 = np.random.randint(city_num)
        r2 = np.random.randint(city_num)
        while r2 == r1:
            r2 = np.random.randint(city_num)
        if r1 > r2:
            temp = next_gen[i, r1]
            next_gen[i, r1] = next_gen[i, r2]
            next_gen[i, r2] = temp

def main(seed):
    np.random.seed(seed)
    # 加载距离矩阵
    city_num = 48
    file_path = 'dataset/gr48.txt'
    matrix_distance = load_data(city_num, file_path)

    pop_num = 1000  # 群体个数
    cross_prob = 0.99  # 交叉概率
    mut_prob = 0.99  # 变异概率
    iteration = 100000  # 迭代代数

    # 初始化初代种群和距离，个体为整数，距离为浮点数
    pop = np.array([0] * pop_num * city_num).reshape(pop_num, city_num)
    distance = np.zeros(pop_num)
    # 初始化种群
    rand_pop(city_num, pop_num, pop, distance, matrix_distance)
    evbest_path = pop[0]
    evbest_distance = float("inf")
    best_path_list = []
    best_distance_list = []

    answer = ['10', '12', '31', '5', '33', '8', '22', '21', '17', '27', '32', '9', '14', '6', '26', '36', '11', '16', '48', '13', '1', '29', '7', '28', '44', '41', '46', '18', '34', '23', '25', '3', '19', '4', '30', '38', '20', '35', '42', '39', '40', '2', '45', '43', '47', '37', '24', '15']

    # 循环迭代遗传过程
    for i in range(iteration):
        # 选择
        next_gen = select_sub(pop_num, pop, distance)
        # 交叉
        cross_sub(city_num, pop_num, next_gen, cross_prob, evbest_path)
        # 变异
        mutation_sub(city_num, pop_num, next_gen, mut_prob)
        # 局部搜索(在每个个体附近领域寻找局部最优解)
        local_search(city_num, pop_num, next_gen)

        # 计算每个个体适应度
        for j in range(pop_num):
            distance[j] = comp_dis(city_num, matrix_distance, next_gen[j, :])
        index = distance.argmin()  # index 记录最小总路程

        # 为了防止曲线波动，每次记录最优值，如迭代后出现退化，则将当前最好的个体回退替换为历史最佳
        if distance[index] <= evbest_distance:
            evbest_distance = distance[index]
            evbest_path = next_gen[index, :]
        else:
            distance[index] = evbest_distance
            next_gen[index, :] = evbest_path

        # 存储每一步的最优路径(个体)及距离
        best_path_list.append(evbest_path)
        best_distance_list.append(evbest_distance)

        if i % 1000 == 0:
            print(i, "最佳距离为:", evbest_distance)

    best_path = evbest_path
    best_distance = evbest_distance

    # 指定10为起始点
    start_point = 10
    split_index = int(np.argwhere(best_path == start_point - 1))
    best_path = np.hstack((best_path[split_index:], (best_path[:split_index])))

    # 迭代完成，打印出最佳路径
    print_path(city_num, best_path)
    output_path = [i+1 for i in best_path]
    answer_right = 0
    for i, j in enumerate(output_path):
        if j == int(answer[i]):
            answer_right += 1
    print("准确的个数为", answer_right)
    print("当前最佳距离为:", best_distance)


if __name__ == '__main__':
    seed = 68
    print("编程语言：Python")
    start_time = time.time()
    main(seed)
    print("算法运行时间：", time.time() - start_time, "秒")