求解排列组合问题的解空间动态缩减策略

李章洪，梁晓磊，田梦丹，周文峰

（武汉科技大学汽车与交通工程学院，武汉430065）（*通信作者电子邮箱liangxiaolei@wust.edu.cn）

0 引言

排列组合优化问题是一类NP-hard 问题，此类问题规模的扩大将导致解空间呈指数式增长，对求解算法具有极高的要求。典型的问题有旅行商问题（Travel Salesmen Problem，TSP）、车辆路径调度问题（Vehicle Routing Problem，VRP）、船舶配载（Stowage Optimization，SO）问题等。现代智能优化算法是解决排列组合优化问题的主要方法，目前主要集中于对蚁群优化（Ant Colony Optimization，ACO）算法、模拟退火（Simulated Annealing，SA）算法、遗传算法（Genetic Algorithm，GA）、免疫算法（Immune Algorithm，IA）等启发式算法及其改进等方面，其思路主要以算法自身机制调整及多种算法混合进行算法性能提升。例如：针对TSP，为了避免传统遗传算法容易陷入局部最优解的缺点，于莹莹等［1］引入贪婪算法对种群进行初始化；何庆等［2］将模拟退火算法和遗传算法进行了有效的组合；胡云清［3］提出了一种混沌模拟退火算法来求解VRP，提高了问题的求解速度。针对传统蚁群算法求解速度慢、容易陷入局部最优解的问题，周永权等［4］对蚁群算法信息素的更新规则做出了改变；吴新杰等［5］通过改进基本的蛙跳算法，增大了搜索空间，在一定程度上防止了TSP容易早熟的缺陷；王艳等［6］引入对数递减的惯性权重来影响萤火虫的位置，并结合遗传算法中的选择、交叉、变异等概念对萤火虫算法进行改进；为了增强烟花算法求解TSP的稳定性、提高收敛速度，蔡延光等［7］提出了一种混沌烟花算法。上述为此类问题的研究提供了较好的思路和解决方法，但集中于算法自身搜索机制的改进，对算法搜索行为和问题特征的融合分析较少，当问题规模急剧增加时仍然面临着解空间过大、个体有效搜索缓慢、群体搜索停滞等问题。……