基本信息
- 项目名称：
- 大规模数值优化中变量相关性学习的研究
- 来源：
- 第十二届“挑战杯”作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 大规模数值优化在多个领域中有着广泛的应用，然而目前尚未有通用的解决方法。为处理此类问题，本作品提出了变量相关性的数学形式化定义, 并在协同演化算法中首次引入了不犯第二类错误的变量相关性学习机制。实验研究表明，新算法性能比最先进协同演化算法有了统计显著的全面提升。申报者为一作的论文已被演化计算领域顶级会议PPSN’2010 接受，已由SCI、EI和ISTP 收录，并被发明协同演化的美国研究小组引用。
- 详细介绍：
- 大规模数值优化在空中交通管理、传感器网络、工业设计等国民经济发展和工业建设的多个领域中有着广泛的应用，然而目前尚不存在通用的有效解决方法。 为处理此类问题，本作品提出了变量相关性的数学形式化定义, 并以此位基础，在协同演化算法中首次引入了不犯第二类错误的变量相关性学习机制。基于国际公认测试函数集的实验研究结果表明，作品中介绍的变量相关性学习机制使得新的算法的性能比当前最先进的协同演化算法有了统计显著的全面提升，并进一步阐明了变量相关性的学习在协同演化算法应用中的重要性。 本作品相关的论文已被演化计算领域的顶级会议PPSN’2010 接受，目前已被SCI、EI 和ISTP 权威检索收录。作者受邀在大会上作为唯一本科生做墙报报告，获得国际同行的广泛认可。目前已经被发明协同演化的美国研究小组引用。
作品图片
作品专业信息
撰写目的和基本思路
- 随着当今社会人口的飞速增长和交通网络的发展，大规模数值优化问题在工业生产和日常生活中不断涌现。因为“维数灾难”的存在，现有常规算法往往在大规模问题上失效。为解决该类难题，本作品国际首次提出变量相关性的数学定义，并引入了系统的变量相关性学习机制，同时结合分而治之的思想，成功设计了一种新颖的大规模数值优化算法。基于国际公认测试集的研究结果表示，本作品算法性能是目前国际领先的。
科学性、先进性及独特之处
- 本作品首次提出变量相关性的数学形式化定义，基于此坚实的理论基础，在协同演化算法中首次引入不犯第二类错误的变量相关性学习机制，进而形成了一套新颖的二阶段协同演化算法。在演化计算国际会议CEC'2010提供的标准测试集上，本作品算法是目前世界上已发表性能好的协同演化算法。与之前已存的先进协同演化算法DECC-G以及MLCC相比，在绝大部分测试函数上，CCVIL都有统计显著的优势。
应用价值和现实意义
- 目前在社会生产生产生活的诸多项目中，因为牵涉到成千上万个因素的影响，并且这些因素之间又同时存在复杂的耦合关系。常规方法往往依赖经验丰富的工程师花费大量时间精力制定策划方案。但这样的方案缺乏全局统一规划，离理论最优有较大差距。本作品智能分析相关性信息，结合协同演化算法之后可以高效的解决大规模数值优化问题。本作品将推动相关众多应用领域的发展，对优化整合社会资源和提高工业生产效益都有深远的影响。
学术论文摘要
- 近年来协同演化被认为解决高维优化问题有前景的算法框架，其基本思想是，试图探索问题的决策变量间的相关性信息，并据此将问题分解为多个子问题，每个子问题包含若干互不重叠的决策变量组，组与组之间相对独立的进行优化。互不相关的变量可以被当做单独的规模更小的子问题来进行优化；而相关的变量则必须被分于同一组之中，一起优化求解。早期研究工作采用的是简单的、相对低效的分组策略，比如单维分组法和对半分组法。随后，研究者提出了更高效、自适应的分组策略，例如DECC-G和MLCC。然而，现存的这些分组策略都是粗粒度的，不能够适应不同的分组大小和保证分组的合理性。在本文中，我们提出了一个新颖、具有变量相关性学习能力、基于协同演化的算法框架（CCVIL）。CCVIL首先假设给定问题的所有变量都相互独立，因而放于各不相同的分组之中。此后，CCVIL将采集变量相关的证据，一旦有足够证据说明来自不同分组的两个变量是相关的，则将变量所在的两个分组合并。我们将使用大规模黑盒优化的测试函数集来衡量新算法框架的性能。
获奖情况
- "Large-Scale Global Optimization Using Cooperative Coevolution with Variable Interaction Learning", in 'Parallel Problem Solving from Nature, PPSN XI', 2010. 申请人为论文的第一作者及通讯作者。该论文被演化计算领域顶级国际会议——PPSN'2010接受，同时被SCI、EI和ISTP权威检索。PPSN会议两年一届，是演化计算领域最早、享有盛誉的会议，第十一届会议于2010年9月11日至2010年9月15日在波兰克拉科夫举办。上届会议于2008年在德国举办，中国大陆并没有论文被接受。申请人作为唯一一名第一作者的本科生受邀在大会上做墙报报告，获得国际同行的广泛认可。目前论文已经被发明协同演化的美国研究小组引用。
鉴定结果
- 论文录用通知中译本： 我们很高兴通知您提交至PPSN’2010的论文已被接受并收录至会议录。因为我们收到了大量的论文提交，您的论文被接受是一项重大的成就！
参考文献
- 一、PPSN国际会议评价参考 PPSN会议官方网站的录用文章列表（本文序号为#66）： ~ppsn/accepted.php Springer官方网站里本论文的下载入口： 二、技术文献目录 Potter, M.A., De Jong, K.A.: Cooperative coevolution: architecture for evolving coadapted subcomponents. Evolutionary Computation 8(1) (2000) 1–29 Yang, Z., Tang, K., Yao, X.: Large scale evolutionary optimization using cooperative coevolution. Information Sciences 178(15) (2008) 2985–2999 Tang, K., Li, X., Suganthan, P.N., Yang, Z., Weise, T.: Benchmark functions for the CEC’2010 special session and competition on large scale global optimization. TR, NICAL, USTC, Hefei, Anhui, China (2009) Weicker, K., Weicker, N.: On the improvement of coevolutionary optimizers by learning variable interdependencies. In: IEEE CEC, IEEE Press (1999) 1627–1632
同类课题研究水平概述
- 演化算法在国内外已经有了一定的研究基础，其在低维问题上可行性和有效性已经被广泛证实与接受。然而随着问题规模的增加，演化算法的性能往往出现明显的下降。在实际工程应用中，大规模优化有着广泛的应用，例如大规模电力系统的设计，大规模维数的资源调度和大规模交通网络的车辆调度问题。该类问题因此成为当前研究的一大热点，美国电气和电子工程师协会（IEEE）的计算智能分会还因此成立了大规模全局优化的特别研究小组。过去5年内，国内外许多研究小组投入到对大规模数值优化难题的攻克之中。这些研究主要集中于两个方面： 设计更适合大规模优化的算子：发展这类算子的原因在于，经典的演化算法算子大多针对低维问题上所设计的。而在面对解空间复杂程度大大增加的高维问题时，它们的效果骤降，这种现象激发研究人员进行更有针对性的算子设计。这类方法将大规模黑盒优化问题本身当成一个整体来进行优化，并未分而治之的思想，故真正使得它们性能优越的原因在于专门设计的算子。文献[1]将一种专门针对大规模问题的自适应策引入差分演化（Differential Evolution）算法。针对大规模问题专门设计算子而得到的算法往往对问题的依赖性强，算法的可扩放能力有限。 [1] Brest, J., Zamuda, A., Fister, I. & Maučandec, M. Large scale global optimization using self-adaptive differential evolution algorithm. CEC 2010, pp. 1-8 结合协同演化算法，采用分而治之的思想。在采用协同演化算法解决大规模问题时，如何合理分组使得各组之间不存在相互依赖关系便成为了关键问题。文献[2]通过函数值提升的大小估计可能的变量相关性。 [2] Omidvar, M.N., Li, X. & Yao, X. Cooperative Co-evolution with delta grouping for large scale non-separable function optimization. CEC 2010, pp. 1-8
