论文研读-异构问题学习的自动编码进化搜索

论文研读-异构问题学习的自动编码进化搜索

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

1. Introduction

• EA是一种基于种群的搜索方法，它遵循达尔文的自然选择或优胜劣汰的原则[1]。由于其强大的搜索能力和实现的简单性，多年来，其已经成功地应用于各种问题的现实问题中。例如连续优化问题[2]、[3]、组合优化问题[4]-[8]、多因子优化[9]、[10]等。尽管进化算法取得了很大的成功，但众所周知，进化算法涉及迭代复制过程，这被认为是缓慢的，因此在计算预算有限的情况下限制了进化算法的实用性[11]-[14]。
• 为了提高现有进化算法的效率，文献中提出了重用以往相关问题的搜索经验，成功地增强了对调度问题[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.
• 另一方面，Pelikan和HausChild[18]建议将预先定义的特定于问题的距离度量与从先前优化经验中挖掘的先验分布相结合，以改进模型导向的优化方法，例如分布估计算法(EDA)，而不是重复使用精确的过去的解。此外，Santanaet al.[19]建议将子问题的结构信息（先前的参数设置）转移到EDA聚集矩阵的构建中，以解决多标记标记单核苷酸多态性问题。接下来，Iqbalet al.[21]提出了一项研究，即重用从小规模问题中提取的构建块，以更有效地解决复杂的大规模问题。然而，由于这些转换方法是为基于模型的进化优化方法（如EDA）设计的，所以它们不能应用于无模型的EAs，如GA。
• 与上述两类重用过去搜索经验以增强进化搜索的方法不同，第三类尝试重用埋藏在过去搜索经验优化解决方案中的结构化公共知识。由于结构化知识是直接从优化解中学习的，与解的表示无关，因此它可以在无模型EAs中跨不同大小、不同表示形式的问题重用。 , 特别是，在[13]和[17]中，提出了一种智能进化优化的模因计算范式，该范式以模因的形式传递从以前的问题解决经验中学习到的结构化知识。将车辆路径和圆弧路径作为问题的研究领域，通过将知识模因定义为从过去优化的路径解决方案中获取的转换矩阵，在各种不同大小、拓扑等的路径实例上观察到进化搜索的显著改进。然而，值得注意的是，由于知识模因的具体定义，这种方法只能用于解决组合优化问题。如果遇到持续优化问题，并且[13]和[17]中要求的问题实例、任务信息等学习数据不可用，则会失败。

[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.

• 以此为线索，我们在这里的目标是开展一项智能进化搜索研究，该研究具有在连续优化中跨越异构问题的学习能力。就我们所知，文献中没有或很少有研究考虑到在无模型进化搜索算法中学习和重用过去的搜索经验，用于具有不同性质的连续优化问题，如不同的问题维度、目标数量等。特别是在本文中，我们提出了一种自动编码进化搜索范式，该范式能够从过去的搜索经验中以问题解决方案的形式获得知识，这些知识可以在搜索过程中注入到当前群体中.在我们提出的搜索范式中，学习组件的基本组成部分是一个单层去噪自动编码器（DA），该编码器源自其传统对应物[22]， 它拥有一个封闭形式的解决方案，不会给进化解算器（ES）带来太多计算负担。 此外，为了评估所提出的模因搜索范式的有效性，首先对复杂的多目标连续优化问题进行了全面的实证研究，其中事先的指导有助于提高搜索性能，然后对纤维增强聚合物（FRP）的真实案例进行了研究复合材料制造业。
• 闭式解也被称为解析解，与数值解对应。闭式解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].

以下关键：划重点

• 个人理解：一个向量d维向量x shape=[d,1], 可以通过自动编码器将其表示为一个d'维的向量y,权重W是一个 shape=[d',d] 的矩阵，得到的乘积Wx是一个shape=[d',1]的向量， 加上一个shape=[d',1]的偏置向量bias 简称b, 然后通过sigmoid 函数s(x)变成向量y shape=[d',1]. 隐层表示y 也被称为latent representation潜在的表示
• 同样 y 也可以通过一个权重W’和一个偏置向量b'而被重新映射为重构矩阵z shape=[d,1] ,权重W' shape=[d,d'] 加上一个shape=[d, 1]的bias b'

• DA是上述基本自动编码器的一个简单变体，它在将输入映射到隐藏表示之前破坏输入。通过最小化（1），对其进行训练，以从其损坏版本重新构建（或去噪）原始输入X。通常，隐藏表示将进一步用作机器学习的新表示
• 但是，需要注意的是，隐藏表示法还提供了损坏输入x和修复的“干净”输入x之间的连接。以此为线索，在本文中，我们不使用隐藏表示法作为原始数据的新表示法，而是建议将其用作损坏输入和修复输入之间的桥梁，以便跨问题重用有用知识，以增强持续优化的进化搜索，这将在后面的第三节中详细说明。
• 这里说明一下：意思是只是学习W和W’，b以及B'而不用y
• 可以看出哈，这个自动编码器的方法是可以适应源任务和迁移维度的维度的，即是两者的维度和决策范围不同也没关系

2.2 memetic computing

• 今天，新的模因论科学代表了与文化进化中的遗传学相似的精神世界，它已经延伸到生物学、认知、心理学等领域，并引起了极大的关注[27]。模因计算被定义为一种范式，它将模因的概念作为编码在计算表示中的信息单位，用于解决问题[28]。

[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.

• 【memetic computing的常用定义】在过去几十年中，模因通常被视为个体学习过程，或增强基于群体的搜索算法能力的局部搜索算子[12]、[27]、[29]–[31]。该集成已作为规范EA的扩展而建立，在文献中命名为混合、自适应混合或模因算法（MA），并成功用于解决许多实际搜索问题，包括连续优化[32]、组合优化[6]、[33]、约束优化[34]然而，由于模因在道金斯的《自私基因》一书中被定义为“通过模仿进行文化传播的基本单位”，它在MA中作为个体学习过程的表现形式并没有体现模因的真实性质和潜在优点。（PS：模因算法大部分时候被认为是一种局部搜索或者hybrid方法，但也可认为是独立于基因型的一种种群文化）
• 为了进一步探索以模因为中心的解决问题的计算范式，文献中也出现了模因的其他表现形式。例如，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

• 在本节中，我们首先给出单层DA的理论推导，单层DA在以问题解决方案的形式从过去的搜索经验中转移知识以增强进化搜索方面起着关键作用。接下来，详细介绍了我们提出的具有跨异构问题学习能力的自动编码搜索范例。

3.1 Single Layer Denoising Autoencoder for Reusing Past Search Experiences

• 首先向Ps和Pt中补0使其形状一致

• 为了简化表示，假设输入的是常量特征，并且在映射中加入合适的偏差bias M=[M,b] , 然后(2)式子中的公式会变成(3)式， tr表示矩阵求迹 (一个n*n矩阵A的对角线,从左上方至右下方对角线)上各个元素的总和被称为矩阵A的迹 ， 而(3)式的闭环解可以写作如下表示：

• t到s的知识迁移只用乘以一个矩阵M就可以了~，并且由于是一个闭解，因此不会添加很多额外的计算量

3.2 Autoencoding Search With Learning Across Heterogeneous Problems

• 提出的具有异构问题学习能力的自动编码搜索的工作流程如下所示
• input:PC_g表示当前任务g代，PP_g表示过去任务g代，BS最优秀的解/解集 (如果是单目标是一个解向量，多目标是一个矩阵，一行表示一个解，列表示解的维度)，
• output:注射的知识

• step1: 维度对齐
• step2：当前解作为目标，历史解作为源，计算mapping M
• step3：将最优秀的解或者解集BS通过映射矩阵M将其映射到LS
• step4: 将step1中为了对齐维度添加的0元素做截断处理
• step 6-10 同理，因为维度的不同而补零的矩阵不同

• 如图3所示，对于给定的新问题实例pnew，进化搜索过程将首先进行初始化、复制(即交叉和变异)过程。随后，当用户定义的条件满足时，就会发生过去搜索体验的转移。在本文中，为简单起见，过去搜索经验的转移发生在一个固定的生成间隔，即git，它是用户定义的，在本文中一直设置为10。