组织进化算法求解SAT问题

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