遗传算法是一种模拟自然选择和遗传机制的搜索启发式算法，广泛应用于解决优化和搜索问题。它模仿生物进化过程中的遗传学机制，包括选择、交叉（杂交）和变异等操作。遗传算法主要由以下几个步骤组成：初始化种群、评估适应度、选择、交叉、变异以及终止条件。
遗传算法的基本流程
1. 初始化种群：随机生成一个初始解集，每个解称为一个个体。个体可以是数值型或字符串形式，取决于问题的性质。
2. 评估适应度：根据预定的目标函数计算每个个体的适应度值。适应度值反映了个体在解决问题上的表现，值越大表示该个体越优。
3. 选择：基于适应度值从当前种群中选择一些个体作为下一代的父母。常见的选择方法有轮盘赌选择、锦标赛选择等。
4. 交叉：将选中的父母进行配对，通过交换部分基因来产生新的后代。交叉概率决定了交叉发生的频率。
5. 变异：以一定的变异概率随机改变后代的一部分基因，增加种群多样性，防止过早收敛于局部最优解。
6. 终止条件：当达到预设的迭代次数或适应度达到预期目标时，算法停止运行，并输出最优解。
Python示例代码
下面是一个简单的遗传算法实现，用于求解一个简单的数学问题，如找到函数$f(x) = x^2 - 4x + 4$的最大值。
```python
import random
def fitness(x):
return -(x2 - 4x + 4) 负号是因为我们希望最大化这个函数
def generate_population(size, low, high):
return [random.uniform(low, high) for _ in range(size)]
def select_parents(population, fitnesses):
total_fitness = sum(fitnesses)
probabilities = [f/total_fitness for f in fitnesses]
parents = random.choices(population, weights=probabilities, k=2)
return parents
def crossover(parent1, parent2):
alpha = random.random()
child1 = alpha parent1 + (1 - alpha) parent2
child2 = alpha parent2 + (1 - alpha) parent1
return child1, child2
def mutate(individual, mutation_rate):
if random.random() < mutation_rate:
mutation_amount = random.uniform(-1, 1)
individual += mutation_amount
return individual
主程序
population_size = 100
mutation_rate = 0.01
generations = 100
low_bound, high_bound = -10, 10
population = generate_population(population_size, low_bound, high_bound)
for generation in range(generations):
fitnesses = [fitness(x) for x in population]
new_population = []
while len(new_population) < population_size:
parent1, parent2 = select_parents(population, fitnesses)
child1, child2 = crossover(parent1, parent2)
child1 = mutate(child1, mutation_rate)
child2 = mutate(child2, mutation_rate)
new_population.extend([child1, child2])
population = new_population
best_solution = max(population, key=fitness)
print("Best solution found: ", best_solution, "with fitness:", fitness(best_solution))
```
此代码段展示了遗传算法的基本框架，包括种群初始化、适应度计算、选择、交叉、变异等步骤。通过调整参数，如种群大小、迭代次数、变异率等，可以控制算法的表现。