机器学习中的遗传算法

引言

遗传算法 (GA) 是一种令人兴奋且创新的计算机科学问题解决方法，其灵感来源于自然选择和遗传学。自然选择是构成遗传算法 (GA) 形式的基础，它属于更广泛的进化算法 (EA) 类别。最常用于通过使用突变、交叉和选择等生物学启发式算子来革新各个领域，以开发解决优化和搜索问题的有效方案。

什么是遗传算法？

遗传算法 (GA) 是一类计算优化方法，模仿了自然选择和遗传过程。通过模仿进化过程，它们用于通过迭代地改进一组可能的解决方案来解决复杂问题。这些算法使用存储在各种数据结构中或作为二进制数字字符串的一组潜在解决方案。

遗传算法的基础是一个“种群”的概念，代表当前问题的一组可能解决方案。种群中的每个个体都代表一个特定的解决方案，其特征由一组称为基因的变量决定。这些基因可以表示为二进制字符串、实值或其他数据格式，它们编码了解决方案的特性或属性。

遗传算法中的初始种群通常是随机产生的。然后，个体经历一系列重复，称为代或时期，在此期间，个体经历了选择、交叉和突变等过程。这些功能类似于生物进化中看到的遗传变异、自然选择和繁殖过程。

在选择阶段，使用适应度函数来评估当前种群中的候选个体。适应度函数衡量每个解决方案解决问题的有效程度。通过根据个体的适应度得分来选择个体，从而模拟了“适者生存”的原则，增加了它们被进一步处理的可能性。

一种称为交叉（也称为重组）的遗传操作发生在两个选定的个体交换遗传物质以产生后代时。这个过程类似于有性生殖，其中通过合并父母双方的遗传物质，创造出具有不同遗传构成的后代。

突变会导致某些个体基因发生微小、不可预测的变化。通过在整个种群中保持遗传多样性，此过程可以探索解决方案空间的各种区域。

应用遗传算子后，形成的新种群将替换上一代。这个过程会一直持续，直到满足终止条件，例如通过超过预定数量的迭代或在给定代数内达到预定的适应度水平。

遗传算法通过多代搜索解决方案空间，优先选择适应度值更高的解决方案。通过迭代地使用交叉、突变和选择，算法最终可以收敛到最优或接近最优的解决方案。

遗传算法已成功应用于各种优化问题，包括参数调整、调度、路由和机器学习。由于它们能够搜索广阔的解决方案空间并发现全局最优或接近最优的解决方案，因此在标准优化技术可能因复杂或非线性问题而失败的情况下，它们非常有用。

使用遗传算法的算法方法

遗传算法的重要组成部分

• 染色体： 染色体是解决手头问题的一种方式。
• 基因： 基因是染色体的一个组成部分。
• 种群： 问题的一组可能解决方案。
• 选择： 从整个种群中选择正确答案的机制。
• 交叉（重组）： 使用两种方法，从而增加后代数量如下。
• 突变： 随机交换解决方案的特征，以保持种群的多样性。
• 适应度函数： 一个接受答案并产生解决方案中合适方面（可能被称为主要适应度函数）的函数。有时，目标函数与适应度函数完全相同，但在其他情况下，为了解决手头的问题，两者可能有所区别。

遗传算法如何工作？

让我们看一个例子，优化一个典型的活动：确定从家到工作场所的最佳通勤路线。

假设您希望每天找到从家到工作的最快路线以最大化通勤效率。您可以从多种路线中选择，每种路线的行驶时间、距离和交通模式都不同。遗传算法可以帮助您确定最佳路线。

染色体/个体

基因在染色体上分组。例如，可以使用一个位代表一个基因的二进制字符串来表示染色体。

人口

由于每条染色体代表一个个体，因此种群由构成该个体的所有不同染色体组成。

适应度函数

适应度函数根据适应度得分计算每次迭代中个体的评估。

得分更高的个体更有可能被选中进行交叉并传递到下一代，因为它们是更好的候选者。

例如，如果挑战是分类，并且使用遗传算法进行特征选择，那么模型的准确性将是适应度函数。

编码解决方案

在这种情况下，可能的解决方案可以表示为组合城市或通勤路径上的点。例如，您可以将每条可能的路线写成一个城市 ID 字符串，如“A-B-C-D-E-F”，其中每个字母代表一个不同的位置（例如，街道、交叉路口或地标）。

初始化

首先，生成一个可能的路线的初始种群。可以随机生成一组路线，或者您可以从现有路线开始。

求值

在评估种群中的每条路线时，这些主要因素将是行程时间、行驶距离、交通状况和其他相关因素。应借助评估函数确定每条路线的质量，其中反映不同选项质量的值应尽可能低（例如，距离、交通拥堵时间等）。

选拔

在评估了种群中每个成员的适应度后，选择种群中将能够繁殖并产生下一代后代的成员。可用的选择技术包括：

• 轮盘赌选择
• 锦标赛选择
• 基于排名的选择

交叉

为了产生代表后代的另一个个体，通常选择当前代的两个个体，并交换它们的基因。这也被称为交叉或交配，它涉及通过两个亲本形成新个体，最终产品将是（）。

有各种各样的交叉技术，

• 单点交叉
• 两点交叉
• 均匀交叉

突变

突变因此意味着染色体发生非自愿的变化，其中引入了新的模式。

可用的突变技术类型，

• 翻转位突变
• 高斯突变
• 交换突变

新一代

下一代的新种群由前几代中少量优秀的个体以及通过交叉和突变产生的后代组成。这确保了可行解决方案将被保留和延续。

终止

GA 对指定代数执行选择、交叉和突变过程，或直到满足终止条件。终止条件可以是限制迭代次数或达到可行解决方案（例如，评估值较低的路线）。

最终解决方案

最佳选项，通常是评估值最低的选项，表示您日常通勤的最佳或接近最佳路线，一旦 GA 结束。

通过交叉、突变和选择的迭代应用，GA 有助于探索和演化路线种群，逐步聚焦您日常行程的最短和最优路线。

重要的是要记住，为了平衡探索和利用，GA 需要正确的参数设置，包括种群大小、选择技术、交叉率和突变率以及终止条件。

遗传算法与传统算法的区别

• 搜索空间是问题所有潜在解决方案的集合。在特征选择方面，R.F.E. 与遗传算法相比更优，因为它在搜索空间中维护多个集合，而传统算法只维护一个集合。
• 传统算法寻求更多信息，而遗传算法只需要一个目标函数来评估个体的适应度。
• 传统算法无法并行运行；相反，它们必须单独计算每个个体的适应度。遗传算法则不然。
• 遗传算法与其他算法的一个显著区别在于，前者直接作用于潜在解决方案，而后者作用于它们的表示，也称为编码或染色体。
• 虽然遗传算法可以从不同代中产生多个最优解决方案，但传统算法最终只能产生一个解决方案。
• 交叉和突变等遗传算子增加了遗传算法提供全局最优解决方案的可能性，但这并非必然。传统算法不太可能产生全局最优解决方案。
• 与标准算法不同，标准算法是确定性的，而遗传算法是随机的和概率性的。
• 由于现实世界的问题是多模态的（包含许多局部最优解），因此标准算法难以处理。然而，当选择正确的参数时，遗传算法由于其广阔的解决方案空间，可以很好地处理这些问题。

遗传算法的优点

• 并行性
• 全局优化
• 扩展的解决方案空间集
• 所需信息较少
• 提供多个理想解决方案
• 基于概率的方法
• 使用染色体表示遗传信息

遗传算法的缺点

• 需要某些定义
• 超参数调整
• 计算复杂性

遗传算法的应用

遗传算法 (GA) 被广泛应用于许多不同的行业。以下是一些值得注意的遗传算法的用途：

优化问题

遗传算法 (GA) 在解决优化相关问题方面非常有效，因为它们能够快速选择正确的选项（如果存在大量选项）。这些问题包括资源分配、投资组合优化、参数调整以及数学函数优化等。遗传算法通过交叉、突变和选择等遗传算子生成一组潜在解决方案或染色体。这个解决方案的种群越来越接近最优，并为 GA 提供了搜索解决方案空间的机会。

组合优化

遗传算法 (GA) 可以有效解决涉及有限集合选择、组合或组件排列的组合优化问题。一些例子包括旅行推销员问题 (TSP)、车辆路径问题 (VRP)、装箱问题、工作调度和 DNA 序列比对。与染色体一样，遗传算法是假定的解决方案，通过进化过程找到最优的元素组合。

机器学习

遗传算法 (GA) 在机器学习中有益，特别是在调整机器学习模型的参数数量和配置方面。一些常见的可以与超参数一起优化的超参数包括学习率、正则化参数和神经网络的设计。它们的另一个用途是特征选择，其中算法需要创建一组特征子集，以便选择最适合特定任务的子集。

进化机器人学

进化机器人学是一个研究领域，其中 GA 被应用于分析机器人动作和控制策略的发育变化。虽然机器人控制参数或策略由所谓的基因链表示，但 Galois 组装可以提供解决缺陷（如稳定性、速度、功耗和灵活性）的规范的解决方案。最有用的是那些通过分析难以找到最合适控制技术的 GA。

图像和信号处理

模式和信号识别、降噪、图像特征提取和图像重建是 GA 执行的一些任务。为了提高图像质量，它们可以操纵重建算法的参数。它们还可以优化信号处理中的滤波设置，以便对噪声信号进行清理，只留下重要信息。它们还可以用于自动特征提取，涉及开发特征提取算法以从图像或信号中获取相关特征或对象。

金融建模

遗传算法 (GA) 可应用于任何涉及风险评估、交易策略和投资组合选择的金融建模任务。因此，GA 可以增强确定不同资产投资组合的最佳比例的过程，以确保最大回报和最低风险。这些策略还允许交易者根据市场状况调整某种形式的交易特征，并试图最大化收益。遗传算法为模拟复杂的金融系统提供了一种灵活且易于调整的方法。

这些用途表明了遗传算法在解决不同应用领域中的搜索和优化问题方面的多功能性和有效性。乐观的进化算法或 GA 由于其搜索解决方案容量、控制约束以及获得自适应解决方案的能力，在分析复杂的实际问题方面具有优势。

遗传算法示例

遗传算法已在不同活动领域的不同业务问题中得到实施。以下是一些当前突出的 GA 示例：

谷歌的 DeepMind

谷歌子公司 DeepMind 已将其遗传算法应用于人工智能研究。AlphaFold 是一个很好的例子，它使用 GA 开发了蛋白质折叠模型，彻底改变了 DeepMind 的运营。蛋白质的功能需要了解其三维排列，这些结构与药物开发和疾病研究相关。上述结构被算法准确预测。

特斯拉的自动驾驶任务

遗传算法被用于电动汽车和可持续能源公司特斯拉的自动驾驶技术中。这些技能与自动驾驶活动相关，并通过算法在神经网络上得到改进。通过使用 GA 帮助它们学习或执行得更好，这将使特斯拉的自动驾驶系统更安全、更高效。

亚马逊的物流运营

亚马逊通过使用遗传算法提高了订单履行和交付的效率。预计通过 GA 可以实现更高的交付效率和更好的供应链管理，因为可以解决许多复杂的路由和调度问题。借助提供动态优化的新改进算法，亚马逊可以轻松满足客户期望，这些期望基于实时收集的数据不断演变。

Autodesk 的设计优化

计算机辅助设计和工程解决方案软件公司 Autodesk 已在其软件产品中实施了遗传算法。它们允许用户使用 GA 进行优化，例如，开发高效的 3D 结构或确定机械零件的适当设计。

Uber 的进化优化器

打车公司 Uber 创建了一个名为 Evolutionary Optimizer 的优化系统。为了提高 Uber 动态定价系统的有效性，在这项研究中使用了遗传算法。该优化器通过根据历史和实时需求函数调整定价策略，从而在提供公平的消费者定价体验的同时提高了公司的收入。

波音的机翼设计优化

通过使用遗传算法重新设计机翼以优化波音的飞机设计。遗传算法被用于跨音速桁架支撑机翼 (TTBW) 和翼身融合体 (BWB) 等项目中，以测量不同的机翼形状、尺寸和类型。得益于这种策略，波音能够减轻飞机的重量、提高燃油效率并增强飞机的空气动力学性能。

福特的车辆路线优化

福特汽车公司通过应用 GA 改进了车辆路线。福特在其项目中使用了 GA，以在考虑交通模式、物品尺寸和交付窗口截止日期等变量的情况下，为卡车找到最佳路线。由于这项优化工作，福特能够减少交付时间、提高整体效率并简化物流运营。

西门子制造过程优化

跨国技术公司西门子利用遗传算法优化了其生产过程。西门子在其努力中采用 GA 来简化工业工厂的工作流程模式、机器设置和生产计划。通过这种策略，西门子能够降低其制造过程的成本、最大限度地减少停机时间并提高生产效率。

英伟达的 GPU 架构优化

英伟达使用遗传算法进行 GPU 架构优化。为了提高 AI 和游戏应用的性能和能效，图形适配器 (GA) 被用来研究和优化图形处理单元设计特性。

丰田的供应链优化

丰田利用 GA 来简化其国际供应链。通过使用 GA，通过改进物流路线、库存控制和制造计划，提高了供应链效率，同时降低了成本。

这些例子表明了各种行业的公司如何使用遗传算法来解决具有挑战性的优化问题、提高生产力并促进各自领域的创新。

结论

遗传算法 (GA) 将变得更加强大和有影响力，这得益于其广泛的应用、不断提高的计算能力、与其他优化方法和机器学习算法的混合、对不断变化的环境的适应能力、处理多目标问题的能力以及领域特定的应用。

此外，并行和分布式计算范式，以及旨在提高解释和可解释性的举措，将支持 GA 在解决复杂优化问题方面的广泛使用和效率，使其成为未来决策和解决问题的宝贵工具。