进化算法

贡献者： 待更新

　　 （本文根据 CC-BY-SA 协议转载自原搜狗科学百科对英文维基百科的翻译）

　　 在人工智能中，进化算法（EA）是进化计算的子集，[1]是一种基于一般群体的元启发式优化算法。进化算法使用受生物进化启发的机制，例如生殖，突变，复合和选择。优化问题的候选解在种群中发挥个体的作用，适应度函数决定了解的质量。种群的演化会在重复应用上述算子之后发生。

　　 进化算法通常对所有类型的问题都有很好的近似解，因为它们在理想情况下不对底层的适应度做任何假设。应用于生物进化建模的进化算法的技术通常限于探索基于细胞过程的微观进化过程和规划模型。在进化算法的大多数实际应用中，计算复杂性是一个禁止因素。事实上，这种计算复杂性是由于适应度函数评估。适应度近似是克服这一困难的解决方案之一。然而，看似简单的进化算法通常可以解决复杂的问题；因此，算法复杂性和问题复杂性之间可能没有直接联系。

1. 履行

　　 第一步:随机生成个体的初始种群。(第一代)

　　 第二步:评估该群体中每个个体的适应度(时间限制、达到的足够适应度等)。

　　 步骤三:重复以下再生步骤，直到终止:

1. 选择最适合繁殖的个体。(父母)
2. 通过杂交和变异操作培育新个体，以生育后代。
3. 评估新个体的个体适应性。
4. 用新个体替换最不适合的人群。

2. 类型

　　 类似的技术在遗传表示和其他实现细节以及特定应用问题的性质上存在差异。

• 遗传算法–这是最流行的进化算法类型。人们寻求以数字串的形式来解决问题(传统上是二进制的，尽管最好的表示通常是反映正在解决的问题的那些东西)，[2]通过应用诸如重组和突变(有时一个，有时两个)之类的算子。这种类型的进化算法经常用于最优化问题。它的另一个名字是费图拉，源自拉丁语，用于繁殖。[2]
• 遗传编程–这里的解决方案是以计算机程序的形式，它们的适应度由它们解决计算问题的能力决定。
• 进化规划–类似于遗传规划，但是程序的结构是固定的，并且允许其数值参数进化。
• 基因表达式编程–和遗传编程一样，GEP 也开发了计算机程序，但它探索了基因型-表型系统，其中不同大小的计算机程序编码在固定长度的线性染色体中。
• 进化策略–使用实数向量作为解的表示，通常使用自适应突变率。
• 差分进化-基于向量差异，因此主要适用于数值优化问题。
• 神经进化–类似于遗传编程，但基因组通过描述结构和连接权重来表示人工神经网络。基因组编码可以是直接的，也可以是间接的。
• 学习分类器系统（LCS）–这里的解决方案是一组分类器(规则或条件)。密执安-LCS 在单个分类器的级别上进化，而匹兹堡-LCS 使用分类器集的总体。最初，分类器只是二元的，但现在包括实数、神经网络或 S-表达式类型。适应性通常通过基于强度或准确性的强化学习或监督学习方法来确定。

3. 与生物过程的比较

　　 可能的限制许多进化算法中缺乏明确的基因型-表型区别。在自然界中，受精卵细胞经历一个被称为胚胎发生的复杂过程，成为成熟的表型。这种间接的编码被认为使遗传搜索更健壮(即降低致命突变的概率)，并且还可以提高生物体的进化性。[3][4]这种间接(也称为生成或发展)编码也使得进化能够利用环境中的规律性。[5]最近在人工胚胎发生或人工发展系统的工作，试图解决这些问题。基因表达式编程成功地探索了基因型-表型系统，其中基因型由固定长度的线性多基因染色体组成，表型由多个不同大小和形状的表达树或计算机程序组成。[6]

4. 相关技术

　　 群体算法包括：

• 蚁群优化——基于蚂蚁通过信息素通信觅食形成路径的思想。主要适用于组合优化和图问题。
• 流道根算法(RRA)——受到自然界植物流道和根的功能的启发[7]
• 人工蜂群算法——基于蜜蜂觅食行为。主要用于数值优化，并扩展到解决组合优化、约束优化和多目标优化问题。
• 蜜蜂算法——基于蜜蜂的觅食行为。它已经应用于路由和调度等许多应用中。
• 布谷鸟搜索算法——受到了布谷鸟寄生孵卵的启发。它还使用了 levy flight，因此适合全局优化问题。
• 电气优化优化——基于电子流通过电阻最小的电路支路的行为。[8]
• 粒子群优化——基于动物群集行为的思想。也主要适用于数值优化问题。

5. 其他基于群体的元启发式方法

• 狩猎搜寻——一种受一些动物(如狼)群体狩猎启发的方法，这些动物组织它们的位置来包围猎物，每个猎物的位置和其他动物的位置，尤其是它们的领导者的位置相关。这是一种连续优化方法，[9]适合作为组合优化方法。[10]
• 自适应维度搜索——与自然启发的元启发式技术不同，自适应维度搜索算法不将任何隐喻作为基本原则来实现。相反，它使用一种简单的面向性能的方法，基于每次迭代时搜索维度比参数的更新。[11]
• 萤火虫算法——灵感来自萤火虫的行为，它们通过闪光相互吸引。这对于多模式优化特别有用。
• 和声搜索——基于音乐家在寻找更好和声时的行为理念。该算法适用于组合优化和参数优化。
• 高斯自适应——基于信息论。用于最大化制造产量，平均适应度或者平均信息量。
• 文化基因算法——一种混合方法，受理查德·道金斯模因概念的启发，它通常采取基于种群的算法和能够执行局部细化的个体学习过程的形式。强调利用特定问题的知识，并试图以协同的方式协调本地和全球搜索。
• 帝企鹅群体——一种受帝企鹅群体行为启发的方法。企鹅群中的帝企鹅寻求创造适当的热量并调节它们的体温，这种热量完全由企鹅的运动来协调和控制。[12]

6. 例子

　　 计算机模拟 Tierra 和 Avida 试图建立宏观进化动力学模型。

7. 走廊

　　 [13] [14] [15]

• 在具有有界全局最优的约束罗森布鲁克函数上的两种群进化搜索。

• 约束罗森布罗克函数上的两种群进化搜索，全局最优不受限制。

• 基恩函数分布算法的估计

• 两人 EA 搜索 Simionescu 函数的有限最优解。

8. 参考文献

　　 [1] ^Vikhar, P. A. Evolutionary algorithms: A critical review and its future prospects. Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). Jalgaon, 2016, pp. 261-265. ISBN 978-1-5090-0467-6..

　　 [2] ^Cohoon, J; et al. Evolutionary algorithms for the physical design of VLSI circuits (PDF). Advances in Evolutionary Computing: Theory and Applications. Springer, pp. 683-712, 2003. ISBN 978-3-540-43330-9..

　　 [3] ^霍恩比和波拉克。“为身体-大脑进化创造具有创成式表示的高级组件”。人工生命，8(3):223–246，2002。.

　　 [4] ^杰夫·克伦、本杰明·贝克曼、查尔斯·奥弗里亚和罗伯特·彭诺克。“用超净生成编码进化协调的四足步态”。美国电气与电子工程师协会进化计算会议论文集进化机器人学专题部分，2009 年。挪威特隆赫姆。.

　　 [5] ^J.克鲁恩、奥弗里亚和彭诺克，《生成式编码如何随着问题规则性的降低而变得有用？》，载于 PPSN 鲁道夫、詹森、卢卡斯、波洛尼和贝乌姆编辑。)，第 5199 卷计算机科学讲义，第 358-367 页，斯普林格，2008 年。.

　　 [6] ^费雷拉，c .，2001 年。“基因表达式编程:解决问题的一种新的自适应算法”。复杂系统，第 13 卷，第 2 期:87–129。.

　　 [7] ^F.Merrikh-Bayat，“runner-root 算法:由自然界植物的 runner 和 root 启发的解决单峰和多峰优化问题的元启发式算法”，应用软计算，第 33 卷，第 292-303 页，2015 年.

　　 [8] ^Khalafallah Ahmed; Abdel-Raheem Mohamed (2011-05-01). "Electimize: New Evolutionary Algorithm for Optimization with Application in Construction Engineering". Journal of Computing in Civil Engineering. 25 (3): 192–201. doi:10.1061/(ASCE)CP.1943-5487.0000080..

　　 [9] ^R.Oftadeh 等人(2010 年)，“一种受动物群体狩猎启发的新型元启发式优化算法:狩猎搜索”，60，2087–2098。.

　　 [10] ^Amine Agharghor; Mohammed Essaid Riffi (2017). "First Adaptation of Hunting Search Algorithm for the Quadratic Assignment Problem". Europe and MENA Cooperation Advances in Information and Communication Technologies: 263–267. doi:10.1007/978-3-319-46568-5_27. ISBN 978-3-319-46567-8..

　　 [11] ^Hasanç ebi，o .，Kazemzadeh Azad，S. (2015)，"自适应维搜索:离散桁架尺寸优化的新元启发式算法"，Computers and Structures，154，1–16。.

　　 [12] ^Harifi, Sasan; Khalilian, Madjid; Mohammadzadeh, Javad; Ebrahimnejad, Sadoullah (2019-02-25). "Emperor Penguins Colony: a new metaheuristic algorithm for optimization". Evolutionary Intelligence (in 英语). doi:10.1007/s12065-019-00212-x. ISSN 1864-5917..

　　 [13] ^Simionescu, P.A.; Beale, D.G.; Dozier, G.V. (2004). "Constrained optimization problem solving using estimation of distribution algorithms" (PDF). Proc. of the 2004 Congress on Evolutionary Computation - CEC2004. Portland, OR: 1647–1653. doi:10.1109/CEC.2006.1688506. Retrieved 7 January 2017..

　　 [14] ^Simionescu, P.A.; Dozier, G.V.; Wainwright, R.L. (2006). "A Two-Population Evolutionary Algorithm for Constrained Optimization Problems" (PDF). Proc 2006 IEEE International Conference on Evolutionary Computation. Vancouver, Canada: 1647–1653. doi:10.1109/CEC.2006.1688506. Retrieved 7 January 2017..

　　 [15] ^Simionescu, P.A. (2014). Computer Aided Graphing and Simulation Tools for AutoCAD Users (1st ed.). Boca Raton, FL: CRC Press. ISBN 978-1-4822-5290-3..