论文研究-基于离散Morse理论的优化模型.pdf

所需积分/C币:20 2019-09-20 18:23:15 712KB .PDF

论文研究-基于离散Morse理论的优化模型.pdf,  根据Forman的离散Morse理论的特点,提出一种基于离散Morse理论的优化模型. 该模型利用在3维空间点构建离散Morse函数进行最优化的算法,得到了问题的最优解或近似最优解,同时也证明了构建的函数确实是复形上的离散Morse函数. 这是一个全新的尝试. 实验在4个典型的测试函数中进行,结果证明了该模型的有效性,且该模型尤其适用于
1030 系统工程理论与实践 第34卷 的边界点且x∈X,则点(x,h(x)的邻域同胚于R封闭半空间很明显,凸包三角剖分是一个有边界的m 维流形 本文中凸包三角剖分由 Delaunay三角剖分实现.对于一个有限集合X={x1,x2,…,xN}R,它的 Delaunay三角剖分是m-维单形的集合.而n-维单形是通过在其邻域内数据点的连接形成的. Delaunay三 角网是唯一的(任意四点不能共圆), Delaunay三角网中任一单形的外接球(对3维空间来说)范围内不会有 其他点存在 在X的 Delaunay三角剖分中,用h(x)代替x产生复形K.本文中随机产生3000个坐标点的结果如 图1所示 表1运算实例(30000个坐标点) 建立单纯复形的时间 实例 CPU(s) 0.028 0.032 0.038 F4 0.05 图1 Delaunay三角剖分 42算法 构造离散梯度向量场(Dⅴ F-Algorithn) 本文以修正的Hase图中的子图R;(i=1,2,…,dimK)来考虑构造离散梯度向量场.在R1中连接i 维临界单元和(-1)维临界单元之间的有向路径正好与这些单形之间的离散梯度路径相对应令A:、B1、C2 分别存储复形k的i维单形.子图中的顶点有两类:(-1)维单形存储在A-1uCl-1中;维单形存储 在C:B2中分别在维单形与此单形的每个面之间加一条边所形成的有向边方向由单形指向其低一维的 面至多只有一条边例外.若G∈B2,则r(o)与a之间边的方向由r(o)→a 根据子图R;顶点的分析,可得知有向边的源点有两类:存储在C2中的i维单形和存储在A;-1中的 (-1)维单形(此单形的唯一依附面是r-1().同样,有向边的终点也有两类:存储在C-1中的(-1)维 单形和i维单形,此单形的所有(-1)维面7存储在B;-1中除了面r(7) DVF-Algorithm算法包含两部分: generating= group(K,h,p)和 cancelling- critical simplea(K,h,) generati ng-group(K,h,p)产生未经调整的A、B、C和r; cancelling- critical simplex(K,h,)修正已 产生的A、B、C和r,从而产生较优的离散梯度向量场 1. generating-group(K, h, p) Step1输入有限单形K,映射函数h:Ko→R; Step2初始化相关参数.设定A,B,C为空;设定映射r:B→A,其中r(a)是a的一个面;给定忍耐 系数p为一个大于等于0的值 Sep3取1个υ∈K0,求?的较低链域K′,若K′为空,则把v放入C中(v为局部最小值);否则把 放入A中,在K上重新定义h:K6→R作为h的约束条件,再转Step2重新执行,直至K上的单形 分别存入A,B,C'; Step4找到uo∈C,使得h(uo)最小把,wo]放入B中定义r(v,0)=v;对每个a∈C"-10, 把0*0放入C中;对每个a∈B,把0*0放入B,把U米r(0)放入A中,定义r(米)=*r'() Step5再转Step3执行,直到K0中的顶点取完为止; 在上述的算法中,我们都是在顶点的较低邻域链上进行.在此邻域内定义h,用劢′代替h,这样h取得 最小值的顶点就是h下降最快的方向,由此可构造离散梯度向量场.h定义的方法有很多.本文采用以下定 义:h(u)=(h(u)-h(v)/(v,),其中l({v,])表示的是边[v,的欧式距离 在已产生的离散梯度冋量场中、如发现存在这样一条路径:以σ∈C:为起点,T∈C3-1为终点,且使 maxb(a)-max(r)最小,则执行函数2 2. canLcelliny-cTilicalsimmple (K, u, j Step1对每个σ∈C,T∈C-1找到所有的梯度路径σ=ai→σ2→…→σi:∈C-1,从中选择 m3=max{max()}(即maxh(a)-max(7)取最小值) 第4期 张建萍,等:基于离散 Morse理论的优化模型 1031 Step2找到唯一的梯度路径 O=O1一 k=T,其中T=r(a计+1),7是o;的 一个面且7≠7+1 Step3从C中删除σ和r,把r放入B,把a放入A中; Step4翻转σ到r的方向,r(r)=σ 4.3构造离散 Morse函数 DVF- Algorithm输出结果包括修正后的A,B,C和r:B→A;输出的目的是对单形赋值形成离散 Morse函数以及形成修正的 Hasse图.C存储临界单元,r给出非临界单元的配对.离散 Morse函数给定 r(o)值大于a的值,而给σ的其他依附面值小于σ的值 文中我们借助顶点映射h来构建离散 Morse函数.显然之前定义的函数maxh只有在dimK-1时 才是离散 Morse函数.根据离散 Morse函数和离散梯度向量场的定义,我们把maxh进行缩放,提出一个弓 理,定义离散 Morse函数h,并对引理进行证明 引理1把h扩展成h就是通过 generating-group(K,h,p)产生Hase图的过程给定>0,对任意 单形T可定义h′满足|h(7)-maxh(T)≤e 证明对所有的顶点v≠W,假定|h(v)-h()>3ε.如果K′是顶点的低值链域,在K′可定义出离 散 Morse函数g设定go∈(h(v),h(u)+l].令是使h取得最小值的K上的顶点,则u0是K′的临 界单元.在顶点v的链域上定义h:h(,0])=h(v)一E,b(v米r)=9() 现在来做两个假设:1.如果T是σ的依附面且h()≥b(),则a∈B,T=r().2.对所有的 σ∈B,满足h(r()≥1′(σ).假设1说明b是离散Mose函数,假设2则说明l′产生的Hase图与 generating- group(K,h,p)产生的一致 证明令v是σ的最大顶点,则h(v)=maxh().若a≠,令a′是单形,则a=* 为了证明假设1,令是r的最大顶点.若≠v,则h(7)≥b(a)≥h()-≥b(u)+2≥h(r)+e 显然不等式矛盾,所以=v,也就是T在υ的低值临域内.首先假定r=v,那只有一种可能a=v,o], 所以r()=7.若假定r≠v,则v邻域中存在单形r使得7=U*T,所以9(7)≥90(o),且对7′只有 种可能即T=r(a). 对假设2进行证明.若r(o)=U,显然假设成立因为={,o且h(a)=h()-.若r(a)≠t,那 么r(0)=*r(0),则h(r()=9(y1(m)≥9()=h'(a) 定理3如果是K的顶点且h(v)最小,那么DVF- Algorithm会把作为一个临界单元输出 临界顶点是λ取得局部最小值的顶点,然而不是每个局部最小值顶点 都是临界顶点.因为如果取得局部最小值的顶点v和h的鞍点10相连接, 解空间数据集X 则v可能就不会产生临界顶点同样的,临界2维单形e和h的局部最大 值m相邻接,但是若m与h的鞍点相连接,则e可能不会是临界单元 构建单纯复形K 所以优化问题的最优解就是在C的0-单元上选取.图2给出优化算 法的流程. 构建离散梯度向量场V 4.4离散 Morse函数的最优化 在文献{3中已证明找到最优离散 Morse函数的问题是一个 MAX-SNP 构建离散 Morse函数f 难问题.但是这样的最优化 Morse函数是存在的.下面给出证明 证明虽然在一个给定的复形K上可定义无限个离散 Morse函数,但是 计算、比较0-临界单元的值 存在有限数量的离散梯度向量场。因为离散梯度向量场可看成是 hasse图 的配对且配对数少于2#),这样K中就存在尽可能少的临界单形 输出结果 5实验结果及分析 图2优化七模型的流程图 卜面对本文提出的算法进行实验验证和分析.算法由 Visual c++2005实现,图形在 Geomview中显 由于 Geomview是在Uniⅸ环境下运行,而 Cygwin在 Windows中提供了一个模拟Unⅸx环境实验采 用表2中4个标准测试函数叫进行一系列实验这4个测试函数具有不同的特点,可以充分测试算法对不 同类型问题的优化性能 F1和F2是连续的单峰函数,其中F2是一个经典的复杂优化问题,取值区间内走势平坦,要收敛到全 局最优点的机会微乎其微.F3和F4是复杂的非线性多峰函数,存在大量局部极值,可以检验算法的全局搜 1032 系统工程理论与实践 第34卷 索和逃离局部极值的能力 表2标准测试函数 测试函数 F2= +(m 1)2)[2.048,2048] F3=∑,=1(x2-10c0s(27x2)+10 -5.12,512] F4 )+1 51实验方法及参数设置 利用 Forman的离散 Morse理论建立优化模型,将本文算法用于上述列出的4种测试函数 算法中参数的设置情况: 函数维数dim=3,数据规模size=30000随机点的位置范围为表2中x;的区间.表3记录了算法循 环100次寻优的最优结果(最优 Morse函数)、寻优结果的平均值及与最优值的比较结果. 52实验结果与分析 521算法在测试函数中求解结果及分析 本实验的所有数据均为测试函数在其取值范围內随机产生.表3详细记录了算法寻优结果及与最优解 的差值 表优化模型的实验结果 测试函数最优 Morse函数平均寻优结果与最优值差值 F1 (1,0.0,0 (2,5,2,0) 4.22E+01 422E+01 F3 (1,10,0) 1.01E+01 1.01E401 F4 (1,0.0,0) 7E-02 4E-02 由表3最优值与参考文献[11中的最优值进行比较可以看出,我们构建的离散 Morse函数能够取得或 接近取得函数的最优值.说明通过构建最优离散 Morse函数进行函数优化的思路可行,且能取得较好的效 果 对于单峰函数,DVF- Algorithm所得最优解的收敛精度较高.对于多峰函数,此算法有可能会陷入局部 最优,但我们可以尝试通过调整参数的方法尽可能避开收敛于某一局部极值点 通过大量的模拟实验发现,此种方法进行优化问题求解结果的准确性很大程度上取决于问题空间的取值 类型取值类型是整型的求解结果效果要好于浮点型的求解效果,这是因为我们在顶点的低值链域上h定义 为两个顶点坐标的欧氏距离所致 522算法求解过程及结果在 Geomview中的图形表示 实验以F4为例来讨论.实验中,我们把构造的离散 Morse函数在可视化界面中显示.在窗囗中有点和 不同的球.顶点和球之间通过线连接通过线连接的单形是临界单形.球包着单形的重心,线连接着它的相关 面的重心 通过 generating- group(k,h,p)算法构造 Morse函数产生的临界单元数为(2,3,2,0).求解结果界面如 图3所示,其中A表示0-维临界单形,Bi表示1-维临界单形,Ci表示2-维临界单形. A2 图3F4的求解界面 第4期 张建萍,等:基于离散 Morse理论的优化模型 1033 1)显示0-1层梯度路径 图4所示的梯度路径通过 cancelling-criticalsi mple.(K,h,j),可消除临界单元A2和B1 2)显示1-2层梯度路径 图4显示0-1层梯度路径(用箭头表示) 图5显示1-2层梯度路径(用箭头表示) 图5所示的梯度路径通过 cancelling- critical simplex(K,h,j),消除了临界单元C2和B3以及C1和 B2.算法执行完毕后,仅剩临界单元A,即为F4的最小值或近似最小值.实验证明了算法的有效性及可行 性 6结束语 本文提出∫一种在3维空闰点构建离散 Morse函数求最优解的算法,并证明∫构建的函数确实是K上 的离散 Morse函数,并得到间题的最优解或近似最优解.这是一个全新的尝试.同时构建了一种基于离散 Morse理论的优化模型,实验的结果证明了该模型的有效性 需要说明的是,在对多峰函数构建最优离散 Morse函数时,还需要对参数进行人工的调整,才能尽可能 的避免过早陷入局部最优.另外,为提高取得最优值的精度,对问题的解空间数据类型需要一定的限制.这是 下一步工作需要解决的问题 参考文献 1 Milnor J. Morse theory M. New Jersey: Princeton University Press, 1963 2 Edelsbrunner H, Harer J, Zomorodian A Hierarchical Morse-Smale complexes for piecewise linear 2-manifoldsJJ Discrete Computational Geometry, 2003, 30(1):87-107 3 Forman R. Morse theory for cell complexes J. Advances in Mathematics, 1998, 134(1): 90-145 4 Forman R. A user's guide to discrete Morse theory[J]. Seminare Lotharinen de Combinatore, 2002, 48(2): 1-35 5 Ayala R, Fernandez L M, Vilches J A. Defining discrete Morse functions on infinite surfaces[C// The 20th European Workshop on CoIllpulaliOnal Geometry. Seville spaiN, March, 2004: 25-26 6 Lewiner T, Lopes H, Tavares G. Toward optimality in discrete Morse theory J. Experimental Mathematics, 2003 12(3):271-286 7 King Il, Knudson K. Generating discrete Morse function from point dataJ. Experimental Mathematics, 2005 14(4):43544 [8 Edelsbrunner H. Harer J, Natarajan V, et al. Morse-Smale complexes for piecewise linear 3-manifolds[C1// Proceedings of the 19th Annual Symposium on Computational Geometry, New York: ACM Press, 2003: 361 9 Dold A Lectures on algebraic topology M. New York: Springer Press, 2009 10 Forman R, Wolf M. Six themes on variation[M]. New York: AMS, 2004: 13-31 11 Huang H, Qin H, Hao Z F, et al. Example-based learning particle swarm optimization for continuous optimiza tion[J. Information Sciences, 2012, 182(1): 125-138

...展开详情
试读 6P 论文研究-基于离散Morse理论的优化模型.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于离散Morse理论的优化模型.pdf 20积分/C币 立即下载
    1/6
    论文研究-基于离散Morse理论的优化模型.pdf第1页
    论文研究-基于离散Morse理论的优化模型.pdf第2页

    试读已结束,剩余4页未读...

    20积分/C币 立即下载 >