量子Grover算法及其应用

深入剖析了G rover算法,最后将其应用于经典密码学,对序列密码和分组密码等进行了攻击和分析.     

Combining a Local Search and Grover’s Algorithm in Black-Box Global Optimization

Grover’s quantum algorithm promises a quadratic acceleration for any problem formulable as a search. For unstructured search problems, its implementation and performance are well understood. The curse of dimensionality and the intractability of the general global optimization problem require any identifiable structure or regularity to be incorporated into a solution method. This paper addresses the application of Grover’s algorithm when a local search technique is available, thereby combining the quadratic acceleration with the acceleration seen in the multistart method. The author thanks Dr. Bill Baritompa for helpful discussions.     

Implementing Pure Adaptive Search with Grover's Quantum Algorithm

Pure adaptive search (PAS) is an idealized stochastic algorithm for unconstrained global optimization. The number of PAS iterations required to solve a problem increases only linearly in the domain dimension. However, each iteration requires the generation of a random domain point uniformly distributed in the current improving region. If no regularity conditions are known to hold for the objective function, then this task requires a number of classical function evaluations varying inversely with the proportion of the domain constituted by the improving region, entirely counteracting the PAS apparent speedup. The Grover quantum computational search algorithm provides a way to generate the PAS iterates. We show that the resulting implementation, which we call the Grover adaptive search (GAS), realizes PAS for functions satisfying certain conditions, and we believe that, when quantum computers will be available, GAS will be a practical algorithm.     

半无限规划的一阶最优性条件和牛顿型算法

在Fischer-Burmeister非线性互补函数的基础上,得到了半无限规划问题的一个新的一阶必要条件,并将半无限规划问题转化成一个光滑的无约束优化问题,给出了适合该问题的一个Damp-Newton算法,数值例子表明:算法结构简单,数值计算有效.     

基于非线性相位恢复的X射线相位衬度断层成像算法

对全息测量下的X射线相位衬度断层成像问题提出了一种新的重建算法．该算法的主要想法是利用牛顿迭代法求解非线性的相位恢复问题．我们证明了牛顿方向满足的线性方程是非适定的,并利用共轭梯度法得到方程的正则化解．最后利用模拟数据进行了数值实验,数值结果验证了算法的合理性以及对噪声数据的数值稳定性,同时通过与线性化相位恢复算法的数值结果比较说明了新算法对探测数据不要求限制在Fresnel区域的近场,适用范围更广．     

Cluster Analysis for Large Datasets: An Effective Algorithm for Maximizing the Mixture Likelihood

Abstract

The primary model for cluster analysis is the latent class model. This model yields the mixture likelihood. Due to numerous local maxima, the success of the EM algorithm in maximizing the mixture likelihood depends on the initial starting point of the algorithm. In this article, good starting points for the EM algorithm are obtained by applying classification methods to randomly selected subsamples of the data. The performance of the resulting two-step algorithm, classification followed by EM, is compared to, and found superior to, the baseline algorithm of EM started from a random partition of the data. Though the algorithm is not complicated, comparing it to the baseline algorithm and assessing its performance with several classification methods is nontrivial. The strategy employed for comparing the algorithms is to identify canonical forms for the easiest and most difficult datasets to cluster within a large collection of cluster datasets and then to compare the performance of the two algorithms on these datasets. This has led to the discovery that, in the case of three homogeneous clusters, the most difficult datasets to cluster are those in which the clusters are arranged on a line and the easiest are those in which the clusters are arranged on an equilateral triangle. The performance of the two-step algorithm is assessed using several classification methods and is shown to be able to cluster large, difficult datasets consisting of three highly overlapping clusters arranged on a line with 10,000 observations and 8 variables.     

求总极值问题的最优性条件

郑权提出了求总极值问题的积分－水平集的概念性算法,同时给出了最优性条件。本文提出了修正的积分－水平集算法,并且给出了类似的总极值存在的最优性条件。     

基于模矢搜索和遗传算法的混合约束优化算法

近年,免梯度方法又开始引起大家的注意，由于不需要计算函数的梯度．特别适合用来求解那些无法得到梯度信息或需要花很大计算量才能得到梯度信息的问题．本文构造了一个基于模矢搜索和遗传算法的混合优化算法．在模矢搜索方法的搜索步，用一个类似于遗传算法的方法产生一个有限点集．算法是全局收敛的.     

整数规划的布谷鸟算法

布谷鸟搜索算法是一种新型的智能优化算法．本文采用截断取整的方法将基本布谷鸟搜索算法用于求解整数规划问题．通过对标准测试函数进行仿真实验并与粒子群算法进行比较,结果表明本文所提算法比粒子群算法拥有更好的性能和更强的全局寻优能力,可以作为一种实用方法用于求解整数规划问题．     

有时间窗装卸问题的多策略分组编码遗传算法

根据有时间窗装卸问题(PDPTW)的数学模型,设计了多策略分组编码遗传算法,将禁忌思想用于产生可行解的启发式插入算法之中,对计算实例进行了求解,结果表明,此算法可以有效求得有时间窗装卸问题的近似最优解.     

建立在割线条件上的新Liu-Storey型共轭梯度法的全局收敛性(英文)

我们基于拟牛顿法的割线条件提出两种LS型共轭梯度法.有趣的是,我们提出的方法中对于βk的计算公式与戴和廖[3]提出的有相似的结构.但是,新方法能够在合理的假设下保证充分下降性,这一点是戴-廖方法所不具备的.在强Wolfe线搜索下,给出了新方法的全局收敛结果.数值结果论证了该方法的有效性.     

The theoretic design of NMR pulses program of arbitrary N-qubit Grover’s algorithm and the NMR experiment proof

Grover’s quantum searching algorithm is most widely studied in the current quantum computation research, and has been implemented experimentally by NMR (Nuclear Magnetic Resonance) technique. In this article, we design arbitrary N-qubit NMR pulses program of Grover’s algorithm based on the multiple-quantum operator algebra theory and demonstrate 2-qubit pulses program experimentally. The result also proves the validity of the multiple-quantum operator algebra theory     

带有动力学条件的高维一相Stefan问题

本文我们证明了带有动力学条件的高维一相Ｓｔｅｆａｎ总题局部古典解的存在唯一性。     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

带服务优先级车辆路径问题的扫描禁忌搜索算法

提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

The Gradient Theory of the Phase Transitions with Dirichlet Boundary Condition

§ 1.Introduction　 In this paper,we study the asymptotic behavior of minimizers{ uε} ε>0 (ε→ 0 ) of thevariational probleminf∫Ω[εp- 1 | Du| p + 1εW(x,u) ] dx:u∈ W1 ,p(Ω ) ,u =g,x∈ Ω (Pε)where p>1 ,N≥ 2 ,andΩ RN is a bounded open domain with Ω∈C2 .　 This kind of problems comes from the theory of phase transitions and are widelystudied in recent years.In [1 ]— [1 4] ,the authors investigated these problems underthe integral constraint∫Ωudx =constant,In [1 5]— [1 6] ,…     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

遗传算法的物理解释

提出了一种理想化的模拟仿生搜索算法——扰动算法 ,以此方法为基础 ,分析了遗传算法的搜索过程和效率问题 ,阐明了遗传算法作为一种次优算法的有效性 .相对于遗传算法的生物解释 ,本文给出了相应的物理解释 .同时 ,本文为遗传算法、进化策略和模拟退火算法找到了一种统一的物理解释 ,揭示了这些重要的仿生类算法实质上的相似性 .     

不等式约束最优化的一个使用非单调搜索的可行算法

对不等式约束最优化问题本文提出了一个新算法。算法使用了非单调搜索,它不仅放松了每步迭代中对搜索的限制,而且使得算法迭代到一定阶段后具有非常简洁的形式,在不需要严格互补条件的较弱假设下,算法是整体和超线性收敛的。