一个SAT问题有解的充要条件

合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路.     

利用正交方法解SAT问题

提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路.     

基于混合蚁群遗传算法的SAT问题求解

根据SAT问题的特点,通过分析传统蚁群算法和遗传算法在求解SAT问题上的不足,提出一种基于混合蚁群遗传算法的SAT问题求解方法。给出一种新的初始解的生成方式;在迭代过程中,根据较优解的累积信息提出进化算子;利用当前得到的最优解,通过改变不满足子句中文字的取值,增加变异算子。最后选取标准测试集中的20个实例对算法进行测试,实验结果表明:改进后的算法通常仅通过较少次数的迭代就能找到解,能够有效避免蚁群算法和遗传算法过早收敛的缺点,具有较强的寻优能力。     

一种求解难SAT问题的改进DP算法

DP算法是求解SAT问题的最有效完全算法之一，论文分析和讨论了DP算法中的各种分枝文字策略，并基于对不满足解数估计的方法，提出了一个有效的分枝文字策略，实验结果表明，提出的改进DP算法对难SAT实例有较好的平均性能。     

基于改进微分进化算法的机构综合新方法

针对机构综合的非线性方程组求解问题提出了一种改进的微分进化算法.该算法是将方程组转换成一个优化问题,在进化过程中,该算法根据进化情况采用动态参数调整机制提高算法的搜索效率,并且对种群重叠状况进行实时监视,对重叠个体利用混沌搜索策略来进一步提高算法的全局寻优能力.机构综合实例结果分析表明,文中提出的改进微分进化算法高效、且全局寻优能力强.     

基于混合蛙跳算法的背包问题求解

混合蛙跳算法(SFLA)是一种全新的后启发式群体进化算法,具有高效的计算性能和优良的全局搜索能力.背包问题是一个典型的 NP完全问题.首先建立了背包问题基于 0/1规划的数学模型,阐述了混合蛙跳算法的基本理论.针对离散搜索空间,提出了SFLA的改进算法,应用该算法解决了背包问题.在实例上的运行结果表明本文方法的可行性和有效性.     

基于粒子群统计规律的PSO算法

粒子群优化（particle swarm optimization，PSO）算法是一类基于群体智能的全局优化算法，以其计算迅速和易于实现而得到广泛的应用．但作为一种进化算法，它在很多问题中却容易过早收敛，陷入早熟．这与粒子群采用单一的进化策略有关，因为过于单一的进化策略使粒子群整体上有一种趋同性．针对标准PSO算法的这个问题提出了一种改进方法，改进后的PSO-σ算法实质上是Kennedy讨论过的认知模型、社会模型和完全模型的混合算法．从算法的收敛性、准确性和稳定性等方面对这种改进的算法作了试验和分析，发现均优于标准PSO算法．     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

大规模多目标进化优化算法研究进展

现实中存在许多大规模多目标优化问题（Large-scale Multi-objective Optimization Problem,LSMOP）,它们对传统的多目标进化算法（Multi-objective Evolutionary Algorithm,MOEA）提出了挑战,有关LSMOP的研究已成为多目标优化领域的研究热点之一。本文系统分析了近年来提出的各种大规模多目标进化优化算法（Large-scale Multi-objective Optimization Evolutionary Algorithm,LSMOEA）,根据这些算法的主要思想和技术特点将它们粗略地分成4种类型,即基于协同进化（Cooperative Coevolution,CC）、基于决策变量分析、基于问题重构以及其他方法,并对今后LSMOP的研究方向提出建议,以期将LSMOP的研究引向深入。     

MARG-MU（2）的结构和复杂度

SAT问题（可满足性问题）是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向。本文主要利用（1,＊）-消解方法研究了差为2的边缘极小不可满足公式集（MARG-MU（（2））的结构和复杂度：在结构方面,胁MARG—MU（2）中的公式要么是F2^2,要么是某一文字在其中仅出现一次的公式;在复杂度方面,如果MARG-MU（2）对（1,＊）-消解封闭,则某个含有,1个变元和n＋2个子旬的公式是否为MARG-MU（2）中的公式的问题可以在时间O（n^3）内被判定。     

基于人类进化算法的背包问题求解方法

背包问题是计算机算法中的一个NP完备类困难问题,使用传统的优化方法在求解较大规模的背包问题时,都存在计算量大、迭代时间长的缺陷．人类进化算法是模拟人类进化机理而建立的一种智能优化算法,本文阐述了人类进化算法的基本原理和实现方法．为提高背包问题的求解速度和精度,将人类进化算法应用于背包问题的求解,演示了算法的工作过程．试验结果表明,使用该方法求解背包问题是完全可行的和有效的,与众多优化算法相比,人类进化算法具有更高的求解效率．     

基于学习的GSAT算法

在GSAT算法的基础上，引进学习的概念，设计了一种新的SAT求解算法，用若干DIMAC的测试实例进行了仿真实验研究，比较了基于学习的GSAT算法与著名的Random Walk GSAT算法，结果表明两种算法对于随机SAT的实例比较有效，但对于Real-World SAT的实例性能较差。     

Memetic算法及其在分类中的应用研究

群体智能优化算法Memetic算法(Memetic Algorithm,MA)采用进化算法的操作流程,引入局部搜索算子,使其在问题的求解中保证较高收敛性能的同时又能获得较高质量的解,克服了遗传算法等传统全局优化算法易"早熟"的问题,同时避免陷入局部解。在MA框架基础上,提出了全局动态适应MA算法,采用遗传算法为全局搜索算子,k-means算法为局部搜索算子。使用Java语言实现算法并对UCI中分类实验数据集进行测试,结果表明,将遗传算法和k-means结合的全局动态适应MA在分类问题中具有较高准确率。     

基于演化算法的SAT问题求解

演化计算方法是近年来迅速发展起来的一种全新随机搜索和优化方法.首先介绍了演化算法的基本原理,然后给出了基于演化思想求解著名逻辑学问题——布尔可满足问题(SAT)的过程,最后分析了该方法的主要特点.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

低维函数的快速优化算法

基于群体的进化算法是求解函数优化问题的常用方法,但存在收敛速度慢和易陷入早熟的缺点．提出了一个基于（1＋1）-ES分块进化的低维函数优化算法,采用分块进化,引入丢弃不重要分块和二次优化求精的策略,实现了全局搜索过程和局部搜索过程的分离．通过算法分析,表明了算法比较适合于低维函数．仿真结果表明了提出的算法的抗早熟能力和求解效率均优于FEP．     

带断层约束的Delaunay三角剖分混合算法

三角剖分是构建高精度数字高程模型(DEM)的基础,在各个领域都有广泛的应用。特别是在约束数据域下的Delaunay三角剖分更具有重大的研究价值,前人已经做了大量的工作,并提出了一系列经典的剖分算法。在对传统算法进行研究与分析后,总结了传统算法的优缺点,结合了逐点插入法、三角网生长法以及分治法的思想,提出了一种高效的、带断层约束的Delaunay三角剖分混合算法。该算法在建立无约束的DT(Delaunay Triangulation,DT)网格的基础上通过嵌入加密后的断层数据来实现带断层约束的CDT(Constrained Delaunay Triangulation,CDT)网格。通过实例比较,说明了混合算法在构网质量和时间效率上都优于传统算法。     

基于压缩感知的无线传感器网络节点定位算法

为了得到有效的、通用的定位算法,提出了两种新的定位算法——基于压缩感知的无线传感器网络节点定位算法（NLCS）及其改进算法（INLCS）.NLCS算法利用压缩感知和加权质心算法进行节点位置估计.提出了伪跳数以改进NLCS算法,提升了算法的定位性能.这两种算法解决定位问题必须满足3个条件,使其更适合于实际应用.仿真结果表明,相对于LSRC和LSVM定位算法,这两种算法有更好的定位性能.