Solving constraint-satisfaction problems by a genetic algorithm adopting viral infection

Several approximate algorithms have been reported to solve large constraint-satisfaction problems (CSPs) within a practical time. While those papers discuss techniques to escape from local optima, this paper describes a method that actively performs global searches. The present method improves the rate of search of genetic algorithms by using viral infection instead of mutation. Partial solutions of a CSP are considered to be viruses, and a population of viruses is created, as well as a population of candidate solutions. The search for a solution is conducted by crossover and infection. Infection substitutes the gene of a virus for the locus decided by the virus. Experimental results using randomly generated CSPs prove that the proposed method is faster that usual genetic algorithms at finding a solution when the constraint density of a CSP is low.