资源描述：
《组合最优化问题及其求解优化算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、组合最优化问题最基本的特点就是变量是离散的,由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以
2、使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。1)基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。拉格朗日松弛（LR）算法求解问题的主要思
3、想是分解和协调。首先对于NP难的优化问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Columngeneration,CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一
4、个下界。同时基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性能。2)启发式算法根据求解问题的特点，按照人们经验或某种规则设计的。这是一种构造式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，相对比较简单，这种方法的求解速度较快，但所得解的质量不一定好。3)基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法。这类智能优化算法常见的有：模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算
5、法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等，这些算法也称超启发式算法(Meta-heuristic)。智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特
6、殊信息、易于实现且速度较快等优点,受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。本文的仿真实验分为两个部分,一为通过对实际大规模数据进行的实验,验证算法解决实际问题的能力;二为通过人工产生的小规模数据,测试随机产生的小规模算例，检验算法的解的质量。为验证禁忌搜索算法的质量,使用ILOG公司的约束规划软件CP求解小规模数据,并将CP产生的结果同禁忌搜索产生的结果相比较。在同CP比较中,禁忌搜索算法用远小于CP计算的时间获得了优于或等于CP的解,证明了算法的解质量。第一类实验中,从国内规模最大的
7、某钢铁企业获取了4套实时数据。模型中关于惩罚和目标函数的权重由此钢铁企业的资深专家给定。实验结果如表1所示。禁忌搜索算法较初始解平均改进幅度18158%,证明了禁忌搜索算法面对实际大规模问题的有效性。第二类实验中,随机产生了6组数据以模拟钢铁企业的实际生产情况。使用约束规划软件CP进行求解,通过比较CP和禁忌搜索算法的结果来衡量算法的解的质量。根据实际生产环境,模拟了两个小型的生产系统,分别包含3个和5个工序层,每个工序层上有2个机组。通过控制工单的质量改变问题的规模。CP和禁忌搜索算法的结果如表2所示。禁忌搜索算法在所有6组实验中,获得了等于或者优于C
8、P优化软件所获得的解,而所消耗的计算时间远远少于CP所消耗的时间。考虑CP是目前
