正文

Optimal Selection：基于混合优化算法的覆盖设计问题求解系统

CS360人工智能课程项目，实现精确算法与启发式混合求解器，解决组合数学中的覆盖设计问题

组合优化覆盖设计问题分支限界启发式算法Numba加速FlaskPython集合覆盖

发布时间 2026/04/29 15:44最近活动 2026/04/29 15:51预计阅读 2 分钟

章节 01

Optimal Selection项目导读：混合优化算法求解覆盖设计问题

Optimal Selection是CS360人工智能课程团队项目，旨在解决组合数学中的NP难问题——覆盖设计问题。该项目实现了精确算法与启发式混合的高性能求解器，结合Numba加速等技术提升效率，并提供友好的Web界面，可应用于实验设计、机器学习数据采样等多个领域。

章节 02

覆盖设计问题的背景与数学定义

覆盖设计问题是组合优化中的经典NP难问题，需从候选样本中选择最少k元组，使任意j个样本组合至少出现在s个k元组中。其数学定义涉及参数m（样本池大小45-54）、n（选择样本数7-25）、k（每组大小4-7）、j（覆盖子集大小s≤j≤k）、s（覆盖次数3-7）等，约束为s≤j≤k≤n≤m。例如从9个样本选6元组，要求任意5样本组合至少出现5次，最优解含14组。

章节 03

系统架构与混合算法设计

Optimal Selection采用四层架构：1.预处理层：问题约简+位掩码编码缩小搜索空间；2.下界估计层：计数下界与Schönheim下界评估解质量并剪枝；3.混合求解器：小规模用分支限界（LNS+局部搜索）得最优解，中大规模用启发式暖启动；4.质量搜索层（v2增强）：全局贪心构造、固定B下降压缩、LNS破坏修复、局部搜索抛光。

章节 04

技术实现亮点

项目技术亮点包括：1.Numba JIT加速关键循环，提升30倍速度；2.全位集编码（Python大整数）优化中等规模实例的集合操作；3.自适应时间预算：按问题规模分配120/300/600秒，65%用于构造，35%用于质量搜索；4.规模保护机制：避免超大规模实例内存爆炸；5.K组去重支持多重覆盖场景。

章节 05

应用场景与性能评估

应用场景涵盖实验设计（医学/农业试验）、机器学习数据采样、统计抽样、组合测试。性能测试分三层：正确性测试（小型实例验证解正确）、质量测试（中等实例gap可接受）、压力测试（极端参数稳定性）。v2版本在n=20,k=6,j=5,s=4实例中组数从185降至178。

章节 06

局限性与未来改进方向

当前局限：超大规模实例（n>25）求解效率低；参数范围有限；并行化不足。未来方向：引入遗传/模拟退火算法；分布式并行求解；支持灵活约束（权重/优先级）；提供解结构可视化工具。

章节 07

安装与使用指南

系统依赖Python3.11+，需安装Flask、NumPy、Numba。安装步骤：pip install flask numpy numba；启动方式：python web_app.py或./start.sh。首次运行Numba需10-30秒编译，后续用缓存。默认运行在http://localhost:3000，支持移动设备访问。