一种新的背包加强算法

背包问题是著名的NP问题,因此它一度成为密码学界的研究热点。由最初的Merkle-Hellman背包算法到后来的Chor-Rivest背包算法,但很多算法都相继被破译。本文提出了一种加强背包算法,具有操作简易性和较强的安全性,可以运用于网络通信加密系统。     

对一种新的背包加强算法的破解

自从Shamir提出攻击Ralph Merkle和Martin Hellman背包密码系统的算法以来，背包密码系统在算法设计上进行了改进，使其在改进后能抵挡Shamir攻击。但由于自身算法设计上可能存在缺陷，其中有一些改进后的背包密码系统会带来新的安全问题。本文是关于一篇题为《一种新的背包加强算法》（注：发表于《电脑与知识》第2004．29期）一文中提出的背包密码算法的破解算法。     

对一种新的背包加强算法的破解

自从Shamir提出攻击RalphMerkle和MartinHellman背包密码系统的算法以来,背包密码系统在算法设计上进行了改进,使其在改进后能抵挡Shamir攻击。但由于自身算法设计上可能存在缺陷,其中有一些改进后的背包密码系统会带来新的安全问题。本文是关于一篇题为《一种新的背包加强算法》(注:发表于《电脑与知识》第2004.29期)一文中提出的背包密码算法的破解算法。     

一种基于多背包的密码算法

本文介绍了背包问题和L3-格基约简算法并加以深刻的分析,在此基础上提出了一种基于多背包的加密算法,该算法大大加强了背包加密算法的安全性,可以有效的对抗L3-格基约简算法。     

背包问题的一种自适应算法

背包问题是经典的NP-hard组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法,利用归并原理和4个非平衡的子表,提出一种求解该问题的自适应算法,算法可根据计算资源和问题实例规模的大小,允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4),在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明,自适应算法可显著扩大背包实例的求解规模,从时间和空间上改进背包问题现有算法的性能．     

一种基于背包公钥的语音信息隐藏算法

针对在传输语音秘密信息过程中存在破坏或窃取的问题,提出一种鲁棒性较强的信息隐藏方法。把一段语言作为秘密信息隐藏到宿主音频中,在公共信道中传递秘密信息。该算法是根据人类听觉系统在小波域中嵌入秘密信息,并且利用背包公钥可以使隐藏的信息具有加密功能。对于外界的噪声、压缩、滤波干扰有很强的抗干扰能力。     

一种新的求解0-1背包问题的混合算法

该文汲取了蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种求解0-1背包问题的混合型算法,该算法充分利用了前者的搜索能力和后者的种群多样性。仿真实验对算法的部分参数进行了分析,并与其他文献的算法进行比较,结果表明,该算法是一种具有较高性能的混合优化算法。     

对二元一次不定方程背包方案的格攻击

研究分析背包密度大于0.9408的背包密码方案的安全性非常重要. 针对基于二元一次不定方程的难解函数的新型背包公钥密码算法, 由公钥和密文构造一个格来攻击该方案, 通过采用NTL库验证上述格攻击算法的效率, 从而证明了该攻击方法的有效性. 进而说明此新型背包公钥密码体制是不安全的.     

对一种背包公钥密码改进方案的安全性分析

背包公钥密码算法是比较热门的加密算法之一,目前仍有很多密码研究者在研究背包公钥密码的改进算法。文献[1]提出了两个改进的背包公钥密码方案,本文对这些改进算法进行了安全性分析,并就其中一个方案进行了格规约攻击。通过计算实验说明这种改进之后的背包公钥密码算法仍然是不安全的。     

一种新的求解MMKP问题的ACO&PR算法

针对多选择多维背包问题(MMKP)的特点,设计一种新型混合算法(ACO＆PR).该算法将线路重连算法(PR)嵌入蚁群算法(ACO),在搜索过程中既考虑解的质量,又考虑解的分散性.线路重连算法在重连过程中,向导解的属性逐步引入起始解属性中,可快速获得该线路上的最优解.实验结果表明,该算法优于其他现有较好的方法,获得了较好的结果.     

A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems

Multidimensional knapsack problem (MKP) is known to be a NP-hard problem, more specifically a NP-complete problem, which cannot be resolved in polynomial time up to now. MKP can be applicable in many management, industry and engineering fields, such as cargo loading, capital budgeting and resource allocation, etc. In this article, using a combinational permutation constructed by the convex combinatorial value \(M_j=(1-\lambda ) u_j+ \lambda x^\mathrm{LP}_j\) of both the pseudo-utility ratios of MKP and the optimal solution \(x^\mathrm{LP}\) of relaxed LP, we present a new hybrid combinatorial genetic algorithm (HCGA) to address multidimensional knapsack problems. Comparing to Chu’s GA (J Heuristics 4:63–86, 1998), empirical results show that our new heuristic algorithm HCGA obtains better solutions over 270 standard test problem instances.     

An improved firefly algorithm for solving dynamic multidimensional knapsack problems

There is a wide range of publications reported in the literature, considering optimization problems where the entire problem related data remains stationary throughout optimization. However, most of the real-life problems have indeed a dynamic nature arising from the uncertainty of future events. Optimization in dynamic environments is a relatively new and hot research area and has attracted notable attention of the researchers in the past decade. Firefly Algorithm (FA), Genetic Algorithm (GA) and Differential Evolution (DE) have been widely used for static optimization problems, but the applications of those algorithms in dynamic environments are relatively lacking. In the present study, an effective FA introducing diversity with partial random restarts and with an adaptive move procedure is developed and proposed for solving dynamic multidimensional knapsack problems. To the best of our knowledge this paper constitutes the first study on the performance of FA on a dynamic combinatorial problem. In order to evaluate the performance of the proposed algorithm the same problem is also modeled and solved by GA, DE and original FA. Based on the computational results and convergence capabilities we concluded that improved FA is a very powerful algorithm for solving the multidimensional knapsack problems for both static and dynamic environments.     

A new exact algorithm for concave knapsack problems with integer variables

Concave knapsack problems with integer variables have many applications in real life, and they are NP-hard. In this paper, an exact and efficient algorithm is presented for concave knapsack problems. The algorithm combines the contour cut with a special cut to improve the lower bound and reduce the duality gap gradually in the iterative process. The lower bound of the problem is obtained by solving a linear underestimation problem. A special cut is performed by exploiting the structures of the objective function and the feasible region of the primal problem. The optimal solution can be found in a finite number of iterations, and numerical experiments are also reported for two different types of concave objective functions. The computational results show the algorithm is efficient.     

一种新的改进OPTA细化算法

深入研究改进的OPTA细化算法,针对已有算法中存在细化后毛刺较多的问题,提出了一个新的改进OPTA细化算法。该算法在原有细化算法的基础上,根据纹线角度和弯曲方向的不同采用不同的细化顺序,并修改了消除模板,改进了保留模板的去除情况。大量实验表明,该算法在继承原有算法优点的基础上显著地减少了细化后的毛刺,是一种较为理想的细化算法。     

An improved monkey algorithm for a 0-1 knapsack problem

The 0-1 knapsack problem is a classic combinational optimization problem. However, many exiting algorithms have low precision and easily fall into local optimal solutions to solve the 0-1 knapsack problem. In order to overcome these problems, this paper proposes a binary version of the monkey algorithm where the greedy algorithm is used to strengthen the local search ability, the somersault process is modified to avoid falling into local optimal solutions, and the cooperation process is adopted to speed up the convergence rate of the algorithm. To validate the efficiency of the proposed algorithm, experiments are carried out with various data instances of 0-1 knapsack problems and the results are compared with those of five metaheuristic algorithms.     

An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem

This paper presents an improved fruit fly optimization algorithm (IFFOA) for solving the multidimensional knapsack problem (MKP). In IFFOA, the parallel search is employed to balance exploitation and exploration. To make full use of swarm intelligence, a modified harmony search algorithm (MHS) is proposed and applied to add cooperation among swarms in IFFOA. In MHS, novel pitch adjustment scheme and random selection rule are developed by considering specific characters of MKP and FOA. Moreover, a vertical crossover is designed to guide stagnant dimensions out of local optima and further improve the performance. Extensive numerical simulations are conducted and comparisons with other state-of-the-art algorithms verify that the proposed algorithm is an effective alternative for solving the MKP.     

一种新型粒子群改进遗传算法

传统优化算法均存在各种局限,无法同时满足性能优良算法的几个标准:不容易陷入局部最优解、收敛速度较快、具有框架性及可结合性。在传统粒子群与遗传算法的基础上,结合其他常用算法,提出一种新型混合智能优化算法——粒子群改进遗传算法。该算法在变异环节、交叉环节、淘汰环节中引入许多其他算法的优点加以改进。最后,通过修正某控制系统的控制参数验证了新算法相对于传统单一优化算法的先进性。