解一类组合优化问题的新方法-论文.pdf

《解一类组合优化问题的新方法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、石油仪器2014年第28卷第3期PETRoLEUMINSTRUMENIS·61··方法研究·解一类组合优化问题的新方法王晓萍贾建涛(1．西安文理学院软件学院陕西两安)(2．中国石油技术开发公司北京)摘要：混合LT法是解决一类组合优化问题的新型方法。这种方法将等式约束用Lagrange方法来处理，将0—1约束用罚函数或障碍函数来处理。文章根据这种新型方法的构造框架，设计了求解一类组合优化问题的一种通用新方法，该方法可以使等式约束自动满足，0—1约束逐步满足。并且对新方法做出收敛性分析，给出了收敛性的必要条件。最后进行了计算机模拟实验，结果说明这种方法是可行的和有效的。关键词：组

2、合优化；HybridLT方法；神经网络中图法分类号：TP30I．6文献标识码：B文章编号：1004—9134(2014)03—0061—03有效0引言然而，Xu等人提出的方法也有缺陷，它无法从组合优化在计算机科学、电子工程等诸多工程领理论上保证找到准确的最优解。本文提出一种新的迭域有着广泛的应用，但它们中的许多问题是NP困难代格式，确保Hybrid—LT方法转化后的问题与原问题的。除了传统的组合优化求解算法外，神经网络方法在同一点取得最优值。进而，本文讨论了Xu未讨论也是解决组合优化问题的一种有效方法。目前，研究的收敛性问题，给出了其收敛的必要条件，在理论上人员在这方面已做了

3、一些行之有效的工作l1。概括说明了其优越性和可行性。本文考虑许多NP困难的起来，主要有两个共同的特征。其一是将约束全部转组合优化问题的如下抽象形式：化为二次罚函数，并将罚函数作为能量函数的一部min(Ⅳ分；其二是通过神经网络把组合优化问题转化为对二．∑v=，=1，⋯，M，i=1次能量函数进行优化的无约束优化问题。由于这些转换后的模型可用Hopfield型网络实现，我们称这些方∑v一mDro，i=1，⋯，JV，J=I法为Hopfield方法[引。但Hopfield型网络无法适应于vi：0or1foreachiandJ(1)非二次的能量函数，因而不能用于求解很多组合优化其中=(V

4、u)N~M，，J=1，⋯，MND~o，i=1，问题，使用范围比较狭窄。为了克服这个缺点，Xu⋯，Ⅳ为给定值。如，TSP问题，标准线性指派问题等人提出了一个Hybrid—LT方法(aHybridofLagrange和K一连通图问题等一系列问题都可写成上面问题(1)andTransformationapproaches)l3j，此法不再限于Hop—的形式[]。field型网络上面所述的两个特征。它把约束分为两个1迭代公式的导出部分，用不同的方法去处理。具体地讲，用Lagrange方法来处理线性等式约束，用罚函数或障碍函数处理考虑问题(1)，我们把线性常量和约束(前两组二值约束(0

5、—1约束)。这样处理有如下的几个优点：约束)做Lagrange变换，并且把二值约束(最后一组)首先，它能用于非二次能量函数，而Hopfield方法只转化为罚函数或障碍函数。即问题转化为如下形式：能用于二次能量函数。其次，它确保满足线性等式约E(v)=(+∑[∑v一。f]+∑【∑v，1flf_1l束(线性常量和约束)自动满足，而Hopfield方法用～M加权的罚函数来做近似处理，参数需外部控制，不能—Dw】+∑∑(1，)(2)保证这些约束自动满足。Lao、Shan和Xu已经证明／~B(vu)：(10’q≥。．Hybrid-LT方法比Hopfield型的方法收敛速度更快、更第一作

6、者简介：王晓萍，女，1962年生，高级工程师，1983年毕业于西北大学计算数学专业，曾长期在西安石油勘探仪器总厂从事软件研发工作，现住西安文理学院软件学院主要从事进化算法研究和软件开发应用研究工作。邮编：710063石油仪器·62·PETRoLEUMINSTRUMENlS首先，=g及≠0’令并GO=G【En()，，Y】，G’=G，[En((’)，(，】，(]变形得定理1(必要条件)：若迭代式收敛到问题的解(3)(，，Y)，且>0，P>0，那么当(’分靠近(后充分大)时，limG(E~k，X¨，Y‘)／pflk—O0。—+oo(4)证明：对k／T>0充分大，若㈨收敛到，则对取V

7、O，存在ko>0，使得当k>／co时，有l一vO．I