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

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

求解SAT问题的量子免疫克隆算法

将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-Inspired Immune Clonal Algorithm,QICA)来求解SAT问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化,加速原有克隆算子的收敛;利用克隆算子的局部寻优能力强的特点,在各个子群体间采用量子交叉操作来增强信息交流,提高种群的多样性防止早熟.实验中,用标准SATLIB库中的3700个不同规模的标准SAT问题对QICA的性能作了全面的测试,并与单纯的量子遗传算法和简单免疫克隆算法以及著名的WalkSAT和PFEA2算法进行比较,仿真实验表明:QICA具有更高的成功率和运算效率.对于具有250个变量、1065个子句的SAT问题,QICA也仅用了1.357s,显示出了优越的性能.     

组织进化算法求解SAT问题

基于组织的概念设计了一种新的进化算法——求解SAT问题的组织进化算法(Organizational Evolutionary Algorithm for SAT problem,0EASAT)．OEASAT将SAT问题分解成若干子问题,然后用每个子问题形成一个组织,并根据SAT问题的特点设计了三种组织进化算子——自学习算子、吞并算子和分裂算子以引导组织的进化．根据组织的适应度,将所有组织分成两个种群——最优种群和非最优种群,然后用进化的方式来控制各算子,以协调各组织间的相互作用．OEASAT通过先解决子问题,再协调相冲突变量的方式来求解SAT问题．由于子问题的规模较小,相对于原问题来说较容易解决,这样就达到了降低问题复杂度的目的．实验用标准SATLIB库中变量个数从20-250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试,并与著名的WalkSAT和RFEA2的结果作了比较．结果表明,OEASAT具有更高的成功率和更高的运算效率．对于具有250个变量、1065个子句的SAT问题,OEASAT仅用了1．524s,表现出了优越的性能．     

基于子句权重学习的求解SAT问题的遗传算法

该文提出了一种求解SAT问题的改进遗传算法（SAT—WAGA）．SAT-WAGA算法有多个改进性特点：将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散．该文最后描述了实现包括SAT—WAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议．实验结果表明：与一般遗传算法相比,SAT—WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善．     

求解SAT问题的算法的研究进展

SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望。     

基于分支回溯的NAE-3SAT问题求解算法

NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.     

基于函数变换的求解SAT问题的新算法

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题。随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的。实验结果表明：与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高。     

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

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

基于寻找可满足2SAT子问题的SAT算法*

可满足问题（SAT）是一个NP-Hard问题。提出了一种求解SAT的新算法（FFSAT）。该算法将SAT问题转换为寻找一个可满足的2-SAT子问题。SAT问题虽然是NP完全问题,但是当所有子句长度不大于2时,SAT问题可以在线性时间求解。使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题。实验结果表明,采用本算法的结果优于UnitWalk。     

O（m^2）时间求解SAT问题的随机算法

传统的求解SAT问题的随机算法主要是对满足解进行搜索,在找不到满足解的情况下,则无法正确判断问题的可满足性。该文提出了两个时间复杂度为O（m^2）求解SAT问题的随机算法SatTestl和SatTest2,这里m为CNF公式中的子句数。这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性,不同于传统的随机算法。其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计,是对传统随机算法的重要改进。试验结果表明,文中提出的算法对相变区域的难SAT实例有较好的求解能力。     

求解SAT问题的退火遗传算法

提出一种将遗传算法与模拟退火算法相结合的SAT问题求解算法SAT-SAGA.该算法以遗传算法流程为主体,并把模拟退火机制融入其中,用以调整优化群体,防止陷入局部最优和出现早熟;在进化过程中算法采用了最优染色体保存策略,防止进化过程的发散.实验表明:该算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.     

混合遗传算法在装箱问题中的应用研究

装箱问题在现实生活中有着广泛的应用,本文针对装箱问题,提出了BF近似算法和遗传算法相结合的混合遗传算法,并在实现上加以了改进,仿真的结果表明该算法在求解装箱问题的表现是良好的。     

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

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

WTA问题的遗传算法研究

提出一种解武器－目标分配问题（weapon target assignment,WTA)的遗传算法,此方法根据遗传算法理论,设计了一种新的武器－目标分级在系式,并缩小了搜索的可行解空间,经多个战例的仿真表明此算法不仅全局收敛性好,稳定性高,易于进行并行处理,而且每个解都具有实际的可分配性。     

基于遗传算法求解TSP问题的一种算法

主要研究了用遗传算法求解TSP问题。阐述了简单遗传算法的设计方法、基本原理和基本步骤。描述了简单遗传算法在TSP问题中的应用现状。根据种群个体的多样性和分布情况,提出了判定遗传算法的截止代数。简单遗传算法具有易于陷入局部最优解、收敛速度慢的特点,针对这些特点,通过改进交叉算子,加入初始化启发信息,提高了遗传算法解的精度和收敛性。     

基于混合遗传算法的作业车间调度问题的研究与仿真

作业车间调度问题(JSP)是一类典型的NP-hard问题,遗传算法(GA)由于其隐合并行性和全局解空间搜索两大优点而成为解决JSP问题的常用工具.但是,由于JSP问题本身的特点,普通遗传算法难以在解此类问题时得到满意解,最突出的问题就是过早收敛于某一局部最优解,使算法效率降低.在此基础上,将遗传算法和模拟退火算法相结合,提出了一种基于遗传和模拟退火的混合算法,该算法将模拟退火算法赋予搜索过程时变性融入其中,具有明显的概率跳跃性,并选取了典型问题进行分析和仿真研究.仿真结果表明,与传统的遗传算法相比该方法是行之有效的.     

基于遗传算法求解时间表问题

基于遗传算法求解时间表问题,通过具体时间表问题的描述和分析,定义了一个新颖的染色体编码方式,然后基于该编码,进一步分析并设计了遗传操作—交叉和变异。算法运行结果显示该方法是可行的。     

一种求解顶点覆盖问题的混合遗传算法

顶点覆盖问题是一个NP难问题,在排序、计算机网络等现实生活中有许多的应用。使用基本遗传算法进行搜索时,存在着局部搜索能力较弱的不足,本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法,将基本遗传算法与局部优化策略相结合,改善遗传算法的局部搜索能力,加快求解该问题的速度。对几种典型无向图的实验证实了新方法的有效性,其整体性能优于现有的一些顶点覆盖问题遗传算法。