组合最优化问题及其求解优化算法

组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中,许多的实际问题本质上是离散事件的而不是连续事件,都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题,NP类问题仍属于可计算问题,即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。

常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题,当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时,理论上可以得到问题的最优解,但由于计算量太大,所以使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时,即使能得到最优解,但所需要的计算时间过长,在实际问题中难以直接应用。

近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快,但并不能保证得到问题的全局最优解。近似算法分为基于数学规划(最优化)的近似算法、启发式算法和基于智能优化的近似算法。

1) 基于数学规划(最优化)的近似算法是根据对问题建立的数学规划模型,运用如拉格朗日松弛、列生成等算法以获得问题的近似解,是以数学模型为基础,采用列生成、拉格朗日松弛和状态空间松弛等求解问题。

拉格朗日松弛(LR)算法求解问题的主要思想是分解和协调。首先对于NP难的优化问题,其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数,使耦合约束解除,形成松弛问题,从而分解为一些相互独立的易于求解的子问题,设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。

与智能优化算法相比,基于数学规划的近似算法的优点是通过建立问题的数学模型,松弛模型中难解的耦合约束或整数约束,得到的松弛问题的最优解可以为原问题提供一个下界。同时基于数学规划的近似算法还具有很好的自我评价功能,通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界,上界与下界进行比较,可以衡量算法的性能。

2) 启发式算法根据求解问题的特点,按照人们经验或某种规则设计的。这是一种构造式算法,比较直观、快速,利用问题的知识设计求解的方法步骤,相对比较简单,这种方法的求解速度较快,但所得解的质量不一定好。

3) 基于智能优化的近似算法是基于一定的优化搜索机制,并具有全局优化性能的一类算法。这类智能优化算法常见的有:模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等,这些算法也称超启发式算法(Meta-heuristic)。

智能优化算法是一种通用的算法框架,只要根据具体问题特点对这种算法框架结构进行局部修改,就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架,具有实践的通用性,适应于求解工业实际问题,能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法,采用不同的搜索策略和优化搜索机制,寻找问题的近似最优解,具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解,但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。

本文的仿真实验分为两个部分,一为通过对实际大规模数据进行的实验,验证算法解决实际问题的能力;二为通过人工产生的小规模数据,测试随机产生的小规模算例,检验算法的解的质量。为验证禁忌搜索算法的质量,使用ILOG公司的约束规划软件CP 求解小规模数据,并将CP 产生的结果同禁忌搜索产生的结果相比较。在同CP 比较中,禁忌搜索算法用远小于CP计算的时间获得了优于或等于CP 的解,证明了算法的解质量。

第一类实验中,从国内规模最大的某钢铁企业获取了4 套实时数据。模型中关于惩罚和目标函数的权重由此钢铁企业的资深专家给定。实验结果如表1 所示。禁忌搜索算法较初始解平均改进幅度18158 % ,证明了禁忌搜索算法面对实际大规模问题的有效性。

第二类实验中,随机产生了6 组数据以模拟钢铁企业的实际生产情况。使用约束规划软件CP进行求解,通过比较CP 和禁忌搜索算法的结果来衡量算法的解的质量。根据实际生产环境,模拟了两个小型的生产系统,分别包含3 个和5 个工序层,每个工序层上有2 个机组。通过控制工单的质量改变问题的规模。CP 和禁忌搜索算法的结果如表2 所示。禁忌搜索算法在所有6 组实验中,获得了等于或者优于CP 优化软件所获得的解,而所消耗的计算时间远远少于CP 所消耗的时间。考虑CP是目前最好的约束规划软件之一,小规模的实验证明了算法的解的质量。

组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中,许多的实际问题本质上是离散事件的而不是连续事件,都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题,NP类问题仍属于可计算问题,即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。

常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题,当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时,理论上可以得到问题的最优解,但由于计算量太大,所以使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时,即使能得到最优解,但所需要的计算时间过长,在实际问题中难以直接应用。

近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快,但并不能保证得到问题的全局最优解。近似算法分为基于数学规划(最优化)的近似算法、启发式算法和基于智能优化的近似算法。

1) 基于数学规划(最优化)的近似算法是根据对问题建立的数学规划模型,运用如拉格朗日松弛、列生成等算法以获得问题的近似解,是以数学模型为基础,采用列生成、拉格朗日松弛和状态空间松弛等求解问题。

拉格朗日松弛(LR)算法求解问题的主要思想是分解和协调。首先对于NP难的优化问题,其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数,使耦合约束解除,形成松弛问题,从而分解为一些相互独立的易于求解的子问题,设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。

与智能优化算法相比,基于数学规划的近似算法的优点是通过建立问题的数学模型,松弛模型中难解的耦合约束或整数约束,得到的松弛问题的最优解可以为原问题提供一个下界。同时基于数学规划的近似算法还具有很好的自我评价功能,通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界,上界与下界进行比较,可以衡量算法的性能。

2) 启发式算法根据求解问题的特点,按照人们经验或某种规则设计的。这是一种构造式算法,比较直观、快速,利用问题的知识设计求解的方法步骤,相对比较简单,这种方法的求解速度较快,但所得解的质量不一定好。

3) 基于智能优化的近似算法是基于一定的优化搜索机制,并具有全局优化性能的一类算法。这类智能优化算法常见的有:模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等,这些算法也称超启发式算法(Meta-heuristic)。

智能优化算法是一种通用的算法框架,只要根据具体问题特点对这种算法框架结构进行局部修改,就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架,具有实践的通用性,适应于求解工业实际问题,能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法,采用不同的搜索策略和优化搜索机制,寻找问题的近似最优解,具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解,但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。

本文的仿真实验分为两个部分,一为通过对实际大规模数据进行的实验,验证算法解决实际问题的能力;二为通过人工产生的小规模数据,测试随机产生的小规模算例,检验算法的解的质量。为验证禁忌搜索算法的质量,使用ILOG公司的约束规划软件CP 求解小规模数据,并将CP 产生的结果同禁忌搜索产生的结果相比较。在同CP 比较中,禁忌搜索算法用远小于CP计算的时间获得了优于或等于CP 的解,证明了算法的解质量。

第一类实验中,从国内规模最大的某钢铁企业获取了4 套实时数据。模型中关于惩罚和目标函数的权重由此钢铁企业的资深专家给定。实验结果如表1 所示。禁忌搜索算法较初始解平均改进幅度18158 % ,证明了禁忌搜索算法面对实际大规模问题的有效性。

第二类实验中,随机产生了6 组数据以模拟钢铁企业的实际生产情况。使用约束规划软件CP进行求解,通过比较CP 和禁忌搜索算法的结果来衡量算法的解的质量。根据实际生产环境,模拟了两个小型的生产系统,分别包含3 个和5 个工序层,每个工序层上有2 个机组。通过控制工单的质量改变问题的规模。CP 和禁忌搜索算法的结果如表2 所示。禁忌搜索算法在所有6 组实验中,获得了等于或者优于CP 优化软件所获得的解,而所消耗的计算时间远远少于CP 所消耗的时间。考虑CP是目前最好的约束规划软件之一,小规模的实验证明了算法的解的质量。


相关文章

  • 粒子群算法和蚁群算法的结合及其在组合优化中的应用e
  • 空间电子技术 !"空间电子技术TECHNOLOGYSPACEELECTRONIC2007年第2期粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 (西安电子科技大学综合业务网国家重点实验室,西安710071) ...查看


  • 具有变异特征的蚁群算法
  • JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT 1999年 第36卷 第10期 Vol.36 No.10 1999 具有变异特征的蚁群算法 吴庆洪 张纪会 徐心和 摘 要 蚁群算法是一种新型的模拟进 ...查看


  • 混合智能算法及其在供水水库群优化调度中的应用
  • 水 2007年12月利SHUILI学XUEBAO报第38卷第12期文章编号:0559.9350(2007)12-1437一07 混合智能算法及其在供水水库群优化调度中的应用 刘卫林1'2,董增川1,王德智3 (1.河海大学水文水资源与水利工 ...查看


  • 自适应蚁群算法
  • 第 卷第 期 年 月 文章编号: ( ) 控制理论与应用 , , 自适应蚁群算法! 张纪会 (东北大学控制仿真中心・沈阳, ) 高齐圣徐心和 (青岛化工学院计算机系・青岛,・沈阳, )(东北大学控制仿真中心 ) 摘要:蚁群算法是由意大利学者 ...查看


  • 旅行商问题描述及其蚁群优化算法
  • 计算机研究与发展 JournalofComputerResearchandDevelopment ISSN 1000-1239/CN11-1777/TP 47(3):434-444.2010 基于多粒度的旅行商问题描述及其蚁群优化算法 冀俊 ...查看


  • 食用农产品采购合同组合反向拍卖的优化
  • 中国流通经济2012年第11期口电子商务 食用农产品采购合同组合反向拍卖的优化 顾小林1一,浦徐进1,曹文彬1 (1.江南大学,江苏无锡214122:2.河海大学,江苏南京210098) 摘要:目前食用农产品采购成本较高.应从根本上对采购方 ...查看


  • 粒子群优化算法及其应用
  • 2006年第1期信息技术 InformationTechnology 中图分类号:TP391.9 文献标识码:A 文章编号:1009-2552(2006)01-0053-04 粒子群优化算法及其应用 范 娜,云庆夏 (西安建筑科技大学管理科 ...查看


  • 基本遗传算法及其在函数优化中的作用
  • <人工智能及其应用大作业(一)> 题 目: 学 号: 姓 名: 基本遗传算法及其在函数优化中的作用 基本遗传算法及其在函数优化中的应用 摘要: 从遗传算法的编码.遗传算子等方面剖析了遗传算法求解无约束函数优化问题的一般步骤, 并 ...查看


  • 基于ABC算法的逻辑推理题快速求解方法_李林菲
  • 计算机技术与发展第21卷 第6期 ol.21 No.6 V 2011年6月June 2011COMPUTERTECHNOLOGYANDDEVELOPMENT 基于ABC算法的逻辑推理题快速求解方法 李林菲,马 苗 (陕西师范大学计算机科学学 ...查看


热门内容