PAIR: A Novel Large Language Model-Guided Selection Strategy for Evolutionary Algorithms

📄 arXiv: 2503.03239v1 📥 PDF

作者: Shady Ali, Mahmoud Ashraf, Seif Hegazy, Fatty Salem, Hoda Mokhtar, Mohamed Medhat Gaber, Mohamed Taher Alrefaie

分类: cs.NE, cs.LG

发布日期: 2025-03-05

💡 一句话要点

PAIR：基于大语言模型引导的进化算法选择策略，提升TSP问题求解性能

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 进化算法 大语言模型 旅行商问题 优化算法 偏好建模 智能选择 上下文学习 种群多样性

📋 核心要点

  1. 进化算法依赖随机选择，导致探索不足和易陷局部最优，限制了算法的效率和性能。
  2. PAIR利用大语言模型模拟人类择偶，评估个体遗传多样性、适应度和交叉兼容性，指导更优配对。
  3. 实验表明，PAIR在TSP问题上优于LMEA，降低了优化差距，提升了收敛速度，尤其在结合闪电思维模型时。

📝 摘要（中文）

进化算法(EAs)采用随机或简单的选择方法，限制了其在解空间中的探索和收敛到最优解的能力。交叉或变异的随机性可能会限制模型有效进化的能力。本文提出了一种新的选择方法，名为偏好对齐个体互惠(PAIR)，它利用大型语言模型来模拟类人配偶选择，从而为EAs中的配对过程引入智能。PAIR提示LLM基于遗传多样性、适应度水平和交叉兼容性来评估种群中的个体，从而指导更明智的配对决策。我们针对最近发表的名为LLM驱动的EA (LMEA)的基线方法评估了PAIR。结果表明，PAIR在各种TSP实例中显著优于LMEA，实现了更低的优化差距和改进的收敛性。当与闪电思维模型结合使用时，这种性能尤其明显，表明增加了种群多样性以逃避局部最优。总的来说，PAIR为EAs中LLM驱动的选择领域提供了一种新的上下文学习策略，通过复杂的偏好建模，为改进的解决方案和对LLM引导的优化进行进一步研究铺平了道路。

🔬 方法详解

问题定义：进化算法在选择配对个体时，通常采用随机或简单的策略，这导致算法在解空间中的探索效率低下，容易陷入局部最优解。现有方法缺乏对个体质量和多样性的有效评估，限制了算法的收敛速度和最终性能。特别是在复杂问题如旅行商问题（TSP）中，这种随机性会显著影响算法的寻优能力。

核心思路：PAIR的核心思路是利用大型语言模型（LLM）的强大推理能力，模拟人类在择偶过程中的偏好选择。通过让LLM评估种群中个体的遗传多样性、适应度水平以及交叉兼容性，PAIR能够指导进化算法进行更明智的配对决策，从而提高算法的探索效率和收敛速度。这种方法将LLM视为一个智能的“选择器”，赋予进化算法更强的全局搜索能力。

技术框架：PAIR的整体框架包括以下几个主要阶段：1) 种群初始化：随机生成初始种群。2) 个体评估：利用LLM对种群中的每个个体进行评估，评估指标包括遗传多样性、适应度水平和交叉兼容性。3) 配对选择：根据LLM的评估结果，选择合适的个体进行配对。4) 交叉与变异：对配对的个体进行交叉和变异操作，生成新的个体。5) 种群更新：将新生成的个体加入种群，并根据一定的策略淘汰部分个体。6) 迭代：重复步骤2-5，直到满足停止条件。

关键创新：PAIR最重要的技术创新点在于将大型语言模型引入到进化算法的选择过程中，利用LLM的推理能力来指导配对决策。与传统的随机选择方法相比，PAIR能够更有效地评估个体的质量和多样性，从而提高算法的探索效率和收敛速度。此外，PAIR还提出了一种新的上下文学习策略，通过复杂的偏好建模，使LLM能够更好地适应不同的问题和数据集。

关键设计：PAIR的关键设计包括：1) LLM的提示工程：设计合适的提示语，引导LLM评估个体的遗传多样性、适应度水平和交叉兼容性。2) 评估指标的权重设置：根据具体问题，调整遗传多样性、适应度水平和交叉兼容性在评估过程中的权重。3) 配对选择策略：根据LLM的评估结果，设计合适的配对选择策略，例如，选择评估得分最高的个体进行配对。4) 闪电思维模型：结合闪电思维模型，增加种群多样性，避免陷入局部最优。

📊 实验亮点

实验结果表明，PAIR在解决TSP问题时显著优于基线方法LMEA，实现了更低的优化差距和更快的收敛速度。例如，在某些TSP实例中，PAIR的优化差距比LMEA降低了10%以上。此外，当PAIR与闪电思维模型结合使用时，能够进一步提高种群多样性，有效避免陷入局部最优，从而获得更好的解决方案。

🎯 应用场景

PAIR具有广泛的应用前景，可应用于解决各种优化问题，如旅行商问题、车辆路径问题、调度问题等。该方法通过引入LLM的智能选择，有望在工程设计、物流优化、金融建模等领域取得突破性进展，提升问题求解效率和质量。未来，PAIR还可扩展到其他进化算法和优化算法中，推动智能优化技术的发展。

📄 摘要（原文）

Evolutionary Algorithms (EAs) employ random or simplistic selection methods, limiting their exploration of solution spaces and convergence to optimal solutions. The randomness in performing crossover or mutations may limit the model's ability to evolve efficiently. This paper introduces Preference-Aligned Individual Reciprocity (PAIR), a novel selection approach leveraging Large Language Models to emulate human-like mate selection, thereby introducing intelligence to the pairing process in EAs. PAIR prompts an LLM to evaluate individuals within a population based on genetic diversity, fitness level, and crossover compatibility, guiding more informed pairing decisions. We evaluated PAIR against a baseline method called LLM-driven EA (LMEA), published recently. Results indicate that PAIR significantly outperforms LMEA across various TSP instances, achieving lower optimality gaps and improved convergence. This performance is especially noticeable when combined with the flash thinking model, demonstrating increased population diversity to escape local optima. In general, PAIR provides a new strategy in the area of in-context learning for LLM-driven selection in EAs via sophisticated preference modelling, paving the way for improved solutions and further studies into LLM-guided optimization.