FPTR
一种在硬截止时间约束下优化无线调度等实时决策问题的框架,通过分离强制可行解构造与可选精炼阶段,并采用事务性设计确保每个候选解在截止时间前通过可行性验证且严格改进目标才被采纳,从而保证始终输出可行解。
时间轴 (近 90 天)
FPTR(可行性保持的事务性精炼)是一种优化框架,其核心是始终维护一个已验证的可行分配(现任解),每个精炼阶段独立构建候选解,仅在候选解完整、通过可行性验证且严格改进目标时才替换现任解。
FPTR将强制输出构建与可选精炼分离,首先通过基础构造器生成初步可行解,随后依次执行四个精炼阶段。
FPTR的四个精炼阶段依次为:缓冲区感知的资源选择、兼容组用户共享、基于剩余需求的波束掩码重建、两个资源的联合重新分配。
在150个固定合成实例上,FPTR完整流水线的平均流量比轻量级波束优先参考方案提升3.83%,比其Base构造器提升1.79%。
在另一组匹配输入的测试中,FPTR完整流水线在输出延迟超过100毫秒即零效用的约束下,比六种独立搜索基线(ALNS、禁忌搜索、遗传算法、模拟退火、迭代局部搜索和GRASP)高出6.68%至8.35%。
在内部套件的全部750次FPTR完整流水线运行中,均返回可行分配,且没有一次运行超过100毫秒。
通用搜索框架(如ALNS、禁忌搜索、遗传算法、模拟退火、迭代局部搜索、GRASP)在硬截止时间下可能因无法保证每次迭代输出可行解而失效,而FPTR通过事务性精炼规避了这一缺陷。
FPTR的架构适用于任何需要在硬截止时间下持续输出可行解的优化场景,不仅限于无线调度。
FPTR的开源实现已提供,支持独立复现。
全部知识事实 (9)
FPTR(可行性保持的事务性精炼)是一种优化框架,其核心是始终维护一个已验证的可行分配(现任解),每个精炼阶段独立构建候选解,仅在候选解完整、通过可行性验证且严格改进目标时才替换现任解。
50%待验证FPTR将强制输出构建与可选精炼分离,首先通过基础构造器生成初步可行解,随后依次执行四个精炼阶段。
50%待验证FPTR的四个精炼阶段依次为:缓冲区感知的资源选择、兼容组用户共享、基于剩余需求的波束掩码重建、两个资源的联合重新分配。
50%待验证在150个固定合成实例上,FPTR完整流水线的平均流量比轻量级波束优先参考方案提升3.83%,比其Base构造器提升1.79%。
50%待验证在另一组匹配输入的测试中,FPTR完整流水线在输出延迟超过100毫秒即零效用的约束下,比六种独立搜索基线(ALNS、禁忌搜索、遗传算法、模拟退火、迭代局部搜索和GRASP)高出6.68%至8.35%。
50%待验证在内部套件的全部750次FPTR完整流水线运行中,均返回可行分配,且没有一次运行超过100毫秒。
50%待验证通用搜索框架(如ALNS、禁忌搜索、遗传算法、模拟退火、迭代局部搜索、GRASP)在硬截止时间下可能因无法保证每次迭代输出可行解而失效,而FPTR通过事务性精炼规避了这一缺陷。
50%待验证FPTR的架构适用于任何需要在硬截止时间下持续输出可行解的优化场景,不仅限于无线调度。
50%待验证FPTR的开源实现已提供,支持独立复现。
50%