搜索
遗传算法简介主讲人：目录1.背景简介……………遗传算法的生物学背景2.算法原理……………算法流程及算子的介绍3.算法评价……………优缺点及适用性评估背景简介遗传算法的生物学原理：•适者生存原则•自然选择•遗传和变异•种群演化遗传算法适用场景•NP问题：一个问题的单个解可以在有限时间内被验证。•具体适用于诸多领域如函数优化、组合优化、生产调度、自动控制、机器学习、图像处理、人工生命、遗传编程、机器学习、数据挖掘等。均有很好的表现。基本算法原理一般流程：1.初始化人工种群种群个体染色体基因2.计算个体的适应度3.进行选择，交叉，变异等操作4.迭代2，3步，直到满足停止规则基本算法原理初始化人工种群：•确定个体：对问题进行编码浮点数编码：真值编码二进制编码：解空间映射到二进制序列•确定种群：确定种群数量上限（20~100）加入随机的个体交叉/变异概率基本算法原理计算适应度：•适应度函数的选择–有目标：以结果函数为评估函数为原型–无明确目标：种群的变化率基本算法原理种群世代更替：•选择–根据适应度进行排序–概率选择函数/精英机制•交叉–对选择的结果进行交叉操作–概率交换部分序列生成新序列•变异–概率变异算法原理选择算子：•轮盘赌选择法•排序选择法•最优个体/截断选择法•锦标赛选择法算法原理选择算子：•轮盘赌选择法•选择保留的父代数量为n个体ID12345678适应度9.577.531.5841被选概率0.230.170.180.070.040.190.10.02累积概率0.230.770.60.940.980.420.871适应度轮盘赌个体1个体2个体3个体4个体5个体6个体7个体8算法原理选择算子：•排序选择法个体ID16327458适应度9.58.07.57.04.03.01.51.0被选概率0.220.20.170.140.10.080.060.03个体ID12345678适应度9.577.531.5841算法原理选择算子：•最优个体/截断选择法n=4个体ID12345678适应度9.577.531.5841算法原理选择算子：•锦标赛选择法个体ID12345678适应度9.577.531.584171.5=选择2作为父代算法原理选择算子：•轮盘赌选择法•排序选择法•最优个体/截断选择法•锦标赛选择法影响：适应度函数转换，选择强度，收敛速度，解的多样性算法原理交叉算子：•单点交叉/两点交叉/多点交叉•均匀交叉/离散交叉算法原理交叉算子：•单点交叉/两点交叉/多点交叉：10101100101100100011001000101100算法原理交叉算子：•单点交叉/两点交叉/多点交叉：10101100101111000011001000100010算法原理交叉算子：•均匀交叉/离散交叉：基于固定概率10101100101010000011001000110110算法原理变异算子：•基本位变异：基因反转/等位值替换•均匀变异：均匀随机分布值替换•高斯近似变异：正态分布值替换算法原理变异算子：•基本位变异：基因反转/等位值替换1010110010100100算法原理变异算子：•均匀变异：均匀随机分布值替换11.534.71.64511范围[0，8]，步长取2，可能的变异值：0，2，4，6，8，取到每个变异值的概率相同算法原理变异算子：•高斯近似变异：正态分布值替换11.534.71.64511范围[0，8]，根据高斯分布取可能的变异值，取值概率符合正态分布遗传算法的优势•适用于灰箱/黑箱问题•潜在并行性•适应度函数评价，计算复杂度小•收敛性强•具有可扩展性，易与其他算法结合遗传算法的不足•早熟/过早收敛•不适用于局部搜索•计算量大，搜索时间长•并行性开发不够充分研究改进方向•收敛性/早熟的预防•遗传算子的设计•遗传算子的自适应设计•并行化研究感谢倾听