《数学建模常用智能算法及其Matlab实现资料课件.ppt》由会员分享，可在线阅读，更多相关《数学建模常用智能算法及其Matlab实现资料课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、2023/3/10,1,数学建模常用智能算法 及其Matlab实现,负 责 人：胡 丹 成 员：袁莉莉 王 霖 侯金灵 马婷 指导教师:周 长 礼,2023/3/10,2,引言,在管理科学、计算机科学、分子物理学和生物以及超大规模集成电路设计等科技领域中，存在着大量的组合优化问题，其中的NP完全问题，其求解时间随问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸的。,2023/3/10,3,为此我们引入现今流行的智能算法，如遗传算法，模拟退火算法，禁忌搜索算法，蚁群算法，和粒子群算法等。我们前期所做的主要工
2、作是参考了一些相关书目，组织了讨论小组，对相关的算法进行了研究，并利用这些智能算法解决了TSP问题，下面我们就这些智能算法进行详细介绍。,2023/3/10,4,遗传算法是在70年代初期由美国密执根大学的Holland教授发展起来的。1975年，Holland发表了第一批比较系统论述遗传算法的专著自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems）。遗传算法主要借用生物进化中“适者生存”的规律揭示了大自然生物进化过程中的一个规律：最适合生存的个体往往产生了更大的后代群体。,2023/3/10,5,蚁群算法是由意大利学者A，Dof
3、igo，M，Maniezzo 等人于1992 年通过模拟自然界中蚂蚁集体寻食的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性,但搜索时间长且易限入局部最优解是其突出的缺点。A C O 算法由一群简单的人工蚂蚁通过人工信息素(即一种分布式的数字信息,人工蚂蚁利用该信息和问题相关的启发式信息逐步构造问题的解，相当于真实蚁群的外激素，简称信息素)进行间接通讯，相互协作，从而求出问题的最优解。,2023/3/10,6,禁忌搜索（Tabu Search 简称TS）的思想最早由FredGlover(1986)提出，它是对局部邻域搜索的一种扩展，是
4、一种全局逐步寻优算法，禁忌搜索算法在局部搜索过程中，使用一个“记忆”装置，即禁忌表，驱使算法禁忌重复相同的搜索步骤，转而搜索解空间的新区域，以逃离局部最优。,2023/3/10,7,粒子群算法（Particle Swarm Optimization,PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远则找到食物的最优策略最简单有效的就是搜寻目前离食物最近的鸟的周围区域。,2023/3/10,8,模拟退火算法是198
5、2年KirkPatrick将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度加到很高,再缓慢降温(即退火)，使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。,2023/3/10,9,TSP问题综述,旅行商问题是一个典型的NP完全问题。它可简单地描述为：对于n个城市，它们之间的距离已知,一旅行商要从某一城市出发走遍所有的城市，且一个城市只能经过一次,最后回到出发城市，问如何选择路线可使所走过的路程最短。,2023/3/10,10,建立TSP问题的数学模型如下：,2023/3/10,11,遗传算法的原理,遗传
6、算法通过模拟生物学的自然选择和自然遗传机制模拟生命进化的原理来寻求问题的最优解，它的基本思想是：把问题的解表示成“染色体”，在执行遗传算法之前，随机地给出一群初始“染色体”(种群)即假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样，经过一代一代的进化，最后收敛到最适应环境的一个“染色体”上，它就是问题的最优解。,2023/3/10,12,遗传算法的描述,Step 1 初始化种群规模size、交叉概率Pc、变异概率Pm和迭代次数t。Step 2 随机产生初始种群；计算初始种群的适
7、应度。Step 3 根据一定的选择策略选择父体1和父体2。Step 4 产生一个01随机数。Step 5 判断P1Pc是否成立，如果成立，把父体1和父体2按一定交叉方法生成子个体1和子个体2；否则把父体1和父体2作为新的子个体1和子个体2。,2023/3/10,13,Step 6 判断P2Pm，如果成立把子个体1和子个体2按一定变异方法变异。Step 7 判断产生子个体数是否等于种群规模，如 果是则转向Step8；否则转向Step3。Step 8 评估种群的适应度；新产生的子代成为 父代。Step 9 判断是否满足终止条件，如果满足则终止；否 则转向Step 3,2023/3/10,14,遗传
8、算法流程图,2023/3/10,15,遗传算法的优点与缺陷,遗传算法简单、易于实现，能够并行化，具有强鲁棒性和全局搜索能力。遗传算法与其他启发式算法有较好的兼容性，可以用其他的算法求初始解。缺点则表现为早熟现象、局部寻优能力较差等。所以，一些常规遗传算法并不一定是针对某一问题的最佳求解。,2023/3/10,16,禁忌搜索算法,禁忌搜索算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征，是局部搜索算法的一种推广，它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证多样化的有效探索，以最终实现全局优化。,2023/3/10,17,禁忌
9、搜索算法主要过程,Step l 算法初始化，设置参数，包括城市数目、禁忌长度、候选集长度和最大迭代步数等Step 2 生成初始解，作为迭代搜索的起点 Step 3 根据上述初始解，按照一定规则生成邻域，并在邻域中选取元素生成候选集。Step 4 由于邻域的相互性，将已经搜过的解进行禁忌，避免迂回搜索，以跳出局部最优,2023/3/10,18,Step 5 从候选集中选出未被禁忌表禁忌的当前局部最优解，若此解优于当前解，则用其替换当前解，成为最优解Step 6 更新禁忌表（增添新的禁忌解或 根据解禁准则，对满足条件的解进行解禁）Step 7 判断是否满足终止条件(设为限定最大迭代步数，或满足所要
10、求精度)，若满足，则输出最优解，终止算法；若不满足，则将当前局部最优解作为下次迭代的起点，转Step 3各种优化算法解决TSP问题,2023/3/10,19,禁忌搜索算法优点,从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局最优性。终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率限制或者目标值偏离程度为终止规则。,2023/3/10,20,蚁群算法,蚁群算法是通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强
11、的鲁棒性。它由一群简单的人工蚂蚁通过人工信息素进行间接通讯，相互协作，从而求出问题的最优解。,2023/3/10,21,蚁群算法描述,Step 1 初始每条路径上的信息激素浓度相等。Step 2 把m只蚂蚁随机地放置在n个城市上,并把已访问的城市写入禁忌表。Step 3 如果第 k(k=1,2,m)只蚂蚁还有未访问的城市,则该只蚂蚁根据决策 选择下一个城市(i是该蚂蚁当前所在城市，j(N-禁忌表),是一个由城市i 到城市 j 之间的路径长度和信息激素浓度构成的函数),把选择的城市j 写入禁忌表，直到所有的城市访问完。,2023/3/10,22,Step 4 计算 k(k=1,2,m)条路径的路
12、径长度，选出本次最优路径。Step 5 根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度，清空禁忌表。Step 6 判断是否满足结束条件,如果不满足，转到Step 2；否则结束。下图为流程图,2023/3/10,23,2023/3/10,24,蚁群算法的主要特点,(1)分布式计算、正反馈机制和贪婪式搜索相结合；(2)具有很强的并行性；(3)更好的可扩充性；(4)概率型的通用全局优化方法；(5)不依赖于优化本身的严格数学性质，诸如连续性、可导性；各种优化算法解决TSP问题,2023/3/10,25,粒子群算法,PSO算法是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子(点)，这些
13、粒子在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。PSO算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。,2023/3/10,26,粒子群算法的数学描述 在D维的搜索空间中，有随机分布的m个粒子组成的一个初始粒子群，每个粒子有各自的位置和速度。如第i个粒子的位置表示为一个D维的向量,速度也是一个D 维的向量，记为。每个粒子记住自己在迭代过程中找到的最优位置，记为，整个粒子
14、群迄今为止搜索到的最优位置为全局最优解记。这样的寻优为局部PSO算法，经过一定的迭代后，改用全局最优解，即全局PSO算法进行迭代以加快收敛。,2023/3/10,27,可用下面的公式来表示粒子每轮的更新行为：(2.1)(2.2)其中 为粒子速度，为粒子位置，C1，C2称为学习因子或加速常量，通常在 间取值，C1为调节粒子飞向自身最好位置的步长,C2 为调节粒子向全局最好位置飞行步长；r1，r2 是（0，1）区间内两个随机正数，为个体意识（个体最佳解位置），为群体最佳解位置.为惯性权重，使粒子保持运动惯性，控制前一速度对当前速度的影响;t 为飞行的次数。,2023/3/10,28,粒子群算法的流
15、程如下：Step l：初始化，设定加速常数C1和C2，最大进化代数 将当前进化代数置为 t=1，在定义空间 中随机产生m个粒子X1,X2,Xm，组成初始种群X(t),随机产生各粒子初速度V1，V2,VS组成位移变化矩阵V(t)。Step 2：计算种群中所有粒子的适应值，初始化每粒子pbest为当前粒子，设定种群的gbest为当前种群的最优粒子。,2023/3/10,29,Step 3：种群x(t)演化，对种群中的每一个粒子：(1)按(2.1),(2.2)式更新粒子的位置和速度。(2)计算粒子的适应值。(3)比较粒子的适应值和自身的最优值pbest。如果当前值比pbest更优，则更新pbest为
16、当前值，并更新pbest位置到n维空间中的当前位置。(4)比较粒子适应值与种群最优值。如果当前值比gbest更优，则更新gbest为当前种群最优粒子。Step 4：检查结束条件，若满足，则结束寻优；否则，t=t+1，转至Step 2.。结束条件为寻优达到最大进化代数，或评价值小于给定精度。,2023/3/10,30,模拟退火算法,模拟退火算法是80年代发展起来的一种用于求解大规模优化问题的随机搜索算法，它以优化问题求解过程与物理系统退火过程之间的相似性为基础；优化的目标函数相当于金属的内能；优化问题的自变量组合状态空间相当于金属的内能状态空间；问题的求解过程就是找一个组合状态，使目标函数值最小
17、。利用Metropolis准则并适当地控制温度的下降过程实现模拟退火，从而达到在多项式时间内求解全局优化问题的目标。,2023/3/10,31,模拟退火算法描述,Step 1 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L step 2 对k=1，L做第(3)至第6步：step 3 产生新解S Step 4 计算增量t=C(S)-C(S)，其中C(S)为评价函数,2023/3/10,32,Step 5 若t0，然后转第2步。,2023/3/10,33,模拟退火算法的优缺点：,与以往的近似算法相比,模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较
18、少受到初始条件约束等优点。,2023/3/10,34,各种算法应用TSP问题及结果分析,我们将各种智能算法应用于解决TSP问题，下面我们以30个城市的TSP问题为例进行结果分析下表为30个城市的TSP仿真结果，其中30个城市的坐标如下：x,y=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50,20
19、23/3/10,35,实验环境：MATLAB 7.0 实验方法：在算法中设置计数器，当解转移迭 代次数达到计数器规定的值时，无须考虑算法的终止条件即刻终止算法观察实验结果，实验结果统计。设置算法参数：遗传算法中初始种群的大小为100，交叉概率为0.8。变异概率为0.1。在蚁群算法中信息素重要程度的参数,启发式因子重要程度的参数,信息素蒸发系数,信息素增加强度系数.禁忌算法中禁忌长度为150，保留前100个最好候选解。,2023/3/10,36,图3.1 30个城市坐标位置图,2023/3/10,37,2023/3/10,38,以下是上述四种算法最好解的结果图示遗传算法的最好解的路径和搜索过程如下图所示：,2023/3/10,39,蚁群算法的最好解的路径和搜索过程如下图所示：,2023/3/10,40,禁忌搜索算法最好解的路径和搜索过程如下所示：,2023/3/10,41,模拟退火算法最好解的路径和搜索过程如下图所示：,2023/3/10,42,实验结果比较分析,3 种算法的共同特点是鲁棒性较强，对基本算法模型稍加修改，便可以应用于其他问题具有并行性，易于并行实现 从对实际的组合优化问题的研究中发现，选择何种算法要根据具体所求解的问题的特点。,
