如何用遗传算法求解：带时间窗和旅行距离约束的开放式TSP问题（不返回起点）

Question

请指导：
在下面PYTHON代码的基础上，使用遗传算法（改进的遗传算法更好），在各目标点的时间窗，以及旅行商最大旅行距离的约束条件下，求解最佳TSP路径（并在图上显示），使得访问的目标点数量最多。

import matplotlib.pyplot as plt
import numpy as np
from matplotlib.pylab import mpl

mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这俩条可以让图形显示中文

# 定义10个目标点坐标数据
citys = np.zeros((10, 2))
x_c = np.random.uniform(1, 10, 10)  # 在(1,10)中取出10个随机数
y_c = np.random.uniform(1, 10, 10)  # 在(1,10)中取出10个随机数
for i in range(10):
    citys[i] = [x_c[i], y_c[i]]

# 定义旅行商出发点坐标
start_point = [5., 5.]

# 定义时间窗和距离约束条件
citys_travel_time = [10, 10, 10, 10, 10, 20, 20, 20, 20, 20]  # 各目标点的访问耗时(min)
citys_end_time = [120, 120, 120, 150, 150, 150, 150, 180, 180, 180]  # 各目标点允许的最晚访问时限(min)
max_travel_dist = 16  # 最大旅行距离为16(km)
speed = 0.1  # 旅行商的速度为0.1 km/min

# 求解最佳路线，使得访问目标点数量最大化
'''
    使用遗传算法（改进的遗传算法更好），在各目标点的时间窗，以及旅行商最大旅行距离的约束条件下，
求解最佳路径（并在图上显示），使得访问的目标点数量最多。
'''

# 绘图
plt.figure(figsize=(8, 8))  # figsize:确定画布大小
# 绘制目标点
for i in range(10):  
    plt.scatter(x_c[i],  # 横坐标
                y_c[i],  # 纵坐标
                s=100,
                c='b',  # 点的颜色
                label='目标点')  # 标签 即为点代表的意思
# 绘制出发点
plt.scatter(start_point[0],  # 横坐标
            start_point[1],  # 纵坐标
            s=400,
            c='r',  # 点的颜色
            label='出发点')  # 标签 即为点代表的意思

plt.xlim(0, 11)
plt.ylim(0, 11)
plt.xlabel('x轴（km）', fontsize=14)
plt.ylabel('y轴（km）', fontsize=14)
plt.show()

Answer 1

import numpy as np
from scipy.spatial.distance import pdist, squareform
import matplotlib.pyplot as plt

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

# 定义遗传算法类
class GeneticAlgorithm:
    def __init__(self, city_coords, start_point, max_travel_dist, city_times, end_times, speed, population_size=100,
                 mutation_rate=0.01, generations=500):
        self.city_coords = city_coords
        self.start_point = start_point
        self.max_travel_dist = max_travel_dist
        self.city_travel_times = city_times
        self.city_end_times = end_times
        self.speed = speed
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        self.generations = generations
        self.distance_matrix = squareform(pdist(city_coords))  # 计算城市间距离矩阵
        self.num_cities = city_coords.shape[0]
        self.population = self.init_population()

    def init_population(self):
        population = []
        for _ in range(self.population_size):
            individual = np.random.permutation(self.num_cities)
            population.append(individual)
        return np.array(population)

    def fitness(self, individual):
        total_dist = np.sum(
            [self.distance_matrix[individual[i], individual[i + 1]] for i in range(len(individual) - 1)])
        total_dist += np.linalg.norm(self.start_point - self.city_coords[individual[0]])  # 开始到第一个城市
        total_dist += np.linalg.norm(self.start_point - self.city_coords[individual[-1]])  # 最后一个城市到开始

        total_time = np.sum([self.city_travel_times[individual[i]] for i in range(len(individual))])
        total_time += total_dist / self.speed

        time_elapsed = 0
        visited_cities = 0
        for idx in individual:
            travel_time = np.linalg.norm(
                self.start_point - self.city_coords[idx]) / self.speed if visited_cities == 0 else self.distance_matrix[
                                                                                                       individual[
                                                                                                           visited_cities - 1], idx] / self.speed
            time_elapsed += travel_time + self.city_travel_times[idx]
            if time_elapsed > self.city_end_times[idx]:
                break
            visited_cities += 1

        return visited_cities - total_dist / self.max_travel_dist

    def select(self):
        tournament_size = 5
        selected_indices = np.random.choice(range(self.population_size), tournament_size, replace=False)
        tournament = self.population[selected_indices]
        fitness_scores = np.array([self.fitness(individual) for individual in tournament])
        winner_index = np.argmax(fitness_scores)
        return tournament[winner_index]

    def crossover(self, parent1, parent2):
        start, end = sorted(np.random.choice(range(self.num_cities), 2, replace=False))
        offspring = -np.ones(self.num_cities, dtype=int)
        offspring[start:end] = parent1[start:end]
        pointer = end
        for gene in parent2:
            if gene not in offspring:
                if pointer >= self.num_cities:
                    pointer = 0
                offspring[pointer] = gene
                pointer += 1
        return offspring

    def mutate(self, individual):
        if np.random.rand() < self.mutation_rate:
            swap_indices = np.random.choice(range(self.num_cities), 2, replace=False)
            individual[swap_indices] = individual[swap_indices[::-1]]
        return individual

    def evolve(self):
        new_population = []
        for _ in range(self.population_size):
            parent1 = self.select()
            parent2 = self.select()
            offspring = self.crossover(parent1, parent2)
            offspring = self.mutate(offspring)
            new_population.append(offspring)
        self.population = np.array(new_population)

    def run(self):
        best_fitness = -np.inf
        best_path = None
        for generation in range(self.generations):
            self.evolve()
            for individual in self.population:
                current_fitness = self.fitness(individual)
                if current_fitness > best_fitness:
                    best_fitness = current_fitness
                    best_path = individual
        return best_path, best_fitness


# 根据问题设置参数
city_coords = np.zeros((10, 2))  # 初始化城市坐标数组
x_c = np.random.uniform(1, 10, 10)  # 生成x坐标
y_c = np.random.uniform(1, 10, 10)  # 生成y坐标
for i in range(10):
    city_coords[i] = [x_c[i], y_c[i]]  # 填充城市坐标

start_point = np.array([5., 5.])  # 设置旅行商的起始点坐标
max_travel_dist = 16  # 设置最大旅行距离(km)
city_times = [10, 10, 10, 10, 10, 20, 20, 20, 20, 20]  # 设置每个城市的访问时间(min)
end_times = [120, 120, 120, 150, 150, 150, 150, 180, 180, 180]  # 设置每个城市的最晚访问时间(min)
speed = 0.1  # 设置旅行速度(km/min)

# 实例化遗传算法类
ga = GeneticAlgorithm(city_coords, start_point, max_travel_dist, city_times, end_times, speed, population_size=100,
                      mutation_rate=0.01, generations=100)
best_path, best_fitness = ga.run()

# 转换最佳路径为坐标用于绘图
best_path_coords = np.array([city_coords[i] for i in best_path])

# 绘制最佳路径
plt.figure(figsize=(10, 10))
plt.scatter(city_coords[:, 0], city_coords[:, 1], c='b', s=100)
plt.scatter(start_point[0], start_point[1], c='r', s=200, marker='*')
for i in range(len(best_path_coords) - 1):
    plt.plot([best_path_coords[i][0], best_path_coords[i + 1][0]], [best_path_coords[i][1], best_path_coords[i + 1][1]],
             'c--')
plt.plot([start_point[0], best_path_coords[0][0]], [start_point[1], best_path_coords[0][1]], 'g--')
plt.plot([start_point[0], best_path_coords[-1][0]], [start_point[1], best_path_coords[-1][1]], 'g--')
plt.title('遗传算法找到的最佳TSP路径')
plt.xlabel('x轴（km）')
plt.ylabel('y轴（km）')
plt.show()

print("最佳路径:", best_path)
print("最佳适应度分数:", best_fitness)