python写基于遗传算法的tsp问题
时间: 2023-11-04 07:04:03 浏览: 31
以下是一个基于遗传算法的TSP问题的Python代码示例:
```python
import random
# 遗传算法参数
POPULATION_SIZE = 20
MUTATION_RATE = 0.1
ELITISM_COUNT = 2
# TSP问题参数
CITIES = [(60, 200), (180, 200), (80, 180), (140, 180), (20, 160), (100, 160), (200, 160), (140, 140), (40, 120), (100, 120), (180, 100), (60, 80), (120, 80), (180, 60), (20, 40), (100, 40), (200, 40), (20, 20), (60, 20), (160, 20)]
# 计算两个城市之间的距离
def distance(city1, city2):
x1, y1 = city1
x2, y2 = city2
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
# 计算每个个体的适应度
def fitness(individual):
distance_sum = 0
for i in range(len(individual) - 1):
distance_sum += distance(CITIES[individual[i]], CITIES[individual[i+1]])
distance_sum += distance(CITIES[individual[-1]], CITIES[individual[0]])
return 1 / distance_sum
# 生成随机个体
def create_individual():
individual = list(range(len(CITIES)))
random.shuffle(individual)
return individual
# 生成初始种群
def create_population():
return [create_individual() for _ in range(POPULATION_SIZE)]
# 交叉操作
def crossover(parent1, parent2):
child = [None] * len(parent1)
start = random.randint(0, len(parent1) - 1)
end = random.randint(0, len(parent1) - 1)
if start > end:
start, end = end, start
for i in range(start, end + 1):
child[i] = parent1[i]
j = 0
for i in range(len(parent2)):
if not parent2[i] in child:
if child[j] is None:
child[j] = parent2[i]
j += 1
else:
j += 1
return child
# 变异操作
def mutate(individual):
for i in range(len(individual)):
if random.random() < MUTATION_RATE:
j = random.randint(0, len(individual) - 1)
individual[i], individual[j] = individual[j], individual[i]
return individual
# 选择操作
def selection(population):
fitnesses = [fitness(individual) for individual in population]
sorted_fitnesses = sorted(fitnesses, reverse=True)
mating_pool = []
for i in range(ELITISM_COUNT):
index = fitnesses.index(sorted_fitnesses[i])
mating_pool.append(population[index])
for i in range(POPULATION_SIZE - ELITISM_COUNT):
index1 = fitnesses.index(sorted_fitnesses[random.randint(0, POPULATION_SIZE - 1)])
index2 = fitnesses.index(sorted_fitnesses[random.randint(0, POPULATION_SIZE - 1)])
mating_pool.append(crossover(population[index1], population[index2]))
return mating_pool
# 主函数
def main():
population = create_population()
for generation in range(100):
population = selection(population)
population = [mutate(individual) for individual in population]
print("Generation", generation + 1, "Best fitness:", fitness(population[0]))
print("Best individual:", population[0])
if __name__ == "__main__":
main()
```
该代码中,我们首先定义了TSP问题的城市坐标和遗传算法的参数(种群大小、变异率、精英数量)。然后我们定义了计算两个城市之间距离的函数、计算个体适应度的函数、生成随机个体和初始种群的函数。接着我们定义了交叉、变异和选择操作的函数。最后我们在主函数中进行100代遗传算法,并输出每代最佳个体的适应度和最佳个体。