Combinatorial complexity problem reduction by the use of artificial vaccines

摘要

A general method to reduce computing time for large combinatorial optimization problems by the use of a novel proposal is presented. It is based on reducing the problem complexity by the systematic application of vaccines, it is inspired in the concept of immunization derived from Artificial Immune Systems. The method can be applied practically to any combinatorial problem program solver such as genetic algorithms, memetic algorithms, artificial immune systems, ant colony optimization, the Dantzig–Fulkerson–Johnson algorithm, etc., providing optimal and suboptimal routes outperforming the selected algorithm itself. As a direct consequence of reducing problem complexity, the method provides a means to bring combinatorial optimization open problems that are too big to be treated by known techniques to a tractable point where acceptable solutions can be obtained. To demonstrate the proposed methodology the Traveling Salesman Problem for huge quantity of cities was used, we tested the method with modern evolutionary algorithms and the Concorde program. Comparative experiments that shows the effectiveness of the method are presented.