《数学建模专题之遗传算法》由会员分享，可在线阅读，更多相关《数学建模专题之遗传算法（100页珍藏版）》请在金锄头文库上搜索。
1、数学建模专题之 遗传算法v 重庆理工大学v 主讲：肖汉光v Email:数学建模专题之遗传算法 Contents遗传算法概述1标准遗传算法2遗传算法简单举例：函数极值3遗传算法优化神经网络5遗传算法求解TSP问题4遗传算法的实现6数学建模专题之遗传算法 Contents of Section 11.4什么是遗传算法1.11.21.3遗传算法的特点遗传算法的发展历程遗传算法的研究和应用领域1 遗传算法概述数学建模专题之遗传算法 1 遗传算法概述1.1 遗传算法（Genetic Algorithm, GA） 一种仿生全局优化算法 模仿生物的遗传进化原理（Darwins theory of evol
2、ution xmax=1.8506;f(xmax)=3.8503;数学建模专题之遗传算法v 模拟结果进化的过程：世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503数学建模专题之遗传算法v考虑问题：能否用遗传算法解决以下问题1、2、3、数学建模专题之遗传算法 Contents of Section 4巡回旅行商问题4.14.24.3基本操作计算仿真结果4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法 4
3、 遗传算法求解巡回旅行商问题4.1 巡回旅行商问题City5City1 City2City3City4巡回旅行商问题（Traveling salesman problem, TSP）可描述如下 ：已知N个城市之间的相互距离，现有一推销员必须遍历这N个城市，并 且每个城市只能访问一次，最后又必须返回出发城市，如何安排他访问 这些城市的次序，使其旅行路线总长度最短？ 数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题CHN31问题60 Cities数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题TSP具有广泛的应用背景和重要理论价值 ，特别在机器人运动规划中得到许多应用，例 如：移动机器
4、人的全局路径规划问题（如右上 图）、焊接机器人的任务规划问题（如右下图 ）等等。但是，巡回旅行商问题中可能的路径数目 与城市数目N呈指数型增长，所有的旅程路线 组合数为其已经被证明属于NP难题。例如30个城 市的路线对应约有对庞大的搜索空间寻求最优解，常规方 法和现有的计算工具存在着诸多的计算 困难。 数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题序号X坐标Y坐标序号X坐标Y坐标序号X坐标Y坐标 118541171442176428776126460222260374781368582325624717114836924623252538155869258776583516546226
5、91387450175167278346813401837842841269184019419429452110244220299304435本例所用30个城市的XY坐标：数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题4.2 基本操作 （1）编码与解码采用对访问城市序列进行排列组合的方法编码，即某个巡回路径的 染色体是该巡回路径的城市序列。对于N（N为城市总数）进制编码， 即每个基因仅从1到N得整数里面取一个值，每个个体的长度为N。根据编码方法，一次求解得出的最优解（个体）是所访问的城市的 次序，需要转换成相应的城市坐标进行输出，则只需将个体的染色体值 作为存储30个城市坐标的矩阵的下
6、标来引用，输出对应的矩阵元素，便 可实现解码。一行的前30个元素 为一个个体30个城市的 访问次序该种访问次序 路径的距离利用矩阵 来存储：数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题（2）适应度函数：在TSP问题中，用路径的总长度作为适应度函数来衡 量求解结果是否最优，路径越短对应的个体越优，其适应度值应 越大。 两城市间的距离为： 个体代表的路径的总长度为： 则可采用倒数法将适应度函数取为： （3）选择操作：将群体中适应度较大的C个个体直接替换适应度较小的 C个个体。其中C值与选择算子和群体规模的关系在这里取为：数学建模专题之遗传算法A1：（ 3 4 5 6 ） 第一步：保留交叉
7、点的中间部分第二步：交换对应位置的子串A2：（ 0 8 5 3 ） A2：（4 2 90 8 5 31 7 6）A1：（0 1 23 4 5 67 8 9）291 7974 遗传算法求解巡回旅行商问题本例中采用有序交叉执行交叉操作。有序交叉能够有效地继承双 亲的部分基因成分，达到了进化的遗传功能，使该遗传算法并不盲目 搜索，二是趋向于使群体具有更多的优良基因。交叉后，考察父个体 与子个体的适应度来决定是否更新种群。具体操作过程如下（以09 编码为例）：（4）交叉操作 父个体：（“|”表示交叉点） 301 248664数学建模专题之遗传算法变异后子代个体：5 6 7 | 8 4 1 2 | 3
8、9 04 遗传算法求解巡回旅行商问题变异操作中，若变异后子代的适应度值更加优异，则保留子代染 色体，否则仍保留父代染色体。本例中，采用倒置变异法。例如：假 设当前个体为“5678412390”，如果当前随机值p0，1pmutation，则 随机选择来自同一个体的两个点（设为“8”和“2” ），执行变异操作， 即倒置该两点的中间部分。产生的新个体为“5672148390”。 （5）变异操作 （6）群体初始化2变异前父代个体：5 6 7 | | 3 9 0148pop=zeros(s,t); for i=1:s pop(i,1:t-1)=randperm(t-1); end数学建模专题之遗传算法
9、4 遗传算法求解巡回旅行商问题4.3 计算仿真结果990.0829 路径长度：迁移代数：50数学建模专题之遗传算法 4遗传算法求解巡回旅行商问题4.3 计算仿真结果701.7754 路径长度：迁移代数：100数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题4.3 计算仿真结果624.1821 路径长度：迁移代数：150数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题4.3 计算仿真结果523.2674 路径长度：迁移代数：200数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题4.3 计算仿真结果491.4063 路径长度：迁移代数：250数学建模专题之遗传算法 4 遗传算法求
10、解巡回旅行商问题4.3 计算仿真结果453.1959路径长度：迁移代数：300数学建模专题之遗传算法 4 遗传算法求解巡回旅行商问题4.3 计算仿真结果430.3986 路径长度：迁移代数：350数学建模专题之遗传算法4.3 计算仿真结果424.8693 路径长度：迁移代数：400Best4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法距离为426.64Km 的访问次序距离为424.78Km的 访问次序（最优）距离为431.94Km 的访问次序4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法距离为424.78Km的 访问次序（最优）距离为466.30Km 的访问次序距离为454.75K
11、m 的访问次序4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法4.4 关于遗传算法操作算子的验证4 遗传算法求解巡回旅行商问题“实验数据 ”课程所做 的正交试 验极差分 析结果（ 迁移500代 后退出的 结果）。数学建模专题之遗传算法对于上表，有（验证）以下基本结论： （1）遗传算法搜索求解能力与四个因素有关：群体规模、选 择算子、交叉率和变异率 。 （2）从主到次依次为：交叉率群体规模选择算子 变异率。 （3）A3-B2-C1-D3是优选方案。4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法左图（进行50次独 立运算求解，每次 迁移1000代，有36 次能收敛到全局最 优解）是比较优
12、的 参数组合。实际上 可看出，迭代进行 到450代之后，所 得到得最优个体基 本不再发生变化， 且其最优路径与真 实的最有路径差距 非常小。4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法左图（进行50次 独立运算求解， 每次迁移1000代 ，有24次能收敛 到全局最优解） 表明：选择算子 取值太大，收敛 速度很快，但陷 入局部最优解的 可能性大大提高 ，而基本上不可 能再跳出来。约350代 便收敛4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法左图（进行50次 独立运算求解， 每次迭代1000代 ，仅有6次能收 敛到全局最优解 ）表明：交叉率 选取太大，导致 群体中的优良模 式遭到破
13、坏，产 生较大的代沟， 从而使搜索走向 随机化。450Km 左右4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法左图（进行50次 独立运算求解， 每次迁移1000代 ，有18次能收敛 到全局最优解） 表明：变异率选 取太大，遗传算 法几乎退化为随 机搜索，陷入局 部最优解后比较 难跳出来。约380代 左右4 遗传算法求解巡回旅行商问题数学建模专题之遗传算法*79uGA优优化NN的权权重（结结构确定）uGA优优化NN的结结构：神经经元数和连连接 状况x1输出层隐藏层输入层x2yxnw1wiwn5遗传算法优化神经网络数学建模专题之遗传算法*80n 编码（实数编码)1、GA优化NN的权重数学建模
14、专题之遗传算法*81v定义义适应应度 直接采用方差和. 评估过程：对每个解进行样本测试（前 向计算），计算其实际输出和期望输出 的误差（适应度）。如果有一个个体的 适应度满足精度要求，则结束1、GA优化NN的权重数学建模专题之遗传算法*82n遗传操作：交叉1、GA优化NN的权重数学建模专题之遗传算法*831、GA优化NN的权重n遗传操作：变异数学建模专题之遗传算法*841、GA优化NN的权重数学建模专题之遗传算法*85nBP算法和GA算法结结合GA擅长长全局优优化搜索，BP擅长长局部优优化 搜索；两者结结合，可提高收敛敛速度。克服 GA过过早收敛敛的问题问题1、GA优化NN的权重数学建模专题之
15、遗传算法*86先用GA找出全局最优优解的大概位置，然后采用BP 算法微调调得到全局最优优解。1、GA优化NN的权重nBP算法和GA算法结结合：方法一GA+BPGA转换点数学建模专题之遗传算法*871、GA优化NN的权重nBP算法和GA算法结结合：方法二交替使用BP和GA第一步:利用GA找出一个最优优解；第二步：利用BP对该对该 最优优解进进行微调调；第三步：如果发现发现 微调调后的最优优解不够够理想，则则返回第一步；否则则停 止。数学建模专题之遗传算法*88v 算法：1.随机产产生一个具有N个个体的初始群体；2.计计算每个个体的适应值应值 ，如果有一个个体的适应应度 满满足精度要求，则结则结
16、束，否则进则进 行下一步；3.按适应应度比例挑选选出父本群体；4.对对父本群体进进行杂杂交、变变异操作得到新的群体；5.找出当前群体中适应应度最大的个体best；6.对对best用BP进进行一到二次学习习，得best；7.用best替代best，转转向2；1、GA优化NN的权重数学建模专题之遗传算法*89v编码编码vNN的连连接拓扑可以用一个连连接矩阵阵 表示矩阵阵中的每个元素若为为0，则则表示相 应应的神经经元之间间无连连接；若为为1，表 示有连连接。v 按行排列形成一个染色体2、GA优化NN的结构数学建模专题之遗传算法*902、GA优化NN的结构数学建模专题之遗传算法*91n评估和遗传操作2、GA优化NN的结构数学建模专题之遗传算法*92思考题1、能否利用GA同时优 化NN的结构和 参数？数学建模专题之遗传算法 6 遗传算法的实现vMatlab的GA工具箱vMatlab的G
