优化遗传算法大作业

优化设计大作业 遗传算法 院系：机电工程学院 专业：机械设计制造及自动化 年级： 姓名： 学号： 目录 1. 实验目的 1.1 了解并掌握遗传算法的原理，流程和编码策略 1.2 学习 gaot 工具箱和谢菲尔德遗传算法工具箱，并理解其中函数 1.3 自行编制遗传算法程序对简单的函数进行寻优并测试，熟悉遗传算法编程 流程 2. 实验条件 2.1 硬件环境 2.2 软件环境 3. 实验原理 3.1 遗传算法简介 3.2 遗传算法流程 (1)编码 (2)生成初始种群 (3)适应度评估 (4)选择 (5)交叉 (6)变异 4.实验步骤、结果、分析 5.附件：实验程序代码 1.实验目的 1.1 了解并掌握遗传算法的原理，流程和编码策略 1.2 学习 gaot 工具箱和谢菲尔德遗传算法工具箱，并理解其中函数 1.3 自行编制遗传算法程序对简单的函数进行寻优并测试，熟悉遗传算法编程 流程 2.实验条件 2.1 硬件环境： Intel(R) Celeron(R) M CPU 420 1.60GHz 1.5GB 内存 2.2 软件环境 Microsoft Windows XP，MATLAB6.5 ，goat 工具箱 3.实验原理 3.1 遗传算法简介： 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生 物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它 是由美国 Michigan 大学 J.Holland 教授于 1975 年首先提出来的，并出版了颇 有影响的专著Adaptation in Natural and Artificial Systems，GA 这个名称 才逐渐为人所知，J.Hilland 教授所提出的 GA 通常为简单遗传算法（ SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的， 而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每 个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的 主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它 决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的 映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二 进制编码，初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代 （generation）演化 产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness） 大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover ）和变异（ mutation），产生出代表新的 解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适 应于环境，末代种群中的最优个体经过解码（decoding ），可以作为问题近似 最优解。 3.2 遗传算法流程 (1)编码 遗传算法先将解空间的解数据表示成遗传空间的基因型串结构数据，他们 的不同组合就构成了不同的点。 (2)生成初始种群 采用随机的方法产生若干个初始串结构数据，每个串结构数据代表一个个 体，全体初始串结构数据构了初始种群。种群的大小一般是 20100，这样既 可以提高遗传算法的稳定型，又能够保证种群的多样性，容易获得全局最优解。 (3)适应度评估 对于不同的优化问题，采用不同的适应度函数来评价个体的优劣性。通常 有一些常用的带欺骗性的函数用于测试。 (4)选择 按照适者生存的目的，从当前的种群中选择出适应度强的优良个体，使它 们有机会作为父代产生下一代，适应度强的个体被选择的概率大。 (5)交叉 交叉算子根据交叉率将种群中两个个体随机的交换某些基因，从而产生新 一代个体。新个体组合了父辈个体的特性。交叉率根据具体问题确定，一般取 0.250.75，这样既可以得到高适应度的结构，又可以保证搜索效率。 (6)变异 变异算子根据交叉率随机地在当前种群中选择一个个体，对其以一定的概 率随机地改变串结构数据中的某个串的数值，从而产生新一代个体。变异率不 宜取得过高，一般取 0.0050.20。 4. 实验步骤、结果、分析 本文采用函数 为优化函数，取值区间为-1,2。选择二进制编码，种群中 个体数 H 为 40，每个种群的长度为 20，使用代沟为 0.9，最大遗传代数为 25。 使用基于适应度的重插入确保四个最适应的个体总是被连续传播到下一代。这 样，在每一代中有 36(NIND)*(GGAP)个新个体产生。区域描述器 FieldD 描述 染色体的表示和解释，每个格雷码采用 20 位二进制，变量区间为 -1,2。程序 段 Chrom=crtbp(NIND, PRECI)表示一个初始种群 Chrom 被函数 crtbp 创建， 它是由 NIND 个均匀分布、长度为 PRECI 的二进制串构成的。基于排序的适应 度分配计算由程序段 FitnV=ranking(-ObjV)实现。对于这个等级评定算法的缺 省设置是选择等差为 2 和使用线性评估，给最适应个体的适应度值为 2，最差 个体的适应度值为 0，这里的评定方法假设目标函数是最小化的，所以 ObjV 前 加了一个负号，使目标函数最大化。适应度值结果由向量 FitnV 返回。选择层 使用高级函数选择调用低级函数随机遍历抽样例程 sus，SelCh 包含来自原始 染色体的 GGAP*NIND 个个体，这些个体将使用高级函数 recombin 进行重组， recombin 使个体通过 SelCh 被选择再产生，并使用单点交叉例程 xovsp，使用 交叉概率 Px=0.7 执行并交叉。交叉后产生的子代被同一个矩阵 SelCh 返回， 实际使用的交叉例通过支持使用不同函数名字串传递给 recombin 而改变。为 了产生一组子代，变异使用变异函数 mu1.子代再次由矩阵 SelCh 返回，变异 概率缺省值 PM=0.7/Lind=0.0017，这里 Lind 是假定的个体长度。再次使用 bs2rv，将个体的二进制编码转化为十进制编码，计算子代的目标函数值 ObjVSel。由于使用了代沟，子代的数量比当前种群数量要小，因此使用恢复 函数 reins。这里 Chrom 和 SelCh 是矩阵，包含原始种群和子代结果。这两个 事件的第一个被使用单个种群和采用基于适应度的恢复，基于适应度的恢复用 SelCh 中的个体代替 Chrom 中最不适应的个体。原始种群中个体的目标函数值 ObjV 随后又作为函数 reins 的输入参数，子代中个体的目标函数值由 ObjVSel 提供。reins 返回具有插入子代的新种群 Chrom 和该种群中个体的目标函数值 ObjV。每次迭代后的最优解和解的均值放在 trace 中，这个遗传优化的结果包 含在矩阵 ObjV 中。决策变量值为 variable(1)。 下面画出迭代后个体的目标函数值分布图和遗传算法性能跟踪图。遗传算法的 运行结果如下： (1)图 3.1 为目标函数 的图像。 X 图 3.1 目标函数图像 (2)图 3.2 为目标函数图像和初始随机种群个体分布 图 3.1 种群初始分布图 (3)图 3.3 经过 5 次遗传迭代后，寻优结果如图 3.3 所示 图 3.3 经过 5 次遗传迭代后结果 (4)图 3.4 经过 15 次遗传迭代后，寻优结果如图 3.4 所示 图 3.4 经过 15 次遗传迭代后结果 (5)图 3.5 经过 25 次遗传迭代后，寻优结果如图 3.5 所示。此时 x=1.8505， f(x)=3.8503。 图 3.4 经过 15 次遗传迭代后结果 (6)图 3.5 经过 25 次遗传迭代后，最优解的变化和种群均值的变化。 图 3.5 经过 25 次遗传迭代最优解和种群均值的变化 5. 附件：实验程序代码 figure(1); fplot(variable.*sin(10*pi*variable)+2.0,-1,2); %画出函数曲线 %定义遗传算法参数 NIND=40; %个体数目(Number of individuals) MAXGEN=25; %最大遗传代数 (Maximum number of generations) PRECI=20; %变量的二进制位数(Precision of variables) GGAP=0.9; %代沟(Generation gap) trace=zeros(2, MAXGEN); %寻优结果的初始值 FieldD=20;-1;2;1;0;1;1; %区域描述器(Build field descriptor) Chrom=crtbp(NIND, PRECI); %初始种群 gen=0; %代计数器 variable=bs2rv(Chrom, FieldD); %计算初始种群的十进制转换 ObjV=variable.*sin(10*pi*variable)+2.0; %计算目标函数值 while genMAXGEN FitnV=ranking(-ObjV); %分配适应度值(Assign fitness values) SelCh=select(sus, Chrom, FitnV, GGAP); %选择 SelCh=recombin(xovsp, SelCh, 0.7); %重组 SelCh=mut(SelCh); %变异 variable=bs2rv(SelCh, FieldD);%子代个体的十进制转换 ObjVSel=variable.*sin(10*pi*variable)+2.0; %计算子代的目标函数值 Chrom ObjV=reins(Chrom, SelCh, 1, 1, ObjV, ObjVSel); %重插入子代的新种 群 variable=bs2rv(Chrom, FieldD); gen=gen+1; %代计数器增加 %输出最优解及其序号，并在目标函数图像中标出，Y 为最优解,I 为种群的序 号 Y, I=max(ObjV);hold on; plot(variable(I), Y, bo); trace(1, gen)=max(ObjV); %遗传算法性能跟踪 trace(2, gen)=sum(ObjV)/length(ObjV); end variable=bs2rv(Chrom, FieldD); %最优个体的十进制转 hold on, grid; plot(variable,ObjV,b*); figure(2); plot(trace(1,:); hold on; plot(trace(2,:),-.);grid legend(解的变化,种群均值的变化) 遗传算法的优点： 1. 与问题领域无关切快速随机的搜索能力。 2. 搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较， robust. 3. 搜索使用评价函数启发，过程简单 4. 使用概率机制进行迭代，具有随机性。 5. 具有可扩展性，容易与其他算法结合。 遗传算法的缺点： 1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后 还需要对问题进行解码, 2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选 择严重影响解的品质,而目前这些参数的选择大部分是依靠经验. 3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精 确的解需要较多的训练时间。 4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。 5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的 一个研究热点方向。 在现在的工作中，遗传算法（1972 年提出）已经不能很好的解决大规模计算量 问题，它很容易陷入“ 早熟 ”。常用混合遗传算法，合作型协同进化算法等来替 代，这些算法都是 GA 的衍生算法。 遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索 出，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以 方便地进行分布式计算，加快求解速度。但是遗传算法的局部搜索能力较差， 导致单纯的遗传算法比较费时，在进化后期搜索效率较低。在实际应用中，遗 传算法容易产生早熟收敛的问题。采用何种选择方法既要使优良个体得以保留， 又要维持群体的多样性，一直是遗传算法中较难解决的问题。 模拟退火算法虽具有摆脱局部最优解的能力，能够以随机搜索技术从概率的 意义上找出目标函数的全局最小点。但是，由于模拟退火算法对整个搜索空间 的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，使得模拟退火 算法的运算效率不高。模拟退火算法对参数（如初始温度）的依赖性较强，且 进化速度慢。 遗传算法的手工模拟计算示例 例：求下述二元函数的最大值： (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码 为一种符号串。本题中，用无符号二进制整数来表示。 因 x1, x2 为 0 7 之间的整数，所以分别用 3 位无符号二进制整数来 表示，将它 们连接在一起所组成的 6 位无符号二进制数就形成了个体的基因型，表示一个 可行解。 例如，基因型 X101110 所对应的表现型是： x 5，6 。个体的表现型 x 和基因型 X 之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的 初始群体数据。 本例中，群体规模的大小取为 4，即群体由 4 个个体组成，每个个体可通 过随机方法产生。 如：011101 ，101011 ， 011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其 遗传机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可 直接利用目标函数值作为个体的适应度。 (4) 选择运算 选择运算(或称为复制运算) 把当前群体中适应度较高的个体按某种规则或模 型遗传到下一代群体中。一般要求适应度较高