第27卷第7期 2010年7月 计算机应用与软件
Co m puter Applicati o ns and Soft w are Vo l 27No . 7
Ju. l 2010
0 1规划中并行隐枚举法的实现方式
曾 艳
(华中师范大学计算机科学与技术系 湖北武汉430079)
摘 要 0 1规划中, 当变量较大时, 状态数过多、时间耗费较大, 隐枚举法是目前解决0-1规划问题最有效的方法, 并行计算的
特点是快速解决大型且复杂的计算问题。结合并行计算和隐枚举法来解决这个问题, 并且对隐枚举法做了一定的改进, 使得在串行计算中难以实现的问题在并行计算机上得到了解决, 并用实例验证了算法的可行性和优越性。关键词 0 1规划 并行计算 隐枚举法
I M PLEMENTI NG APPROACH FOR PARALLEL I M PLI CI T ENU M ERATI ON I N 0 1PROGRAMM I NG
Zeng Y an
(Depart m e n t of Co m pu ter S cie n ce and T ec hn ology, Cen t ra l Ch i na N orma l Un i versit y, W uhan 430079, H ubei , Ch ina )
Abstrac t In 0 1prog ramm i ng, t he mo re t he variab les are , the mo re the sta tes are and the l ong er t he ti m e costs . A t present , i m pli c it enu
m erati on m ethod is t he best w ay to so l ve it . A cco rd i ng t o t he character i stic o f para ll e l compu ting , it can so lve b i g and comp l ex proble m s fast . A m ethod co m bi n i ng the pa ra lle l compu ting w it h t he i m pli c it enu m erati on i s presented i n t h is paper to reso l ve t he proble m m entioned above . A nd , there is so m e i m provem entm ade on the i m plicit enu m erati on , so the proble m wh i ch is hard to ser ial computi ng can be so l v ed by parall e l computers . A n exa m ple i s g i ven for the proof o f the feasi b ility and predom inance o f the a l gor it hm . K eywords 0 1prog ramm i ng P ara ll e l computi ng I m pli c it enu m erati on me t hod
程。它是相对于串行计算而言的, 所谓的并行计算分为时间上
0 引 言
对于有n 个变量的0 1规划问题, 由于每个变量只取0、1两个值, 故n 个变量所有可能的0 1组合数有2个。在现实生活中, 很多问题都可以转换成0 1规划问题, 比如席位分配问题、排序问题、资源配置问题等, 而对于0 1规划的问题, 目前最普遍的解法就是枚举法, 即检查变量取值为0或1的每一种组合, 比较目标函数值以求得最优解。在此基础上人们采用了隐枚举法、遗传算法、动态规划法等方法, 虽然在一定程度上加快了求解速度、缩短了问题的解决时间, 但这些方法都是基于串行计算来实现的, 只能当变量较小时来达到优化的目的。但是当n 较大时, 比如:当n =64时, 264 1. 845 1019, 以每秒解决107种状态的速度, 则需要5. 85 104年, 用串行计算根本是不可能的。并行计算能同时使用多种计算资源解决计算问题, 能快速解决大型且复杂的计算问题, 是当前世界上主要用于解决大规模、高精度问题的方法, 它能解决很多串行计算不能解决的问题。目前国内外对用并行算法来解决0 1规划问题的研究并不多, 基于0 1规划问题在生活中的重要性以及并行算法的高效性, 本文对用并行隐枚举法来解决0 1规划的问题进行了一定的探讨。
n
的并行和空间上的并行, 时间上的并行就是指流水线技术, 而空间上的并行则是指用多个处理器并发的执行计算。集群系统逐渐成为高性能并行计算的主要硬件平台, 它是将一组相互独立的计算机通过高速的通信网络而组成的一个单一的计算机系统, 并以单一系统的模式进行管理[1]。并行计算的主要目的:一是为了提供比传统计算机快的计算速度; 二是解决传统计算机无法解决的问题。
M P I(Message P assi ng Interface) 是消息传递并行程序设计的标准之一, 是目前最主要的并行环境。它适用于基于分布内存的并行计算机系统的消息传递模型, 具有移植性好、功能强大、效率高等多种特点, 而且有多种不同的免费、高效、实用的实现版本, 几乎所有的并行计算机厂商都提供对它的支持, 这是其他并行环境无法比拟的[2,
3]
。
隐枚举法(I m pli c it Enu m erati on M ethod) 是Ba l as E 在1965年提出的, 是以0 1整数规划为背景建立的。它只检查一部分变量组合, 在这过程中根据已有信息自动舍弃许多不可能成为最优解的组合, 求得最优解, 从而大大减少了工作量[4, 5]。隐枚举法只需比较目标函数在一小部分组合点上的取值大小就能求得最优解和最优值。弥补了完全枚举法迭代次数过大的缺点。
1 并行计算与隐枚举法
收稿日期:2008-12-17。曾艳, 本科生, 主研领域:高性能计算及
算资过
2 0 1规划问题并行算法设计
2. 1 算法设计基本原理
0 1规划问题中各个状态的处理计算是唯一的, 本文中以各个状态为对象, 每个节点(或从进程) 处理等量的状态数。假设有n 个变量, 即个2状态, 有m +1个进程。
算法基本原理如下:
1) 程序初始化生成m +1个进程, 每个进程I D 号分别为0, 1, ! , m -1, m 。
2) 进程0作为主处理器, 其操作包括两个方面的内容:∀将2n 个状态划分为m 个状态组, 并且将这m 个状态组分配给m 个相应的从进程; #检查是否有从进程向其发送满足条件的局部最优解, 若有则接受消息, 并且与当前的全局最优解进行比较。
3) 进程1, 2, ! , m, 作为从进程, 其操作包括两个方面的内容:∀接受主进程发送来的状态组, 在局部区域内进行搜索, 得
到一个局部最优解; #将局部最优解发送给主进程, 等待新的任务。
4) 直到所有的从进程计算完毕, 将局部最优解发送给主进程, 主进程得到最后的全局最优解。
n
3 应用实例
一个旅行者有一个最多能装15公斤的背包, 现在有6件物品, 它们的重量分别是3, 6, 2, 3, 7, 1; 它们的价值分别为4, 7, 5, 7, 8, 15; 若每种物品只有一件, 求旅行者能获得最大总价值Z 。
分析:这个问题转换成数学模型为:
M =3x 1+6x 2+2x 3+3x 4+7x 5+x 6∃15
求:
Z =M ax {4x 1+7x 2+5x 3+7x 4+8x 5+15x 6}
式中, x 1, x 2, x 3, x 4, x 5, x 6的取值为0或1。这个实例中一共有6个变量, 共有64个状态。(1) 用串行完全枚举法求解
目标函数需要计算64次, 约束条件需要计算64次, 总共需要计算128次。当{x 1, x 2, x 3, x 4, x 5, x 6}={111101}时, m =15, Z =38。
(2) 用并行隐枚举法进行求解设从处理器数目为4。
S tep 1 将状态数进行分组, 先试探性求一个可行解, 易看出{x 1, x 2, x 3, x 4, x 5, x 6}={0, 0, 0, 0, 0, 1}满足约束条件, 故为一个可行解, 且相应的目标函数值为Z =15, 将4x 1+7x 2+5x 3+7x 4+8x 5+15x 6%15作为过滤条件, 在从进程中计算出每个状态的目标函数值, 如表1所示。
表1 从进程状态分配情况
进程号
1
各个进程的状态{0, 0, 0, 0, 0, 0}
! ! {0, 0, 1, 1, 1, 1}{0, 1, 0, 0, 0, 0}
! ! {0, 1, 11, 1, 1}{1, 0, 0, 0, 0, 0}
! ! {1, 0, 1, 1, 1, 1}{1, 1, 0, 0, 0, 0}
! ! {1, 1, 1, 1, 1, 1}
目标函数值
! ! 3522! ! 424! ! 3911! ! 46
2. 2 算法具体实现
设有2n 个状态, m 个从进程, g l o _best为主进程中记录全局最优解的变量, part _best[i](i =1to m ) 为相对应的m 个从进程中的记录局部最优解的变量, state[i](i =1t o m ) 记录从进程的状态, st a te[i]=0表示从进程i 空闲, group [i]记录从进程i 中所接受到需要处理的状态。假设所需要求的最优解是极大值问题。
核心算法如下:
初始化:将2n 个状态划分成m 个状态组, 并分配给各个从进程, stat e [i ]=1
试探性求一个满足约束条件的可行解, 计算出相应的目标函数值为Z
W h il e(存在s t ate[i]==1) { }
将目标函数值大于等于Z 的状态数按照目标值进行从大到小排序For(j=1; j
{//s 为目标函数值大于等于Z 的状态数If(状态j 满足约束条件) {part_best[i ]=z[k]; }
state[i ]=0;
If(part_best[i ]>glo_best)glo_best=p art_best[i];//将局部最优解和全局最优解进行比较
}
, break; }
对于从进程, i 寻找局部最优解For(j =1; j
n
2
3
4
S tep 2 在各个从进程中根据过滤条件删除目标函数值小于15的状态, 然后按照目标函数值从大到小将状态进行排序
(各从进程最终结果数如表2所示), 并且计算约束条件, 如表3所示。
表2 各进程中满足条件的情况
进程号
1234
各进程中Z>=15状态数
10141215
最大Z 值
35423946
{
求出所有状态的目标值z[j ];
If(状态j 的目标函数值小于Z) {删除相应的状态; }
由上述例子和结果可得, 用串行完全枚举的方法, 需要计算128次, 且每个状态都需要枚举, 假设计算机处理每个状态的时间为t 秒, 则方法(1) 中一共需要128t 秒的时间, 而用本文的算
(页)
用了计算简单的模加运算。而且本文的方案基于椭圆曲线离散对数困难问题构造, 可以用较短的密钥实现基于离散对数的签名方案同等的安全性。表1给出了本文方案与文献[4]和文献[6]中的方案在委托、签名和验证阶段的各种运算的计算总量对比。有代理的有序多重签名方案的运算总量的对比情况大致相同, 在此不再赘述。假设在一次有代理的广播多重数字签名过程中, 共有n 个签名人, 其中有t 个代理签名人和n -t 个原始签名人参加了签名。
表1 本文方案与文献[4]和文献[6]方案的计算量对比运算类型模乘运算模幂运算求逆运算
本文方案7n +t+2
00
文献[4]方案7n+3t +310n+4t 0
文献[6]方案
15n+30n+1
ti onalC on f eren ce on Infor m ati on and Co mm un ication Securit y . Berli n:Spri nger Verlag , 1997:223-232.
(上接第269页)
法, 由上述表2和表3可知, 每个从进程需要计算16次目标函数值, 排序后, 从进程对于约束条件的计算最多需要4次, 即总共需要时间20t 秒的时间就可以得到最大值38。利用串行枚举法所需时间是本文算法的6倍多, 可见利用本文中的算法节省了大量的时间, 提高了运算效率。
表3 并行隐枚举法执行过程表
进程号
1
各个进程的状态{0, 0, 1, 1, 1, 1}
! ! {0, 0, 0, 1, 1, 0}{0, 1, 1, 1, {0, 1, 0, 1, {0, 0, 1, 1,
! ! {0, 1, 0, 0,
1, 1}
1, 1}1, 1}1, 0}
目标函数值
35! ! 15423735! ! 153934! ! 1646413938! ! 16
约束条件M
&
根据表1可以看出本文提出的方案较文献[4]的方案不仅模乘运算量要小而且省略大量的模幂运算, 较文献[6]的方案则主要体现在省略了较多的模乘运算和约n 次的求逆运算。所以本文提出的有代理的多重数字签名方案效率更高, 实用性更好。
2
&
4 结 论
本文研究了有代理的多重签名方案, 这种签名允许部分签名人委托其代理人进行签名, 在现实中比普通多重签名方案和代理多重签名方案有更广泛的应用。因此研究有代理的多重签名更具有应用价值, 而且有利于普通多重签名方案和代理多重签名方案的研究。然后本文基于椭圆曲线的离散对数困难问题提出了两个有代理的多重签名方案, 并对两个方案的安全性和效率做了详细的讨论。两个方案安全性较高、计算简单, 效率较好, 从理论上分析可知能抵抗系统攻击者的各种攻击。
3
{1, 0, 1, 1, 1, 1}{1, 0, 0, 1, 1, 1}
! ! {1, 0, 1, 1, 0, 0}{{{{1, 1, 0, 1, 1, 0, 1, 1, ! ! {1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
1,
1, 1, 0, 1}1}1}1}
&
4
&
0, 0}
4 结 论
0 1规划问题中, 变量数目较大时, 用串行计算是很难解决, 甚至不能得到解决。本文结合高性能并行计算和隐枚举法来解决这个问题, 并对隐枚举法进行了改进, 即按照目标函数值的大小进行排序, 每个从进程只需要按照顺序检查其变量组合的可行性, 得到的第一个可行解就是局部最优解, 然后局部最优解和全局最优解进行比较, 最终得到全局最优解。从上述实例中可以看到, 本文的算法确实提高了解题速度, 对于计算较大规模的题目具有一定的应用价值。但由于排序本身需要耗费一定的时间, 当规模较小时, 并不一定能够达到优化的目的, 而且对于规模较大时, 如何减少排序花费的时间仍然是一个值得探讨的问题。
参考文献
[1]Y L, i G B a, i G X iao . Proxy mu lti s i gnat u re sch e m e a n e w t ype of proxy
si gnat u re sche m e [J].E lectron ics Letters , 2000, 36(6):527-528. [2]王晓明, 符方伟. 一种代理多重数字签名方案的安全性分析[J].
通信学报, 2002, 23(4):98-102.
[4]鲁荣波, 何大可, 王常吉. 改进的代理多重签名方案[J].计算机应
用研究, 2007, 24(12):165-170.
[5]王连海, 王英龙. 基于DLP 的有代理的多重数字签名方案研究
[J ].通信学报, 2005, 26(12):37-42.
[2]K ob litz N. E lli p tic C urve Cryptos yste m [J ].M athe m atics of C o mpu t a
tion , 1987, 48:203-209.
[6]于成尊, 王彩芬, 刘军龙, 等. 基于椭圆曲线的有代理的多重签名
[J ].计算机应用研究, 2006, 23(10):113-115.
[7]王连海, 徐秋亮. 基于椭圆曲线密码体制的代理签名方案研究
[J ].计算机应用研究, 2004, 21(4):122-126.
[8]Sun H M , H sieh B T . On t he securit y of so m e proxy s i gnat u re sche m e
[EB /OL].h tt p://eprin t . iacr . org /2003/068.
[9]W ang G , Bao F , Zh ou J , Deng R H. S ecu ri ty anal ys i s of s o m e proxy
si gnat u res[A ].In f or m ati on S ecu ri ty C ryptology IC I S [C ].Sp ri ger V erlag , 2004, 305-319.
[10]纪家惠, 李大兴. 新的代理多签名体制[J ].计算机研究与发展,
2004, 41(4):715. 719.
[, D . P re /of I n
参考文献
[1]J I A M ei l. i M aster S lave Para ll elM i nd Evol uti on ar C o m pu tati on B ased
on M PI[J].Joutnal ofNort h U n i vers it y of ch i na(Nat u ral S ci en ce ED Iti on ) , 2007, 28.
[2]罗省贤, 何大可. 基于M P I 的网络并行计算环境及应用[M].成
都:西南交通大学出版社, 2001:104-197.
[3]黄旭东, 林鹭. 基于L i nux 集群的并行环境简单架设[J].计算机应
用研究, 2004(11):254-256.
[4]Q i n T ai gu , i Zhu H anye . An I mp roves I m p li cit Enum erati on M et hod
[J].三峡大学学报, 2007, 29(6).
[5]C ybenko G. Approx i m ati on s by Superpos iti ons of S ig m oi dal Fun cti on
M athe m l S ignals and , 1989(2):314.