文档介绍：遗传算法理论
遗传算法的概要
问题的提出
对于一个求函数最大的优化问题一般可以描述为下述数学规划模型
式中, 为决策变量,f(x)为目标函数,式(1-2),(1-3)为约束条件,U为基本空间,R是U的一个子集,称为可行集。
总的来讲,求最优解或近似最优的方法主要有三种:枚举法,启发式算法和搜索算法,随着问题种类的不同和规模的扩大,上述方法都不理想,遗传算法却提供了这类问题一个有效方法,开创了一种新的全局优化搜索算法。
遗传算法中,将N维决策向量用n个记号Xi(i=1,2,...n)所组成的符号串X来表示:
把每个Xi看成一个遗传基因,它的所有可能取值称为等位基因,这样,X就可看做是由n个遗传基因所组成的一个染色体。
遗传算法中,决策变量X组成了问题的解空间。对问题最优的搜索是通过染色体X的搜索过程来进行的,从而由所有染色体X就组成了问题的搜索空间。
遗传算法的基本概念和术语
与生物界的进化过程相类比,遗传算法中有以下几个非常重要的概念和术语:
种群(population) 染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。
适应度(fitness)度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会。
选择(selection) 指决定以一定的概率从种群中选择若干个体的操作。一般而言,选择的过程是一种基于适应度的优胜劣汰的过程。
交叉(crossover) 将群体内的各个个体随机搭配成对,对每个个体以某个概率(交叉概率,交换它们之间的部分染色体,
变异(mutation) 对群体中的每个个体以某一概率(变异概率)改变某一个或某些基因座上的基因值为其它的等位基因。
编码(coding) DNA中遗传信息在一个长链上按一定的模式排列,也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。
解码(decoding) 从遗传子型到表现型的映射。
遗传算法的手工模拟计算示例
(1)个体编码 x1,x2取0~7之间的整数,可分别用3为无符号二进制整数来表示,将它们连接成一起所组成的6位无符号二进制整数就形成个体的基因型,表示一个可行解。如基因型X=101110所对应的表现型是X=[5,6].个体表现型和基因型X之间可通过编码和解码程序相互转换。
(2)初始群体的产生规模取4,随机产生
(3)适应度计算本例目标函数总取非负值,可求函数最大值为最优目标,以此计算个体的适应度。
(4)选择运算
选择方法——适应度比例法(转轮法)
按各染色体适应度大小比例来决定其被选择数目的多少。
某染色体被选的概率:Pc
(5)交叉运算
方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体).
新的子辈染色体: A’ 11010001
B’ 01011110
(6)变异运算
GA的流程
遗传算法的特点
遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算,而遗传算法是一决策变量的某种形式的编码为运算对象。
遗传算法直接以目标函数值作为搜索信息。传统算法不仅需要利用目标函数值,而且往往还需要目标函数的到数值等其它辅助信息。因而遗传算法避开了求导的障碍。
遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往从解空间中的一个初始点开始迭代搜索过程。
遗传算法使用了概率搜索技术这优于传统算法的确定性搜索,因为从一个点到另一个点的确定性有可能使搜索永远达不到最优点
遗传算法的基本实现技术 BY朱诗颖