进化算法是什么？关于进化算法的科普介绍

创闻用户 2022-07-27 13:56:12

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

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

履行

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

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

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

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

类型

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

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

与生物过程的比较

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

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

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