求解SAT问题的多智能体社会进化算法

基于Agent社会合作机制以及智能体对环境的感知和反作用能力提出了一种新的求解SAT问题的多智能体社会进化方法MASEA(Multi-Agent Social Evolutionary Algorithm).该方法在多智能体进化思想的基础上,引入人类社会"关系网模型"的概念来建立智能体所能感知的邻域环境;同时在保留原有的竞争算子和自学习算子前提下,根据智能体具有竞争协作的特性,设计了一个新的算子——协作算子来共同完成整个进化过程.以标准SATLIB库中变量个数从20~250的3700个不同规模的标准SAT问题以及基于RB模型所产生的随机实例对MASEA的性能进行了全面的测试,并与其他一些具有较高性能算法的结果进行了比较.结果表明,MASEA具有更高的成功率和更高的运算效率.     

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

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

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

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

基于组织调整的进化算法求解TSP问题

研究了组织这个经济学中的概念在求解优化问题时的可能应用,给出了一种基于组织调整的进化算法EAOA(EvolutionaryAlgorithmBasedonOrganizationAdjustment)。结合TSP问题,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法具有较强的问题求解能力。     

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

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

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

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

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

基于"聚类排序选择"优化遗传算法求解SAT问题时,引入交叉算子和变异算子,并根据适应度函数及问题本身特性,调节阈值δ,生成新的种群聚类。这种遗传算法有效地抑制了算法的延迟收敛,从而保证了为可满足性公式能够快速找到一个可满足性指派。同时,在遗传算法中引入了DPLL算法,对部分变元进行消解,提高了算法的求解效率。相关的实验数据表明,本算法的性能明显优于同类算法。     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

结合启发式算子的单变量边缘分布算法求解SAT问题

单变量边缘分布算法(UMDA)是一种新的进化算法,是求解复杂问题的一种有效算法.根据SAT问题的特点,本文提出了一种求解SAT问题的改进单变量边缘分布算法(HeUMDASAT),该算法结合SAT问题本身固有的结构信息与当前群体的优秀解所提供的全局信息,构造了一个新的启发算子,并将此算子结合到单变量边缘分布算法中.此算子不同于随机搜索算子,由其产生的个体可以使得算法跳出局部最优并探索新的潜在区域,并且加快算法的收敛速度.用SATLIB库中的标准SAT问题对HeUMDASAT算法进行测试,实验结果表明该算法在求解速度和成功率方面都有明显的改善.     

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

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

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。     

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

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

组织进化数值优化算法

基于经济学中“组织”的概念 ,该文提出一种新的进化算法———组织进化算法 ,来解决无约束和有约束的数值优化问题 .该算法与传统遗传算法、进化规划、进化策略的运行机制完全不同 ,其进化操作不直接作用于个体上 ,而作用在组织上 ,为此 ,该文定义了三种组织进化算子———分裂算子、吞并算子和合作算子来引导种群进化 .理论分析证明组织进化算法具有全局收敛性 .实验中 ,用 4个无约束和 6个有约束标准函数对算法进行了测试 ,与 3个新算法作了比较 ,并对组织进化算法的性能作了深入分析 .结果表明 ,该文算法无论在解的质量上还是在计算复杂度上都优于其它算法 .对于有约束问题 ,只用了简单的静态罚函数就得到了良好的效果 ,这表明该文算法的搜索机制非常有效 ,不易陷入局部最优 .最后 ,参数分析的结果表明该文算法具有性能稳定、成功率高、对参数不敏感等优越的性能     

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

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

一种改进的求解TSP问题的演化算法

演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法．实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353．860997,优于吴斌等运用分段算法得到的最短路径30354．3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770．924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快．     

一个解决高校排课问题的演化算法

针对当前高校存在的排课效率低下问题,有必要采用一种有效的算法结合计算机实现自动排课。文中在比较各种不同算法的基础上,提出了一种使用局部杂交算子的演化算法。该算法采用矩阵编码方案,通过惩罚函数满足排课表问题的多重约束条件。模拟实验证明,该算法可有效地解决高校排课问题。     

可满足性问题的三维DNA图结构算法

论文提出用三维图结构解决DNA分子计算问题,给出了解决3-SAT问题的方法。在所提出的方法中,算法所要求的步骤与公式中变量的数目相等。