Abstract: 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, 3700 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.

Key words: particle swarm optimization, artificial immune system, clonal selection, orthogonal design, satisfiability problem