求解SAT问题的改进粒子群优化算法

利用限制哆公式的相关理论将可满足性问题（SAT）等价转换为定义在{0,1}^n上的多项式函数优化问题,并将二进制粒子群优化算法（BPSO）与局部爬山搜索策略相结合,给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法（简称IBPSO）．数值实验表明,对于随机产生的3-SAT问题测试实例,该算法的计算结果均优于著名的WalkSAT算法和SATI．3算法．     

嵌入极值优化的混合粒子群优化算法

针对标准粒子群算法容易陷入局部极值和精度低的问题,提出一种嵌入极值优化算法的粒子群优化算法。在线性下降的惯性权重粒子群算法运行过程中,间隔一定迭代次数与极值优化算法相结合,利用其波动性增加种群的多样性,并有效结合粒子群算法较强的全局探索能力和极值优化算法精细的局部搜索性能,以较高精度收敛到全局极值。仿真实验结果表明,该混合算法是一种求解高维多峰连续函数极值的有效方法。     

求解无约束全局优化的改进的单填充函数法

填充函数法是一种求解多变量、多极值函数全局最优化的有效方法,这种方法的关键是构造填充函数。为此文中根据文献[1]的思想,考虑优化问题minf（x）x∈R^n,针对f（x）为局部Lipschirz连续函数,构造了一种简单的单填充函数,容易证明相对于传统的填充函数,该填充函数在参数较小时就能保持其填充性质,且全局收敛速度快。根据这个填充函数还提出了一个求解无约束优化问题的填充函数算法,对4个基准测试函数的数值试验表明该方法是有效的。     

求解无约束全局优化的改进的单填充函数法

填充函数法是一种求解多变量、多极值函数全局最优化的有效方法,这种方法的关键是构造填充函数.为此文中根据文献[1]的思想,考虑优化问题minf(x)x∈Rn,针对f(x)为局部Lipschitz连续函数,构造了一种简单的单填充函数,容易证明相对于传统的填充函数,该填充函数在参数较小时就能保持其填充性质,且全局收敛速度快.根据这个填充函数还提出了一个求解无约束优化问题的填充函数算法,对4个基准测试函数的数值试验表明该方法是有效的.     

基于微粒群优化算法的间歇过程迭代学习

在实际的间歇过程优化控制中面临着模型参数不确定性的问题,并且基于梯度的优化控制技术在处理具有多个局部极值的目标函数时,往往会陷入局部极值点.针对该问题,提出一种基于微粒群优化算法的间歇过程产品质量迭代学习策略.结合间歇过程产品质量控制问题的特点和各种约束条件,利用微粒群优化算法在非线性问题求解及大尺度空间搜索上的优势,...     

基于多峰函数优化的无线传感网稀疏事件检测

为提高无线传感网稀疏事件检测的实时性,提出一种基于多峰函数优化的压缩感知事件检测算法。该算法利用多峰函数最小化方法求解压缩感知检测算法中的欠定线性方程组问题。首先构造连续高斯函数对多峰目标函数进行逼近,而后通过求解连续函数的最优化问题得到多峰函数最小化的解。仿真实验表明新算法与以往的压缩感知检测算法相比,同一长度的事件向量,多峰函数最小化检测可在保证重构准确度的前提下有效缩短检测时间,而重构误差与经典算法基本一致。     

一类求解全局优化问题的F—C函数法

填充函数法和跨越函数法是两种求解多变量、多极值函数全局最优化的有效方法,这些方法的关键是构造填充函数或者跨越函数.为此结合全局优化问题的填充函数法和跨越函数法,考虑优化问题minf(x),针对f(x)为无Lipschitz连续函数,定义了一个求解全局优化问题的F-C函数.基于这个定义,提出了一类无参数的F-C函数.研究了所构造F-C函数的理论性质,并按照其理论性质提出了一个求解无约束优化问题的F-C函数算法.数值实验表明,所给的方法是有效的.     

求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

基于分组的启发式SAT新算法——DC&DS算法

目前提高求解SAT问题完全算法的计算效率问题已成为挑战性研究问题。提出了一种基于启发式分组的SAT完备算法。启发式分组策略将一个全局搜索问题,转为局部搜索问题。并将该策略引入到结合BDD与SAT算法的形式验证中,与一般的启发式SAT算法相比,该算法在求解速度和求解问题的规模等方面都明显地改进了,实验结果表明了该算法的可行性和有效性。     

直接搜索模拟退火算法的自适应改进

针对直接搜索模拟退火算法求解高维优化问题存在稳定性差、收敛成功率低现象,提出一种自适应的直接搜索模拟退火算法。该算法通过构造基于迭代温度动态调整搜索范围的新点产生方式和自适应寻优模块,增强了算法跳出局部极值和加快邻域搜索的能力,利用柯西分布状态发生函数的大范围遍历特点,弥补了直接搜索模拟退火算法求解高维多峰值问题易陷入局部解和计算效率低的不足。结合可行规则法处理约束问题,典型高维函数和工程优化设计实例的测试结果表明,该算法能够有效求解高维优化问题,整体性能较直接搜索模拟退火算法有显著提高。     

社会认识优化在非线性规划问题中的应用

社会认识优化(Society Cognitive Optimization,SCO)是一种基于社会认知理论提出的模拟人类社会的演化算法.社会认识优化是通过竞争选择和领域搜索来模拟社会认知理论中的社会学习能力,用代理来代表社会中的人,用知识库来代表社会中的知识,通过代理与知识库之间不断的交互来模拟人类的社会学习过程,从而达到优化学习的目的.命题逻辑中合取范式的可满足性(Satisfyability,SAT)问题是当代理论计算机科学的核心问题,是一典型的NP完全问题.可满足性问题的有效解决有着重要的理论意义和实际应用价值.文中将社会认识优化算法应用于求解可满足性问题,得到了比较满意的结果.     

基于粒子群优化的非平滑非负矩阵分解算法

传统的非平滑约束的非负矩阵分解算法(nsNMF)在处理高光谱数据时,存在对初始值敏感、容易陷入局部最优值等缺陷。为此,提出一种基于粒子群优化(PSO)的nsNMF算法。采用传统nsNMF算法迭代的结果作为初始值,以避免PSO的盲目搜索。通过PSO搜索端元光谱矩阵,利用nsNMF算法更新端元光谱矩阵和丰度矩阵,以缩小搜索空间,降低计算复杂度,避免陷入局部最优。在合成数据集和真实数据集上的实验结果表明,与传统nsNMF算法相比,该算法能获得更好的全局最优解,端元光谱和丰度值更接近真实值。     

Distributed SAT

We present DPLL ABT, a distributed Satisfiability solver (SAT) (Ansótegui and Manyà in IberoAm J Artif Intell 7(20):43–56, 2003) designed to solve distributed SAT problem instances. Since SAT is a particular case of constraint satisfaction, we propose a solving method based on the Asynchronous Backtracking algorithm (ABT) (Yokoo et al. in IEEE Trans Knowl Data Eng 10(5):673–685, 1998) developed for distributed constraint reasoning. In addition, we have applied the Davis-Putnam procedure (DPLL) in every agent, plus the minimum conflict heuristic in case DPLL does not detect any inconsistency. The resulting algorithm improves the performance in terms of communication cost and computational effort versus the basic ABT. The SAT instance is distributed into agents, which cooperate to solve SAT instances just sharing the minimum information. We also present the experimental results that demonstrate the performance of the method in terms of communication and execution time comparing the performance with the basic ABT algorithm.     

改进的模糊C-均值聚类算法

为了克服模糊C-均值（FCM）聚类算法易陷入局部极小值和对初始值敏感的缺点,提出了一种基于改进量子蚁群的模糊聚类算法。将量子计算原理和蚁群算法相结合来改进FCM算法。初期采用量子遗传算法生成信息素分布,后期利用蚁群算法的全局搜索性、并行计算性等特点避免聚类陷入局部最优解。实验证明该算法保证了种群的多样性,有较好的全局收敛性,克服了模糊C-均值聚类算法的不足,能有效解决未成熟收敛的问题,使聚类问题最终快速、有效地收敛到全局最优解。     

基于改进的遗传算法求解可满足性问题

遗传算法(GA)是由Holland提出的一种基于进化论的仿生算法,非常适于求解最优化问题.为了更好地利用SGA求解SAT问题,在将SAT问题等价转换为{0,1}n上的多项式是否存在零点的判断问题基础上,将局部搜索算法(LSA)与SGA相结合,给出一种求解3-SAT问题的改进混合遗传算法(MHGA),并通过对随机大规模3-SAT问题实例的实际求解验证了MHGA的可行性与有效性.     

DSM中一种新型Cache一致性管理算法

存储器一致性管理是分布式共享存储器ＤＳＭ（ｄｉｓｔｒｉｂｕｔｅｄｓｈａｒｅｄｍｅｍｏｒｙ）系统的一个重要问题．在基于目录和所有者管理一致性的ＤＳＭ系统中,如何适时地更新所有者链表以及目录中关于所有者的信息是缩短查表时间的关键．本文介绍一种新型的链表更新算法的设计及其性能分析．分析表明,这种方案对维护存储器一致性来说,具有较灵活的适应性并有助于缩短查表时间,提高系统性能．该算法也可适用于树形层次结构的一致性管理方案．     

高阶Hopfield神经网求解合取范式可满足性问题

本文提出用高阶Ｈｏｐｆｉｅｌｄ神经网络求解ＳＡＴ问题，给出了连续及离散高阶神经网络模型与相应的离散快速求解算法，证明了网络的稳定性，并用实验证明了该方法的可行性，且将该算法与Ｌｏｃａｌ Ｓｅａｒｃｈ算法进行了比较。     

高精度时变参数模型谱估计及应用

现有时变自回归(TVAR)模型参数谱估计容易导致谱峰漂移。针对该问题,提出一种基于组合目标函数和遗传算法的TVAR参数估计方法,并将之应用于飞行器结构响应序列的建模及谱估计。通过U-C算法获得TVAR模型参数的初始估计;依据现代谱估计理论结合连续函数极值存在的必要条件,推导模型参数的频域约束条件并构造组合目标函数;采用遗传算法对模型参数初始估计值进行优化。应用结果证明了该方法的有效性。