模拟退火算法在TSP问题中的优化研究+源码(2)
时间:2017-04-24 22:29 来源:毕业论文 作者:毕业论文 点击:次
1.2粒子群算法 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的并行进化算法(（Evolutionary Algorithm - EA）。PSO 算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 1.3模拟退火算法 模拟退火算法的基本思想是： ①加温过程：从给定的初始解决方案开始的，引入随机因素，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变差，也就是以一定概率接受使非优化的解。 ②恒温过程：它由一个类似于物理过程中温度T的全局控制参数t决定，在每一个温度t的条件下都使用t来持续进行“新解的产生—判断—接受或舍弃”的启发式迭代的Metropolis过程，类似于固体在每一确定温度下使内部晶体趋于热平衡产生结晶的过程。在目标函数的限制下，经过满足条件的接受或舍弃过程后，可以求得给特定控制参数t值时优化问题的近似最优解。 ③冷却过程：以退火速率所确定的退火速度去减小参数t的值，在每一个温度时重复恒温过程产生近优解。当控制参t数逐渐减小到截至温度时，系统也随之到达稳定的平衡状态，最后系统的整体状态对应于优化问题最优解。因为固体退火必须缓慢降温，才能使固体在每一温度下都达到热平衡。最终趋于平衡状态。因此控制参数的值必须缓慢递减，才能使模拟退火算法最终接近优化问题的整体最优解。模拟退火算法要从邻域中随机产生一个新解，对于TSP问题，它的邻域指的是两条路径除局部有差别外，大多数路径或次序相同。 2.模拟退火算法的退火过程的分析 2.1模拟退火算法的伪代码： (1)对于初始状态的选取对整个算法结果是不影响的，因此无差别的选取S0为初始状态，令S(0)=S0，同时设初始温度T，令标志i=0。 (2)使T=Ti，以T和2—OPT方式随机产生新的解Si。通过Metropolis准则，返回的状态S作为当前解，Si=S0。 (3)按照参数ε降温，即Ti+1=εTi，其中Ti+1<Ti，i = i+1。 (4)检查终止条件或者重新迭代，如果内、外循环次数到达上限或者T达到截止温度，满足则转步骤(5)，否则转步骤(2)。 (5)当前解Si为最优解，输出结果，停止。 TSP问题的Metropolis算法描述如下： (1)初始化过程，无差别的产生城市序列List[x1,x2,x3……xi,…… xj,……,xn]在温度T下，进行以下操作。 (2)按2—OPT方式根据当前解List所处的状态S产生一个近邻子集P，随机产生两个城市下标i , j交换两个城市的位置产生一个新的序列NewList[x1,x2,x3……xj,…… xi,……,xn]，得到的新解只是在大部分相同小部分不同，将其作为一个新状态S´作为下一个候选解，计算目标函数路径长度之差△C=C(S´)-C(S)。 (3)如果△C´<O，则表示路径优化的方向正确那么接受当前解S´，否则，为了使结果避免出现局部最优解的陷阱，若与当前温度有关的概率数大于概率EXP(-△C´／T)则接受S´跳出局部最优解的陷阱。若S´被接受，则令List=NewList，否则List不变。 (4)检查是否满足内循环次数上限条件，若满足，继续一下过程，否则跳转到步骤(2)。 (责任编辑：qin) |