遗传算法 遗传算法

遗传算法 GeneticAlgorithms 简称GA 一种基于自然选择原理和自然遗传机制的搜索 寻优 算法 它是模拟自然界中的生命进化机制 在人工系统中实现特定目标的优化 流程 关于遗传算法的基本概念1个例子 袋鼠攀登山峰一个具体的遗传算法的例子用matlab解决遗传算法 GA适用范围 函数优化 非线性 多目标的函数优化问题 组合优化 目标是从组合问题的可行解集中求出最优解 生产调度自动控制图像处理机器学习 生物遗传概念在遗传算法中的对应关系 适者生存 算法停止时 最优目标值的解有最大的可能被留住个体 解染色体 解的编码基因 解中每一分量的特征适应性 适应度函数值种群 根据适应度函数值选取的一组解交配 通过交配原则产生一组新解的过程变异 编码的某一分量发生变化的过程 遗传算法步骤 1 根据具体问题确定可行解域 确定一种编码方法 能用数值串或字符串表示可行解域的每一解 2 对每一解应有一个度量好坏的依据 它用一函数表示 叫做适应度函数 适应度函数应为非负函数 3 确定进化参数群体规模M 交叉概率Pc 变异概率Pm 进化终止条件 例子 袋鼠 遗传算法的实现过程实际上就像自然界的进化过程那样 首先寻找一种对问题潜在解进行 数字化 编码的方案 建立表现型和基因型的映射关系 然后用随机数初始化一个种群 那么第一批袋鼠就被随意地分散在山脉上 种群里面的个体就是这些数字化的编码 接下来 通过适当的解码过程之后 得到袋鼠的位置坐标 用适应性函数对每一个基因个体作一次适应度评估 袋鼠爬得越高 越是受我们的喜爱 所以适应度相应越高 用选择函数按照某种规定择优选择 我们要每隔一段时间 在山上射杀一些所在海拔较低的袋鼠 以保证袋鼠总体数目持平 让个体基因交叉变异 让袋鼠随机地跳一跳 然后产生子代 希望存活下来的袋鼠是多产的 并在那里生儿育女 遗传算法并不保证你能获得问题的最优解 但是使用遗传算法的最大优点在于你不必去了解和操心如何去 找 最优解 你不必去指导袋鼠向那边跳 跳多远 而只要简单的 否定 一些表现不好的个体就行了 把那些总是爱走下坡路的袋鼠射杀 以后你会慢慢理解这句话 这是遗传算法的精粹 例子一 编制袋鼠的染色体 基因的编码方式 那么我们如何利用编码方式来为袋鼠的染色体编码呢 因为编码的目的是建立表现型到基因型的映射关系 而表现型一般就被理解为个体的特征 受到人类染色体结构的启发 我们可以设想一下 假设目前只有 0 1 两种碱基 我们也用一条链条把他们有序的串连在一起 因为每一个单位都能表现出1bit的信息量 所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征 这就是二进制编码法 染色体大致如下 010010011011011110111110 1 物竞 适应度函数 fitnessfunction 自然界生物竞争过程往往包含两个方面 生物相互间的搏斗与及生物与客观环境的搏斗过程 但在我们这个实例里面 你可以想象到 袋鼠相互之间是非常友好的 它们并不需要互相搏斗以争取生存的权利 它们的生死存亡更多是取决于你的判断 因为你要衡量哪只袋鼠该杀 哪只袋鼠不该杀 所以你必须制定一个衡量的标准 而对于这个问题 这个衡量的标准比较容易制定 袋鼠所在的海拔高度 因为你单纯地希望袋鼠爬得越高越好 所以我们直接用袋鼠的海拔高度作为它们的适应性评分 即适应度函数直接返回函数值就行了 比如我们有5条染色体 他们所对应的适应度评分分别为 5 7 10 13 15 所以累计总适应度为 P 总 5 7 10 13 15 50P1 5 50 10 P2 7 50 14 2 天择 选择函数 selection 自然界中 越适应的个体就越有可能繁殖后代 但是也不能说适应度越高的就肯定后代越多 只能是从概率上来说更多 毕竟有些所处海拔高度较低的袋鼠很幸运 逃过了你的眼睛 那么我们怎么来建立这种概率关系呢 下面我们介绍一种常用的选择方法 轮盘赌 RouletteWheelSelection 选择法 遗传算子 交叉算子变异算子 交叉算子 1 单点交叉2 两点交叉与多点交叉3 均匀交叉4 算术交叉 单点交叉 在个体编码中随机设置一个交叉点 然后在该点相互交换两个配对个体的部分染色体 两点交叉与多点交叉 在个体编码串中随机设置两个交叉点 然后进行部分基因交换 变异算子 1 基本位变异2 均匀变异3 边界变异4 非均匀变异5 高斯近似变异 基本位变异 概率问题 具体例证 可以看出这个函数有多个极值 思路如下 1 确定决策变量和约束条件2 建立优化模型3 确定编码方法4 确定解码方法5 确定个体评价方法6 设计遗传算子 确定编码方法 1000桶酒10个犯人 其中有一桶毒酒 问怎么利用10个犯人找出毒酒 提示 编码 将变量转化为二进制串 串的长度取决于所要求的精度 例如 变量X1的区间是 a b 要求的精度是小数点后四位 也就意味着每个变量被分成 b a 10000个部分 对一个变量的二进制串位数 用以下公式计算 如何解码 解码方法 如 000001010100101001 5417x 3 0 5417 12 1 3 2 18 1 2 687969 由于时间的关系 初始种群可随机生成如下 U1 000001010100101001101111011111110 U2 001110101110011000000010101001000 相对应的十进制实际值为 U1 x1 x2 2 687969 5 361653 U2 x1 x2 0 474101 4 170144 确定个体评价方法 1 将染色体串进行反编码 转换成真实值 在本例中 意味着将二进制串转化为实际值 2 评价目标函数f x 3 将目标函数值转为适应度 对于极大值问题 适应度就等于目标函数值 eval U1 f 2 687969 5 361653 19 805119eval U2 f 0 474101 4 170144 17 370896 以适应度大小作为概率来选择 交叉 U1 000001010100101001101111011111110 U2 001110101110011000000010101001000 在 1 32 之间随机生成一个数 作为交叉点 假如交叉位是1 那么 U1 000001010100101001101111011111110 U2 001110101110011000000010101001000 就变为 U 1 001110101110011000000010101001000 U 2 000001010100101001101111011111110 变异 如果该位基因原是1 变异后则为0 将变异概率设为P 0 01 就是说 在平均水平上 种群内所有基因的1 要进行变异 如果一个种群有十个个体 染色体有33个基因 那么33 10 330 330 0 01 3 3 那么这个种群上每一代有3 3个变异基因 这里我们用基本位变异 所以随机确定一个基因位置 再重新确定每个个体的适应度 然后继续重复 直到达到你需要的多少代 matlab中的遗传算法函数 1 创建种群 crtbase crtbp crtp2 适应度计算 ranking scaling3 选择函数 reins rws select sus3 交叉算子 recdis recint reclin recmut recombin xovdprs xovmp xovsh xovshrs xovsp xovsprs 4 变异算子 mut mutate mutbga5 实用函数 bs2rv rep 创建种群 crtbp 创建任意离散随机种群创建一个染色体长度为9 有六个个体的随机种群 Chorm lind baseV crtbp 6 9 适应度计算 ranking 常用的基于秩的适应度计算考虑具有10个个体的种群 其当前目标值如下 ObjV 12345109876 选择函数 rws 轮盘选择考虑8个个