遗传算法的应用示例代码

遗传算法（Genetic Algorithm, GA）是一种模拟自然选择和遗传机制的优化搜索方法，常用于解决复杂优化问题。以下是一个简单的遗传算法应用示例，用Python实现了一个简单的“旅行商问题”（Traveling Salesman Problem, TSP）求解器：

import random
import numpy as np

# 旅行商问题数据
cities = [(0, 0), (10, 0), (20, 20), (0, 20)]

# 函数计算两点间的距离
def distance(city1, city2):
    return np.sqrt((city1 - city2)**2 + (city1 - city2)**2)

# 初始化种群
population_size = 50
routes = [random.sample(cities, len(cities)) for _ in range(population_size)]
route_lengths = [sum(distance(city1, city2) for city1, city2 in zip(route[:-1], route[1:])) + distance(route[-1], route) for route in routes]

# 遗传操作
def crossover(parent1, parent2):
    mid = random.randint(1, len(routes) - 1)
    offspring1 = parent1[:mid] + parent2[mid:]
    offspring2 = parent2[:mid] + parent1[mid:]
    return offspring1, offspring2

def mutation(route):
    index1, index2 = random.sample(range(len(route)), 2)
    route[index1], route[index2] = route[index2], route[index1]
    return route

def evolve_population():
    new_population = []
    while len(new_population) < population_size:
        parent1, parent2 = random.choices(routes, weights=route_lengths, k=2)
        offspring1, offspring2 = crossover(parent1, parent2)
        offspring1 = mutation(offspring1)
        offspring2 = mutation(off offspring2)
        new_population.extend([offspring1, offspring2])
    return new_population

# 迭代优化
best_route = routes
for _ in range(100):  # 设置迭代次数
    new_population = evolve_population()
    best_route_length = min(map(lambda x: route_lengths[x], new_population))
    best_route = new_population[route_lengths.index(best_route_length)]

print(f"最优路线: {best_route}")
print(f"最短路线长度: {best_route_length} (单位：距离)")