数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  在线办公 | 
数值计算与计算机应用  2017, Vol. 38 Issue (4): 297-311    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
多水平直接搜索全局优化方法
刘群锋, 陈景周, 徐钦桂
东莞理工学院计算机学院, 广东东莞 523808
GLOBAL OPTIMIZATION BY MULTILEVEL DIRECT SEARCH
Liu Qunfeng, Chen Jingzhou, Xu Qingui
College of Computer Science and Network Security, Dongguan University of Technology, Dongguan 523808, China
 全文: PDF (639 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 直接搜索是数值最优化中的重要思想.DIRECT算法是基于直接搜索思想的一个流行的全局优化算法.本文首先回顾了新近提出来的一个具有三水平直接搜索框架的全局优化算法MrDIRECT,着重回顾了MrDIRECT算法是怎样消除DIRECT算法的“渐近无效”行为的,并为此提供了更多的数值证据.然后,本文提出了一个具有四水平直接搜索框架的MrDIRECT算法,讨论了其收敛性,并对之进行了大量的数值测试.我们的目的是检验水平数的增加对算法效率的影响.结果表明,水平数的增加带来的数值效果的改善并不足以抵消计算成本的增加,总体数值效果不如三水平MrDIRECT算法.最后,本文指出MrDIRECT算法采用的多水平直接搜索框架的重要优势是,能够很灵活地平衡局部搜索和全局搜索,从而可用于设计更多的多水平直接搜索全局优化算法.本文验证的水平数增加未必带来整体数值效果的改善这一结论也可用于指导这类算法的设计.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词全局优化   直接搜索   多水平算法   MrDIRECT算法     
Abstract: Direct search is an important method in numerical optimization. The DIRECT algorithm is a popular global optimization algorithm based on direct search. In this paper, we review firstly a recently proposed multilevel robust DIRECT (MrDIRECT) algorithm, especially how it can eliminate the "eventually inefficient behavior" of the DIRECT algorithm through adopting three levels of search spaces. We provide some more numerical experiments to support MrDIRECT's such ability. Then we propose a new version of MrDIRECT which adopts four levels of search spaces. Our main purpose is to verify the affection of the number of search levels. Extensive numerical results show that four search levels bring no significant improvement but consumes much more computational cost. Therefore, our conclusion is that large number of search levels are not suitable for multilevel search in global optimization. Finally, we pointed out that the idea of multilevel direct search spaces is very convenient in balancing between local search and global search, and therefore can be used to design other global optimization algorithms. Moreover, the numerical result obtained in this paper is helpful for the choice of the number of search levels in multilevel direct search global optimization algorithms.
Key wordsGlobal optimization   Direct search   Multilevel algorithm   MrDIRECT   
收稿日期: 2017-01-16;
基金资助:

国家自然科学基金(#61773119)和广东省自然科学基金(#2015A030313648)资助.

引用本文:   
. 多水平直接搜索全局优化方法[J]. 数值计算与计算机应用, 2017, 38(4): 297-311.
. GLOBAL OPTIMIZATION BY MULTILEVEL DIRECT SEARCH[J]. Journal of Numerical Methods and Computer Applicat, 2017, 38(4): 297-311.
 
[1] 刘群锋.非单调Frame型直接搜索共轭梯度法[J].计算数学,2011,33(3):249-256. 浏览
[2] 刘群锋,曾金平,张忠志,程万友.基于混合非单调下降条件的直接搜索方法[J].计算数学,2015,37(2):213-224. 浏览
[3] Androulakis I P,Maranas C D,Floudas C A.αBB:A global optimization method for general constrained nonconvex problems[J].Journal of Global Optimization,1995,7(4):337-363.
[4] Dolan E D,MoréJ J.Benchmarking optimization software with performance profiles[J].Mathematical Programming,2002,91:201-213.
[5] Björkman M,Holmström K.Global optimization using the DIRECT algorithm in Matlab[J].Advanced Modeling and Optimization,1999,1:17-37.
[6] Elsakov S M,Shiryaev V I.Homogeneous algorithms for multiextremal optimization[J].Computational Mathematics and Mathematical Physics,2010,50(10):1642-1654.
[7] Finkel D E.Global optimization with the DIRECT algorithm.PHD thesis,North Carolina State University,2005.
[8] Finkel D E,Kelley C T.Additive scaling and the DIRECT algorithm[J].Journal of Global Optimization,2006,36:597-608.
[9] Floudas C A,Pardalos P M.State of the art in global optimization:computational methods and applications[M].London:Kluwer academic publishers,1996.
[10] Floudas C A,Gounaris C E.A review of recent advances in global optimization[J].Journal of Global Optimization,2009,45:3-38.
[11] Gaviano M,Kvasov D E,Lera D and Sergeyev Ya D.Algorithm 829:Software for Generation of Classes of Test Functions with Known Local and Global Minima for Global Optimization[J].ACM Transactions on Mathematical Software,2003,9(4),469-480.
[12] Gaviano M,Lera D.Test functions with variable attraction regions for global optimization problems[J].Journal of Global Optimization,1998,13(2):207-223.
[13] Gablonsky J M,Kelley C T.A locally-biased form of the DIRECT algorithm[J].Journal of Global Optimization,2001,21:27-37.
[14] Hedar A.http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm.
[15] He J,Watson L T,et al.Dynamic data structures for a direct search algorithm[J].Computational Optimization and Applications,2002,23(1):5-25.
[16] Hinton G E,Osindero S and Teh Y.A fast learning algorithm for deep belief nets[J].Neural Computation,2006,18:1527-1554.
[17] Hinton,G E and Salakhutdinov R R.Reducing the dimensionality of data with neural networks[J].Science,2006,313(5786):504-507.
[18] Holland J H.Adaption in nature and artificial systems.2nd ed.Cambrige,MA:MIT Press,1992.
[19] Holmstrom K,Goran A O,Edvall M M.User's Guide for TOMLAB 7.Tomlab optimization.http://tomopt.com.
[20] Huyer W,Neumaier A.Global optimization by multilevel coordinate search[J].Journal of Global Optimization,1999,14(4):331-355.
[21] Jones D R,Perttunen C D,Stuckman B E.Lipschitzian optimization without the Lipschitz constant[J].Journal of Optimization Theory and Application,1993,79(1):157-181.
[22] Jones D R.The DIRECT global optimization algorithm.In Floudas C.A.,Pardalos:The Encyclopedia of Optimization.Kluwer Academic,2001.
[23] Kennedy J,Eberhart R C.Particle swarm optimization,In:proceeding of the IEEE iternational conference on neural networks IV,Piscataway:IEEE,1995,1942-1948,
[24] LeCun Y,Bengio Y,Hinton G E.Deep Learning.Nature,2015,521:436-444.
[25] Liu Q F.Linear scaling and the DIRECT algorithm[J].Journal of Global Optimization,2013,56(3):1233-1245.
[26] Liu Q F.Order-2 stability analysis of particle swarm optimization[J].Evolutionary Computation,2015,23:187-216.
[27] Liu Q F,Cheng W Y.A modified DIRECT algorithm with bilevel partition[J].Journal of Global Optimization,2014,60(3):483-499.
[28] Liu Q F,Zeng J P.Global optimization by multilevel partition[J].Journal of Global Optimization,2015,61(1):47-69.
[29] Liu Q F,Zeng J P,Yang G.MrDIRECT:A multilevel robust DIRECT algorithm for global optimization problems[J].Journal of Global Optimization,2015,62(2):205-227.
[30] Liu Q F,Yang G,Zhang Z Z,Zeng J P.Improving the convergence rate of the DIRECT global optimization algorithm[J].Journal of Global Optimization,2017,67(4):851-872.
[31] Liuzzi G,Lucidi S,Piccialli V.A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems[J].Computational Optimization and Applications,2010,45(2):353-375.
[32] Liuzzi G,Lucidi S,Piccialli V.A partion-based global optimization algorithm[J].Journal of Global Optimization,2010,48:113-128.
[33] Liuzzi G,Lucidi S,Piccialli V.Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization.Computational Optimization and Applications.DOI:10.1007/s10589-015-9741-9,2015.
[34] Ljunberg K,Holmgren S.Simultaneous search for multiple QTL using the global optimization algorithm DIRECT[J].Bioinformatics,2004,20(12):1887-1895.
[35] Moré J,Wild S.Benchmarking Derivative-Free Optimization Algorithms[J].SIAM Journal on Optimization,2009,20(1):172-191.
[36] Pardalos P M,Schoen F.Recent advances and trends in global optimization:deterministic and stochastic methods.In:Proceedings of the Sixth International Conference on Foundations of Computer-Aided Process Design,DSI 1-2004,2004,119-131.
[37] Paulavi?ius R,Sergeyev Y D,Kvasov D E and?ilinskas J.Globally-biased Disimpl algorithm for expensive global optimization[J].Journal of Global Optimization,2014,59:545-567.
[38] Rios L M,Sahinidis N V.Derivative-free optimization:a review of algorithms and comparison of software implementations[J].Jouranl of Global Optimization,2013,56(3):1247-1293.
[39] Sergeyev Y D,Kvasov D E.Global search based on efficient diagonal partitions and a set of Lipschitz constants[J].SIAM Journal on Optimization,2006,16(3):910-937.
[40] Tawarmalani M,Sahinidis N V.A polyhedral branch-and-cut approach to global optimization[J].Mathematical Programming,2005,103(2):225-249.
[41] ilinskas A.On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions[J].Applied Mathematics and Computation,2012,218(16):8131-8136.
[1] 申培萍, 申子慧. 广义线性多乘积问题的完全多项式时间近似算法[J]. 数值计算与计算机应用, 2017, 39(3): 287-294.
[2] 高岳林, 吴佩佩. 非线性整数规划的一个新的无参数填充函数算法[J]. 数值计算与计算机应用, 2017, 39(3): 321-327.
[3] 申培萍, 申子慧. 一类广义分式规划问题的完全多项式时间近似算法[J]. 数值计算与计算机应用, 2015, 37(2): 179-185.
[4] 刘群锋, 曾金平, 张忠志, 程万友. 基于混合非单调下降条件的直接搜索方法[J]. 数值计算与计算机应用, 2015, 37(2): 213-224.
[5] 申培萍, 张永俊, 梁彦超. 一类广义分式规划问题的ε-近似算法[J]. 数值计算与计算机应用, 2014, 36(3): 303-308.
[6] 刘群锋. 非单调Frame型直接搜索共轭梯度法[J]. 数值计算与计算机应用, 2011, 33(3): 249-256.
[7] 刘浩, 倪勤. 二次插值模型直接搜索算法的参数分析[J]. 数值计算与计算机应用, 2008, 29(4): 266-276.
[8] 李慧贤,李英华. 改进的进化算法解最短路问题[J]. 数值计算与计算机应用, 2007, 28(1): 47-55.
[9] 余胜生,文元桥,周敬利. 隧道算法的分布式并行计算模型[J]. 数值计算与计算机应用, 2006, 27(4): 299-306.
[10] 靳利霞,唐焕文,李斌,计明军,朱训芝. 一类连续函数模拟退火算法及其收敛性分析[J]. 数值计算与计算机应用, 2005, 27(1): 19-30.
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10