数学建模常用智能算法及其Matlab实现

2023/9/151数学建模常用智能算法

及其Matlab实现负责人：胡丹

成员：袁莉莉王霖侯金灵马婷

指导教师:周长礼2023/9/152引言在管理科学、计算机科学、分子物理学和生物以及超大规模集成电路设计等科技领域中，存在着大量的组合优化问题，其中的NP完全问题，其求解时间随问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸的。城市2425262728293031计算时间1s24s10m4.3h4.9d136d10.8a325a2023/9/153为此我们引入现今流行的智能算法，如遗传算法，模拟退火算法，禁忌搜索算法，蚁群算法，和粒子群算法等。

我们前期所做的主要工作是参考了一些相关书目，组织了讨论小组，对相关的算法进行了研究，并利用这些智能算法解决了TSP问题，下面我们就这些智能算法进行详细介绍。2023/9/154遗传算法是在70年代初期由美国密执根大学的Holland教授发展起来的。1975年，Holland发表了第一批比较系统论述遗传算法的专著《自然系统和人工系统的自适应》（AdaptationinNaturalandArtificialSystems）。遗传算法主要借用生物进化中“适者生存”的规律揭示了大自然生物进化过程中的一个规律：最适合生存的个体往往产生了更大的后代群体。2023/9/155蚁群算法是由意大利学者A，Dofigo，M，Maniezzo等人于1992年通过模拟自然界中蚂蚁集体寻食的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性,但搜索时间长且易限入局部最优解是其突出的缺点。ACO算法由一群简单的人工蚂蚁通过人工信息素(即一种分布式的数字信息,人工蚂蚁利用该信息和问题相关的启发式信息逐步构造问题的解，相当于真实蚁群的外激素，简称信息素)进行间接通讯，相互协作，从而求出问题的最优解。2023/9/156禁忌搜索（TabuSearch简称TS）的思想最早由FredGlover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，禁忌搜索算法在局部搜索过程中，使用一个“记忆”装置，即禁忌表，驱使算法禁忌重复相同的搜索步骤，转而搜索解空间的新区域，以逃离局部最优。2023/9/157粒子群算法（ParticleSwarmOptimization,PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远则找到食物的最优策略最简单有效的就是搜寻目前离食物最近的鸟的周围区域。2023/9/158模拟退火算法是1982年KirkPatrick将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度加到很高,再缓慢降温(即退火)，使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。2023/9/159TSP问题综述旅行商问题是一个典型的NP完全问题。它可简单地描述为：对于n个城市，它们之间的距离已知,一旅行商要从某一城市出发走遍所有的城市，且一个城市只能经过一次,最后回到出发城市，问如何选择路线可使所走过的路程最短。2023/9/1510建立TSP问题的数学模型如下：2023/9/1511遗传算法的原理

遗传算法通过模拟生物学的自然选择和自然遗传机制模拟生命进化的原理来寻求问题的最优解，它的基本思想是：把问题的解表示成“染色体”，在执行遗传算法之前，随机地给出一群初始“染色体”(种群)即假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样，经过一代一代的进化，最后收敛到最适应环境的一个“染色体”上，它就是问题的最优解。2023/9/1512遗传算法的描述Step1初始化种群规模size、交叉概率Pc、变异概率Pm和迭代次数t。Step2随机产生初始种群；计算初始种群的适应度。Step3根据一定的选择策略选择父体1和父体2。Step4产生一个0～1随机数。Step5判断P1<Pc是否成立，如果成立，把父体1和父体2按一定交叉方法生成子个体1和子个体2；否则把父体1和父体2作为新的子个体1和子个体2。2023/9/1513

Step6判断P2<Pm，如果成立把子个体1和子个体2按一定变异方法变异。Step7判断产生子个体数是否等于种群规模，如果是则转向Step8；否则转向Step3。Step8评估种群的适应度；新产生的子代成为父代。Step9判断是否满足终止条件，如果满足则终止；否则转向Step3．2023/9/1514遗传算法流程图2023/9/1515遗传算法的优点与缺陷遗传算法简单、易于实现，能够并行化，具有强鲁棒性和全局搜索能力。遗传算法与其他启发式算法有较好的兼容性，可以用其他的算法求初始解。缺点则表现为早熟现象、局部寻优能力较差等。所以，一些常规遗传算法并不一定是针对某一问题的最佳求解。2023/9/1516禁忌搜索算法禁忌搜索算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征，是局部搜索算法的一种推广，它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证多样化的有效探索，以最终实现全局优化。2023/9/1517禁忌搜索算法主要过程Stepl算法初始化，设置参数，包括城市数目、禁忌长度、候选集长度和最大迭代步数等Step2生成初始解，作为迭代搜索的起点Step3根据上述初始解，按照一定规则生成邻域，并在邻域中选取元素生成候选集。Step4由于邻域的相互性，将已经搜过的解进行禁忌，避免迂回搜索，以跳出局部最优2023/9/1518Step5从候选集中选出未被禁忌表禁忌的当前局部最优解，若此解优于当前解，则用其替换当前解，成为最优解Step6更新禁忌表（增添新的禁忌解或根据解禁准则，对满足条件的解进行解禁）Step7判断是否满足终止条件(设为限定最大迭代步数，或满足所要求精度)，若满足，则输出最优解，终止算法；若不满足，则将当前局部最优解作为下次迭代的起点，转Step3各种优化算法解决TSP问题2023/9/1519禁忌搜索算法优点

从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局最优性。终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率限制或者目标值偏离程度为终止规则。2023/9/1520蚁群算法

蚁群算法是通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性。它由一群简单的人工蚂蚁通过人工信息素进行间接通讯，相互协作，从而求出问题的最优解。2023/9/1521蚁群算法描述Step1初始每条路径上的信息激素浓度相等。Step2把m只蚂蚁随机地放置在n个城市上,并把已访问的城市写入禁忌表。Step3如果第k(k=1,2,……,m)只蚂蚁还有未访问的城市,则该只蚂蚁根据决策选择下一个城市(i是该蚂蚁当前所在城市，j<(N-禁忌表),是一个由城市i到城市j之间的路径长度和信息激素浓度构成的函数),把选择的城市j写入禁忌表，直到所有的城市访问完。2023/9/1522Step4计算k(k=1,2,……,m)条路径的路径长度，选出本次最优路径。Step5根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度，清空禁忌表。Step6判断是否满足结束条件,如果不满足，转到Step2；否则结束。下图为流程图2023/9/15232023/9/1524蚁群算法的主要特点(1)分布式计算、正反馈机制和贪婪式搜索相结合；(2)具有很强的并行性；(3)更好的可扩充性；(4)概率型的通用全局优化方法；(5)不依赖于优化本身的严格数学性质，诸如连续性、可导性；各种优化算法解决TSP问题2023/9/1525粒子群算法

PSO算法是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子(点)，这些粒子在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。PSO算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。2023/9/1526粒子群算法的数学描述

在D维的搜索空间中，有随机分布的m个粒子组成的一个初始粒子群，每个粒子有各自的位置和速度。如第i个粒子的位置表示为一个D维的向量,速度也是一个D维的向量，记为。每个粒子记住自己在迭代过程中找到的最优位置，记为，整个粒子群迄今为止搜索到的最优位置为全局最优解记。这样的寻优为局部PSO算法，经过一定的迭代后，改用全局最优解，即全局PSO算法进行迭代以加快收敛。2023/9/1527可用下面的公式来表示粒子每轮的更新行为：

(2.1)(2.2)其中为粒子速度，为粒子位置，C1，C2称为学习因子或加速常量，通常在间取值，C1为调节粒子飞向自身最好位置的步长,C2为调节粒子向全局最好位置飞行步长；r1，r2是（0，1）区间内两个随机正数，为个体意识（个体最佳解位置），为群体最佳解位置.为惯性权重，使粒子保持运动惯性，控制前一速度对当前速度的影响;t为飞行的次数。2023/9/1528粒子群算法的流程如下：Stepl：初始化，设定加速常数C1和C2，最大进化代数将当前进化代数置为t=1，在定义空间中随机产生m个粒子X1,X2,…,Xm，组成初始种群X(t),随机产生各粒子初速度V1，V2,…,VS组成位移变化矩阵V(t)。Step2：计算种群中所有粒子的适应值，初始化每粒子pbest为当前粒子，设定种群的gbest为当前种群的最优粒子。2023/9/1529Step3：种群x(t)演化，对种群中的每一个粒子：(1)按(2.1),(2.2)式更新粒子的位置和速度。(2)计算粒子的适应值。(3)比较粒子的适应值和自身的最优值pbest。如果当前值比pbest更优，则更新pbest为当前值，并更新pbest位置到n维空间中的当前位置。(4)比较粒子适应值与种群最优值。如果当前值比gbest更优，则更新gbest为当前种群最优粒子。Step4：检查结束条件，若满足，则结束寻优；否则，t=t+1，转至Step2.。结束条件为寻优达到最大进化代数，或评价值小于给定精度