大型语言模型在空间感知提案生成中用于局部搜索求解p中位问题的基准测试

《Computers, Environment and Urban Systems》:A benchmark of large language models for spatially informed proposal generation in local search for the p-median problem

【字体: 大 中 小 】 时间:2026年07月25日 来源:Computers, Environment and Urban Systems 8.9

编辑推荐:

  研究人员提出LLM-1Swap框架,将大型语言模型(LLM)作为提案生成器嵌入单交换(one-swap)局部搜索中,配合外部确定性评估与ε-贪婪(ε-greedy)接受机制。研究人员在六个TSPLIB实例与多个p值上测试三种前沿LLM,对比精确混合整数规划(M

  
研究人员提出LLM-1Swap框架,将大型语言模型(LLM)作为提案生成器嵌入单交换(one-swap)局部搜索中,配合外部确定性评估与ε-贪婪(ε-greedy)接受机制。研究人员在六个TSPLIB实例与多个p值上测试三种前沿LLM,对比精确混合整数规划(MIP)与五种经典启发式。结果表明,LLM引导的搜索优于贪婪基线,在小规模案例接近最优,且评估次数远少于禁忌搜索(Tabu Search)。消融实验显示仅提供坐标不足够,迭代状态反馈与全局空间摘要可提升鲁棒性。LLM能生成有意义的空间感知提案,但仍落后于成熟启发式,这推动更强混合设计的发展。
研究背景与动机
在地理空间研究领域,生成式人工智能尤其是大型语言模型(Large Language Model,LLM)正被探索融入优化流程。现有LLM用于优化的工作多聚焦自然语言转模型、代码生成或作为黑盒进化优化器,而在经典空间优化工作流内部,LLM能否真正利用空间关系仍缺乏受控基准。p中位问题(p-median problem)自Hakimi于1960年代提出以来,是选址科学中NP难(NP-hard)的经典模型,广泛应用于消防站、医院、充电站布局等。尽管精确法(如分支定界)与启发式/元启发式(贪婪增删、Teitz–Bart单交换、禁忌搜索、变邻域搜索)已高度成熟,但LLM能否作为“空间感知提案者”在单交换局部搜索中提出高质量交换,尚未被系统评测。为此,研究人员在《Computers, Environment and Urban Systems》发表本研究,构建LLM-1Swap基准,以经典启发式为参照,量化LLM的空间推理能力。
主要关键技术方法
研究人员选用六组TSPLIB欧氏点集(eil51、eil101、ch150、pr152、u159、kroB200),每组配三至四个p值构成小规模至中等规模测试。算法侧设三类对照:精确MIP(PuLP+CBC)、经典启发式(Greedy Add、Greedy Drop、Best-Improving单交换、简易Tabu Search)、LLM引导单交换(LLM-1Swap)并接入OpenAI o4-mini、GPT-4.1与Claude Sonnet 4.5。LLM-1Swap在Algorithm 1中维护当前解St与目标值f(St),每轮以模块化提示(A–I组件)喂入坐标、k-means聚类摘要(k=p)、离群点(μ+2σ)、设施统计、最难分配点、按增益排序的候选关站点等派生空间信号,LLM产出至多K个单交换提案,外部确定性oracle算目标,无改进则重提示至多R次,最终以ε-greedy接受(1?ε选当前最优,ε选非最优)并更新最优解,辅以change-guard防立即可逆。超参随实例规模自适应(K=10–15,T=40–100,M=8–20,R=3–6,ε=0.05–0.12)。
研究结果
4.4.1 示例轨迹
在eil51(p=3)从随机解{11,31,35}出发的GPT-4.1运行中,迭代1–5快速将间隙由23.9%压至1.8%;第6步ε-探索接受劣解(间隙回弹至13.2%),第7步即达全局最优{15,16,47}(间隙0%),后续探索期正确留存最优。轨迹证明LLM引导推理配ε-greedy可有效穿越解地形。
4.4.2 计算结果与经典启发式比较
解质量上,Tabu Search与随机起点Best-Improving(BI)在18组设定中best-of-all间隙多为0.00%,LLM-1Swap在eil51/ch150小p下best-of-all常达0%或<1.72%,均值间隙随规模上升(p=10时1.56–2.10%,p=40时3.02–8.08%)。o4-mini在中小例均值最低但大p方差剧增,Claude-4.5大例最稳,GPT-4.1居中。效率上,经典启发式亚秒级;LLM因推理耗时百至万秒,但评估候选数仅102–103次,不到Tabu Search(105–106次)的0.1%,说明LLM是“知情提案器”。运行时长对N缩放指数α≈1.87、对p指数β≈0.59–0.69,慢于BI(α=2.48)但token处理主导延迟。
4.4.3 提示消融
坐标仅单次直出效果最差;迭代坐标+历史仍显著逊于全提示,证明迭代反馈与派生空间摘要(聚类、top-gain短名单)必要。删top-candidates(H)在大不规则例(pr152、kroB200)明显变坏;删worst-assigned(G)反而匹配或优于全提示(池化Wilcoxon显著),说明过度引导至局部难点未必利全局;删cluster(D)在pr152/u159/kroB200退化;outlier(E)删减无显著影响,坐标已含该信息。
4.4.4 已接受改进交换的后验空间富集
对GPT-4.1全提示下10067次已接受改进交换标注:Q2(插入top-5增益点)占55.7% vs 空期望4.1%;Q1(移除top-2 p95设施)占40.0% vs 14.4%;Q3(移除冗余低loss设施)21.9% vs 14.4%,均p<0.0001。证明LLM提案非随机,集中于缓解尾压、开高增益点、弱冗余移除。
讨论与结论翻译
研究人员将LLM作提案器嵌入单交换局部搜索,外部算分与ε-greedy接受,公平对照经典启发式。LLM-1Swap在51–200点六例多p下展现有意义空间推理:近优、胜贪婪构造、将搜索集中至极少候选;但Tabu Search等在质量/时长/鲁棒性仍更强,故本研究贡献在刻画LLM引导空间提案的当下能力而非替代经典p中位启发式。核心权衡在于经典法擅长高速扫邻域,LLM以高信息提案换吞吐,未来可通过提示压缩、降调用、与快速局部改进及轻量记忆(tabu式账本)杂交来提速。消融指明坐标不足、迭代反馈必需、聚类与top-gain可靠、worst-point与outlier提示效用不及预期;提示组件效用依空间结构而异,自适应提示是方向。更进一步,可让LLM不仅提提案而设计邻域过滤器、交换打分、接受与多样化机制,迈向LLM驱动的空间优化自动算法设计。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号