数学建模常用智能算法及其Matlab实现资料课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,*,2024/11/21,1,数学建模常用智能算法 及其,Matlab,实现,负 责 人：,胡 丹,成 员：,袁莉莉 王 霖 侯金灵 马婷,指导教师,:,周 长 礼,2023/9/131数学建模常用智能算法 及其Matla,2024/11/21,2,引言,在管理科学、计算机科学、分子物理学和生物以及超大规模集成电路设计等科技领域中，存在着大量的组合优化问题，其中的,NP,完全问题，其求解时间随问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸的,。,城市,24,25,26,27,28,29,30,31,计算时间,1s,24s,10m,4.3h,4.9d,136d,10.8a,325a,2023/9/132引言在管理科学、计算机科学、分子物理学和,2024/11/21,3,为此我们引入现今流行的智能算法，如遗传算法，模拟退火算法，禁忌搜索算法，蚁群算法，和粒子群算法等。,我们前期所做的主要工作是参考了一些相关书目，组织了讨论小组，对相关的算法进行了研究，并利用这些智能算法解决了,TSP,问题，下面我们就这些智能算法进行详细介绍。,2023/9/133,2024/11/21,4,遗传算法是在,70,年代初期由美国密执根大学的,Holland,教授发展起来的。,1975,年，,Holland,发表了第一批比较系统论述遗传算法的专著,自然系统和人工系统的自适应,（,Adaptation in Natural and Artificial Systems,）。遗传算法主要借用生物进化中“适者生存”的规律揭示了大自然生物进化过程中的一个规律：最适合生存的个体往往产生了更大的后代群体。,2023/9/134遗传算法是在70年代初期由美国密执根大学,2024/11/21,5,蚁群算法是由意大利学者,A,，,Dofigo,，,M,，,Maniezzo,等人于,1992,年通过模拟自然界中蚂蚁集体寻食的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性,但搜索时间长且易限入局部最优解是其突出的缺点。,A C O,算法由一群简单的人工蚂蚁通过人工信息素,(,即一种分布式的数字信息,人工蚂蚁利用该信息和问题相关的启发式信息逐步构造问题的解，相当于真实蚁群的外激素，简称信息素,),进行间接通讯，相互协作，从而求出问题的最优解。,2023/9/135蚁群算法是由意大利学者A，Dofigo，,2024/11/21,6,禁忌搜索（,Tabu Search,简称,TS,）的思想最早由,FredGlover(1986),提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，禁忌搜索算法在局部搜索过程中，使用一个“记忆”装置，即禁忌表，驱使算法禁忌重复相同的搜索步骤，转而搜索解空间的新区域，以逃离局部最优。,2023/9/136禁忌搜索（Tabu Search 简称,2024/11/21,7,粒子群算法（,Particle Swarm Optimization,PSO,）最早是由,Eberhart,和,Kennedy,于,1995,年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景,:,一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远则找到食物的最优策略最简单有效的就是搜寻目前离食物最近的鸟的周围区域。,2023/9/137粒子群算法（Particle Swar,2024/11/21,8,模拟退火算法是,1982,年,KirkPatrick,将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对,NP,完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度加到很高,再缓慢降温,(,即退火,),，使达到能量最低点。如果急速降温,(,即为淬火,),则不能达到最低点,。,2023/9/138模拟退火算法是1982年KirkPatr,2024/11/21,9,TSP,问题综述,旅行商问题是一个典型的,NP,完全问题。它可简单地描述为：对于,n,个城市，它们之间的距离已知,一旅行商要从某一城市出发走遍所有的城市，且一个城市只能经过一次,最后回到出发城市，问如何选择路线可使所走过的路程最短。,2023/9/139TSP问题综述旅行商问题是一个典型的NP,2024/11/21,10,建立,TSP,问题的数学模型如下：,2023/9/1310建立TSP问题的数学模型如下：,2024/11/21,11,遗传算法的原理,遗传算法通过模拟生物学的自然选择和自然遗传机制模拟生命进化的原理来寻求问题的最优解，它的基本思想是：把问题的解表示成“染色体”，在执行遗传算法之前，随机地给出一群初始“染色体”,(,种群,),即假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样，经过一代一代的进化，最后收敛到最适应环境的一个“染色体”上，它就是问题的最优解。,2023/9/1311遗传算法的原理 遗传算法通过模拟,2024/11/21,12,遗传算法的描述,Step 1,初始化种群规模,size,、交叉概率,Pc,、变异概率,Pm,和迭代次数,t,。,Step 2,随机产生初始种群；计算初始种群的适应度。,Step 3,根据一定的选择策略选择父体,1,和父体,2,。,Step 4,产生一个,0,1,随机数。,Step 5,判断,P1Pc,是否成立，如果成立，把父体,1,和父体,2,按一定交叉方法生成子个体,1,和子个体,2,；否则把父体,1,和父体,2,作为新的子个体,1,和子个体,2,。,2023/9/1312遗传算法的描述Step 1 初始化种,2024/11/21,13,Step 6,判断,P2Pm,，如果成立把子个体,1,和子个体,2,按一定变异方法变异。,Step 7,判断产生子个体数是否等于种群规模，如,果是则转向,Step8,；否则转向,Step3,。,Step 8,评估种群的适应度；新产生的子代成为,父代。,Step 9,判断是否满足终止条件，如果满足则终止；否,则转向,Step 3,2023/9/1313,2024/11/21,14,遗传算法流程图,2023/9/1314遗传算法流程图,2024/11/21,15,遗传算法的优点与缺陷,遗传算法简单、易于实现，能够并行化，具有强鲁棒性和全局搜索能力。遗传算法与其他启发式算法有较好的兼容性，可以用其他的算法求初始解。,缺点则表现为早熟现象、局部寻优能力较差等。所以，一些常规遗传算法并不一定是针对某一问题的最佳求解。,2023/9/1315遗传算法的优点与缺陷遗传算法简单、易于,2024/11/21,16,禁忌搜索算法,禁忌搜索算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征，是局部搜索算法的一种推广，它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证多样化的有效探索，以最终实现全局优化。,2023/9/1316禁忌搜索算法禁忌搜索算法是一种全局性邻,2024/11/21,17,禁忌搜索算法主要过程,Step l,算法初始化，设置参数，包括城市数目、禁忌长度、候选集长度和最大迭代步数等,Step 2,生成初始解，作为迭代搜索的起点,Step 3,根据上述初始解，按照一定规则生成邻域，并在邻域中选取元素生成候选集。,Step 4,由于邻域的相互性，将已经搜过的解进行禁忌，避免迂回搜索，以跳出局部最优,2023/9/1317禁忌搜索算法主要过程Step l,2024/11/21,18,Step 5,从候选集中选出未被禁忌表禁忌的当前局部最优解，若此解优于当前解，则用其替换当前解，成为最优解,Step 6,更新禁忌表（增添新的禁忌解或 根据解禁准则，对满足条件的解进行解禁）,Step 7,判断是否满足终止条件,(,设为限定最大迭代步数，或满足所要求精度,),，若满足，则输出最优解，终止算法；若不满足，则将当前局部最优解作为下次迭代的起点，转,Step 3,各种优化算法解决,TSP,问题,2023/9/1318Step 5 从候选集中选出未被禁,2024/11/21,19,禁忌搜索算法优点,从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。,选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局最优性。,终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率限制或者目标值偏离程度为终止规则。,2023/9/1319禁忌搜索算法优点 从移动规则看，每次,2024/11/21,20,蚁群算法,蚁群算法是通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性。它由一群简单的人工蚂蚁通过人工信息素进行间接通讯，相互协作，从而求出问题的最优解。,2023/9/1320蚁群算法 蚁群算法是通过模拟自然,2024/11/21,21,蚁群算法描述,Step 1,初始每条路径上的信息激素浓度相等。,Step 2,把,m,只蚂蚁随机地放置在,n,个城市上,并把已访问的城市写入禁忌表。,Step 3,如果第,k(k=1,2,m),只蚂蚁还有未访问的城市,则该只蚂蚁根据决策 选择下一个城市,(i,是该蚂蚁当前所在城市，,j(N-,禁忌表,),是一个由城市,i,到城市,j,之间的路径长度和信息激素浓度构成的函数,),把选择的城市,j,写入禁忌表，直到所有的城市访问完。,2023/9/1321蚁群算法描述 Step 1 初始每条,2024/11/21,22,Step 4,计算,k(k=1,2,m),条路径的路径长度，选出本次最优路径。,Step 5,根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度，清空禁忌表。,Step 6,判断是否满足结束条件,如果不满足，转到,Step 2,；否则结束。,下图为流程图,2023/9/1322Step 4 计算 k(k=1,2,2024/11/21,23,2023/9/1323,2024/11/21,24,蚁群算法的主要特点,(1),分布式计算、正反馈机制和贪婪式搜索相结合；,(2),具有很强的并行性；,(3),更好的可扩充性；,(4),概率型的通用全局优化方法；,(5),不依赖于优化本身的严格数学性质，诸如连续性、可导性；,各种优化算法解决,TSP,问题,2023/9/1324蚁群算法的主要特点(1)分布式计算、,2024/11/21,25,粒子群算法,PSO,算法是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子,(,点,),，这些粒子在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。,PSO,算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。,2023/9/1325粒子群算法 PSO算法,2024/11/21,26,粒子群算法的数学描述,在,D,维的搜索空间中，有随机分布的,m,个粒子组成的一个初始粒子群，每个粒子有各自的位置和速度。如第,i,个粒子的位置表示为一个,D,维的向量,速度也是一个,D,维的向量，记为 。每个粒子记住自己在迭代过程中找到的最优位置，记为 ，整个粒子群迄今为止搜索到的最优位置为全局最优解记 。,这样的寻优为局部,PSO,算法，经过一定的迭