遗传算法入门

目录

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

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

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

• 一个种群中有许多个体。
  
• 每个个体都有其独特的基因（DNA），决定了它的性状（比如身高、速度）。
  
• 环境资源有限，个体之间需要竞争。适应环境的个体更有可能生存下来并繁衍后代（自然选择）。
  
• 后代通过交叉（父母的基因混合）和变异（基因发生微小随机变化）继承父母的基因。
  
• 经过一代又一代的繁衍，整个种群的适应度会越来越高，因为优良的基因被保留和组合，最终进化出能很好适应环境的个体。
  

遗传算法就是将这个过程数字化，以寻找问题的最优解。
目标： 找到一个问题的最优解；
做法： 用数字化模拟这个过程。
数字模拟化的过程：
遗传算法的工作流程其实是一个循环迭代的过程，可以概括为以下五步：
1 初始化： 随机生成一个由多个“个体”（潜在解）组成的初始种群。
2 评估： 用适应度函数计算种群中每个个体的适应度分数。
3 选择： 根据适应度高低，择优选择“父母”个体。高适应度个体有更高概率被选中繁衍后代。
4 交叉： 模拟基因重组，将选中的“父母”的染色体部分交换，产生新的“后代”个体。
5 变异： 以很低概率随机改变后代染色体中的部分基因，引入新特性。
∞ 循环： 新产生的后代形成新的种群，取代旧的种群。然后重复步骤2-5，直到满足终止条件（如找到足够好的解或达到最大迭代次数）。
案例——背包问题

一些术语了解：

• 个体与染色体：在算法中，一个可能的解决方案（比如一个设计参数、一个时间表）被看作一个“个体”。这个个体的完整“基因蓝图”就是它的染色体，通常用一串数字（二进制或十进制）表示。
  
• 种群：不是单个个体在进化，而是一群个体（一个种群）在一起进化，这模拟了自然界中的生物种群。
  
• 环境与适应度：待解决的问题本身（如“成本最低”、“效率最高”）就是算法的“环境”。衡量一个解决方案好坏的标准被量化为适应度函数。个体越适应环境（解决方案越好），其适应度得分就越高。
  

场景设定：
你是一个要去野营的孩子，你有一个容量有限的背包。你面前摆着5件物品，每件物品的价值和体积都不同。
你的目标是：在背包容量限制下，选择一些物品装进去，使得背包里所有物品的总价值最高。
物品列表如下：
物品价值（元）体积（升）水壶102书54零食153外套205手电筒122第一步 —— 初始化

核心是：将一个数学优化问题，转化为一个用“数字基因”表示的“虚拟生物”的生存与繁衍问题。这一步也叫编码过程。
我们如何用一个“基因”来表示一种装包方案？
我们用一串二进制代码（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个关键：

• 如果总体积超过8升，这个方案就是无效的，我们给它很低的分数（比如0分）。
  
• 谁的总价值高，谁就保留谁下来。
  

我们来计算一下：

• 个体A 10101：物品 = 水壶(2L) + 零食(3L) + 手电筒(2L)。总体积 = 7L (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种可能。而是通过保留高价方案（选择）、组合不同方案的优点（交叉）、以及偶尔尝试新选择（变异），像搭积木一样，一步步地“进化”出接近最优的装包方案。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！