采用正交免疫克隆粒子群算法求解SAT问题  

Orthogonal immune clone particle swarm optimization for the SAT problem

作　　者：丛琳[1] 沙宇恒[1] 焦李成[1] 

机构地区：[1]西安电子科技大学智能信息处理研究所,陕西西安710071

出　　处：《西安电子科技大学学报》2007年第4期616-621,共6页Journal of Xidian University

基　　金：国家自然科学基金资助(60133010;60372045);国家863计划资助(2002AA135080);国家973计划资助(2001CB309403)

摘　　要：根据Kennedy和Eberhart提出的二进制粒子群算法，基于抗体克隆选择理论提出一种求解合取范式可满足问题的粒子群算法——正交免疫克隆粒子群算法．该算法将合取范式可满足问题转换为求解目标函数最小值的优化问题，为提高收敛速度，根据子句的先验知识计算出个体的初始指派概率对种群进行初始化．为了避免算法早熟收敛，提高粒子群个体解分布的均匀性，将离散正交交叉算子用于免疫基因操作中，并给出适应于求解合取范式可满足问题的免疫粒子群进化算子．实验采用标准SATLIB库中变量个数从20～250的3700个不同规模的标准合取范式可满足问题对正交免疫克隆粒子群算法的性能作了全面的测试，并与标准粒子群算法和免疫克隆选择算法进行了比较．结果表明，正交免疫克隆粒子群算法的成功率在3个算法中最高，运行时间和评价次数最少．Based on the Binary Particle Swarm Optimization given by Kennedy and Eberhart and the clonal selection theory, a novel Orthogonal Immune Clone Particle Swarm Optimization （OICPSO） was presented to solve SAT problems. In this paper, the SAT problems are converted into global minimum optimization problems. In order to increase the convergence speed, according to the known knowledge of clauses, the individual＇s assign probability is calculated for being used to initialize the population. To avoid the algorithm prematurity and enhance the uniformity of individual＇s distribution, the discrete orthogonal crossover operator is used in immune gene operations, and the immune PSO evolutionary operators to the SAT problems are presented. In experiments, 3 700 benchmark SAT problems in SATLIB are used to test the performance of OICPSO. The number of variables of these problems ranges from 20 to 250. Moreover, the performance of OICPSO is compared with the standard Particle Swarm Optimization （SPSO） and Immune Clonal Selection Algorithm （ICSA）. All experimental results show that the success ratio of OICPSO is the highest and that the run time and number of function evaluations are the least among the three algorithms.

关 键 词：粒子群优化 人工免疫系统 克隆选择 正交设计 可满足性问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]