Autoencoding Evolutionary Search With Learning Across Heterogeneous Problems
此篇文章为 L. Feng, Y.-S. Ong, S. Jiang, A. Gupta, Autoencoding Evolutionary Search With Learning Across Heterogeneous Problems, IEEE Trans. Evol. Computat. 21 (2017) 760–772. https://doi.org/10.1109/TEVC.2017.2682274. 的论文学习笔记,只供学习使用,不作商业用途,侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正!
摘要
为了提高进化算法的搜索性能,已有文献提出在搜索过程中重用从过去优化经验中获取的知识,并显示出很好的应用前景。在文献中,通常有三种方法来重用过去搜索经验中的知识,即 精确存储和重用过去的解,重用基于模型的信息,以及重用从过去优化的解中获取的结构化知识 在本文中,我们重点研究了第三种用于 增强进化搜索的知识重用 与已有工作不同的是,本文研究的是跨异构连续优化问题的知识转移问题,这些问题具有不同的属性,如问题维度、目标个数等,这些都是现有方法所不能处理的。特别地,我们提出了一种新的具有跨异构问题学习能力的自动编码进化搜索范式。**在我们提出的范例中,从搜索经验中学习结构化知识的基本要素是单层去噪自动编码器(DA),它能够通过将过去的优化解作为新遇到的问题的解的破坏版本来建立问题域之间的联系。The essential ingredient for learning structured knowledge from search experience in our proposed paradigm is a single layer denoising autoencoder (DA), which is able to build the connections between problem domains by treating past optimized solutions as the corrupted version of the solutions for the newly encountered problem. 此外,由于导出的DA具有闭合形式的解,因此相应地重用过去搜索经验中的知识不会给进化搜索带来太多额外的计算负担。为了对所提出的搜索范式进行评估,对复杂的多目标优化问题进行了全面的实证研究,并结合纤维增强聚合物复合材料制造业的实际案例进行了研究。
key word: Index Terms—Evolutionary optimization, knowledge transfer, learning, memetic computation
为了提高现有进化算法的效率,文献中提出了重用以往相关问题的搜索经验,成功地增强了对调度问题[15]、旅行商问题[16]和弧路径问题[17]等实例的进化搜索。这是因为在自然界中,问题很少孤立存在,解决以前相关问题的经验通常会产生有用的信息,如果处理得当,这些信息可以导致更有效的问题解决过程。具体的例子可以包括精确存储和重用过去的解决方案[15]、[16]、重用基于模型的信息[18]、[19]、以及重用从优化的解决方案中捕获的结构化知识[20]。特别值得一提的是,Louis和McDonnell[15]建议存储过去问题的已被优化的解,并通过基于案例的推理重新使用它们来辅助遗传算法(GA)搜索。不是在每个问题上开始一次新的搜索,而是将从以前已经解决的类似问题中提取的适当的中间解决方案周期性地注入到GA群体中。在另一项研究中,Cunningham和Smyth[16]提出了从过去的问题中直接重用已建立的高质量时间表来解决旅行推销员问题。由于[15]和[16]都只考虑过去解的直接插入,它们不能很好地应用于具有不同结构性质的问题,如问题顶点大小、拓扑结构、表示等。[15] S. J. Louis and J. McDonnell, “Learning with case-injected genetic algorithms,”IEEE Trans. Evol. Comput., vol. 8, no. 4, pp. 316–328, Aug. 2004. [16] P . Cunningham and B. Smyth, “Case-based reasoning in scheduling: Reusing solution components,”Int. J. Prod. Res., vol. 35, no. 11, pp. 2947–2962, 1997. [17] L. Feng, Y .-S. Ong, M.-H. Lim, and I. W. Tsang, “Memetic search with interdomain learning: A realization between CVRP and CARP ,”IEEE Trans. Evol. Comput., vol. 19, no. 5, pp. 644–658, Oct. 2015. [18] M. Pelikan and M. W. Hauschild, “Learn from the past: Improving model-directed optimization by transfer learning based on distancebased bias,” Missouri Estimation Distrib. Algorithms Lab., Univ. Missouri at St. Louis, St. Louis, MO, USA, Tech. Rep. 2012007, 2012. [19] R. Santana, A. Mendiburu, and J. A. Lozano, “Structural transfer using EDAs: An application to multi-marker tagging SNP selection,” inProc. IEEE Congr . Evol. Comput., Brisbane, QLD, Australia, 2012, pp. 1–8. [20] L. Feng, Y .-S. Ong, I. W.-H. Tsang, and A.-H. Tan, “An evolutionary search paradigm that learns with past experiences,” inProc. IEEE World Congr . Comput. Intell. Congr . Evol. Comput., Brisbane, QLD, Australia, 2012, pp. 1–8.
[13] L. Feng, Y .-S. Ong, A.-H. Tan, and I. W. Tsang, “Memes as building blocks: A case study on evolutionary optimization + transfer learning for routing problems,”Memetic Comput., vol. 7, no. 3, pp. 159–180, 2015. [17] L. Feng, Y .-S. Ong, M.-H. Lim, and I. W. Tsang, “Memetic search with interdomain learning: A realization between CVRP and CARP ,”IEEE Trans. Evol. Comput., vol. 19, no. 5, pp. 644–658, Oct. 2015.
闭式解也被称为解析解,与数值解对应。闭式解closed form solution)也叫解析解(analytical solution),就是一些严格的公式,给出任意的自变量就可以求出其因变量,也就是问题的解, 他人可以利用这些公式计算各自的问题。所谓的解析解是一种包含分式、三角函数、指数、对数甚至无限级数等基本函数的解的形式。用来求得解析解的方法称为解析法〈analytic techniques〉,解析法即是常见的微积分技巧,例如分离变量法等。
2. PRELIMINARY
2.1 去噪自动编码器(Denoising Autoencoder)
DA是DNN的基本组成部分,Anautoencoderis the basic building block of deep learning networks that attempts to reproduce its input, i.e., the target output is equal to the input itself [22].
[27] X. S. Chen, Y .-S. Ong, M.-H. Lim, and K. C. Tan, “A multi-facet survey on memetic computation,”IEEE Trans. Evol. Comput., vol. 15, no. 5, pp. 591–607, Oct. 2011. [28] Y .-S. Ong, M. H. Lim, and X. S. Chen, “Memetic computation—Past, present & future [Research Frontier],”IEEE Comput. Intell. Mag., v o l . 5 , no. 2, pp. 24–31, May 2010.
为了进一步探索以模因为中心的解决问题的计算范式,文献中也出现了模因的其他表现形式。例如,Situngkir[37]利用模因论对文化进行了结构化分析,其中模因被视为最小的信息单位。Heylighen和Chielens[38]讨论了文化进化中模因的复制、传播和复制操作。此外,Fenget al.[39]提出了一个模因多智能体系统,面向具有模因自动机的类人社会智能体,而Acamporate et al.[40]引入模因智能体作为智能探索者,为电子学习创造“及时”和个性化体验。最近,模因被建模为一个转换矩阵,用作加速路由问题进化搜索的先验知识[13]。
在本文中,我们通过对模因搜索进行研究,通过学习跨异构问题进行持续优化,为模因计算做出贡献。与现有的模因计算工作相比,在当前提出的范式中,模因已被定义为有用的知识,这些知识被捕获和重用,以增强跨连续优化问题的进化搜索过程,这些问题可能在问题维度、目标数量等方面有所不同, 并且不能通过第 I 部分中提到的方法处理。此外,如图 2 所示,就像人类大脑中用于应对日常生活和解决问题的知识一样,DA 学习到的知识模因驻留在 ES 的人工大脑中,扮演着积极偏向搜索的角色新遇到的问题。建议的自动编码模因搜索的细节将在下一节中介绍。
注意:这里知识从两个方面来,一个是从前学过的知识,一个是当前代优化后的种群。
3. PROPOSED AUTOENCODING SEARCH PARADIGM WITH LEARNING ACROSS HETEROGENEOUS PROBLEMS