增强型群论优化算法求解折扣{0-1}背包问题

群论优化算法(GTOA)是基于群论方法提出的一个离散演化算法,非常适于求解以整型向量为可行解的组合优化问题。为了进一步提高GTOA求解折扣{0-1}背包问题(D{0-1}KP)的性能,首先指出了它的随机线性组合算子(RLCO)未能充分考虑当前个体位置信息的不足,基于个体基因保留策略对其进行改进。然后,在随机反向变异算子(IRMO)中引入增强0分量变异策略,用于处理因个体0分量无法及时变异而导致的解的质量下降、种群多样性降低等问题。在改进上述两个算子的基础上,提出了增强型GTOA(EGTOA),并基于它给出求解D{0-1}KP的新方法。随后,将改进策略应用于二进制GTOA(GTOA-2),提出了增强型GTOA-2(EGTOA-2)及其求解D{0-1}KP的新方法。为了验证EGTOA和EGTOA-2的性能提高程度与优异性,分别利用它们求解四类大规模D{0-1}KP实例,通过与GTOA、GTOA-2以及求解D{0-1}KP的已有8个最先进算法的比较表明:EGTOA和EGTOA-2求得最优解的能力比GTOA和GTOA-2提高了至少1.14倍,比8个最先进算法提高了5%~60%,它们的平均性能比GTOA、GTOA-2以及8个最先进算法的性能更佳。因此,EGTOA和EGTOA-2是当前求解D{0-1}KP的最佳算法。

基于随机背包的公钥密码

该文构造了一个背包型公钥密码算法。该背包公钥密码具有如下优点:加解密只需要加法和模减法运算,因此加解密速度快;该算法是基于随机背包问题而不是易解背包问题而构造的;证明了在攻击者不掌握私钥信息情况下该密码算法能抵抗直接求解背包问题的攻击,包括低密度攻击和联立丢番图逼近攻击等;证明了攻击者能够恢复私钥信息与攻击者能够分解一个大整数是等价的。分析表明,该算法是一个安全高效的公钥加密算法。

随机背包公钥密码的分析与改进

针对随机背包公钥密码方案,提出一种私钥恢复攻击方法。发现Wang等人所构造的随机背包公钥方案实际上是隐含使用了一个特殊的超递增背包。通过使用普通超递增背包代替该特殊超递增背包,将超递增背包隐藏在随机选择的背包中,对原方案进行了改进,提出一种新的基于中国剩余定理的背包公钥密码方案。改进后的方案消除了原方案存在的设计缺陷,能够抵抗针对原方案提出的格规约攻击、低密度攻击以及shamir攻击。

求解随机时变背包问题的确定性算法

随机时变背包问题(RTVKP)是智能计算领域中的一个动态组合优化问题,具有重要的理论与应用价值.对于背包载重随机变化的RTVKP问题(记为RTVKP3),首先利用改进的动态规划法提出了一种适于求解具有较小物品价值和较大背包载重的RTVKP3的确定性算法(记为MDP-RTVKP),给出了MDP-RTVKP可成功求解RTVKP3的必要条件;然后,基于MDPRTVKP和DPforRTVKP的不同适用性提出了一种适于求解任意RTVKP3实例的有效方法 GenericDPfRTVKP,并通过对大规模RTVKP3实例的仿真计算验证了GenericDPfRTVKP的通用性与高效性.

求解0-1背包问题的改进混合遗传算法

针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作.在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与HGA算法进行实验对比分析,并研究了变异概率对新算法性能的影响.实验结果表明新算法收敛速度快,寻优能力强.

基于Euler-fermat小定理实现的背包公钥密码体系

提出一种基于欧拉和费尔玛小定理实现的背包公钥密码体系,且给出算法和算例,算例说明算法操作简易无需计算乘法逆元、由欧拉和费尔玛小定理实现的背包公钥密码体系有较强的安全性．

一种求解多背包问题的改进的人工鱼群算法

多背包问题是优化领域中典型的NP难题,传统算法由于计算复杂性高或收敛速度慢等缺点,结果往往不能令人满意。针对上述问题提出了一种求解多背包问题的改进的人工鱼群算法(IAF-SA)。首先将多背包放入方式整数编码,其次对不可行人工鱼编码、不充分人工鱼编码采用"随机修复"策略进行修复,并对人工鱼群算法(AFSA)中觅食、聚群和追尾等行为和产生的人工鱼编码进行改进和修复,最后结合实验对IAFSA算法分析和检验。实验结果表明,求解多背包问题的IAFSA算法相对其它算法不仅具有更快收敛速度和更强鲁棒性,而且以较大的概率收敛于原问题的最优解。

基于加法运算实现的两类新背包公钥密码体系

背包公钥体系的研究一直是密码学研究中的活跃领域．文章根据Merkle-Hellman背包公钥体系构造思想基于加法运算利用随机向量实现了两种新的背包公钥密 码体系,新体系无需求乘法逆元,但较MH-KPKC安全性更强,计算量更小,更易操作．

基于混沌系统的椭圆曲线密码算法研究

通过Chebyshev多项式产生的伪随机数,简化了背包密码体制,同时将背包密码体制与椭圆曲线密码体制结合,产生了一种新型椭圆曲线密码算法,通过对该算法的分析,认为算法简单,安全性高,方案可行。

求解0-1背包问题的量子狼群算法

针对0-1背包问题,在基本狼群算法的基础上,提出了量子狼群算法.借鉴量子编码方式,定义了种群中粒子的概率位置和准确位置,通过量子旋转门控制人工狼概率位置向全局最好位置逼近,然后以量子塌缩实现了概率位置向准确位置的映射,兼顾了算法的导向性与随机性.选取了8个经典0-1背包问题与3个高维背包问题进行了测试,并与其他算法进行比较,实验结果表明,量子狼群算法能够有效搜索全局最优解,特别是在高维背包问题中具有较好性能.

基于加法及Matthews混沌实现的背包公钥密码体系

研究Matthews混沌系统构造随机向量的方法,且利用随机向量实现一种新的基于加法的参与背包公钥密码体系。该密码体系无需求乘法逆元,计算量小容易操作,因混沌随机向量的完全性更强。

求解0-1背包问题的改进离散和声搜索算法

提出一种求解0-1背包问题的改进离散和声搜索算法(IDHS).该算法应用分布估计算法的概率思想,设计自适应调整策略,提高算法的搜索能力.引入精英培养机制,加强精英和声的开发,提高算法逃离局部最优的概率.通过随机修复方法和置换策略来改善和声的可行性,增加解的多样性.对背包问题进行测试,结果验证了IDHS算法的有效性.

一种新型量子演化算法及其应用研究

针对传统演化算法难以模拟量子物理特性的难题,提出一种新型量子演化算法模型。采用将进化算法与量子计算相结合的方法,在常规染色体结构上附加随机干涉,从数理角度模拟量子计算的叠态、纠缠等特性。将其应用于解决多维背包问题,实验结果表明,该算法能增加种群的基因多样性,并提高全局优化能力。

两种基于欧拉定理的背包概率加密体制

本文根据欧拉定理对背包加密体制进行了改进,为了防止破译,采取了变形序列,将超递增序列转化为非超递增的伪随机序列,使得每次加密的密文都不同,加大了破译密文的难度.从而提高了背包加密体制的安全性.