当前位置: 首页 > news >正文

遗传算法入门

目录
  • 物种进化的目的
  • 案例——背包问题
    • 第一步 —— 初始化
    • 第二步 — 适应度评估
    • 第三步 — 遗传操作(进化核心:选择、交叉、变异)
    • ∞ 循环
    • 总结


image

遗传算法是什么?
遗传算法是一种受生物进化论(特别是自然选择和遗传学)启发的搜索和优化算法。它模拟了“物竞天择,适者生存”的过程,用于解决复杂的优化问题,尤其是在传统数学方法难以奏效的情况下。


物种进化的目的

梳理一个生物物种的进化过程:

  • 一个种群中有许多个体。

  • 每个个体都有其独特的基因(DNA),决定了它的性状(比如身高、速度)。

  • 环境资源有限,个体之间需要竞争。适应环境的个体更有可能生存下来并繁衍后代(自然选择)。

  • 后代通过交叉(父母的基因混合)和变异(基因发生微小随机变化)继承父母的基因。

  • 经过一代又一代的繁衍,整个种群的适应度会越来越高,因为优良的基因被保留和组合,最终进化出能很好适应环境的个体。

遗传算法就是将这个过程数字化,以寻找问题的最优解。
目标: 找到一个问题的最优解;
做法: 模拟一个生物物种进化过程,用数字化模拟这个过程。


数字模拟化的过程:
遗传算法的工作流程其实是一个循环迭代的过程,可以概括为以下五步:

1 初始化: 随机生成一个由多个“个体”(潜在解)组成的初始种群。

2 评估: 用适应度函数计算种群中每个个体的适应度分数。

3 选择: 根据适应度高低,择优选择“父母”个体。高适应度个体有更高概率被选中繁衍后代。

4 交叉: 模拟基因重组,将选中的“父母”的染色体部分交换,产生新的“后代”个体。

5 变异: 以很低概率随机改变后代染色体中的部分基因,引入新特性。

∞ 循环: 新产生的后代形成新的种群,取代旧的种群。然后重复步骤2-5,直到满足终止条件(如找到足够好的解或达到最大迭代次数)。


案例——背包问题

一些术语了解:

  • 个体与染色体:在算法中,一个可能的解决方案(比如一个设计参数、一个时间表)被看作一个“个体”。这个个体的完整“基因蓝图”就是它的染色体,通常用一串数字(二进制或十进制)表示。

  • 种群:不是单个个体在进化,而是一群个体(一个种群)在一起进化,这模拟了自然界中的生物种群。

  • 环境与适应度:待解决的问题本身(如“成本最低”、“效率最高”)就是算法的“环境”。衡量一个解决方案好坏的标准被量化为适应度函数。个体越适应环境(解决方案越好),其适应度得分就越高。


场景设定:
你是一个要去野营的孩子,你有一个容量有限的背包。你面前摆着5件物品,每件物品的价值和体积都不同。

你的目标是:在背包容量限制下,选择一些物品装进去,使得背包里所有物品的总价值最高。

物品列表如下:

物品 价值(元) 体积(升)
水壶 10 2
5 4
零食 15 3
外套 20 5
手电筒 12 2

第一步 —— 初始化

核心是:将一个数学优化问题,转化为一个用“数字基因”表示的“虚拟生物”的生存与繁衍问题。这一步也叫编码过程。

我们如何用一个“基因”来表示一种装包方案?
我们用一串二进制代码(0和1)来表示,长度等于物品的数量。

  • 1 代表“拿”这个物品
  • 0 代表“不拿”这个物品

例如:

  • 染色体 10101 表示:拿水壶(1)、不拿书(0)、拿零食(1)、不拿外套(0)、拿手电筒(1)。
  • 染色体 01010 表示:不拿水壶、拿书、不拿零食、拿外套、不拿手电筒。

我们随机生成几种不同的装包方案,作为初始的“想法”或“种群”。
假设我们初始的4个“个体”(装包方案)是:

  • 个体A: 1 0 1 0 1 (拿水壶、零食、手电筒)
  • 个体B: 0 1 1 0 0 (拿书、零食)
  • 个体C: 1 1 0 1 0 (拿水壶、书、外套)
  • 个体D: 0 0 0 1 1 (拿外套、手电筒)

第二步 — 适应度评估

目的:设计一个适应度函数 来评估每个个体对环境的适应程度,即解的好坏。适应度越高,个体越优秀。

我们的“适应度函数”就是计算这个方案的总价值。2个关键:

  1. 如果总体积超过8升,这个方案就是无效的,我们给它很低的分数(比如0分)。
  2. 谁的总价值高,谁就保留谁下来。

我们来计算一下:

  • 个体A 10101:物品 = 水壶(2L) + 零食(3L) + 手电筒(2L)。总体积 = 7L (<8L),总价值 = 10+15+12 = 37元。适应度 = 37。
  • 个体B 01100:物品 = 书(4L) + 零食(3L)。总体积 = 7L,总价值 = 5+15 = 20元。适应度 = 20。
  • 个体C 11010:物品 = 水壶(2L) + 书(4L) + 外套(5L)。总体积 = 11L (>8L)!超重了! 适应度 = 0。
  • 个体D 00011:物品 = 外套(5L) + 手电筒(2L)。总体积 = 7L,总价值 = 20+12 = 32元。适应度 = 32。

第三步 — 遗传操作(进化核心:选择、交叉、变异)

a. 选择
根据适应度高低来选择父母。个体A和D分数高,更可能被选中。个体C因为无效,最容易被淘汰。

假设我们选中了 个体A (10101)个体D (00011) 作为父母。

b. 交叉
我们让他们在中间某个位置(比如第2位之后)交换基因。

  • 父母A: 10 | 101
  • 父母D: 00 | 011

交换后,得到两个孩子:

  • 孩子1: 10 | 011 -> 10011 (拿水壶、不拿书、不拿零食、拿外套、拿手电筒)
  • 孩子2: 00 | 101 -> 00101 (不拿水壶、不拿书、拿零食、不拿外套、拿手电筒)

c. 变异
以很小的概率,随机改变孩子某个位子的选择。
假设孩子1 10011 的第三位(零食)发生了变异,从0变成了1

  • 孩子1就变成了 10111

∞ 循环

形成新种群与终止检查:

  • 我们用新生的孩子(10111, 00101等)替换掉老一代中较差的个体(如个体B和C),形成新一代种群。

  • 检查终止条件

    • 我们计算新种群中每个个体的适应度。比如 10111(拿水壶、零食、外套、手电筒)总体积=12L,超重!适应度为0。而 00101(拿零食、手电筒)总体积=5L,价值=27元。
    • 我们发现还没有一个方案的价值能超过第一代个体A的37元,或者我们设定的迭代次数还没到。
    • 于是,我们回到第2-3步,继续评估、选择、交叉、变异...
    • 在不断的迭代中,算法可能会组合出像 10101(价值37)或 10001(拿水壶和手电筒,价值22,但体积小,为后续组合留空间)这样的优秀基因,并最终可能找到一个比37元更优的解(如果存在的话)。

总结

通过背包问题,可以看到遗传算法如何聪明地探索所有可能的组合:

它不会盲目地尝试所有\(2^5\)=32种可能。而是通过保留高价方案(选择)、组合不同方案的优点(交叉)、以及偶尔尝试新选择(变异),像搭积木一样,一步步地“进化”出接近最优的装包方案。

http://www.hskmm.com/?act=detail&tid=35091

相关文章:

  • 关于keil5生成bin文件的方法
  • 2025 年食品级润滑油脂厂家最新推荐榜单:聚焦纳米材料技术突破,甄选核心竞争力突出的企业
  • 2025 年食品级润滑油源头厂家最新推荐排行榜:聚焦国产标杆企业,54 项专利加持,助力企业精准选品食品级润滑油液压油/食品级润滑油齿轮油/食品级润滑油烘焙设备润滑油厂家推荐
  • 2025年精密弹簧厂家权威推荐榜:压缩弹簧、拉伸弹簧、异形弹簧专业制造商实力解析与选购指南
  • CF2109E Binary String Wowee
  • 中电金信:GienTech动态 | 迪拜2025海湾信息技术展举办,这些精彩别错过→
  • 20232310 2025-2026-1 《网络与系统攻防技术》 实验二实验报告
  • Nginx怎么帮国标GB28181算法算力平台EasyGBS “传话”?教你用HTTP让Nginx代理EasyGBS的Web页面服务
  • 2025年不锈钢管件厂家权威推荐榜:欧标卡压管件/国标管件/薄壁沟槽管件,9045弯头全系列精准选购指南
  • wsl连接 USB 设备
  • 【完整版】vcruntime140_1.dll缺失?3步快速修复教程(含官方修复工具+系统适配指南)
  • 如何系统化掌握 iOS 26 App 耗电管理,多工具协作
  • 2025年磨粉机厂家权威推荐榜:雷蒙磨粉机/环辊磨粉机/摆式磨粉机/矿石磨粉机/超细磨粉机/高压磨粉机,大型磨粉机源头厂家精选
  • linux 学习平台 arm+x86 搭建 - 详解
  • user read only folder
  • 2025 年 MacBook / 苹果电脑清理应用程序最新推荐榜单:精选适配 macOS 系统的高性能系统优化工具
  • 第六周第一天6.1
  • 2025 运动木地板厂家最新推荐榜:权威甄选行业前五优质品牌,附专业选择指南
  • 基于OpenGL实现三维树木生长动画的解决方案
  • 2025年液压阀块厂家权威推荐榜:液压阀块加工、阀块零件机加工、液压阀加工、各种液压阀块专业制造商深度解析
  • rust如何查看和修改当前编译器版本
  • 如何实现文件批量重命名后再进行批量打包下载
  • ML-Summit2025|从游戏AI到工程机械,具身智能的实践与应用
  • SpringBoot使用TraceId日志链路追踪
  • 马尔可夫决策过程的理解
  • 2025年服装辅料厂家权威推荐榜:服饰辅料,全品类辅料,箱包辅料源头厂家精选,品质保障与创新设计深度解析
  • 逆向 | 逃离鸭科夫 frida hook 锁血
  • 2025 年球墨铸铁管厂家最新推荐榜:涵盖 K9/C 级供水等多规格,优质厂家选购指南 k9级球墨铸铁管/c25级球墨铸铁管/c30球墨铸铁管/c级球墨铸铁管厂家推荐
  • 2025年掘进机/综掘机厂家权威推荐榜:专业制造与技术实力深度解析,高效掘进设备优选指南
  • 洛谷P2474 [SCOI2008] 天平 题解