埠虏慰腺目录物种进化的目的案例——背包问题第一步 —— 初始化第二步 — 适应度评估第三步 — 遗传操作进化核心选择、交叉、变异∞ 循环总结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个关键如果总体积超过8升这个方案就是无效的我们给它很低的分数比如0分。谁的总价值高谁就保留谁下来。我们来计算一下个体A 10101物品 水壶(2L) 零食(3L) 手电筒(2L)。总体积 7L (8L)总价值 101512 37元。适应度 37。个体B 01100物品 书(4L) 零食(3L)。总体积 7L总价值 515 20元。适应度 20。个体C 11010物品 水壶(2L) 书(4L) 外套(5L)。总体积 11L (8L)超重了 适应度 0。个体D 00011物品 外套(5L) 手电筒(2L)。总体积 7L总价值 2012 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元更优的解如果存在的话。总结通过背包问题可以看到遗传算法如何聪明地探索所有可能的组合它不会盲目地尝试所有2532种可能。而是通过保留高价方案选择、组合不同方案的优点交叉、以及偶尔尝试新选择变异像搭积木一样一步步地“进化”出接近最优的装包方案。分类: Algorithm