优化设计-基于模拟退火算法的旅行商问题.pdf

《优化设计-基于模拟退火算法的旅行商问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、——基于模拟退火算法的旅行商问题1.基本概念2.组合优化问题的求解3.旅行商问题4.基于退火算法的配送路径优化5.C#环境下的计算实例所谓的最优化问题，是应用数学的一个分支，其研究对象主要如下所示：给定一个函数f：A→R，寻找一个元素X0∈A，使得对于A中所有的X，f（X0）≤f（X）（函数最小化），或者f（X0）≥f（X）（函数最大化）一般情况下，A为欧几里德空间Rn的一个子集，通常由一个A必须满足的约束条件或者不等式来规定。A的元素被称为可行解；f被称为目标函数，或者费用函数。1.1最优化问题的主要分支线性规划当目标函数f是线

2、性函数而且集合A是由线性等式函数和线性不等式函数来确定的，称这一类问题为线性规划整数规划当线性规划问题的部分或所有的变量局限于整数值时，称这一类问题为整数规划问题1.1最优化问题的主要分支二次规划目标函数是二次函数，而且集合A必须是由线性等式函数和线性不等式函数来确定的。非线性规划研究的是目标函数或是限制函数中含有非线性函数的问题。1.1最优化问题的主要分支随机规划研究的是某些变量是随机变量的问题。动态规划研究的是最优策略基于将问题分解成若干个较小的子问题的优化问题。1.1最优化问题的主要分支组合最优化研究的是可行解是离散或是可转化为离散的

3、问题。无限维最优化研究的是可行解的集合是无限维空间的子集的问题，一个无限维空间的例子是函数空间。1.2求解方法最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法①解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。1.2求解方法②直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到

4、最优点。这种方法常常根据经验或通过试验得到所需结果。1.2求解方法③数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。④其他方法：如网络最优化方法等1.3数值计算法对于无约束的优化问题，如果函数是二次可微的话，可以通过找到目标函数梯度为0（也就是鞍点）的那些点来解决此优化问题。此时需要用海森矩阵来确定此点的类型。如果海森矩阵是正定的话，该点是一个局部最小解，如果是负定的话，该点是一个局部最大解，如果海森矩阵是不定的话，该点是某种鞍点。1.3数值计算法要找到那些拐点，我们可以通过猜测一个初始点，然后用

5、比如以下的迭代的方法来找到。梯度下降法牛顿法共轭梯度法线性搜索臵信域方法......1.3数值计算法有约束条件的约束问题常常可以通过拉格朗日乘数转化为非约束问题。例如：最大化f（x，y）限制于g（x，y）=c引入新的变量，拉格朗日乘数λ，则原问题划归为Λ（x，y，λ）=f（x，y）+λ（g（x，y）-c）1.4随机优化法如前所述，并非所有的优化问题都可以用准确的变量显函数进行描述，此时，对于这类问题的优化需要利用随机法。一个典型的例子是组合优化问题，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少。组合优化

6、的难处，主要是加入了拓扑分析，不同的拓扑形态下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个整数优化的问题了。求解组合优化问题的方法大致上可以分为三类，即解析法、随机法和枚举法。搜索方法解析法随机法枚举法直接法间接法导向随机盲目机法动态规划禁忌搜索模拟退火遗传算法……2.1组合优化中邻域的概念在距离空间中，邻域是指以一个点为中心的一个球。在对光滑函数极值的求解中，邻域是一个非常重要的概念，函数的上升及下降都是在一点的邻域中寻求变化方向。在组合优化中，上述邻域的概念显然已经不再适用，但是在一点的附近搜

7、索另一个使目标函数下降或上升的点任然是求解组合优化问题的最基本思路。定义：对于组合优化问题（D，F，f），D上的一个映射N：S∈D→N（S）∈2D称为一个邻域映射，其中2D表示D的所有子集组成的集合，N(S)称为S的邻域，s∈N(S)称为S的一个邻居。2.2优化中可能遇到的问题任何一种优化算法在求解过程中都可能遇到相同的一个问题：陷入局部最优解。右图是一个典型的拥有局部最优解的优化问题，求解过程中，极有可能将A点误判为全局最优解而错过真正的最优解B图1.具有局部最优解的优化问题2.3模拟退火算法下面介绍一种可以在一定程度上克服局部最优解的导

8、向随机搜索方法：模拟退火算法为了克服陷入局部最优解的问题，模拟退火算法使用基于概率的随机搜索技术：当基于邻域的一次操作使当前解的质量提高