Matlab求解旅行商问题的算法应用(3)
时间:2017-06-07 11:49 来源:毕业论文 作者:毕业论文 点击:次
随着温度T的降低， 会逐渐降低. 我们将一次向较差解的移动看做一次温度跳变过程，我们以概率 来接受这样的移动. 3.4 蚁群算法 求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化. 这里的信息素值分布式存储在图中，与各弧相关联. 蚂蚁算法求解TSP问题的过程如下： （1）首先初始化，设迭代的次数为NC. 初始化 （2）将m个蚂蚁置于n个顶点上 （3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游 每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路. 蚂蚁的任务是访问所有的城市后返回到起点，生成一条回路. 设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点. （4）记录本次迭代最佳路线 （5）全局更新信息素值 应用全局信息素更新规则来改变信息素值. 当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新. 全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程. 在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加. 6）终止 若终止条件满足，则结束；否则 ，转入步骤（2）进行下一代进化. 终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限. 4. 遗传算法 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法. 它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则.遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域. 它是现代有关智能计算中的关键技术[2]. 选择(selection)算子、交叉(crossover)算子和变异(mutation)算子是遗传算法的3个主要操作算子. 遗传算法中包含了如下5个基本要素: (1) 对参数进行编码； (2) 设定初始种群大小； (3) 适应度函数的设计； (4) 遗传操作设计； (5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。 4.1 遗传算法的基本原理 遗传算法( Genetic Algorithm ,简称GA) 是近年来迅速发展起来的一种全新的随机搜索与优化算法。与传统搜索算法不同,遗传算法从一组随机产生的初始解,称为群体,开始搜索过程。群体中的每个个体是问题的一个解,称为染色体。这些染色体在后续迭代中不断进化,称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体,称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代群体,再继续进化,这样经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解[3 ] 。遗传算法中使用适应度这个概念来度量群体中的各个个体的在优化计算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关。 (责任编辑：qin) |