遗传算法 遗传算法是一种受生物进化启发的优化算法，属于进化计算的一个分支。它模拟自然选择和遗传学机制，通过迭代过程来寻找复杂问题的近似最优解。其核心思想是：一个问题的潜在解决方案被编码为“染色体”，一个种群由多个这样的染色体组成，通过模拟“选择”、“交叉”和“变异”等操作，让种群逐代进化，最终产生适应度最高（即问题最优或近似最优）的个体。 下面我将逐步拆解其工作原理和关键概念。 第一步：问题表示与初始化 首先，需要将待优化问题的 解决方案编码成一种数据结构 ，这被称为“染色体”或“个体”。最常见的编码方式是二进制字符串（例如，1011001代表一个参数组合），也可以使用实数向量、排列等。算法开始时，会随机生成一个包含N个个体的 初始种群 。这个种群代表了搜索空间的第一个随机采样。 第二步：定义适应度函数 适应度函数是遗传算法的“环境”，它 定量评价每个个体对问题的好坏程度 。这个函数由具体问题定义，它将一个染色体映射为一个数值（适应度值）。例如，在寻找函数最大值的问题中，适应度函数可能就是该函数本身；在旅行商问题中，适应度可能是路径总长度的倒数。适应度值越高，个体“生存”和繁殖的机会越大。 第三步：选择 选择操作模拟“适者生存”，目的是 从当前种群中选出较优的个体作为父代，用于繁殖下一代 。选择概率通常与个体的适应度成正比。常用方法有： 轮盘赌选择 ：每个个体被选中的概率等于其适应度占种群总适应度的比例。 锦标赛选择 ：随机从种群中选取k个个体，将其中适应度最高的选为父代，重复此过程。 选择过程确保了优良的基因有更大机会被保留和传递。 第四步：交叉 交叉（或称杂交）是遗传算法中最主要的搜索算子，模拟生物的有性繁殖。它 将两个父代个体的部分结构进行交换和重组，以产生新的后代个体 。这有助于探索搜索空间中新的区域。例如，在单点交叉中，随机选择一个截断点，然后交换两个父代字符串在该点之后的部分（如父代A: 110|011 和 父代B: 101|100 交叉后产生后代：110100 和 101011）。 第五步：变异 变异操作以很小的概率 随机改变后代个体编码中的某些基因 （如将二进制字符串中的某一位0翻转为1）。它模拟了基因复制过程中的随机错误，为种群引入新的遗传物质， 增加种群的多样性 ，有助于防止算法过早收敛于局部最优解，并探索可能被忽略的搜索区域。 第六步：迭代与终止 经过选择、交叉、变异后，得到一个新的子代种群。然后， 用子代种群替代父代种群，完成一次迭代（一代） 。这个过程反复进行。算法会在满足特定终止条件时停止，常见的终止条件包括：达到预设的最大迭代次数、种群中最优个体的适应度在连续多代内没有显著提升、或找到了满足要求的解。 总结与特点 ： 遗传算法是一种 基于群体的、随机化的搜索算法 。它不依赖于问题的梯度信息，因此适用于不可微、不连续、多峰或高度复杂的优化问题。其并行搜索特性（同时评估多个解）也使其能有效探索广阔的搜索空间。然而，它不能保证找到全局最优解，且设计合适的编码方式、适应度函数以及交叉、变异算子需要领域知识。它被广泛应用于调度、设计优化、机器学习参数调优、机器人路径规划等诸多领域。