数学建模常用智能算法与Matlab实现.pptVIP

* * 模拟退火算法描述 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)为评价函数 * * Step 5 若Δt′0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. Step 6 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 step 7 T逐渐减少，且T-0，然后转第2步。 * * 模拟退火算法的优缺点： 与以往的近似算法相比,模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点。 * * 各种算法应用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] * * 实验环境：MATLAB 7.0 实验方法：在算法中设置计数器，当解转移迭 代次数达到计数器规定的值时，无须考虑算法的终止条件即刻终止算法观察实验结果，实验结果统计。 设置算法参数：遗传算法中初始种群的大小为100，交叉概率为0.8。变异概率为0.1。在蚁群算法中信息素重要程度的参数, 启发式因子重要程度的参数, 信息素蒸发系数, 信息素增加强度系数.禁忌算法中禁忌长度为150，保留前100个最好候选解。 * * 图3.1 30个城市坐标位置图 * * 算法 迭代次数 平均解 最好解 方差 遗传算法 500 476.90924 437.153 1227.217819 蚁群算法 200 428.88 425.649 7.75151 禁忌有哪些信誉好的足球投注网站算法 1000 461.3991 423.949 785.8090 模拟退火算法 100 423.9725 423.7406 0.1358556 * * 以下是上述四种算法最好解的结果图示 遗传算法的最好解的路径和有哪些信誉好的足球投注网站过程如下图所示： * * 蚁群算法的最好解的路径和有哪些信誉好的足球投注网站过程如下图所示： * * 禁忌有哪些信誉好的足球投注网站算法最好解的路径和有哪些信誉好的足球投注网站过程如下所示： * * 模拟退火算法最好解的路径和有哪些信誉好的足球投注网站过程如下图所示： * * 实验结果比较分析 3 种算法的共同特点是鲁棒性较强，对基本算法模型稍加修改，便可以应用于其他问题具有并行性，易于并行实现 从对实际的组合优化问题的研究中发现，选择何种算法要根据具体所求解的问题的特点。 谢 谢！ 放映结束 感谢各位的批评指导！ 让我们共同进步 * * * * * * * 数学建模常用智能算法 及其Matlab实现 负 责 人：胡 丹 成 员：袁莉莉 王 霖 侯金灵 马婷 指导教师: 周 长 礼 * * 引言 在管理科学、计算机科学、分子物理学和生物以及超大规模集成电路设计等科技领域中，存在着大量的组合优化问题，其中的NP完全问题，其求解时间随问题规模呈指数级增长，当规模稍大时就会因时间限制而失去可行性。以目前已成熟的数值计算理论和算法，或者根本无法求解，或者其求解的计算量是爆炸的。 城市 24 25 26 27 28 29 30 31 计算时间 1s 24s 10m 4.3h 4.9d 136d 10.8a 325a * * 为此我们引入现今流行的智能算法，如遗传算法，模拟退火算法，禁忌有哪些信誉好的足球投注网站算法，蚁群算法，和粒子群算法等。 我们前期所做的主要工作是参考了一些相关书目，组织了讨论小组，对相关的算法进行了研究，并利用这些智能算法解决了TSP问题，下面我们就这些智能算法进行详细介绍。 * * 遗传算法是在70年代初期由美国密执根大学的Holland教授发展起来的。1975年，Holland发表了第一批比较系统论述遗传算法的专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems）。遗传算法主要借用生物进化中“适者生存”的规律揭示了大自然生物进化过程中的一个规律：最适合生存的个体往往产生了更大的后