老饼讲解-神经网络 机器学习 神经网络 深度学习
启发式寻解

【原理】遗传算法-入门讲解

作者 : 老饼 发表日期 : 2022-09-14 19:22:08 更新日期 : 2023-11-12 08:50:30
本站原创文章,转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com


遗传算法是著名的智能算法之一,它借鉴于生物遗传进行的机制来寻找一个优秀的解

本文讲解遗传算法的思路和具体流程,并剖析遗传算法的核心思路



    01. 遗传算法的思想与机制    



本节介绍遗传算法的思想与机制,初步了解遗传算法是什么



     遗传算法的思想    


遗传算法是一种借鉴生物遗传进化机制而设计的寻优算法
生物在多代种群迭代中,优胜劣态,最终种群越来越优秀
 
这种机制可以迁移到我们的数学求最优值问题上来
种群个体就相当于我们的解,目标函数就是衡量这个个体优秀程度的指标
所以我们可以借鉴生物是怎么进化到一个优秀个体,来让我们的解,也进化(寻找)到一个更优秀的解




    遗传算法的机制介绍    


遗传算法是以生物进化的概念而设计的一种寻优算法
主要借鉴的机制有三,如下:
  👉
1. 种群与编码                   
 
👉2. 染色体交换与基因突变
 
👉3. 适者生存                    
种群与编码
在刚开始时,遗传算法会先初始化一个种群,即一组X
种群的个体(即每个X)都以编码的形式存在,如下
 
染色体交换与基因突变
然后遗传算法通过个体之间的染色体交换和基因突变来产生新的种群
 
适者生存
最后,根据种群个体的适应度来选择是否能遗留到下一代种群
 
通过这种机制,不断的迭代,使得种群的质量不断优化
直到种群无法进化,或者达到最大迭代次数时,终止迭代,最后输出最优的个体







   02. 遗传算法的算法流程   



本节展示遗传算法的具体算法流程



     遗传算法的算法流程    


遗传算法的算法流程如下:
一、初始化种群                                                                                 

初始化g个解                                                                         
二、迭代T轮                                                                                       
2.1 染色体交换                                                                            
 解与解之间进行部分交换                            
交换的方式是多种多样,具体问题有具体方案         
2.2 基因变异                                                                             
 抽个别解作单独的随机调整                         
2.3 计算个体适应度                                                                   
 越优秀的解,适应度越大                           
2.4 赌轮盘选择一下代                                                               
(1) 生成轮盘                                                                      
按适应度占比分配轮盘面积,适应度越大面积就越大
(2) 赌轮盘选择下一代                                                        
仍抽g个解作为下一代 ,本轮最优必须进入下一轮,
剩余g-1个通过赌轮盘确定选择哪一个(赌g-1次轮盘)
赌轮盘的方法:                                                      
 每次生成一个[0,1]之间的随机数,                
随机数指向轮盘哪个位置就抽哪个                
(有可能重复抽到同一个)                        
三、输出结果                                              
最后,遗传算法输出历史最优的解作为最终的解        




    关于遗传算法的自定义内容    


遗传算法是一种思想,对于具体的问题,
我们需要自行定义如下部分
(1) 染色体交换的方式(即解与解之间如何进行部分交换) 
如果解的形式是一个数值,往往会把它先换为2进制,
再将解进行部分片段交换,以此产生新解            

(2) 基因变异的方式(即单个解如何作出随机改变)           
(3) 适应度的设计(越优秀值的解适应度越大)                  
 如果是最小化问题,且目标函数恒大于0,         
则常见的方法将适应度取为目标函数的倒数       
✍️补充:关于解的编码
如果解X不是编码形式,还需另外设计如何将X转换成编码形式
 例如X如果是数值形式,可以将它转换成二进制形式










  End  







联系老饼