遗传算法解决TSP问题需要改进

[YoshiPark]

使用scikit-opt的遗传算法模型解决TSP问题时，效果好像不理想，比如stplib数据库里面的att48.tsp时，跑出来的结果跟随机的顺序差不多，att48的链接如下：http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/att48.tsp
我的参数设置为：
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=300, max_iter=3000,prob_mut=0.1)
谢谢

[YoshiPark]

这是我实验跑出来的结果：
48 capitals of the US (Padberg/Rinaldi)
Simulated annealing Best distance: 33899.903615127725
Simulated annealing Average distance: 34430.13375274746
Genetic Algorithm Best distance: 87771.26994701447
Genetic Algorithm Average distance: 93383.70990490801
Ant Colony Alogorithm Best distance: 34956.61325328256
Ant Colony Alogorithm Average distance: 35598.34244140098
Solution distance: 33523.70850743559
GA算法跟其他算法跑出来的结果相差甚远，其他数据库也是类似，scikit的遗传算法解TSP问题效果不太理想

[guofei9987]

Now we have a better update using UDF

step1: define your problem (data is from your url)

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

points_coordinate = np.array(
    [
        [6734, 1453], [2233, 10], [5530, 1424], [401, 841], [3082, 1644], [7608, 4458], [7573, 3716], [7265, 1268],
        [6898, 1885], [1112, 2049], [5468, 2606], [5989, 2873], [4706, 2674], [4612, 2035], [6347, 2683], [6107, 669],
        [7611, 5184], [7462, 3590], [7732, 4723], [5900, 3561], [4483, 3369], [6101, 1110], [5199, 2182], [1633, 2809],
        [4307, 2322], [675, 1006], [7555, 4819], [7541, 3981], [3177, 756], [7352, 4506], [7545, 2801], [3245, 3305],
        [6426, 3173], [4608, 1198], [23, 2216], [7248, 3779], [7762, 4595], [7392, 2244], [3484, 2829], [6271, 2135],
        [4985, 140], [1916, 1569], [7280, 4899], [7509, 3239], [10, 2676], [6807, 2993], [5185, 3258], [3023, 1942]]
)

distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')

num_points = points_coordinate.shape[0]


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

step2: make up UDF and run

from sko.GA import GA_TSP


def reverse(self):
    for i in range(self.size_pop):
        if np.random.rand() < self.prob_mut:
            n1, n2 = np.random.randint(0, self.len_chrom - 1, 2)
            if n1 >= n2:
                n1, n2 = n2, n1 + 1
            self.Chrom[i, n1:n2] = self.Chrom[i, n1:n2][::-1]
    return self.Chrom


def run(self, max_iter=None):
    self.max_iter = max_iter or self.max_iter
    for i in range(self.max_iter):
        Chrom_old = self.Chrom.copy()
        self.X = self.chrom2x()
        self.Y = self.x2y()
        self.ranking()
        self.selection()
        self.crossover()
        self.mutation()

        # put parent and offspring together and select the best size_pop number of population
        self.Chrom = np.concatenate([Chrom_old, self.Chrom], axis=0)
        self.X = self.chrom2x()
        self.Y = self.x2y()
        self.ranking()
        selected_idx = np.argsort(self.Y)[:self.size_pop]
        self.Chrom = self.Chrom[selected_idx, :]

        # record the best ones
        generation_best_index = self.FitV.argmax()
        self.generation_best_X.append(self.X[generation_best_index, :])
        self.generation_best_Y.append(self.Y[generation_best_index])
        self.all_history_Y.append(self.Y)
        self.all_history_FitV.append(self.FitV)

    global_best_index = np.array(self.generation_best_Y).argmin()
    global_best_X = self.generation_best_X[global_best_index]
    global_best_Y = self.func(global_best_X)
    return global_best_X, global_best_Y


ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)

ga_tsp.register('mutation', reverse). \
    register('run', run)

best_points, best_distance = ga_tsp.run()

step3: plot the result

fig, ax = plt.subplots(1, 1)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax.plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
plt.show()

plt.figure(2)

plt.plot(ga_tsp.generation_best_Y)

Looks great! May better set those as default.

@YoshiPark

---

The old answer:
prob_mut 不宜过大，这个概率代表的是每个基因变异的概率，而不是整条染色体变异的概率。

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=300, max_iter=800, prob_mut=0.001)

distance: 47864.13182497867

有所改进，但效果还是比其它算法差。
对于较长的路径，GA需要有一些改进策略，这是最近打算做的。

[guofei9987]

version 0.5.3 has set the above as default GA_TSP

[YoshiPark]

Thank You!

[guofei9987]

感谢你提交的bug，是否允许在未来的正式版本 scikit-opt 1.0 把你列为 contributor 呢？