会员注册 | 登录 | 海量教育、办公资料尽在三一文库!
下载费用:0 免费

基于网格划分的混合优化算法

扫一扫手机浏览此亚博体育yabo

下载积分:0
亚博体育yabo格式:DOC |浏览次数:0 |上传日期:2015-11-09

关键词:

内容简介:第29卷第2期 2007年2月文章编号:1001—506X(2007)02—0312—04系统工程与电子技术Systems Engineering and ElectronicsV01.29No.2Feb.2007基于网格划分的混合优化算法陈健1 ,李歧强2山东大学控制科学与工程学院,山东济南250061)(1.青岛理X-大学理学院,山东青岛266033;2.摘要:提出了用于求……86,127。

第29卷第2期 2007年2月文章编号:1001—506X(2007)02—0312—04系统工程与电子技术Systems Engineering and ElectronicsV01.29No.2Feb.2007基于网格划分的混合优化算法陈健1 ,李歧强2山东大学控制科学与工程学院,山东济南250061)(1.青岛理X-大学理学院,山东青岛266033;2.摘要:提出了用于求解大规模优化模型的基于网格划分的混合算法。该算法引入了空间划分和收缩的思想,在求解过程中首先应用全局优化算法确定优解信息,其次使用网格划分和合并将解空间快速划分和收缩为多 个子空间,然后用局部优化算法在模型的极值点附近搜索,可以很快地收敛到极值点。仿真结果表明该算法在搜 索效率、应用范围、解的精确性和鲁棒性上都体现了良好的性能。 关键词:网格划分;优化;演化算法 中图分类号:TP301.6 文献标识码:AHybrid optimization algorithm basedCHEN Jianl。LIongrid partitioningQi—qian92Univ.,Jinan 250061,China)(1.School of Science,Qingdao Technological Univ.,Qingdao 266033,China;2.SchoolofControl Science and Engineering,ShandongAbstract:A hybrid optimization algorithm basedongrid partitioning for solving large—scale optimization isproposed.The algorithm adopts the idea of space partitioning and contracting.Firstly,the global optimization algorithm is usedto togain the information of elite solutions.Then the grid partitioning and uniting the solutions spaceasareorganizeddivide andcontractmulti—subspaces.Finally,in ordertoobtai

亚博体育yabon the extrema the localoptimal algorithm is applied in these subspaces.The numerical simulation result shows that the proposed algo— rithm iS robust,effective,and efficient. Keywords:grid partitioning;optimization;evolutionary algorithm0引言搜索算法,它首先将解空间划分为若干子空间,然后在每个 子空间内分别选取若干个测试点,通过测试点的好坏来确 定保留或淘汰的空间。在局域性不好的搜索空间中,如果 这种算法保留的空间和测试点数不足够大,则很难找到全 局最优点。ACSSOS[51也是一种快速的空间收缩的算法, 但它要求适应值函数的搜索空间具有连续性和凸性,对于 不满足这些条件的问题便无能为力。另外,基于空间收缩 的并行演化算法[61应用了快速有效的不完全演化搜索较优 解的分布信息,通过分布信息定位最优解的可能分布,逐步 缩小求解空间。收缩空间时由于采用了由精英个体决定下 次搜索空间的方法,因此算法具有更高的搜索效率,应用范 围也更广。 笔者研究了一种新的空间划分和收缩算法,应用快速优化技术是一种以数学为基础,用于求解各种工程问 题优化解的应用技术,作为一个重要的科学分支一直受到 人们的广泛重视,并在诸多工程领域得到迅速推广和应用。 但目前在实际生产过程中的优化问题大多是NPC问题。 虽然人们早已采用了遗传算法、模拟退火等现代优化算法 解决这类问题,但是由于算法本身的局限性,在很多问题上 还无法达到高精度和高效率。 在算法中引入空间划分或空间收缩是一种有效改善上 述问题的思想,空间收缩可以快速地缩小寻优空间,极大地 提高收敛速度,空间划分将解空间划分成若干个子空间,在 各个子空间中寻优可以有效地降低算法陷入局部极值的可 能性,提高了算法的精度和收敛速度。现在有很多空间搜 索算法,都是通过空间的划分和淘汰实现搜索。MIHDE 算法[31已经成功解决了很多MINLP问题,但对有些问题得 到的解的质量不高。GT算法[43是一种快速而有效的空间收稿日期:2005—11—30;修回日期:2006一07—17。 基金项目:山东省自然科学基金(Y2003G01)资助课题有效的不完全演化算法得到优解信息,然后应用网

格划分把空间划分和收缩为多个子空间,最后应用局部优化算法 同时搜索多个子空间,从而可以找到多个局部极值。该新 算法在不完全演化中加入了多样化的初始化,以保证初始作者简介:陈健(1969一),女,助教,硕士,主要研究方向为现代优化算法。E—mail;janec@163.com万   方数据 第2期陈健等:基于网格划分的混合优化算法·313·群体在解空间的均匀分布。该算法可以解决线性、非线性、 混合整数规划等模型,不完全演化算法和完全演化算法的 选取也可以根据模型特点和用户要求来选择各种优化 算法。个取值区间是已知的,那么这个变量就叫做半限定变量,这 个区间就是半限定变量真值的一个估计。 定义2半限定变量的限定度设有向量X一(z。,z:, …,z。)∈R”,其对应的半限定向量为X一(X。,Xz,…, X。),则各半限定变量的限定度定义为y(X。)一e”,i一1,2,…,竹 (1)1算法的主要思想1.1空间划分和收缩I.1.1不完全演化和完全演化Mo式中:Ⅵ——收缩后变量五的取值范围,V7。——收缩前变量z。的取值范围,即 1,Xi为连续变量 z。为离散变量大多数的演化算法在运行初期,群体中个体的适应值改进较快,执行到一定代数后,群体中的个体分散在各个峰 值附近,此后用遗传操作很难再改进后代适应值,从而导致 收敛速度变慢。如果当个体分散在各个峰值附近时停止演 化,便称之为不完全演化算法。它的优点是可以快速获取 较优点信息。重复进行不完全演化,便可获得足够多的较 优点信息,为定位最优解、缩小解空间提供依据。 完全演化即将演化算法进行到求得最优解为止,在收 缩后的空间进行完全演化算法,就可以较为容易地求得最 优解。因此一般采用局部寻优能力强或者速度快的算法作 为完全演化算法。1.1.2y.一』|Vr—Vr1N:,(2)『|V77“一V7P I,z,为连续变量 1个数。 限定度是衡量空间收缩程度的工具。半限定变量的限 定度越大,原组合优化问题的解空间就被压缩的越大,搜寻 最优解所花的时间就会越短。 1.3网格划分的思想 网格划分成功应用在聚类问题中,主要思想是以一 定的空间方式而不是点的形式聚类点集,其特点是快N7。,置为离散变量式中:V?“和V?…——X,的区间端点,N,——xi的元素空间划分和收缩通过在解空间内进行不完全演化,快速获得足够数目 的较优点信息。将传统的根据空间来决定测试点的

方法, 改为由测试点来决定空间,把保留空间改为保留测试点。 测试点选取不完全演化后的精英解,由精英解决定的空间 作为下一代的解空间。这样做可以充分利用不完全演化 得到的分布信息,快速高效的对空间进行收缩和划分。最 后在收缩和划分后的子空间内完全演化得到最终的最 优解。 如图1所示某二维空间划分和收缩示意图。假设初始 解空间为图中的方框ABCD,经过一次不完全演化后得到速、有效,它可以应用在任意形状的聚类问题中。基于密度的网格划分n3是一种新颖的聚类方式,它能够快速 的把点集划分到不同的类别中,对大多数问题得到的结 果也非常好。 在大规模优化问题中,空间的收缩和划分思想的引入 对这类优化问题的求解会有很大的帮助。用基于网格的聚 类方法来实现解空间的划分和收缩,是空间划分和收缩的 结合,是一种有效的空间的划分和收缩。1.3.1对解空间应用网格划分了一些精英解——图中的黑点,由这些点确定的新空间为图中虚框所表示的三个子空间。、y该步骤在算法实现不完全演化之后执行,具体做法十 分简单,把空间的每一维均。,、 分为若干个小段,这样所有AB维组合起来就形成了若干个 高维网格,在这里需要注意I.‘.渲.。3i翠.:r…一I罢的问题是划分的疏密直接影 响到了算法的好坏,网格太L|=一;犁● ● -\.|’厂、√r‘l~Z大,起不到划分的效果;网格 太小,会使时间复杂度指数图2对一维问题的网格划分鼾 件;。Cg:。。i .fD增加,所以一个合适的划分是必要的。我们拿一维优化问 题为例,如图2所示,是一种比较优的划分。 定义3 网格密度:网格内精英点的个数。z。,定义4网格中心:假设某网格空间X{(z,,z。)I图1空间划分和收缩示意图z。∈R1),则此网格中心为 z。一(z,+z。)/2,z。∈R” 定义5 定义6 网格距离:为网格中心的欧氏距离。(4)1.2半限定数学方法 定义1半限定变量(Subdefinite Variables)若一个变 量z的实际值(点值)是未知的,但包含该变量实际值的一网格直径d:d一./∑d;,d:是网格在第i维的万   方数据 ·314·系统工程与电子技术第29卷分量。 假设已经通过全局优化算法得到了较优点信息,这些 较优点都分布在各个峰值附近,为了得到解空间的一个较 好的划分,使得每个子空间只拥有一个局部最优解,我们制 定了下面的规则。 假设已知该

问题存在k个局部最优点和m个精英 解,则: 定理1 在划分后每个子空间最多有一个局部最优解的空间应用网格密度合并网格。 确定k值之后,网格合并这一过程也很容易实现。 假设密度大于0的网格个数大于k,那么把网格按照密 度排序,前k个网格作为聚类中心,把剩余的网格合并 到前k个网格,这样得到愚个子空间。若密度大于0的网 格个数小于等于忌,不进行网格合并。 网格合并的具体步骤为: (1)计算网格密度; (2)选择聚类中心; (3)把剩余的网格按照到 各个中心的最短网格距离合并 到某个聚类中心。(5)…n.r、的充分条件是网格直径d=^/≥:d;略小于任意两局部最V—■j厂、优点的欧氏距离√∑(z。一ze)2的最小值。即V{01Lr;2i————————————一d<min./>:(z自一z≈)2。V"7-图3为网格合并后得到的图3对一维问题的网格合并 三个子空间,这里k一3。 1.4全局优化阶段 应用全局优化算法的目的是得到模型的精英解,属于 不完全演化阶段。根据不同的问题可以选择不同的方法。 针对大规模非凸优化问题,本文选择遗传算法作为全局优 化算法。 1.4.1多样化初始化 对于空问划分和收缩算法而言,如果能够保证初始群 体均匀分布在优化空间对找到全局最优解是很有帮助的,证明反证法。若某一网格内存在两个局部最小值, 他们的欧氏距离必然大于等于任意两局部最优点欧氏距离的最小值,由于d<rain^/∑(za—zn)2,该两局部最优点VJ的欧氏距离也必然大于d,因此在以d为直径的超球体中必 然不同时含有这两个局部最小值,因此该网格内也必然不同时含有这两个局部最小值,矛盾。定理2已知k个局部最优点,空间划分后至少有k个 网格的密度大于0。 证明前面假设已经通过全局优化算法得到了较优点 信息,并且k个局部最优点附近都有较优点分布,在这里我 们可以把这些较优点的位置作为局部最优点的位置。由定 理1可知每一个子空间最多包含一个局部最优点,显然定 理成立。 规则 已知m个精英解和k个局部最优点,空间划分对大多数演化算法都是如此。采用受控性随机化和频率记 忆的方法来产生多样化的初始解集。将每一维的变量均分 成竹等分(或者根据先验知识分成相应区间),首先随机选 取一个子区间,选择某一子区间的概率与其频率计数成反 比;然后在该子区间内随机产生一个初始解。这种设计方 法既保证了均衡分布,又保留了随机成分,是一种

基于概率 的多样化初始化方法。后至少有一个网格的密度大于等于m/k。 上述情况都是在已知局部最优点个数时的理想状况, 实际上局部最优点的个数难以知晓,而且全局优化算法确 定的较优点信息也不一定能够定位出所有的局部最优值信 息。从上述定理可以得到: (1)k值越大,划分成的子空间增多,空间收缩的效果 就越好,但是在划分后局部寻优的次数将会增多,因此在解 决实际问题的时候,k值不能选的太大。实际操作时,我们 可以通过改变k值试探,在空间收缩相差不大的情况下选 择最小的忌值。 (2)随着解空间的增大,在空间划分后的网格数目也 要相应增加才能够更好的收缩空间,得到更精确的解。空 间收缩到什么样的程度,这需要通过经验和实际操作,以及 渴望达到的水平对具体问题具体分析。 1.3.2网格合并 由于在空间收缩和划分之后需要在每个子空间进行完 全演化找到最优解,为了降低局部优化的复杂度,我们希望 得到的子空间尽可能少一些,因此在对解空间进行网格划 分之后,首先删除一部分不含有精英解的空间,然后对剩余1.4.2遗传算子 采用基本遗传算法的选择、交叉和变异算子。 1.4.3精英解获得 在遗传算法中加入一个优解池来获得用于空间划分和 收缩的精英解。步骤如下: (1)初始化精英解个数m,初始化优解池; (2)选择优解池中适应值最差个体; (3)遗传操作产生新个体; (4)若产生的新个体的适应值大于最差个体的适应 值,则新解代替最差个体。转(2)。 1.5局部优化阶段 局部优化算法用于空间划分与收缩之后,应选取快速 有效的方法。若模型是连续可微的,我们可以采用最速下 降法、Newton法等应用梯度信息的算法。一般地,可以采 用禁忌搜索等搜索算法完成。 1.6算法流程 (1)应用全局优化算法得到问题的m个精英解; (2)把解空间划分成网格;万   方数据 第2期陈健等:基于网格划分的混合优化算法(3)利用精英解收缩空间,并合并网格,得到k个子 空间; (4)在k个子空间中分别进行局部优化,从而得到问 题的最优解。 2表2仿真(2)几种算法结果比较仿真为了检验算法的性能,对下面2个优化问题进行求解: (1)一个二维多峰函数 max,(z)一COS(2.Onxl)·COS(2.Onx2)·exp(一 (z12+z22)),0421,z2≤1.0 函数有多个极值点。笔者在全局优化阶段采用遗传 算法得到12个精英解,这里种群规模为60,交叉概率 0.8,变

“三一文库”海量教育、办公亚博体育yabo下载,http://www.111doc.com/jiaoxue/c1cc694188cea2b2c16ee85cad371dc4.html,好亚博体育yabo要分享!

此亚博体育yabo为免费亚博体育yabo,请直接点击右侧下载按钮进行下载,亚博体育yabo为doc格式请使用相关软件进行阅读、编辑! 立即下载
  • 上传作者: wx417731977 (上传创作收益人)
    上传时间: 2015-11-09
  • 需要金币: 0 (10金币=人民币1元)
    文件大小: 22 KB
关于本文
本文标题:基于网格划分的混合优化算法
关于111doc - 版权提示 - 收益分配 - 资源合作 - 免责声明 - 友情链接 - 联系我们