1. 基本概念
个体（Individual）： 每个可能的解，可以理解为一个染色体。
种群（Population）： 一组个体，代表问题的解空间的一个采样。
基因（Gene）： 个体的组成成分，可以是数字、字符等。
染色体（Chromosome）： 个体的基因序列，表示个体的特征。
适应度（Fitness）： 评价个体优劣的指标，通常与目标函数相关。
选择（Selection）： 根据适应度，选择优良个体进行繁殖。
交叉（Crossover）： 将两个父代个体的部分基因进行交换，产生新的子代。
变异（Mutation）： 以一定的概率随机改变个体的基因，增加种群多样性。
2. 算法流程
初始化种群： 随机生成一定数量的初始个体。
计算适应度： 根据适应度函数，计算每个个体的适应度值。
选择：
轮盘赌选择： 适应度高的个体被选中的概率大。
锦标赛选择： 从种群中随机选取若干个个体，选择其中适应度最高的个体。
排序选择： 根据适应度排序，选择前几个个体。
交叉：
单点交叉： 随机选择一个交叉点，交换两个父代染色体该点之后的片段。
多点交叉： 随机选择多个交叉点。
均匀交叉： 对于每个基因位，以一定的概率从父代中选择一个基因。
变异：
位变异： 随机选择一个基因位，将其值翻转。
均匀变异： 随机生成一个新值替换原有基因。
替换： 用新生成的个体替换部分或全部旧个体。
终止条件： 判断是否满足终止条件（如达到最大迭代次数、找到最优解等），若满足则终止，否则返回步骤2。
3. 具体例子：旅行商问题（TSP）
问题描述： 一个旅行商要访问n个城市，要求每个城市只访问一次，且最后回到出发城市，如何找到一条最短的旅行路线？
编码： 用一个整数序列表示城市访问顺序。
适应度函数： 路径的总长度。
操作：
初始化： 随机生成多个城市访问顺序。
选择： 根据路径长度选择较短的路径。
交叉： 将两个路径的部分城市顺序交换。
变异： 随机交换两个城市的访问顺序。
4. 关键点
适应度函数设计： 适应度函数直接影响算法的搜索方向。
编码方式： 不同的编码方式会影响算法的性能。
参数设置： 种群大小、交叉概率、变异概率等参数需要调整。
早熟现象： 种群过早收敛于局部最优解，可以通过引入多样性机制来避免。
5. 优势
全局搜索能力强： 不依赖于问题的导数信息，适用于复杂优化问题。
并行性好： 种群中的个体可以并行计算。
鲁棒性强： 对初始解不敏感。
6. 缺点
效率较低： 对于大规模问题，计算量较大。
参数敏感性： 参数设置不当会影响算法性能。
可能陷入局部最优： 需要引入一些机制来避免。
总结
遗传算法是一种模拟自然进化过程的优化算法，通过迭代的方式搜索最优解。其核心思想是通过选择、交叉和变异等操作，不断改进种群的质量。尽管遗传算法具有很多优点，但其应用也存在一些挑战。在实际应用中，需要根据具体问题进行调整和优化，才能取得好的效果。
附上源码：
import random
import math
def fitness_function(x):
"""适应度函数，这里以一个简单的函数为例"""
return math.sin(x) + math.cos(x)
def generate_population(population_size, bounds):
"""生成初始种群"""
return [[random.uniform(bounds[0], bounds[1])] for _ in range(population_size)]
def selection(population, fitness_values, num_parents):
"""轮盘赌选择"""
fitness_sum = sum(fitness_values)
probabilities = [fitness / fitness_sum for fitness in fitness_values]
parents = random.choices(population, weights=probabilities, k=num_parents)
return parents
def crossover(parent1, parent2, crossover_rate):
"""单点交叉"""
if random.random() < crossover_rate:
child = [(parent1[0] + parent2[0]) / 2]
return child
else:
return parent1
def mutation(individual, mutation_rate, bounds):
"""高斯变异"""
if random.random() < mutation_rate:
individual[0] += random.gauss(0, 0.1) # 高斯分布产生变异
individual[0] = min(max(individual[0], bounds[0]), bounds[1]) # 保证不越界
return individual
def genetic_algorithm(population_size, generations, crossover_rate, mutation_rate, bounds):
"""遗传算法主函数"""
population = generate_population(population_size, bounds)
for generation in range(generations):
fitness_values = [fitness_function(individual[0]) for individual in population]
parents = selection(population, fitness_values, population_size)
offspring = []
for i in range(0, population_size, 2):
parent1, parent2 = parents[i], parents[i+1]
child = crossover(parent1, parent2, crossover_rate)
child = mutation(child, mutation_rate, bounds)
offspring.append(child)
population = offspring
# 找到最优个体
best_index = fitness_values.index(max(fitness_values))
return population[best_index]
# 示例用法
bounds = [-10, 10]
population_size = 100
generations = 100
crossover_rate = 0.8
mutation_rate = 0.1
best_individual = genetic_algorithm(population_size, generations, crossover_rate, mutation_rate, bounds)
print("最佳解:", best_individual[0])
print("最大值:", fitness_function(best_individual[0]))
