隐枚举法 |
您所在的位置:网站首页 › 01规划隐枚举法MATLAB代码 › 隐枚举法 |
背景关联 隐枚举法是解决0-1整数规划问题的算法。课题组在研究无人机协同任务规划时,利用隐枚举法解决多无人机的任务分配问题。 0-1规划是整数线性规划的一种特殊情形,指变量只能取0或者1的规划问题。整数规划(Integer Programming)分为纯整数线性规划(所有变量为整数)、混合整数线性规划(部分变量必须取整数)、以及0-1型整数线性规划。目前流行的求解整数规划的方法大多针对整数线性规划。求解方法包括分枝定界法、割平面法、隐枚举法,还有蒙特卡洛方法(蒙特卡洛好神奇,啥都能干),等。 切入正题首先将任务分配问题转换为0-1整数规划模型,这里举最简单的情况。 假设我有m(取m=4)架无人机执行n(取n=2)项不同任务,则变量总数为m*n=8,取x1,x2,x3 ,x4 ,x5,x6,x7,x8 ,其中x1=1则表示飞机1执行任务1,…,以此类推,x8=1则表示飞机4执行任务2。不同无人机-任务对之间的执行时间用 a n 表示,要求总代价时间最小:写出总的代价函数,如:min a1x1+a2x2+a3x3+a4x4+a5x5+a6x6+a7x7+a8x8 增加约束条件:(如油耗、威胁等价等,还有保证任务被完成、一架飞机只能完成一个任务等)s.t. Aeq X =”; (3) 将目标函数中系数为负的变量转换为系数为正的变量; (4) 按照变量系数递增的顺序重新排列目标函数中变量的顺序,同时约束条件中变量顺序对于排列。 预处理完毕,作用是:经过上述步骤得到的目标函数和约束条件使得我们可以按照二进制顺序开始枚举,由于目标函数求最小值,因此从目标函数的下界(x=0)开始,就能尽早找到可行解。 隐枚举找到一个可行解z0后: 若之后寻求的目标函数z1大于该可行解z0,则一定不会是最优解,省去了验证约束条件的步骤,可以直接进行“剪枝”。“剪枝”的意思是:在之后的枚举过程中,直接略去包含当前变量取值子集的情况。 若之后寻求的目标函数z1小于可行解z0,则验证约束条件:若不满足,则继续枚举;若满足,则更新当前可行解,使z0=z1。 至此,用隐枚举解决任务分配模型的过程就结束了。代码是本人16年初的蜜汁风格(汗),就不贴了。最后,推荐大家两个计算规划问题的软件:CPLEX、LINGO,当然MATLAB也很好用。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |