基于智能体的遗传算法——通过自主智能体实现的分布式进化搜索
- 提出者
- Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
- 年份
- 1990s
- 类型
- Hybrid evolutionary-agent simulation
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
基于智能体的遗传算法(ABGA)将遗传算法的种群划分为一系列自主智能体,每个智能体维护一个局部子种群并独立演化。智能体根据邻近性或通信规则定期交换个体(迁移),从而实现搜索空间的并行探索,同时保持种群多样性并避免过早收敛。
方法背后的直觉
传统的遗传算法将整个种群视为一个单一的池,这可能导致一个占主导地位的基因型迅速接管,从而过早收敛到局部最优解。而基于智能体的方法则将子种群分布在排列成邻域拓扑的半自主智能体之间。每个智能体独立地在其局部子种群上运行选择、交叉和变异操作,然后偶尔与邻近智能体共享高适应度个体。这类似于生物物种形成在地理上隔离但偶尔连接的种群中发生的过程,允许不同的进化压力并行作用并在不同生态位之间重组解。
历史学
分布式和并行遗传算法出现在20世纪90年代初,当时研究人员试图克服过早收敛并利用并行硬件。Adamidis和Petridis(1996)形式化了具有不同进化行为的协作智能体种群。随着基于智能体的建模在计算科学中的普及,基于智能体的框架在20世纪90年代末和21世纪初获得了关注,它形式化了现在广泛应用于复杂优化中的自主的、受拓扑控制的交互模型。
何时使用
当适应度景观崎岖或多峰,且标准遗传算法持续过早收敛时;当有可用的并行或分布式硬件可以托管并发智能体进程时;或者当问题结构自然映射到半独立子问题时(例如,区域供应链、多部门政策),应使用ABGA。当探索异质进化压力下的算法行为时也适用。当问题具有单一单峰景观(简单的遗传算法就足够了)、当智能体之间通信的开销主导计算、当种群规模太小而无法有意义地划分,或者当需要中心化种群以实现精确可复现性时,请勿使用。
局限与注意事项
- 迁移策略的调整(速率、拓扑、频率)增加了需要仔细校准且依赖于问题的超参数。
- 智能体之间的通信开销可能会抵消高延迟或松散耦合的计算环境中并行化的优势。
- 理论收敛保证比标准遗传算法弱;对ABGA动力学的正式分析仍是一个开放的研究领域。
- 重现结果需要固定智能体拓扑、迁移计划以及所有智能体的随机种子,这会使复现复杂化。
- 如果子种群规模太小,个体智能体就容易发生遗传漂变,无论迁移如何。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 与随机交配(panmictic)遗传算法相比,保持了更高的种群多样性,减少了在崎岖适应度景观上的过早收敛。
- 自然地利用并行或分布式计算基础设施来解决大规模优化问题。
- 每个智能体的异质算子设置允许同时跨不同策略进行探索与利用。
- 智能体之间的个体迁移使得跨生态位重组成为可能,从而发现新颖的高质量解。
- 模块化架构易于在单个智能体进化循环中集成特定领域的启发式方法。
- 当子种群可以有意义地划分时,可以很好地处理问题维度。
应用
- 调度与物流:分布式作业车间或车辆路径问题,其中地理子问题自然地映射到智能体。
- 工程设计优化:结构或空气动力学设计,具有多峰搜索空间,受益于并行生态位探索。
- 策略模拟:社会模拟模型中的策略参数优化,其中智能体代表区域或部门参与者。
- 机器学习超参数搜索:在分布式计算集群上并行进化调整模型配置。
- 生物信息学:在高维、崎岖的适应度景观上进行蛋白质结构预测和基因网络推断。
- 游戏AI与机器人:在具有协同进化动态的多智能体环境中进化智能体行为策略。
使用方式
使用方式
定义智能体拓扑:指定智能体(子种群)的数量、它们的邻域结构(环形、网格、小世界图或全连接),以及控制智能体何时以及如何交换个体的通信协议。每个智能体都是一个拥有自己染色体池的自主计算实体。
使用随机生成的染色体(或种子解)初始化每个智能体的局部子种群。独立地或统一地为所有智能体设置局部种群大小、遗传算子(交叉类型和速率、变异速率)和选择机制(锦标赛、轮盘、秩排序)。
每个智能体独立地在其局部子种群上运行多代选择、交叉和变异操作。智能体在并行(或顺序模拟中的伪并行)中运行,探索解空间的潜在不同区域,可能采用不同的算子配置,从而在整个系统中保持多样性。
在定义的迁移间隔,智能体根据迁移策略(例如,发送最佳个体、接收并替换最差个体)与邻近智能体共享其部分最佳个体。迁移速率和拓扑结构决定了局部开发与全局探索之间的平衡;过于频繁的迁移会破坏多样性,过于稀疏的迁移则会浪费分布式架构的优势。
所有导入的和本地进化的染色体都根据共享的适应度函数进行评估。智能体可能在迁移后应用局部选择压力,将接收到的个体整合到其种群中,并可能丢弃适应度较低的现有个体。适应度评估是主要的计算成本。
当满足全局停止标准(最大代数、所有智能体最佳适应度收敛或已用时间)时终止。收集所有智能体找到的最佳解作为最终输出。报告每个智能体的收敛曲线,以诊断种群多样性和迁移有效性。
常见陷阱
- 将迁移速率设置得太高会导致子种群多样性崩溃,实际上变成单一池,从而消除了智能体架构的主要优势。
- 忽略邻域拓扑设计:全连接拓扑会导致快速收敛;迁移频率较低的环形拓扑可能会使智能体孤立且停滞。
- 仅在局部评估适应度而不使用共享的全局适应度函数会导致智能体优化不兼容的目标。
- 混淆ABGA与多目标遗传算法:ABGA是为了搜索效率而设计的架构变体,本身并非多目标方法——多目标ABGA需要额外的Pareto机制。
- 在单个智能体收敛时停止,而不是在全局收敛时停止,可能会错过其他智能体仍在进化的更优解。
常见问题
ABGA与标准并行遗传算法有何不同?
标准并行遗传算法通常将单个中心化种群的适应度评估分布在不同处理器上。ABGA为每个智能体提供一个具有自身进化循环的自主子种群;交互仅通过显式迁移发生,而不是通过共享池。这种区别保留了每个智能体的独立选择压力。
应选择何种迁移拓扑?
环形和网格拓扑是标准的起点:它们限制了迁移流并保持了多样性。小世界拓扑(在环形上添加一些长距离连接)可以加速优良解的传播,而不会破坏多样性。除非您想要快速收敛行为,否则通常应避免全连接拓扑。
应选择多少智能体和多大的子种群规模?
一个常见的经验法则是使用4-16个智能体,每个子种群规模为20-50个个体,总种群规模与标准遗传算法相当。智能体太少会削弱该架构的多样性优势;智能体太多而子种群太小则会遭受漂变。需要针对特定问题进行经验调优。
ABGA可用于多目标优化吗?
是的,但必须添加额外的Pareto机制(例如,每个智能体内部的NSGA-II排序)。然后,智能体架构有助于维持更具多样性的Pareto前沿近似。这是多目标ABGA变体的基础。
ABGA保证能找到全局最优解吗?
不能。像所有遗传算法一样,ABGA是启发式的,不提供全局最优性保证。在实践中,提高的多样性保持增加了避免局部最优解的概率,但收敛保证并不比标准遗传算法更强,并且是活跃的理论研究问题。