组合最优化问题及其求解优化算法.doc
版权申诉
38 浏览量
2022-05-30
19:32:43
上传
评论
收藏 38KB DOC 举报
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和
约束函数在其可行域内是也是离散的。在现实世界中，许多的实际问题本质上是离散事件
的而不是连续事件，都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题，
NP类问题仍属于可计算问题，即存在算法来求解。求解这类组合最优化问题方法分为精确
算法和近似算法两类。
常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题，
当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大
规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确
算法并不可行。利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要
的计算时间过长，在实际问题中难以直接应用。
近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较
快，但并不能保证得到问题的全局最优解。近似算法分为基于数学规划（最优化）的近似
算法、启发式算法和基于智能优化的近似算法。
1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉
格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉
格朗日松弛和状态空间松弛等求解问题。
拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。首先对于NP难的优化
问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束
引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的
子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解
的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性
规划、整数规划及混合整数规划问题的算法。
与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，
松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个
下界。同时基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问
题的近优解(或最优解)为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性
能。
2) 启发式算法根据求解问题的特点，按照人们经验或某种规则设计的。这是一种构造
式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，相对比较简单，这种方
法的求解速度较快，但所得解的质量不一定好。
3) 基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类
算法。这类智能优化算法常见的有：模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路
径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子
群算法(PSO)等，这些算法也称超启发式算法(Meta-heuristic)。
智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进
行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具
有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满
意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近
似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解
但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广
泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题
主要的有效方法。
资源评论
