遗传算法最短路径python
时间: 2023-10-29 09:55:56 浏览: 104
遗传算法做最短路径
遗传算法可以用于解决最短路径问题。下面是一个使用遗传算法求解最短路径的示例代码(Python):
```python
import random
class Individual:
def __init__(self, chromosome, graph):
self.chromosome = chromosome
self.fitness = self.calculate_fitness(graph)
def calculate_fitness(self, graph):
distance = 0
for i in range(len(self.chromosome) - 1):
distance += graph[self.chromosome[i]][self.chromosome[i+1]]
return distance
def generate_chromosome(num_nodes):
chromosome = list(range(num_nodes))
random.shuffle(chromosome)
return chromosome
def crossover(parent1, parent2):
crossover_point = random.randint(1, len(parent1) - 2)
child1 = parent1[:crossover_point] + [gene for gene in parent2 if gene not in parent1[:crossover_point]]
child2 = parent2[:crossover_point] + [gene for gene in parent1 if gene not in parent2[:crossover_point]]
return child1, child2
def mutate(chromosome):
index1 = random.randint(0, len(chromosome) - 1)
index2 = random.randint(0, len(chromosome) - 1)
chromosome[index1], chromosome[index2] = chromosome[index2], chromosome[index1]
def genetic_algorithm(graph, population_size, num_generations):
num_nodes = len(graph)
population = []
for _ in range(population_size):
chromosome = generate_chromosome(num_nodes)
individual = Individual(chromosome, graph)
population.append(individual)
for generation in range(num_generations):
population.sort(key=lambda x: x.fitness)
new_population = population[:population_size // 2]
while len(new_population) < population_size:
parent1 = random.choice(population[:population_size // 2])
parent2 = random.choice(population[:population_size // 2])
child1, child2 = crossover(parent1.chromosome, parent2.chromosome)
mutate(child1)
mutate(child2)
new_population.append(Individual(child1, graph))
new_population.append(Individual(child2, graph))
population = new_population
population.sort(key=lambda x: x.fitness)
best_individual = population[0]
return best_individual.chromosome, best_individual.fitness
# 示例使用
graph = [
[0, 2, 4, 1],
[2, 0, 1, 3],
[4, 1, 0, 2],
[1, 3, 2, 0]
]
population_size = 50
num_generations = 100
best_path, shortest_distance = genetic_algorithm(graph, population_size, num_generations)
print("最短路径:", best_path)
print("最短距离:", shortest_distance)
```
这段代码实现了一个基本的遗传算法来求解最短路径问题。在示例代码中,`graph` 是一个表示节点之间距离的邻接矩阵,`population_size` 是种群大小,`num_generations` 是迭代次数。运行代码后,会输出找到的最短路径和对应的最短距离。
请注意,这只是一个简单的示例,实际情况下可能需要根据具体问题进行调整和优化。
阅读全文