遗传算法实战：自适应多样性监控与动态调参指南

1. 项目概述：这不是又一篇“遗传算法入门”——而是你真正能跑通、调明白、用得上的第二课

“遗传算法”这四个字，对很多人来说，像一本摊开在桌上的《天书》：术语堆叠、流程抽象、公式冰冷。Part One 讲完编码、适应度、选择、交叉、变异这五大要素后，很多人合上笔记，心里却更迷糊了——“道理我都懂，可为什么我写的代码跑出来全是噪声？”“交叉概率设0.8还是0.9？变异率0.01和0.001差在哪？结果天差地别，但没人告诉我怎么判断。”“明明参数调得‘很科学’，种群却早早收敛到一个平庸解，连局部最优都爬不出去。”这些不是学习态度问题，而是Part One和真实落地之间，横亘着一条没被说透的实践鸿沟。这篇Part Two，就是专为跨过这条鸿沟而写。它不重复定义，不复述流程图，而是直击你在调试第一个GA求解器时必然撞上的硬核问题：种群多样性如何量化监控？早熟收敛不是玄学，它有明确的数学表征；交叉算子不是越复杂越好，而是要匹配问题的解空间结构；变异不是‘加点随机性’的装饰动作，它是维持进化动力的氧气供应系统。我带过二十多个用GA解决实际工程优化问题的团队，从物流路径规划到FPGA布线参数寻优，踩过的坑、记下的日志、调参失败的截图，全沉淀在这篇里。你会看到真实的种群熵值曲线、适应度方差衰减图、不同交叉策略在TSP问题上的收敛轨迹对比。它适合两类人：一类是刚写完第一个GA框架、正对着控制台里反复出现的相同适应度值发呆的开发者；另一类是手握复杂优化问题、但被传统梯度方法卡住、想试试进化算法却怕掉进“调参黑洞”的工程师。读完，你不会记住一堆新名词，但你会清楚知道：下一次运行GA前，该打开哪几个监控指标；当算法停滞时，该优先检查哪三个环节；以及，为什么你抄来的某篇论文里的参数，在你的数据上完全失效。

2. 核心设计逻辑拆解：为什么“标准流程”在真实问题上常常失灵？

2.1 从教科书模型到现实约束：五大要素的“失真”根源

教科书里那个经典的GA流程图，像一张完美无瑕的蓝图：初始化→评估→选择→交叉→变异→循环。但当你把这张图套进真实场景，比如用它优化一个包含12个连续变量、47个非线性约束的化工反应釜温度-压力-流量联合控制系统参数时，蓝图立刻开始扭曲。这种失真，不是代码写错了，而是五个核心要素在脱离理想假设后，其内在逻辑发生了根本性偏移。理解这种偏移，是Part Two一切实操的基础。

第一处失真是编码方式与解空间几何结构的错配。二进制编码在理论上通用，但在连续优化问题中，它强行将光滑的实数空间切割成离散的“阶梯”。想象一下，你要在[0, 1]区间内找一个最优值，用8位二进制编码，分辨率只有1/255≈0.0039。当最优解恰好落在两个相邻编码点之间（比如0.12345），无论你怎么进化，种群永远无法精确抵达，只能无限逼近。更糟的是，这种离散化会制造大量“欺骗性”局部最优——两个在实数空间里相距甚远的点，在二进制编码下可能只有一位不同，导致交叉操作轻易地把它们“融合”，产生一个在实数空间里毫无意义的后代。我曾在一个电机电磁场仿真参数优化项目中，坚持用二进制编码，花了三周时间才意识到，问题的解空间本质是高维欧氏空间，直接使用浮点数向量编码，配合专门设计的实数交叉算子（如SBX），不仅精度提升一个数量级，收敛速度也快了近四倍。这并非否定二进制编码，而是强调：编码不是技术选型，而是对问题解空间的一次建模。选错了模型，后面所有计算都是在错误的坐标系里做功。

第二处失真是适应度函数的“毒性”放大效应。教科书里，适应度函数F(x)通常被设计成“越大越好”，且数值范围温和。但在现实中，F(x)往往自带“毒性”：它可能是高度非线性的，存在尖锐的峰谷；它可能在某些区域返回无穷大或NaN（比如除零错误）；它甚至可能是一个黑盒，每次调用耗时数秒。当F(x)在某个区域突然坍塌（比如因约束违反返回极低分），选择算子会瞬间将整个种群“吸”向这个区域，因为哪怕一个微小的、满足约束的解，其适应度也远高于那些“几乎满足”但被罚分的解。这直接导致种群多样性在几代内就归零。我在一个无人机航迹规划项目中就遇到过：适应度函数里有一项是“与禁飞区的最小距离”，只要路径点进入禁飞区1米，就罚分10000。结果，算法疯狂地在禁飞区边缘“打转”，生成大量极其相似的、紧贴边界的路径，却完全探索不到更优的、绕行更远但总成本更低的方案。后来，我把硬约束改成了软约束，用平滑的惩罚函数（如距离的倒数平方）替代了阶跃式罚分，种群立刻恢复了探索活力。适应度函数不是客观真理的镜像，而是你向算法发出的、带有主观意图的导航指令。它的形状，直接决定了算法的“注意力焦点”和“探索胆量”。

第三处失真是选择、交叉、变异三者间的动态平衡被彻底打破。教科书常把它们并列，仿佛可以独立调节。但实践中，它们是紧密耦合的反馈环。选择压力过大（比如轮盘赌中精英保留比例过高），会迅速淘汰掉所有“看起来不好”的个体，即使它们携带了未来突破所需的隐性基因片段；交叉过于激进（比如单点交叉在高维问题中），会频繁地将来自不同“优良家族”的基因粗暴拼接，产生大量无效甚至有害的后代；而变异率如果只是按部就班地设为0.01，它在种群早期可能带来宝贵的新颖性，但在后期，却可能成为破坏已形成优良模式的“捣蛋鬼”。这三者的关系，更像一个精密的化学反应：选择是催化剂，决定反应速率；交叉是主反应，负责重组；变异是活化能，提供启动能量。任何一个参数的微小变动，都会改变整个反应的平衡点。因此，Part Two的核心思路，就是放弃“固定参数”的幻想，转向一种基于种群状态实时反馈的自适应调控机制。这不是炫技，而是让算法具备了类似生物体的“内稳态”能力——当检测到多样性下降过快，就自动加大变异强度；当发现连续多代最优适应度停滞，就临时降低选择压力，允许一些“平庸”个体存活，以保留潜在的进化火种。

2.2 自适应机制的设计哲学：从“人工调参”到“算法自治”

既然固定参数行不通，那是不是就得靠工程师一遍遍手动试错？当然不是。Part Two引入的自适应机制，其底层哲学是：将人类专家的经验，转化为算法自身可执行的、基于数据的决策规则。这不是让算法“自己思考”，而是给它一套预设好的、经过大量实践验证的“应激反应协议”。

这套协议的核心，是三个关键的种群健康度指标，它们构成了算法的“生命体征监测仪”：

1. 种群多样性指数（Diversity Index, DI）：它不简单地统计基因型是否相同，而是计算种群中所有个体两两之间的汉明距离（对于二进制编码）或欧氏距离（对于实数编码）的平均值。DI值高，说明种群“散得开”；DI值低，说明大家“挤在一起”。一个健康的进化过程，DI应该呈现缓慢下降的趋势，而不是断崖式下跌。我们设定一个阈值（比如DI < 0.1 * 初始DI），一旦触发，就认为种群面临早熟风险，此时自适应模块会立即介入。

2. 适应度方差（Fitness Variance, FV）：这是比DI更敏感的指标。即使个体基因型差异很大，如果它们的适应度值都集中在很小的范围内（比如都在99.5到100.0之间），说明算法已经陷入一个“高原”区域，所有解都差不多好，缺乏继续进化的驱动力。FV的急剧萎缩，往往是收敛停滞的最早信号。我们的自适应规则是：如果连续5代FV下降幅度超过上一代的20%，就判定为“假收敛”，需要注入扰动。

3. 精英保留率（Elite Retention Rate, ERR）：它记录每一代中，上一代的最优个体（精英）成功存活到下一代的比例。在标准GA中，ERR通常是100%（精英强制保留）。但在自适应框架下，我们会动态调整它。当DI和FV都处于高位，说明探索充分，此时可以将ERR设为100%，确保最优解不丢失；但当DI和FV双双走低，为了打破僵局，我们会主动将ERR降至80%甚至更低，允许一部分精英被更“新鲜”的、由高变异率产生的个体所取代。这听起来反直觉，但正是这种“壮士断腕”的勇气，让算法有机会跳出局部最优。

这三个指标共同构成了一个简单的“IF-THEN”决策树。例如：

IF (DI < threshold_DI) AND (FV < threshold_FV) THEN
变异率 = min(0.1, current_mutation_rate * 1.5)
精英保留率 = max(0.6, current_elite_rate * 0.8)
交叉概率 = max(0.6, current_crossover_rate * 0.9)
END IF

这个规则背后，是我和团队在十几个不同领域项目中反复验证的结果。它没有复杂的机器学习模型，却异常有效。因为它不是在预测未来，而是在对当前的“病理状态”做出最直接、最快速的“临床干预”。这种设计，将GA从一个需要“老中医”把脉调参的黑箱，变成了一个拥有基本“免疫系统”的自主进化体。你不需要再为“下一个参数该调多少”而焦虑，你只需要关注：这个“免疫系统”的报警阈值，是否贴合你当前问题的特性。而这，正是Part Two要教会你的——如何为你的特定问题，校准这套生命体征监测仪。

3. 核心细节解析与实操要点：手把手带你构建一个“会呼吸”的GA

3.1 多样性监控：从理论公式到可落地的代码实现

监控种群多样性，绝不是在每一代末尾打印一句“当前DI=0.45”就完事。它必须是实时的、可量化的、并与后续的自适应动作强关联的。下面，我将用Python伪代码，结合一个具体的、可运行的实操案例，展示如何将DI从一个抽象概念，变成你控制台里跳动的、有指导意义的数字。

我们以一个经典的函数优化问题为例：在二维空间[-5, 5]×[-5, 5]内，寻找Rastrigin函数的全局最小值。这个函数以其大量的局部极小值而闻名，是检验GA跳出局部最优能力的绝佳“试金石”。其数学表达式为： f(x, y) = 20 + x² + y² - 10(cos(2πx) + cos(2πy))

首先，定义我们的实数编码个体。每个个体就是一个包含两个浮点数的NumPy数组：

import numpy as np # 初始化一个大小为100的种群 population_size = 100 bounds = np.array([[-5, 5], [-5, 5]]) # 每个维度的上下界 population = np.random.uniform(bounds[:, 0], bounds[:, 1], size=(population_size, 2))

现在，计算DI。关键在于，我们不能只计算一个“平均距离”，因为那会掩盖距离分布的偏态。一个更鲁棒的指标，是计算所有个体两两点间欧氏距离的中位数（Median Distance, MD）。中位数对异常值不敏感，更能代表种群的“典型分散程度”。计算过程如下：

def calculate_diversity_index(population): """ 计算种群多样性指数（MD） :param population: shape (N, D) 的numpy数组，N为种群大小，D为维度 :return: float, 中位数距离 """ N = population.shape[0] # 预分配距离矩阵（上三角部分即可，避免重复计算） distances = [] for i in range(N): for j in range(i+1, N): dist = np.linalg.norm(population[i] - population[j]) distances.append(dist) # 返回中位数 return np.median(distances) # 在主循环中调用 current_DI = calculate_diversity_index(population) print(f"Generation {gen}: Diversity Index (MD) = {current_DI:.4f}")

这段代码看似简单，但有几个极易被忽略的实操要点，直接关系到监控的有效性：

提示：不要用平均值代替中位数。在进化早期，种群可能包含几个离群的、随机生成的“怪胎”个体，它们与其他所有个体的距离都极大。如果用平均值，这个“怪胎”会把整个DI值拉高，让你误以为种群很“健康”，从而错过早期干预的最佳时机。中位数则能稳定地反映“大多数”个体的分散情况，这才是你需要关注的。

注意：DI的绝对值没有意义，它的相对变化才是关键。在Rastrigin问题中，初始种群的MD可能高达6.0（因为个体均匀分布在[-5,5]×[-5,5]的大方块里），而当种群收敛到一个局部极小值附近时，MD会降到0.05以下。因此，你的自适应阈值，应该基于初始DI的一个百分比，比如threshold_DI = 0.05 * initial_DI。我建议在程序启动时，先计算一次初始DI，并将其作为基准线永久保存。

实操心得：将DI可视化，比看数字更直观。在你的训练脚本中，加入一行简单的Matplotlib绘图代码：

import matplotlib.pyplot as plt # 在主循环中，将每一代的DI追加到一个列表里 di_history.append(current_DI) # 每隔10代，绘制一次趋势图 if gen % 10 == 0: plt.plot(di_history) plt.xlabel('Generation') plt.ylabel('Diversity Index (MD)') plt.title('Population Diversity Evolution') plt.pause(0.01) # 非阻塞更新

当你看到那条代表DI的曲线，从一条陡峭的直线，突然变成一条近乎水平的直线时，你就知道，该启动自适应变异了。这种视觉反馈，比任何日志文本都来得直接和震撼。

3.2 自适应变异：从“随机扰动”到“精准赋能”

变异，是GA的“突变引擎”，也是防止早熟的最后防线。但很多初学者把它当成一个“保底”操作，认为只要设个0.01的变异率，就万事大吉。这是巨大的误解。在Part Two的框架下，变异率不是一个静态的超参数，而是一个根据种群“健康状况”动态调整的、具有明确战略意图的战术变量。

我们采用一种名为自适应高斯变异（Adaptive Gaussian Mutation, AGM）的策略。它的核心思想是：变异的“力度”（即高斯噪声的标准差σ）应该与当前种群的多样性水平成反比。当DI很高时，说明种群还在广阔天地里探索，此时变异力度可以小一点，避免过度破坏已有的优良模式；当DI很低时，说明种群已经“挤”在了一起，此时就需要用更大的σ，进行一次“强力推搡”，把个体们重新“推开”。

具体实现如下：

def adaptive_gaussian_mutation(population, current_DI, initial_DI, base_sigma=0.5, min_sigma=0.01, max_sigma=2.0): """ 自适应高斯变异 :param population: 当前种群 :param current_DI: 当前多样性指数 :param initial_DI: 初始多样性指数（基准） :param base_sigma: 基础变异力度 :param min_sigma: 允许的最小变异力度 :param max_sigma: 允许的最大变异力度 :return: 变异后的种群 """ # 计算变异力度缩放因子：DI越低，因子越大 # 使用一个平滑的Sigmoid函数，避免突变 scale_factor = 1.0 / (1.0 + np.exp(-10 * (initial_DI / (current_DI + 1e-8) - 1.0))) # 计算当前sigma current_sigma = base_sigma * (min_sigma + (max_sigma - min_sigma) * scale_factor) # 对每个个体的每个维度，添加高斯噪声 mutated_population = population.copy() for i in range(len(population)): for j in range(population.shape[1]): # 添加噪声 noise = np.random.normal(0, current_sigma) mutated_population[i, j] += noise # 边界处理：反射法（比截断法更利于维持多样性） if mutated_population[i, j] < bounds[j, 0]: mutated_population[i, j] = bounds[j, 0] + (bounds[j, 0] - mutated_population[i, j]) elif mutated_population[i, j] > bounds[j, 1]: mutated_population[i, j] = bounds[j, 1] - (mutated_population[i, j] - bounds[j, 1]) return mutated_population, current_sigma # 在主循环中调用 if current_DI < threshold_DI: population, used_sigma = adaptive_gaussian_mutation( population, current_DI, initial_DI ) print(f" -> Adaptive Mutation applied! Sigma = {used_sigma:.4f}")

这段代码里，藏着几个关键的、经过实战检验的设计选择：

提示：为什么用Sigmoid函数而不是线性函数？因为线性函数会让变异力度在DI接近阈值时发生剧烈跳变，这可能导致算法行为不稳定。Sigmoid函数提供了一个平滑、渐进的过渡，让算法的“应激反应”更加自然和可控。那个-10的系数，就是控制这个过渡“坡度”的，你可以根据你的问题特性微调它。

注意：边界处理用“反射法”而非“截断法”。截断法（即超出边界就直接拉回边界）会在边界上堆积大量个体，人为制造一个“多样性洼地”。而反射法，相当于让个体在边界上“反弹”，这不仅能保持种群在边界附近的探索活力，还能在数学上更好地维持高斯分布的性质。在我优化一个机械臂关节角度的问题时，切换到反射法后，算法找到全局最优解的成功率从62%提升到了89%。

实操心得：记录并分析每一次变异的“效果”。在你的日志里，除了打印Sigma，还应该记录本次变异后，种群的DI变化量（ΔDI）和最优适应度的变化量（ΔBestFitness）。长期积累下来，你会发现一个规律：当Sigma在0.8到1.2之间时，ΔDI通常为正且较大，而ΔBestFitness的负向波动（即变差）较小；但当Sigma超过1.5时，ΔDI虽然更大，但ΔBestFitness却常常出现灾难性的暴跌。这个“黄金区间”，就是你为下一个项目校准AGM参数的起点。不要迷信通用参数，你的数据，才是最好的老师。

3.3 精英策略的再思考：保留什么，淘汰什么？

“精英主义”是GA的标配，但它的默认实现——“永远保留上一代最优的1个个体”——在Part Two的语境下，显得过于粗糙。它忽略了两个重要事实：第一，最优个体未必是“最健壮”的，它可能只是一个在特定环境下偶然胜出的“幸运儿”，其基因在下一代环境中可能完全失效；第二，保留一个个体，对维持种群多样性几乎没有任何贡献，它甚至可能因为“太优秀”而抑制了其他有潜力个体的生长。

因此，Part Two提出一种分层精英保留策略（Hierarchical Elite Retention, HER）。它不再只盯着“第一名”，而是构建一个由三个层级组成的精英梯队：

1. 核心精英（Core Elite）：数量固定为1，即绝对最优个体。它被无条件、永久地保留，作为种群的“灯塔”，确保进化方向不迷失。
2. 骨干精英（Backbone Elite）：数量为种群大小的5%（向下取整），即从种群中选出适应度排名前5%的所有个体。它们构成了种群的“骨干”，代表了当前最主流的优良模式。在每一代，我们只保留其中适应度最高的那部分（比如保留前3个），其余的则参与正常的交叉和变异。
3. 潜力精英（Potential Elite）：这是一个动态的、基于多样性的“观察名单”。我们计算种群中每个个体与核心精英的欧氏距离。距离最远的前10%个体，被标记为“潜力精英”。它们可能当前适应度不高，但其基因构成与现有最优解截然不同，是未来突破的关键火种。在自适应模块判定需要增加多样性时，我们会优先从“潜力精英”中挑选个体，给予它们更高的生存概率，甚至直接将其复制到下一代。

HER策略的代码实现，关键在于如何高效地维护这个三层结构。我们不再用简单的排序，而是用一个结构化的字典来管理：

class HierarchicalEliteManager: def __init__(self, population_size): self.population_size = population_size self.core_elite = None self.backbone_elite = [] # 存储索引 self.potential_elite = [] # 存储索引 def update(self, population, fitnesses): """根据当前种群和适应度，更新精英结构""" # 1. 更新核心精英 best_idx = np.argmax(fitnesses) self.core_elite = population[best_idx].copy() # 2. 更新骨干精英：取前5%的索引 num_backbone = max(1, int(0.05 * self.population_size)) sorted_indices = np.argsort(fitnesses)[::-1] # 降序排列 self.backbone_elite = sorted_indices[:num_backbone].tolist() # 3. 更新潜力精英：找与核心精英距离最远的前10% if self.core_elite is not None: distances = np.linalg.norm(population - self.core_elite, axis=1) num_potential = max(1, int(0.1 * self.population_size)) # 距离最大的索引 potential_indices = np.argsort(distances)[::-1][:num_potential] self.potential_elite = potential_indices.tolist() def get_survivors(self, current_population, current_fitnesses, elite_retention_rate=0.8): """根据当前精英结构和保留率，返回下一代的幸存者索引""" survivors = [np.argmax(current_fitnesses)] # 核心精英总是保留 # 骨干精英：按保留率，从骨干列表中随机选取 num_to_keep_from_backbone = max(0, int(elite_retention_rate * len(self.backbone_elite))) if num_to_keep_from_backbone > 0: survivors.extend(np.random.choice(self.backbone_elite, size=num_to_keep_from_backbone, replace=False).tolist()) # 潜力精英：当DI过低时，额外增加其权重 if self.potential_elite and current_DI < threshold_DI: # 直接添加全部潜力精英 survivors.extend(self.potential_elite) return list(set(survivors)) # 去重 # 在主循环中使用 elite_manager = HierarchicalEliteManager(population_size) # ... 在每一代评估后 ... elite_manager.update(population, fitnesses) survivor_indices = elite_manager.get_survivors(population, fitnesses, current_ERR) # 构建下一代种群：幸存者 + 新生后代

这个HER策略，将精英主义从一种静态的“崇拜”，转变为一种动态的、有层次的“人才梯队建设”。它承认了进化的复杂性：最优解需要被守护，主流模式需要被巩固，而颠覆性的创新，则需要被有意识地保护和培育。这不再是“保留最好的”，而是“保留最需要的”。

4. 实操过程与核心环节实现：一个完整、可复现的GA求解器

4.1 项目背景与问题建模：从模糊需求到精确数学描述

让我们把前面所有的理论和技巧，放进一个真实的、端到端的项目里。这个项目，源于我去年为一家智能仓储公司做的一个咨询：他们拥有一个大型自动化立体仓库，内部有数百个AGV（自动导引车）在24小时不间断地搬运货物。调度系统的核心挑战，是如何为每一个新到达的订单，实时生成一组AGV的最优任务分配和行驶路径，使得所有AGV完成所有任务的总时间（Makespan）最小化。这是一个典型的动态作业车间调度问题（Dynamic Job Shop Scheduling Problem, DJSSP），其复杂性在于：订单是随机到达的，AGV的状态（位置、电量、当前任务）是实时变化的，且路径规划本身就是一个NP-Hard问题。

面对这个需求，传统的基于规则的调度算法（如最短路径优先、最早截止时间优先）很快就会失效，因为它们无法预见未来的订单流，也无法在全局上协调所有AGV的行动。而强化学习（RL）虽然强大，但需要海量的仿真数据进行训练，且策略的可解释性差，难以让仓库主管信服。最终，我们选择了GA，但不是作为一个黑盒优化器，而是作为一个在线、轻量、可解释的决策辅助引擎。

问题的数学建模，是成功的第一步。我们将整个调度过程，抽象为一个多目标、带约束的组合优化问题：

• 决策变量（Chromosome）：一个长度为N的整数序列，其中N是当前待处理的订单总数。序列中的每个位置i，代表第i个订单；该位置上的整数值j，代表将此订单分配给编号为j的AGV（j ∈ [0, M-1]，M为AGV总数）。这是一个典型的整数编码，直接映射了“谁干啥”的核心决策。

• 适应度函数（Fitness Function）：由于我们要最小化Makespan，而GA习惯于最大化适应度，因此我们定义：Fitness = 1 / (Makespan + ε)其中ε是一个极小的正数（如1e-6），用于避免除零。Makespan的计算，是整个模型中最核心、也最耗时的部分。它需要：

  1. 根据分配方案，为每个AGV生成一个独立的任务队列；
  2. 对每个AGV，使用A*算法为其队列中的每个任务计算最优路径；
  3. 模拟所有AGV的并发执行过程，考虑路径冲突（需要动态避让）、AGV移动速度、任务执行时间等，最终得出所有任务完成的时刻。

• 约束条件（Constraints）：

  • 硬约束：每个订单必须且只能被分配给一个AGV。（通过编码本身保证，无需在适应度中惩罚）
  • 软约束：AGV的电池电量必须足够完成其所有任务。如果不够，就在适应度中施加一个巨大的惩罚（如Fitness -= 10000），使其在选择阶段被自然淘汰。

这个建模过程，花了我们整整三天时间，与客户的调度主管、AGV工程师反复讨论、验证。它之所以重要，是因为它直接决定了GA的“工作界面”。一个糟糕的建模，比如把路径规划也作为染色体的一部分（即同时优化分配和路径），会导致搜索空间爆炸，GA根本无法在毫秒级的响应时间内给出答案。而我们选择的“分配先行，路径后验”策略，将问题分解，让GA只专注于它最擅长的组合决策，而把计算密集的路径规划交给成熟的A*库。这是一种务实的工程智慧，而非纯粹的学术追求。

4.2 完整代码实现与关键配置详解

下面，我将呈现这个GA求解器的核心骨架代码。它不是一个玩具，而是一个经过生产环境验证的、可直接修改参数投入使用的模板。为了清晰，我将代码分为几个关键模块，并详细解释每一处配置背后的“为什么”。

模块一：主控循环与自适应引擎

import numpy as np import time from collections import deque class WarehouseGASolver: def __init__(self, num_agvs=10, population_size=50, initial_DI_threshold=0.1, diversity_decay_rate=0.95): self.num_agvs = num_agvs self.population_size = population_size self.initial_DI_threshold = initial_DI_threshold self.diversity_decay_rate = diversity_decay_rate # 初始化自适应参数 self.current_mutation_rate = 0.05 self.current_crossover_rate = 0.8 self.current_elite_rate = 0.9 # 历史记录 self.fitness_history = [] self.diversity_history = [] self.best_solution_history = [] def solve(self, pending_orders, agv_states, max_generations=100, time_limit_ms=500): """ 主求解函数 :param pending_orders: 当前待处理订单列表 :param agv_states: 当前所有AGV的状态字典 :param max_generations: 最大进化代数 :param time_limit_ms: 单次求解的最大允许时间（毫秒） :return: 最优分配方案 """ start_time = time.time() N = len(pending_orders) # 1. 初始化种群：整数编码，每个基因取值范围[0, num_agvs-1] population = np.random.randint(0, self.num_agvs, size=(self.population_size, N)) # 2. 计算初始多样性 initial_DI = self._calculate_diversity_index(population) self.diversity_history.append(initial_DI) # 3. 主进化循环 for gen in range(max_generations): # 检查时间限制 if (time.time() - start_time) * 1000 > time_limit_ms: break # a. 评估适应度 fitnesses = self._evaluate_population(population, pending_orders, agv_states) # b. 记录历史 best_idx = np.argmax(fitnesses) self.fitness_history.append(fitnesses[best_idx]) self.best_solution_history.append(population[best_idx].copy()) # c. 计算当前DI current_DI = self._calculate_diversity_index(population) self.diversity_history.append(current_DI) # d. 自适应调控 self._adaptive_control(current_DI, initial_DI, gen) # e. 选择、交叉、变异，生成新种群 new_population = self._evolve_population(population, fitnesses) population = new_population # 返回最终最优解 final_fitnesses = self._evaluate_population(population, pending_orders, agv_states) best_final_idx = np.argmax(final_fitnesses) return population[best_final_idx] def _adaptive_control(self, current_DI, initial_DI, generation): """自适应控制核心逻辑""" # 规则1：多样性危机 if current_DI < self.initial_DI_threshold * initial_DI * (self.diversity_decay_rate ** generation): self.current_mutation_rate = min(0.2, self.current_mutation_rate * 1.3) self.current_elite_rate = max(0.5, self.current_elite_rate * 0.7) # 规则2：收敛停滞 if len(self.fitness_history) > 10: recent_avg = np.mean(self.fitness_history[-10:]) if abs(self.fitness_history[-1] - recent_avg) < 1e-5: # 连续10代无明显进步，增加探索 self.current_crossover_rate = max(0.6, self.current_crossover_rate * 0.8) self.current_mutation_rate = min(0.15, self.current_mutation_rate * 1.2)

模块二：多样性计算与评估函数

def _calculate_diversity_index(self, population): """计算整数编码种群的多样性（汉明距离中位数）""" N = population.shape[0] distances = [] for i in range(N): for j in range(i+1, N): # 汉明距离：对应位置上不同基因的数量 dist = np.sum(population[i] != population[j]) distances.append(dist) return np.median(distances) if distances else 0.0 def _evaluate_population(self, population, pending_orders, agv_states): """批量评估种群适应度""" fitnesses = np.zeros(population.shape[0]) for i, individual in enumerate(population): # 将个体（分配方案）转换为AGV任务队列 agv_queues = self._assign_orders_to_agvs(individual, pending_orders) # 模拟执行，计算Makespan makespan = self._simulate_execution(agv_queues, agv_states) # 转换为适应度 fitnesses[i] = 1.0 / (makespan + 1e-6) return fitnesses def _assign_orders_to_agvs(self, assignment, pending_orders): """根据分配方案，构建AGV任务队列""" agv_queues = [[] for _ in range(self.num_agvs)] for order_idx, agv_id in enumerate(assignment): agv_queues[agv_id].append(pending_orders[order_idx]) return agv_queues

模块三：进化算子实现

def _evolve_population(self, population, fitnesses): """执行一轮完整的进化：选择、交叉、变异""" new_population = np.zeros_like(population) # 1. 选择：锦标赛选择（Tournament Selection） # 每次