您好,欢迎访问三七文档
2.098/15.093JRecitation9XuanVinhDoan2004,10,111、启发式算法整数规划一般是不容易得到最优解的。启发式算法可以在合理的计算时间内得到较优的可行解。局域搜索启发式算法应用广泛。局域搜索的一般步骤如下:1、从一个初始可行解出发2、找出相邻的可行解3、从相邻的可行解中找出更好的可行解一般地,局域搜索启发式算法会得到一个局部最优解,而这个局部最优解有时就是全局最优解。算法的好与坏都决定于步骤3。1.1模拟退火方法相邻元素是随机选择的,选上的概率为,np1=∑∈Nnnp。移动的决策取决于目标成本和退火概率:()()()()()()⎪⎩⎪⎨⎧=−−xpxcycexppyTxcycyxyφ其中温度梯度是根据一定的规则选择的,比如tCtTlog)(=或,。tCatT=)(1πa1.2其它方法其它局域搜索式方法还有很多,具体问题有相应的方法。如:禁忌搜索、遗传算法(略有不同),蚁群优化法也是一种。1、禁忌搜索的组成部分:禁忌表(移动的列表或移动的特征的列表),集中化(好的解),多样化(不好的解)。2、遗传算法的组成部分:染色体(解的表示法),选择、交叉、变异。3、蚁群优化:信息素轨迹和启发式愿望(收敛速度)。12、动态规划2.1动态规划要素1、(最重要的)状态变量.kx2、控制(或决策)变量,ku)(kkxUu∈。3、随机变量.kw4、状态转移方程),,(1kkkkkuxfxω=+5、附加费用。)),,()((11kkkNikNNWuxgxgEω∑−=+2.2Bellman最优化原理这里我们想要分个阶段来求出总的最小费用。最后阶段的费用为。在第k阶段状态为下,决定控制变量,使从第阶段到最后的总费用最小。按下面的递推公式:N)(NNxgkxkuk()(){}))),,((),,(min1kkkkkkkkkwxUukkwuxfJwuxgExJkkk+∈+=得到全局最小值为。)(00xJ一般的,一个递归公式需两个元素:1.初始条件ff=02.递归公式)(1kkkfgf=+2.3例题背包问题根据不同的状态定义,递推公式有两种:1.为最优费用,w为重量限制。则要找到:)(wF)(wF()iiwwifFmin0π=ω()(){}iiiimiwwifpwwFwFminmax,1φ+−==2.当时,令为最优费用,为重量限制。则要找到:1=i)(wFiw)(wFm()()0,0000πwifwFwifwF−∞=≥=()()(){}0,max111φwifpwwFwFwFiiiii++++−=2
本文标题:启发式算法
链接地址:https://www.777doc.com/doc-1363503 .html