算法|什么是演化算法｜集智百科
本文图片
“集智百科精选”是一个长期专栏 ， 持续为大家推送复杂性科学相关的基本概念和资源信息 。 作为集智俱乐部的开源科学项目 ， 集智百科希望打造复杂性科学领域最全面的百科全书 ， 欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！
本文是对集智百科中“演化算法 Evolutionary Algorithms”词条的摘录 ， 参考资料及相关词条请参阅百科词条原文 。
目录
一、什么是演化算法？
二、实现过程与类型
三、与生物过程的比较
四、相关技术
五、其他基于群体的元启发式方法
六、相关资源推荐
七、集智百科词条志愿者招募
一、什么是演化算法？
在计算智能领域 ， 演化算法（Evolutionary Algorithms ， 简称EA ， 或称进化算法）是演化计算的子集， 是一种基于群体的元启发式最优化算法 。 演化算法使用了各种模拟生物演化机制的操作 ， 比如繁衍、变异、重组、选择等 。
在群体中每一个个体都是问题的备选解 ， 而适应度函数 fitness function用于计算出每一个解的质量（也就是个体对于环境的适应度） 。 演化就是在不断在群体中进行繁衍、变异、重组、选择这些操作进而找出最优解的过程 。 演化算法之所以在各种优化问题上都经常逼近最优解 ， 是因为它不会对适应度的范围作出预先假设 。
在大多数演化算法的应用中 ， 计算复杂度都是最大障碍 。 事实上 ， 这种计算复杂度来源于适应度函数 。 简化适应度函数 ， 从而计算近似的适应度 ， 是克服这一障碍的方法之一 。 由于看似简单的演化算法常常可以解决复杂的优化问题 ， 因此 ， 算法复杂度应该与问题的复杂性之间 ， 可能没有直接关系 。
二、实现过程与类型
实现过程
第一步：随机生成第一代群体 。
第二步：重复下面各步直到满足中止条件：
计算群体中每个个体的适应度
选择适应度最高个体进行繁衍操作
【算法|什么是演化算法｜集智百科】对于繁衍下来的新个体进行重组和变异操作 ， 以得到后代
计算新个体的适应度
淘汰掉群体中适应度低的个体
其他类型
演化算法的具体技术可以按照遗传信息表达方式、实现细节、以及特定问题的特定处理分类：
遗传算法 Genetic algorithm：这是演化算法中最常用的类型 。 这种技术应用于求解最优解是一组数字的问题 。
遗传编程 Genetic programming：这种技术用于生成一段计算机程序 ， 其适应度是这些计算机程序解决某计算问题的能力 。
演化编程 Evolutionary programming：与遗传编程类似 ， 但其求解的计算机程序的结构是固定的 ， 可以演化的是一些数值参数 。
基因表型编程 Gene expression programming：类似于遗传编程 ， 基因表达规划同样以计算机程序群体来进行演化计算 ， 但它探索了一种基因型-表现型系统 ， 将不同大小的计算机程序都编码成固定长度的“线性染色体” 。
演化策略 Evolution strategy：这种技术以实数向量作为个体 ， 而且使用了自适应的变异率 。
差分演化 Differential evolution：这种算法以向量的差为基础 ， 因此特别适合数值最优化问题 。
神经演化 Neuroevolution：类似于遗传编程 ， 但是其基因组编码可以直接 ， 也可以间接地表示人工神经网络的结构和连接权重 。
学习分类器系统 Learning classifier system（LCS）：这种技术的解是一组分类器（一组规则或者条件） 。 Michigan-LCS 在个体层面进行演化 ， 而Pittsburgh-LCS 使用分类器集合群体来演化 。 最初的时候这些分类器都是0-1编码的 ， 如今包含实数、神经网络、或者S-expression 。 其适应度一般是分类器系统应用于强化学习或有监督学习时的准确率 。
三、与生物过程的比较
对于演化算法来说 ， 一个可能的局限可能是缺少对基因型和表现型的明确区分 。 在大自然中 ， 受精卵会历经发育为胚胎的过程 ， 最终形成成熟的表现型 。 自然选择以表现型而非基因型为选择标准 。
这种间接编码被认为可以使得演化过程更健壮（降低致命突变的概率） ， 并提高器官的进化能力 。 这种间接编码还使得演化能够充分利用环境的规律 。 最近有关人工胚胎学 artificial embryogeny和人工发育系统 artificial developmental system的工作也在寻求解决这一局限的方法 。 基因表型编程这一技术也在基因型-表现型系统的探索中取得成功 。
四、相关技术
与演化算法相关的集群算法 Swarm algorithms 还包括：
蚁群优化算法：这种技术以蚂蚁觅食和通过信息素沟通寻路为基础 ， 最早应用于组化优化和图相关问题 。
茎根算法 Runner-root algorithm：一种受自然中植物的茎和根的功能启发的算法 。
人工蜂群算法 Artificial bee colony algorithm：根据蜜蜂觅食行为设计 ， 最初为数值优化提出 ， 后来扩展至解决组合、受约束的多目标最优化问题 。
布谷鸟搜索 Cuckoo search：根据布谷鸟巢寄生的行为提出 ， 同时使用了列维飞行机制 ， 因此适用于全局最优化问题 。
电子优化算法：这种技术背后的思想是电子流经电路时根据最小电阻原则分流的原理 。
粒子群算法：是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法 ， 主要适合用于解决数值优化问题 。
五、其他基于群体的元启发式方法
狩猎搜索 Hunting Search：根据自然中的狩猎行为提出 ， 一群捕食者 ， 如狼群 ， 组织它们的位置来包围猎物 。 捕食者中每一个个体的位置会根据其他个体 ， 尤其是领袖的位置调整 。 这是一种适合组合优化问题的连续优化方法 。
适应性维度搜索 Adaptive dimensional search：不同于仿生的元启发式技术 ， 适应性维度搜索没有模仿任何大自然中的现象 。 它使用简单的性能导向方法 ， 每一次迭代过程都会更新搜索维度率 search dimension ratio。
萤火虫算法 Firefly algorithm：通过模仿萤火虫发光互相吸引的行为设计 ， 特别适用于多峰函数的最优化求解 。
和弦搜索 Harmony search：参考了音乐家在和弦上的探索 ， 适用于组合优化和参数优化 。
高斯适应 Gaussian adaptation：一种基于信息论的方法 ，用于最大化成品率、平均适应度、平均信息量等 。 参考热力学和信息论中的熵 。
模因算法 Memetic algorithm：这是一种混合方法 ， 参考了理查德·道金斯的模因meme概念 ， 通常采用基于群体的算法形式 ， 再加上能够执行局部优化的个体学习过程 。 这种方法强调利用每个问题自身的特性 ， 并调和局部搜索和全局搜索 。
案例
2020年 ， Google宣布其AutoML-Zero成功复现了一些经典的算法 。
计算机模拟程序Tierra和Avida尝试性地对宏观进化过程的动力学建模 。
画廊
本文图片
1.对具有有限全局最优约束的Rosenbrock函数进行两种群EA搜索
本文图片
2.在约束的Rosenbrock函数上进行的两种群EA搜索 。 全局最优不受限制
本文图片
3.在Keane 作用上的分布估计算法
本文图片
4.两种群EA搜索Simionescu函数的有界最优解
六、相关资源推荐
生命是什么？生命如何起源？生命如何演化？揭开生命复杂性的重重谜题 ， 有赖于生物、化学、物理、计算机等不同背景人士的共同探索 。 我们正在组织关于生命复杂性的系列读书会 ， 持续两个月 ， 研读硬核论文书籍 ， 分享学界前沿成果 。 欢迎对生命复杂性有浓厚兴趣的朋友报名参加 。 读书会第一期在11月5日（周四）晚举办 。
本文图片
这篇文章主要介绍了计算机科学家 Kenneth Stanley提出的基于垫脚石原理的神经演化算法 ， 来解决神经进化存在两大难题：高昂的计算成本和不明确的目标 ， 同时带来了新的研究思路：忽略目标比直接追求目标能更快速实现目标 。 忽略目标或许是制造真正智能机器的最佳方法 。
本文图片
七、百科项目志愿者招募
作为集智百科项目团队的成员 ， 本文内容由Ricky、许许、薄荷参与贡献 。 我们也为每位作者和志愿者准备了专属简介和个人集智百科主页 ， 更多信息可以访问其集智百科个人主页 。
本文图片
以上内容都是我们做这项目的起点 ， 作为来自不同学科和领域的志愿者 ， 我们建立起一个有效的百科团队 ， 分配有审校、翻译、编辑、宣传等工作 。 我们秉持：知识从我而来 ， 问题到我为止的信念 ， 认真负责编撰每一个词条 。
在这里从复杂性知识出发与伙伴同行 ， 同时我们希望有更多志愿者加入这个团队 ， 使百科词条内容得到扩充 ， 并为每位志愿者提供相应奖励与资源 ， 建立个人主页与贡献记录 ， 使其能够继续探索复杂世界 。
推荐阅读
- 兔子|兔兔这么可爱，为什么要吃屎？
- 百度|AI公司百度能给港交所带来什么？
- 结核|再见吧，“结核君”
- 【夜读】豆腐飘香
- 番茄炒鸡蛋先炒番茄还是先炒鸡蛋？其实都不对，正确方法送给你
- 白色的发糕是用什么粉做的，难做吗？
- 做蛋炒饭，先炒蛋呢还是先炒饭呢很多人做的不对，难怪不好吃
- 红豆和玉米面是绝配，一个做皮一个做馅，包好入锅一蒸，特香
- 大脑|你的大脑和心理究竟是什么关系？
- 粒子|人体本身是由一堆粒子组成，怎么会产生思想？