论文部分内容阅读
摘要：模拟退火算法是一种随机搜索算法，可应用于许多前提信息很少的问题，能渐进地收敛于全局最优解。指派问题是组合优化问题中的一种，可用模拟退火算法来解此问题。模拟退火算法解决指派问题时，需要考虑实现此算法的技术问题，例如解的形式，初始温度的计算，邻域的生成方式，解的接受和舍弃，内外循环的中止条件等。在VB编程环境下，实现了该算法的求解过程。实例仿真表明了该方法能够以一定的概率跳出局部最优而实现全局寻优。
关键词：VB；模拟退火算法；指派问题；仿真
中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)35-2153-03
Simulated Annealing Algorithm to Solve Assignment Problem under VB
DUAN Cha-li,CHEN Bo
(Lanzhou Jiaotong University,Lanzhou 730070,China)
Abstract: Simulated annealing algorithm is a random search algorithm, and it can be applied to many problems with little premise information, gradual convergence in the global optimal solution. The assignment problem is one of combinatorial optimization problems. Simulated annealing algorithm can be used to solve assignment problem. When using the algorithm, various technical issues of the algorithm must be considered, such as the form of solution, the initial temperature account, the formation of neighborhood, accepting and giving up the solution, suspension conditions of both inside and outside cycles etc. Under VB programming environment, the author carries out the solution process of the algorithm. Examples simulation shows that the method can jump out of local optimum solution with a certain probability to achieve global optimization.
Key words: VB;simulated annealing algorithm;assignment problem;simulation
1 引言
在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其优势，从而降低成本、提高效益。例如某公司需完成 m项任务，恰好有n名员工可承担这些任务（n≥m）；每项任务只能由一名员工来做，每名员工也只能做一项任务；不同的员工完成各项任务的成本不同。问怎样分配任务公司的花费最小[1] ?这类问题被称为标准的指派问题 (assignment problem)。模拟退火算法(Simulated Annealing,简称SA)的思想最早是由Metropolis等(1953年)提出的，1983年Kirkpatrick等成功的将其用于组合优化问题中。模拟退火算法在某初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优[2]。本文在VB编程环境完成模拟退火算法求解指派问题。
2 指派问题模型
有n个人，m项任务（n≥m），一个人最多可以干一项任务，而一项任务只能由一个人做。cij表示第i个人做第j项任务的费用，找出任务分配方案，使得总费用最小。首先引入一个0-1变量xij：
(1)
模型为：
3 模拟退火算法（SA算法）
模拟退火算法的基本思想是将组合优化问题比做成一个热力学系统，将优化问题的费用函数f(s)比拟成系统的能量E(i),组合优化问题的解s就比拟成退火过程中能量的状态i。把优化求解过程比拟成系统逐步降温( 迭代搜索) 达到最低能量状态的退火过程。通过模拟退火过程获得优化问题的全局最优解，其算法先确定一个能量函数即目标函数,求解最优化问题一般通过Metropolis抽样和退火两个过程实现。该算法在接受较优解的同时,还在一定范围内接受差解,从而使模拟退火算法能跳出局部最优解而获得最优解[3]。
模拟退火算法步骤[4]：
STEP 1:任选—个初始解s0；s:=s0；k:=0；t0:=tmax(初始温度)；
STEP 2:若在该温度达到内循环停止条件，则到STEP3；否则，从邻域N(s)中随机选一个（新解）q,计算Δfsq=f(s)-f(q);若Δfsq≤0，则s:=q;否则若时，则s:=q；重复STEP 2。
STEP 3：tk+1=d(tk)；k:=k+1；若满足停止条件，终止计算；否则，回到STEP 2。
3.1 指派问题解s的形式
n表示员工数目，m表示任务数。在输出结果时，用一个2×m的二维数组来表示解，即第一行表示各项工作，由1到m；第二行表示任务分配 ，即从n个人中选择m个做各项工作。
显然该解满足模型中的约束条件 (3) 、(4) ，如果此解还满足条件(1) 、(2)，则为可行解，否则为不可行解。
3.2 邻域的生成
模拟退火算法中,解的搜索过程是在一个能量状态点附近搜索另外一个能量状态点。在温度tk时刻，指定一个可行解s，然后任意交换两个人的工作，生成一个新的解q，如果满足模型的约束条件(1)和(2) ，则q就是s邻域中的一个可行解。解s的邻域就是由以上方法生成的可行解。
3.3 新解的接受与淘汰
在当前解的邻域中搜索到一个新解，是否接受，要看新解的目标函数值（费用）和当前最优解的目标函数值（费用）的差Δfsq，如果Δfsq≤0，则说明新解的目标函数值较小，当前解被新解代替；否则Δfsq>0，看新解的接受概率是否大于一个在0到1之间的随机数ε，若大于，则接收新解为当前最优解，否则舍弃该解。
关键词：VB；模拟退火算法；指派问题；仿真
中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)35-2153-03
Simulated Annealing Algorithm to Solve Assignment Problem under VB
DUAN Cha-li,CHEN Bo
(Lanzhou Jiaotong University,Lanzhou 730070,China)
Abstract: Simulated annealing algorithm is a random search algorithm, and it can be applied to many problems with little premise information, gradual convergence in the global optimal solution. The assignment problem is one of combinatorial optimization problems. Simulated annealing algorithm can be used to solve assignment problem. When using the algorithm, various technical issues of the algorithm must be considered, such as the form of solution, the initial temperature account, the formation of neighborhood, accepting and giving up the solution, suspension conditions of both inside and outside cycles etc. Under VB programming environment, the author carries out the solution process of the algorithm. Examples simulation shows that the method can jump out of local optimum solution with a certain probability to achieve global optimization.
Key words: VB;simulated annealing algorithm;assignment problem;simulation
1 引言
在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其优势，从而降低成本、提高效益。例如某公司需完成 m项任务，恰好有n名员工可承担这些任务（n≥m）；每项任务只能由一名员工来做，每名员工也只能做一项任务；不同的员工完成各项任务的成本不同。问怎样分配任务公司的花费最小[1] ?这类问题被称为标准的指派问题 (assignment problem)。模拟退火算法(Simulated Annealing,简称SA)的思想最早是由Metropolis等(1953年)提出的，1983年Kirkpatrick等成功的将其用于组合优化问题中。模拟退火算法在某初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优[2]。本文在VB编程环境完成模拟退火算法求解指派问题。
2 指派问题模型
有n个人，m项任务（n≥m），一个人最多可以干一项任务，而一项任务只能由一个人做。cij表示第i个人做第j项任务的费用，找出任务分配方案，使得总费用最小。首先引入一个0-1变量xij：
模型为：
3 模拟退火算法（SA算法）
模拟退火算法的基本思想是将组合优化问题比做成一个热力学系统，将优化问题的费用函数f(s)比拟成系统的能量E(i),组合优化问题的解s就比拟成退火过程中能量的状态i。把优化求解过程比拟成系统逐步降温( 迭代搜索) 达到最低能量状态的退火过程。通过模拟退火过程获得优化问题的全局最优解，其算法先确定一个能量函数即目标函数,求解最优化问题一般通过Metropolis抽样和退火两个过程实现。该算法在接受较优解的同时,还在一定范围内接受差解,从而使模拟退火算法能跳出局部最优解而获得最优解[3]。
模拟退火算法步骤[4]：
STEP 1:任选—个初始解s0；s:=s0；k:=0；t0:=tmax(初始温度)；
STEP 2:若在该温度达到内循环停止条件，则到STEP3；否则，从邻域N(s)中随机选一个（新解）q,计算Δfsq=f(s)-f(q);若Δfsq≤0，则s:=q;否则若
STEP 3：tk+1=d(tk)；k:=k+1；若满足停止条件，终止计算；否则，回到STEP 2。
3.1 指派问题解s的形式
n表示员工数目，m表示任务数。在输出结果时，用一个2×m的二维数组来表示解，即第一行表示各项工作，由1到m；第二行表示任务分配 ，即从n个人中选择m个做各项工作。
显然该解满足模型中的约束条件 (3) 、(4) ，如果此解还满足条件(1) 、(2)，则为可行解，否则为不可行解。
3.2 邻域的生成
模拟退火算法中,解的搜索过程是在一个能量状态点附近搜索另外一个能量状态点。在温度tk时刻，指定一个可行解s，然后任意交换两个人的工作，生成一个新的解q，如果满足模型的约束条件(1)和(2) ，则q就是s邻域中的一个可行解。解s的邻域就是由以上方法生成的可行解。
3.3 新解的接受与淘汰
在当前解的邻域中搜索到一个新解，是否接受，要看新解的目标函数值（费用）和当前最优解的目标函数值（费用）的差Δfsq，如果Δfsq≤0，则说明新解的目标函数值较小，当前解被新解代替；否则Δfsq>0，看新解的接受概率是否大于一个在0到1之间的随机数ε，若大于，则接收新解为当前最优解，否则舍弃该解。