面向 LLM 自动化算法设计的代码相似性再思考

摘要

基于大语言模型的自动化算法设计（LLM-AAD）的兴起，通过自主生成专家级算法的代码实现改变了算法开发。与传统专家驱动的算法开发不同，LLM-AAD 范式中算法背后的主要设计原则往往隐含在生成代码里。因此，直接从代码评估算法相似性、区分真正的算法创新与单纯的语法变化变得至关重要。尽管已有多种代码相似度指标，它们无法捕捉算法相似性，因为其聚焦表层语法或输出等价而非底层算法逻辑。我们提出 BehaveSim，一种通过问题求解行为——即执行过程中产生的中间解序列，称为问题求解轨迹（PSTrajs）——来度量算法相似性的新方法。通过动态时间规整（DTW）量化 PSTraj 间的对齐，BehaveSim 能在语法或输出层面相似的情况下区分逻辑各异的算法。我们展示其两个关键应用：（i）增强 LLM-AAD：把 BehaveSim 集成到既有框架（如 FunSearch、EoH）促进行为多样性，在三个 AAD 任务上显著提升表现。（ii）算法分析：BehaveSim 按行为聚类生成算法，支持对问题求解策略的系统分析——这对不断增长的 AI 生成算法生态是关键工具。本文数据与代码已在 https://github.com/RayZhhh/behavesim 开源。

面向 LLM 自动化算法设计的代码相似性再思考 — 图8：FunSearch+BehaveSim概览。(a) 我们利用一个多岛算法数据库，其中每个岛屿包含按相同分数分组的算法簇。(b) 在选择阶段，从数据库中选出一个岛屿。在所选岛屿内，各簇按分数排定优先级，分数越高越优先。选定一个簇后，再从中选出一个算法，优先选择较短的实现以促进简洁性。(c) 被选中的算法用于构造提示（prompt），引导LLM生成新算法。(d) 对新生成的算法进行评估，以确定其适应度分数与问题求解轨迹。(e) 最后，被评估的算法被分配到行为相似度最高的岛屿，并放入相应的簇。