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

1、2021-12-211负 责 人：胡 丹 成 员：袁莉莉 王 霖 侯金灵 马婷 指导教师: 周 长 礼2021-12-212l在管理科学、计算机科学、分子物理学和生物以及超大规在管理科学、计算机科学、分子物理学和生物以及超大规模集成电路设计等科技领域中，存在着大量的组合优化问模集成电路设计等科技领域中，存在着大量的组合优化问题，其中的题，其中的NP完全问题，其求解时间随问题规模呈指数完全问题，其求解时间随问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者根本无法求解，目前已成熟的数值计算理论和算

2、法，或者根本无法求解，或者其求解的计算量是爆炸的或者其求解的计算量是爆炸的。城市城市2425262728293031计算时间1s24s10m4.3h4.9d136d10.8a325a2021-12-213为此我们引入现今流行的智能算法，如遗传算法，模拟退火算法，禁忌搜索算法，蚁群算法，和粒子群算法等。 我们前期所做的主要工作是参考了一些相关书目，组织了讨论小组，对相关的算法进行了研究，并利用这些智能算法解决了TSP问题，下面我们就这些智能算法进行详细介绍。2021-12-214l遗传算法是在遗传算法是在70年代初期由美国密执根大学年代初期由美国密执根大学的的Holland教授发展起来的。教授发

3、展起来的。1975年，年，Holland发表了第一批比较系统论述遗传算发表了第一批比较系统论述遗传算法的专著法的专著自然系统和人工系统的自适应自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems）。遗传算法主要借用生物进化中）。遗传算法主要借用生物进化中“适者生存适者生存”的规律揭示了大自然生物进化的规律揭示了大自然生物进化过程中的一个规律：最适合生存的个体往往过程中的一个规律：最适合生存的个体往往产生了更大的后代群体。产生了更大的后代群体。2021-12-215l蚁群算法是由意大利学者蚁群算法是由意大利学者A，Dofigo，M，

4、Maniezzo 等人于等人于1992 年通过模拟自然界中蚂蚁年通过模拟自然界中蚂蚁集体寻食的行为而提出的一种基于种群的启发式集体寻食的行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制仿生进化算法。它采用分布式并行计算机制,易与易与其他方法结合其他方法结合,具有较强的鲁棒性具有较强的鲁棒性,但搜索时间长但搜索时间长且易限入局部最优解是其突出的缺点。且易限入局部最优解是其突出的缺点。A C O 算算法由一群简单的人工蚂蚁通过人工信息素法由一群简单的人工蚂蚁通过人工信息素(即一种即一种分布式的数字信息分布式的数字信息,人工蚂蚁利用该信息和问题相人工蚂蚁利用该信息和问题相关的启

5、发式信息逐步构造问题的解，关的启发式信息逐步构造问题的解， 相当于真实相当于真实蚁群的外激素，蚁群的外激素， 简称信息素简称信息素)进行间接通讯，相进行间接通讯，相互协作，从而求出问题的最优解。互协作，从而求出问题的最优解。2021-12-216l禁忌搜索（禁忌搜索（Tabu Search 简称简称TS）的思想最）的思想最早由早由FredGlover(1986)提出，它是对局部邻域提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，搜索的一种扩展，是一种全局逐步寻优算法，禁忌搜索算法在局部搜索过程中，使用一个禁忌搜索算法在局部搜索过程中，使用一个“记忆记忆”装置，即禁忌表，驱使算法禁忌

6、重复装置，即禁忌表，驱使算法禁忌重复相同的搜索步骤，转而搜索解空间的新区域，相同的搜索步骤，转而搜索解空间的新区域，以逃离局部最优。以逃离局部最优。2021-12-217l粒子群算法（粒子群算法（ Particle Swarm Optimization, PSO）最早是由）最早是由Eberhart和和Kennedy于于1995年提出，它的基本概念源于对鸟群觅食行为的年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景研究。设想这样一个场景:一群鸟在随机搜寻一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当

7、前的位都不知道食物在哪里，但是它们知道当前的位置离食物还有多远则找到食物的最优策略最简置离食物还有多远则找到食物的最优策略最简单有效的就是搜寻目前离食物最近的鸟的周围单有效的就是搜寻目前离食物最近的鸟的周围区域区域 。 2021-12-218l模拟退火算法是模拟退火算法是1982年年KirkPatrick将退火思将退火思想引入组合优化领域，提出一种解大规模组合想引入组合优化领域，提出一种解大规模组合优化问题的算法，对优化问题的算法，对NP完全组合优化问题尤完全组合优化问题尤其有效。这源于固体的退火过程，即先将温度其有效。这源于固体的退火过程，即先将温度加到很高加到很高,再缓慢降温再缓慢降温(即

8、退火即退火)，使达到能量最，使达到能量最低点。如果急速降温低点。如果急速降温(即为淬火即为淬火)则不能达到最则不能达到最低点低点。2021-12-219l旅行商问题是一个典型的旅行商问题是一个典型的NP完全问题。它可完全问题。它可简单地描述为：对于简单地描述为：对于n个城市，它们之间的距个城市，它们之间的距离已知离已知,一旅行商要从某一城市出发走遍所有一旅行商要从某一城市出发走遍所有的城市，且一个城市只能经过一次的城市，且一个城市只能经过一次,最后回到最后回到出发城市，问如何选择路线可使所走过的路程出发城市，问如何选择路线可使所走过的路程最短。最短。 2021-12-2110l建立建立TSP问

9、题的数学模型如下：问题的数学模型如下：jiijijxdzminjiijx1ViVjxjiij, 1VSSxSjiij, 1,Vjixij,1 , 02021-12-2111 遗传算法通过模拟生物学的自然选择和自然遗传机制遗传算法通过模拟生物学的自然选择和自然遗传机制模拟生命进化的原理来寻求问题的最优解，它的基本模拟生命进化的原理来寻求问题的最优解，它的基本思想是：把问题的解表示成思想是：把问题的解表示成“染色体染色体”，在执行遗传，在执行遗传算法之前，随机地给出一群初始算法之前，随机地给出一群初始“染色体染色体”(种群种群)即假即假设解。然后，把这些假设解置于问题的设解。然后，把这些假设解置于

10、问题的“环境环境”中，中，并按适者生存的原则，选择出较适应环境的并按适者生存的原则，选择出较适应环境的“染色体染色体”进行复制，再通过交叉、变异过程产生更适应环境的进行复制，再通过交叉、变异过程产生更适应环境的新一代新一代“染色体染色体”群。这样，经过一代一代的进化，群。这样，经过一代一代的进化，最后收敛到最适应环境的一个最后收敛到最适应环境的一个“染色体染色体”上，它就是上，它就是问题的最优解。问题的最优解。2021-12-2112lStep 1 初始化种群规模初始化种群规模size、交叉概率、交叉概率Pc、变、变异概率异概率Pm和迭代次数和迭代次数t。lStep 2 随机产生初始种群；计算

11、初始种群的适随机产生初始种群；计算初始种群的适应度。应度。lStep 3 根据一定的选择策略选择父体根据一定的选择策略选择父体1和父体和父体2。lStep 4 产生一个产生一个01随机数。随机数。lStep 5 判断判断P1Pc是否成立，如果成立，把父是否成立，如果成立，把父体体1和父体和父体2按一定交叉方法生成子个体按一定交叉方法生成子个体1和子个和子个体体2；否则把父体；否则把父体1和父体和父体2作为新的子个体作为新的子个体1和子和子个体个体2。2021-12-2113Step 6 Step 6 判断判断P2PmP2Pm，如果成立把子个体，如果成立把子个体1 1和子个体和子个体2 2按按一

12、定变异方法变异。一定变异方法变异。Step 7 Step 7 判断产生子个体数是否等于种群规模，如判断产生子个体数是否等于种群规模，如 果是则转向果是则转向Step8Step8；否则转向；否则转向Step3Step3。Step 8 Step 8 评估种群的适应度；新产生的子代成为评估种群的适应度；新产生的子代成为 父代。父代。Step 9 Step 9 判断是否满足终止条件，如果满足则终止；否判断是否满足终止条件，如果满足则终止；否 则转向则转向Step 3Step 32021-12-2114遗传算法流程图2021-12-2115l遗传算法简单、易于实现，能够并行化，遗传算法简单、易于实现，能

13、够并行化，具有强鲁棒性和全局搜索能力。遗传算法具有强鲁棒性和全局搜索能力。遗传算法与其他启发式算法有较好的兼容性，可以与其他启发式算法有较好的兼容性，可以用其他的算法求初始解。用其他的算法求初始解。l缺点则表现为早熟现象、局部寻优能力较缺点则表现为早熟现象、局部寻优能力较差等。所以，一些常规遗传算法并不一定差等。所以，一些常规遗传算法并不一定是针对某一问题的最佳求解。是针对某一问题的最佳求解。2021-12-2116l禁忌搜索算法是一种全局性邻域搜索算法，模禁忌搜索算法是一种全局性邻域搜索算法，模拟人类具有记忆功能的寻优特征，是局部搜索拟人类具有记忆功能的寻优特征，是局部搜索算法的一种推广，它

14、通过局部邻域搜索机制和算法的一种推广，它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过破禁相应的禁忌准则来避免迂回搜索，并通过破禁水平来释放一些被禁忌的优良状态，进而保证水平来释放一些被禁忌的优良状态，进而保证多样化的有效探索，以最终实现全局优化多样化的有效探索，以最终实现全局优化 。2021-12-2117lStep l 算法初始化，设置参数，包括城市数算法初始化，设置参数，包括城市数目、禁忌长度、候选集长度和最大迭代步数等目、禁忌长度、候选集长度和最大迭代步数等lStep 2 生成初始解，作为迭代搜索的起点生成初始解，作为迭代搜索的起点 lStep 3 根据上述初始解，按照一定

15、规则生成根据上述初始解，按照一定规则生成邻域，并在邻域中选取元素生成候选集。邻域，并在邻域中选取元素生成候选集。lStep 4 由于邻域的相互性，将已经搜过的解由于邻域的相互性，将已经搜过的解进行禁忌，避免迂回搜索，以跳出局部最优进行禁忌，避免迂回搜索，以跳出局部最优2021-12-2118lStep 5 从候选集中选出未被禁忌表禁忌的当从候选集中选出未被禁忌表禁忌的当前局部最优解前局部最优解 ，若此解优于当前解，则用其替，若此解优于当前解，则用其替换当前解，成为最优解换当前解，成为最优解lStep 6 更新禁忌表（增添新的禁忌解或更新禁忌表（增添新的禁忌解或 根据根据解禁准则，对满足条件的解

16、进行解禁）解禁准则，对满足条件的解进行解禁）lStep 7 判断是否满足终止条件判断是否满足终止条件(设为限定最大设为限定最大迭代步数，或满足所要求精度迭代步数，或满足所要求精度)，若满足，则，若满足，则输出最优解，终止算法；若不满足，则将当前输出最优解，终止算法；若不满足，则将当前局部最优解作为下次迭代的起点，转局部最优解作为下次迭代的起点，转Step 3l各种优化算法解决各种优化算法解决TSP问题问题2021-12-2119l 从移动规则看，每次只与最优点比较，而不与从移动规则看，每次只与最优点比较，而不与经过点比较，故可以爬出局部最优。经过点比较，故可以爬出局部最优。l选优规则始终保持曾

17、经达到的最优点，所以即选优规则始终保持曾经达到的最优点，所以即使离开了全局最优点也不会失去全局最优性。使离开了全局最优点也不会失去全局最优性。l终止规则不以达到局部最优为终止规则，而以终止规则不以达到局部最优为终止规则，而以最大迭代次数、出现频率限制或者目标值偏离最大迭代次数、出现频率限制或者目标值偏离程度为终止规则。程度为终止规则。2021-12-2120 蚁群算法是通过模拟自然界中蚂蚁集体寻径的蚁群算法是通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化行为而提出的一种基于种群的启发式仿生进化算法。它采用分布式并行计算机制算法。它采用分布式并行计算机制,易与其他易与其他

18、方法结合方法结合,具有较强的鲁棒性具有较强的鲁棒性 。它由一群简单。它由一群简单的人工蚂蚁通过人工信息素进行间接通讯，相的人工蚂蚁通过人工信息素进行间接通讯，相互协作，从而求出问题的最优解。互协作，从而求出问题的最优解。2021-12-2121lStep 1 初始每条路径上的信息激素浓度相等。初始每条路径上的信息激素浓度相等。 lStep 2 把把m只蚂蚁随机地放置在只蚂蚁随机地放置在n个城市上个城市上,并并把已访问的城市写入禁忌表。把已访问的城市写入禁忌表。 lStep 3 如果第如果第 k(k=1,2,m)只蚂蚁还有未访只蚂蚁还有未访问的城市问的城市,则该只蚂蚁根据决策则该只蚂蚁根据决策

19、选择下一个城市选择下一个城市( i是该蚂蚁当前所在城市，是该蚂蚁当前所在城市，j(N-禁忌表禁忌表), 是一是一个由城市个由城市i 到城市到城市 j 之间的路径长度和信息激素之间的路径长度和信息激素浓度构成的函数浓度构成的函数),把选择的城市把选择的城市j 写入禁忌表，直写入禁忌表，直到所有的城市访问完。到所有的城市访问完。 ijpijp2021-12-2122lStep 4 计算计算 k(k=1,2,m) 条路径的路径长条路径的路径长度，选出本次最优路径。度，选出本次最优路径。lStep 5 根据本次蚂蚁的访问情况更新每一条根据本次蚂蚁的访问情况更新每一条边上的信息激素浓度，清空禁忌表。边上

20、的信息激素浓度，清空禁忌表。 lStep 6 判断是否满足结束条件判断是否满足结束条件,如果不满足，如果不满足，转到转到Step 2 ； 否则结束。否则结束。下图为流程图下图为流程图 2021-12-21232021-12-2124l(1)分布式计算、正反馈机制和贪婪式搜索相结分布式计算、正反馈机制和贪婪式搜索相结合；合；l(2)具有很强的并行性；具有很强的并行性；l(3)更好的可扩充性；更好的可扩充性；l(4)概率型的通用全局优化方法；概率型的通用全局优化方法；l(5)不依赖于优化本身的严格数学性质，诸如连不依赖于优化本身的严格数学性质，诸如连续性、可导性；续性、可导性；l各种优化算法解决各

21、种优化算法解决TSP问题问题2021-12-2125 PSO算法是将群体中的每个个体视为多维搜索空算法是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子间中一个没有质量和体积的粒子(点点)，这些粒子，这些粒子在搜索空间中以一定的速度飞行，并根据粒子本在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优自

22、己的前进方向和速度大小，从而形成群体寻优的正反馈机制。的正反馈机制。PSO算法就是这样依据每个粒子算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。最终搜索、寻找到问题的最优解。2021-12-2126粒子群算法的数学描述粒子群算法的数学描述 在在D维的搜索空间中，有随机分布的维的搜索空间中，有随机分布的m个粒子组个粒子组成的一个初始粒子群，每个粒子有各自的位置和成的一个初始粒子群，每个粒子有各自的位置和速度。如第速度。如第i个粒子的位置表示为一个个粒子的位置表示为一个D维的向维的向量量 ,速度也是一个速度

23、也是一个D 维的向量，记维的向量，记为为 。每个粒子记住自己在迭代过程。每个粒子记住自己在迭代过程中找到的最优位置，记为中找到的最优位置，记为 ，整个粒，整个粒子群迄今为止搜索到的最优位置为全局最优解子群迄今为止搜索到的最优位置为全局最优解记记 。 这样的寻优为局部这样的寻优为局部PSO算法，经过一定的迭代后，算法，经过一定的迭代后，改用全局最优解，即全局改用全局最优解，即全局PSO算法进行迭代以加算法进行迭代以加快收敛。快收敛。 ,1,2,.,iiii Dxx xx,1,2,.,iiii Dvv vv,1,2,.,iiii Dpp pp,1,2,.,gggg Dpppp2021-12-212

24、7可用下面的公式来表示粒子每轮的更新行为：可用下面的公式来表示粒子每轮的更新行为： (2.1) (2.2) 其中其中 为粒子速度，为粒子速度， 为粒子位置，为粒子位置，C1，C2称为学习因子或加速常量，通常在称为学习因子或加速常量，通常在 间取值，间取值， C1为调节粒子飞向自身最好位置的步长为调节粒子飞向自身最好位置的步长, C2 为为调节粒子向全局最好位置飞行步长；调节粒子向全局最好位置飞行步长；r1，r2 是是（0，1）区间内两个随机正数，）区间内两个随机正数， 为个体意识为个体意识（个体最佳解位置），（个体最佳解位置）， 为群体最佳解位置为群体最佳解位置. 为惯性权重，使粒子保持运动惯

25、性，控制前一为惯性权重，使粒子保持运动惯性，控制前一速度对当前速度的影响速度对当前速度的影响; t 为飞行的次数。为飞行的次数。)()()() 1(,22,11,txprctxprctvwtvdidgdidididi) 1()() 1(,tvtxtxdididi, i dv, i dx0 , 2, i dp,g dpw2021-12-2128粒子群算法的流程如下：粒子群算法的流程如下：Step l： 初始化，设定加速常数初始化，设定加速常数C1和和C2，最大进化，最大进化代数代数 将当前进化代数置为将当前进化代数置为 t = 1 ，在定义空间，在定义空间 中随机产生中随机产生m个粒子个粒子X1

26、,X2,Xm，组成初始，组成初始种群种群X(t),随机产生各粒子初速度随机产生各粒子初速度V1，V2,VS组成组成位移变化矩阵位移变化矩阵V(t)。Step 2： 计算种群中所有粒子的适应值，初始化每计算种群中所有粒子的适应值，初始化每粒子粒子pbest为当前粒子，设定种群的为当前粒子，设定种群的gbest为当前为当前种群的最优粒子。种群的最优粒子。maxTnR2021-12-2129Step 3：种群：种群x(t)演化，对种群中的每一个粒子：演化，对种群中的每一个粒子：(1) 按按(2.1),(2.2)式更新粒子的位置和速度。式更新粒子的位置和速度。(2) 计算粒子的适应值。计算粒子的适应值

27、。(3) 比较粒子的适应值和自身的最优值比较粒子的适应值和自身的最优值pbest。如果当前。如果当前值比值比pbest更优，则更新更优，则更新pbest为当前值，并更新为当前值，并更新pbest位置到位置到n维空间中的当前位置。维空间中的当前位置。(4) 比较粒子适应值与种群最优值。如果当前值比比较粒子适应值与种群最优值。如果当前值比gbest更优，则更新更优，则更新gbest为当前种群最优粒子。为当前种群最优粒子。 Step 4： 检查结束条件，若满足，则结束寻优；否则，检查结束条件，若满足，则结束寻优；否则，t = t + 1，转至，转至Step 2.。结束条件为寻优达到最大进。结束条件为

28、寻优达到最大进化代数化代数 ，或评价值小于给定精度，或评价值小于给定精度 。maxT2021-12-2130 模拟退火算法是模拟退火算法是80年代发展起来的一种用于年代发展起来的一种用于求解大规模优化问题的随机搜索算法，它以优化求解大规模优化问题的随机搜索算法，它以优化问题求解过程与物理系统退火过程之间的相似性问题求解过程与物理系统退火过程之间的相似性为基础；优化的目标函数相当于金属的内能；优为基础；优化的目标函数相当于金属的内能；优化问题的自变量组合状态空间相当于金属的内能化问题的自变量组合状态空间相当于金属的内能状态空间；问题的求解过程就是找一个组合状态，状态空间；问题的求解过程就是找一个

29、组合状态，使目标函数值最小。利用使目标函数值最小。利用Metropolis准则并适当准则并适当地控制温度的下降过程实现模拟退火，从而达到地控制温度的下降过程实现模拟退火，从而达到在多项式时间内求解全局优化问题的目标在多项式时间内求解全局优化问题的目标 。2021-12-2131Step 1 初始化：初始温度初始化：初始温度T(充分大充分大)，初始解，初始解状态状态S(是算法迭代的起点是算法迭代的起点)， 每个每个T值的迭代次值的迭代次数数L step 2 对对k=1，L做第做第(3)至第至第6步：步： step 3 产生新解产生新解S Step 4 计算增量计算增量t=C(S)-C(S)，其中

30、，其中C(S)为为评价函数评价函数 2021-12-2132Step 5 若若t0，然后转第，然后转第2步。步。2021-12-2133 与以往的近似算法相比与以往的近似算法相比,模拟退火算法具有模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点。和较少受到初始条件约束等优点。2021-12-2134 我们将各种智能算法应用于解决我们将各种智能算法应用于解决TSP问题，下面我们以问题，下面我们以30个城市的个城市的TSP问题为例进行结果分析问题为例进行结果分析l下表为下表为30个城市的个城市的TSP仿真结果，其中仿真结果

31、，其中30个城市的坐标如个城市的坐标如下：下：l 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 502021-12-2135l实验环境：实验环境：MATLAB 7.0 l实验方法：在算法中设置计数器，当解转移迭实验方法：在算法中设置计数器，当解转移迭 代次数代次数达到计数器规定的值时，无须考

32、虑算法的终止条件即刻达到计数器规定的值时，无须考虑算法的终止条件即刻终止算法观察实验结果，实验结果统计。终止算法观察实验结果，实验结果统计。l设置算法参数：遗传算法中初始种群的大小为设置算法参数：遗传算法中初始种群的大小为100，交，交叉概率为叉概率为0.8。变异概率为。变异概率为0.1。在蚁群算法中信息素重。在蚁群算法中信息素重要程度的参数要程度的参数, 启发式因子重要程度的参数启发式因子重要程度的参数, 信息素蒸发信息素蒸发系数系数, 信息素增加强度系数信息素增加强度系数.禁忌算法中禁忌长度为禁忌算法中禁忌长度为150，保留前保留前100个最好候选解。个最好候选解。2021-12-213601020304050607080901000102030405060708090100图图3.1 30个城市坐标位置图个城市坐标位置图2021-12-2137算法算法迭代次迭代次数数平均解平均解最好解最好解方差方差遗传算遗传算法法500476.90924437.153 1227.217819蚁群算蚁群算法法200428.88