《遗传算法学习笔记》由会员分享，可在线阅读，更多相关《遗传算法学习笔记（19页珍藏版）》请在金锄头文库上搜索。
1、1. 遗传算法基础1.1. 遗传算法定义：自适应全局优化概率搜索算法1.2.遗传操作：选择：根据各个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择一些优良的 个体遗传到下一代群体P(t+1)中。交叉：将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率(交叉概率)，交 互互相之间的部分染色体。变异：对群体P(t)中的每一个个体，以某个概率(变异概率)，改变某一个或某一些基因座上 的基因值为其他的等位基因。1.3.遗传算法主要运算过程：步骤一：初始化。设置进化代数计数器t=0；设置最大进化代数T；随机生成M个个体作为 初始群体 P(0)。步骤二：个体评价。计算群体P(t
2、 )中各个个体的适应度。 步骤三：选择运算。将选择算子作用于群体。 步骤四：交叉运算。将交叉算子作用于群体。步骤五：变异运算。将变异算子作用于群体。得到下一代群体P(t+1)。步骤六：终止条件判断。若tT，则以进化过程中所得到 的具有最大适应度的个体作为最优解输出，终止计算。1.4.特点：遗传算法以决策变量的编码作为运算对象。直接以目标函数值作为搜索信息。 同时使用多个搜索点的搜索信息。 概率搜索技术。2. 基本遗传算法基本遗传算法simple genetic algorithms：只使用选择算子，交叉算子，变异算子2.1. 基本遗传算法构成要素：染色体编码方法：固定长度二进制符号串表示个体个
3、体适应度评价：按照与个体适应度成正比的概率决定当前群体中每个个体遗传到下一代群 体中的机会，适应度为正数或 0。预先设好目标函数到适应度的转换规则。遗传算子：选择使用比例选择算子；交叉使用单点交叉算子；变异使用基本位变异算子或均 匀变异算子。运行参数：M-群体大小，一般20100； T-终止进化代数，一般100500； Pc-交叉概率，一般0.40.99； Pm-变异概率，一般0.00010.12.2. 基本遗传算法描述形式化定义：8元组心“匚厲，皿匚*Q1)个体编码方法；个体适应度评价函数；初始群体；群体大小；选择算子；交叉算子；变异算 子；遗传运算终止条件procedure SGA ini
4、tP(0);t=0;while(t=T) 计算出个体适应度for(int i=0; iM; i+) evaluate fitness of P(t);for(int i=0; iM; i+) select operation of P(t);for(int i=0; iM/2; i+) crossover operation of P(t);for(int i=0; iM; i+) mutation operation of P(t);for(int i=0; iM; i+) P(t+1) = P(t);t+;2.3. 基本遗传算法的实现1. 个体适应度评价： 越大，遗传到下一代概率也越大；
5、越小，遗传到下一代概率也越小； 正数或 0；目标函数f(X)变换为个体适应度F(X)两种方法:(1) 对于求目标函数最大值的优化问题卩(X) +CU, if f (X) +C罰0F * - (,H f (X) + CmiXOCmin为一个适当小的数：预先制定；进化到当前为止的最小目标函数值；当前代或最近几代的最小目标函数值。(2) 对于求目标函数最小值的优化问题Cmax为一个适当地相对比较大的数：预先制定；进化到当前为止的最大目标函数 值；当前代或最近几代的最大目标函数值。2. 比例选择算子：(有退还随机选择，赌盘选择)个体被选中遗传到下一代的概率与该个体适应度大小成正比； 执行过程：(1)
6、计算出所有个体适应度总和；(2) 计算出每一个体相对适应度大小，即各个体被遗传到下一代群体中的概率(3) 0到1随机数，确定各个体被选定的次数；3. 单点交换算子：执行过程：(1) 群体中的个体两两配对，共有I紗对个体组；(2) 对每一对配对个体，随机设置某一基因座之后的位置为交叉点。染色体长度为n, 共有 n-1 个可能的交叉点位置。(3) 对每一对配对个体，依交叉概率Pc在交叉点相互交换两个个体的部分染色体，产 生新的个体。A：1 0 1 1 0 1 1 1 o 0 单点交叉 A 11O11O111U1B：O 0 0 1 1 1 0 0 H 1；O 0011100=00交叉占4. 基本位变
7、异算子： 执行过程：(1) 对个体的每一个基因座，依变异概率Pm指定变异点；(2) 对每一个指定变异点，对其基因位反运算或用其他基因位代替，产生新个体。基本位变异A：1 0 1 o iii 0 1 0 1 0:A“： 1 0 1 0 ioi 0 1 0 1 0变异点5. 遗传算法的应用步骤第一步：确定决策变量及其约束条件，即确定出个体的表现型X和问题解空间。第二步：建立优化模型，即确定出目标函数的类型(最大？最小？)及其数学描述形式和量 化方法。第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜 索空间。第四步：确定解码方法，即确定基因型X到个体表现型X的对应关系或
8、转化方法。第五步：确定个体适应度的量化评价方法，即确定出由目标函数f(X)到个体适应度F(X)的 转换规则。第六步：设计遗传算子，即确定出选择算子，变异算子，交叉算子的具体操作步骤。 第七步：确定遗传算法的有关运行参数， M， T， Pc， Pm。【例】Rosenbrock函数的全局最大值计算。max f (xi 孔)=100 (工：工2尸十(1 X)2举例：遗传算法构造过程：第一步：确定决策变量及其约束条件，即确定出个体的表现型X和问题解空间。 2.048WW2.0481, 2)(2-7)第二步：建立优化模型，即确定出目标函数的类型(最大？最小？)及其数学描述形式和量 化方法。第三步：确定表
9、示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜 索空间。用长度10位的二进制编码串表示xl,x2,1024个数表示-2.048到2.048共4096个离散点。 例如：基因型 X： 0000110111 1101110001第四步：确定解码方法，即确定基因型X到个体表现型X的对应关系或转化方法。将代码yi转换为xi的解码公式:= 4.096 x1023-2.048（；=1, 2）x1=4.096*55/1023-2.048=-1.818; x2=4.096*881/1023-2.048=1.476个体表现型X-1.818, 1.476第五步：确定个体适应度的量化评价方法，即确定
10、出由目标函数f(X)到个体适应度F(X)的 转换规则。maxf J1，乂2)=100帀)？十(1 列)2目标函数不为负， F(X)=f(x1,x2)第六步：设计遗传算子，即确定出选择算子，变异算子，交叉算子的具体操作步骤。比例选择算子，单点交叉算子，基本位变异算子 第七步：确定遗传算法的有关运行参数， M， T， Pc， Pm。M=80；T=200；Pc=0.6；Pm=0.0013. 遗传算法的基本实现技术3.1.编码方法遗传算法对个体编码实施选择，交叉，变异，不断搜索出适应度较高的个体，并在群体 中增加其数量，最终寻求近似最优解。把一个问题可行解从其解空间转换到遗传算法所能处理的搜索空间的转
11、换方法就叫编 码。首要问题，关键步骤编码方法很大程度上决定如何进行群体的遗传进化运算以及遗传进化运算的效率。 好的编码方法，使得交叉，变异运算简单的实现和执行。差的编码方法，使得交叉，变异运算难以实现，产生无效解。影响效率。编码原则一：有意义积木块编码原则；应使用能易于产生与所求问题相关的且具有低阶 短定义长度模式的编码方案。模式；指具有某些基因相似性的个体的集合。使用易于生成适应度较高的个体的编码方 案。编码原则二：最小字符集编码原则：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。进制编码方法某一参数的取值范围Umin,Umax,用长度1的二进制编码符号串表示该参数，产生2
12、1 不同编码。编码精度：-1解码公式：工=U min +（若妇2一）；： 丁罰优点：编解码简单易行；交叉变异等遗传操作便于实现；符合最小字符集编码规则；便于利用模式定理对算法进行理论分析格雷码编码方法二进制编码为：BKs i厂山格雷编码为： 只品松i HSm *二进制码到格雷码转换公式：gi =b讥 I = m 1, m -2,，1格雷码到二进制码转换公式：a b r+“中I，小 二、 遗传算法中使用格雷码进行个体编码的主要原因：任意两个整数的差，是对应格雷码的 海明距离。遗传算法局部搜索能力不强，因为：新一代群体的产生主要是依靠上一代群体之间的随 机交叉重组来完成。对于变异操作，个体基因型X
13、的微小差异，产生个体表现型X的 相差较大。格雷码不会。优点：提高遗传算法的局部搜索能力；交叉变异等遗传操作便于实现；符合最小字符集 编码原则；便于利用模式定理对算法进行理论分析。浮点数编码方法二进制编码存在连续函数离散化时的映射误差；不便于反应所求问题的特定知识。每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个 数。优点：表示范围较大的数；适合精度较高的遗传算法；便于较大空间的遗传搜索；改善遗传算法计算复杂性；符号编码方法基因值取自一个无数值含义，而只有代码含义的符号集。 优点：符合有意义积木块编码原则；便于在遗传算法中利用所求解问题的专门知识；便 于遗传算法和相关近
14、似算法的混合使用。多参数级联编码方法将各个参数分别以某种编码方法进行编码，按一定顺序连接在一起，组成了表示全部参数的个体编码。每个参数编码方式可以不同，上下界可以不同，编码长度精度可以不同。多参数交叉编码方法将各参数中起主要作用的码位集中在一起，不易被遗传算子破坏掉。参数编码:bxbbnbf。21幻22302罚九1以2宀3小222仏23&23叽?* :叭訪2税叽协级联:适合于各参数之间的相互关系较弱，特别是某一个或少数几个参数起主要作用时 的优化问题。交叉：适合于各参数之间的相互关系较强，各参数对最优解的贡献相当时的优化问题。3.2.适应度函数遗传算法中，群体的进化过程就是以群体中各个个体的适
15、应度为依据，通过反复迭代 不断寻求出适应度较大的个体，最终得到最优解或次优解。目标函数和适应度函数(1) 求最大值：(2) 求最小值：适应度尺度变换：各个个体被遗传到下一代群体中的概率由该个体的适应度来确定。为了克服遗传算法中出现早熟现象(早起收敛)，希望在遗传算法运行的初期阶段， 对适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度， 限制其复制数量，维护群体多样性。为了克服算法运行后期阶段因为个体平均适应度和最佳适应度相近而导致的竞争力 不强的问题，算法对适应度适当放大，扩大个体最佳适应度与其他个体适应度之间 的差异程度，提高个体间的竞争性。定义：在遗传算法运行的不同阶段，对个体的适应度进行适当的扩大或缩小，称为 适应度尺度变换。 线性尺度变换:F二材卜
