遗传算法详解 附python
时间: 2023-09-19 16:05:42 浏览: 59
遗传算法是一种受生物进化理论启发的优化算法,用于求解复杂的优化问题。它模拟了自然界中的进化过程,通过逐代演化产生出越来越好的解。
遗传算法的基本步骤包括:
1. 初始化种群:随机生成一组初始解作为种群。
2. 适应度评估:根据问题的特定目标函数,计算每个个体的适应度,评估其优劣。
3. 选择操作:根据适应度,选择一些个体作为下一代的父代。
4. 交叉操作:对选中的父代进行交叉操作,生成子代个体。
5. 变异操作:对子代中的个体进行变异操作,引入新的基因组合。
6. 替换操作:使用选择策略,将子代替换原来的父代,形成新的种群。
7. 终止条件判断:根据预设的终止条件(如达到指定迭代次数或找到满意解等),决定是否结束算法。
8. 返回结果:返回最优解或符合约束条件的解。
以下是一个简单的遗传算法的Python示例代码:
```python
import random
# 适应度评估函数
def evaluate(solution):
# 根据问题的特定目标函数计算适应度
# 这里以求解函数 f(x) = x^2 为例
fitness = solution ** 2
return fitness
# 初始化种群
def initialize_population(population_size, chromosome_length):
population = []
for _ in range(population_size):
# 随机生成一个个体(解)
chromosome = [random.randint(0, 1) for _ in range(chromosome_length)]
population.append(chromosome)
return population
# 选择操作(简单的轮盘赌选择)
def selection(population, fitness_values):
total_fitness = sum(fitness_values)
probabilities = [fitness / total_fitness for fitness in fitness_values]
selected_indices = []
for _ in range(len(population)):
r = random.random() # 生成0到1之间的随机数
cumulative_prob = 0
for i, prob in enumerate(probabilities):
cumulative_prob += prob
if r <= cumulative_prob:
selected_indices.append(i)
break
selected_population = [population[i] for i in selected_indices]
return selected_population
# 交叉操作(单点交叉)
def crossover(parent1, parent2):
crossover_point = random.randint(1, len(parent1) - 1)
child1 = parent1[:crossover_point] + parent2[crossover_point:]
child2 = parent2[:crossover_point] + parent1[crossover_point:]
return child1, child2
# 变异操作(位翻转)
def mutation(individual, mutation_rate):
mutated_individual = []
for gene in individual:
if random.random() < mutation_rate:
mutated_individual.append(1 - gene) # 翻转基因
else:
mutated_individual.append(gene)
return mutated_individual
# 主函数
def genetic_algorithm(population_size, chromosome_length, max_iterations):
population = initialize_population(population_size, chromosome_length)
iteration = 0
while iteration < max_iterations:
fitness_values = [evaluate(solution) for solution in population]
selected_population = selection(population, fitness_values)
new_population = []
while len(new_population) < population_size:
parent1, parent2 = random.sample(selected_population, 2) # 随机选择两个父代
child1, child2 = crossover(parent1, parent2) # 交叉操作
child1 = mutation(child1, mutation_rate=0.01) # 变异操作
child2 = mutation(child2, mutation_rate=0.01)
new_population.append(child1)
new_population.append(child2)
population = new_population
iteration += 1
best_solution = max(population, key=evaluate)
best_fitness = evaluate(best_solution)
return best_solution, best_fitness
# 示例运行
best_solution, best_fitness = genetic_algorithm(population_size=100, chromosome_length=10, max_iterations=100)
print('Best Solution:', best_solution)
print('Best Fitness:', best_fitness)
```
这个示例代码展示了一个简单的遗传算法实现,用于求解一个二进制编码的最优解,目标函数为 f(x) = x^2。在初始化种群、选择、交叉、变异等操作中,可以根据具体问题进行调整。