type
status
date
slug
summary
标签
category
icon
password
遗传算法的简介
wiki对遗传算法的解释是遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
运用Deap实现遗传算法
关于Deap
DEAP是一个新颖的进化计算框架，用于快速原型设计和测试想法。它力求使算法明确，数据结构透明。它与多进程和SCOOP等并行化机制完美地协调工作。
Deap实现TSP问题
通过实现经典TSP问题来入门Deap
定义优化目标
单目标优化：
creator.create('FitnessMin', base.Fitness, weights=(-1.0, ))weights用来指示最大化和最小化。此处-1.0即代表问题是一个最小化问题，对于最大化，应将weights改为正数，如1.0。单目标优化中weights的大小没有讲究，但是在多目标优化中，weights的大小对应着目标的重要程度以及最大最小化，需要注意。
初始化个体及群体
toolbox提供了一系列的算法来生成个体和种群。
常见的个体编码：
- 实数编码 直接用实数对变量进行编码。优点是不用解码，基因表达非常简洁，而且能对应连续区间。但是实数编码后搜索区间连续，因此容易陷入局部最优。
- 二进制编码 在二进制编码中，用01两种数字模拟人类染色体中的4中碱基，用一定长度的01字符串来描述变量。其优点在于种群多样性大，但是需要解码，而且不连续，容易产生Hamming cliff（例如0111=7, 1000=8，改动了全部的4位数字之后，实际值只变动了1），在接近局部最优位置时，染色体稍有变动，就会使变量产生很大偏移（格雷编码（Gray coding）能够克服汉明距离的问题，但是实际问题复杂度较大时，格雷编码很难精确描述问题）。
- 序列编码 通常在求解顺序问题时用到，例如TSP问题。序列编码中的每个染色体都是一个序列。
- 粒子 粒子是一种特殊个体，主要用于粒子群算法。相比普通的个体，它额外具有速度、速度限制并且能记录最优位置。
常见的种群：
- 一般族群：这是最常用的族群类型，族群中没有特别的顺序或者子族群。
- 同类群(Demes)：同类群即一个族群中包含几个子族群。在有些算法中，会使用本地选择(Local selection)挑选育种个体，这种情况下个体仅与同一邻域的个体相互作用。
- 粒子群：粒子群中的所有粒子共享全局最优。在实现时需要额外传入全局最优位置与全局最优适应度给族群。
TSP问题需要一个序列编码的个体和一个一般族群即可。
TSP问题代码：
定义适应值函数
根据需要定义自己的适应值函数，并使用deap库声明
在使用DEAP时，需要注意的是，无论是单目标还是多目标优化，评价函数的返回值必须是一个
tuple类型。TSP问题代码：
选择操作
函数
简介
selTournament()
锦标赛选择
selRoulette()
轮盘赌选择
selNSGA2()
NSGA-II选择，适用于多目标遗传算法
TSP问题代码：
交叉操作
函数
简介
cxOnePoint()
单点交叉
cxTwoPoint()
两点交叉
cxUniform()
均匀交叉
cxPartialyMatched()
部分匹配交叉PMX
TSP问题代码：
突变操作
函数
简介
mutGaussian()
高斯突变
mutShuffleIndexes()
乱序突变
mutFlipBit()
位翻转突变
mutPolynomialBounded()
有界多项式突变
mutUniformInt()
均匀证整数突变
TSP问题代码：
主函数（遗传算法）
以上代码定义了需要用到了函数工具，接下来就是运用他们
全部代码
小结
- 用的最简单的优化方法，最后的结果不能保证每次都最优，多次运行后，最优解能达到440.
- 在python上不能动态展示规划的路径
- 作者:Fr4nk
- 链接:https://www.frankxx.link/article/230104
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。