Artificial Immune Systems


[Introduction] - [Contacts] - [Research] - [Publications] - [Projects] - [Events] - [Teaching] - [The Giants].

k-SAT


"Bose-Einstein Condensation in Satisfiability Problems",
C. Angione, A. Occhipinti, G. Stracquadanio, G. Nicosia, European Journal of Operational Research, doi: 10.1016/j.ejor.2012.11.039 (to appear).


Firstly we provide a dynamic process, which allows us to represent a k-SAT instance using a graph, and this helps us map a k-SAT instance into a Bose gas. The algorithm we propose is both dynamic and probabilistic. It means that at each step we evaluate some parameters and, depending on the probabilities that they assume certain values, we choose how to proceed. The examples of 3-SAT instances converted into a graph follow the fit-get-rich model.

 

Fig. 1. 3-SAT graph The graph derived by a 20 clauses formula with 60 variables. The weight on each edge represents the probability that the corresponding link is established. It is possible to note that the most connected nodes get the highest number of particles.

Secondly we optimize our algorithm using the rational out degree instead of the integer one, and the preferential attachment method instead of the standard one, in order to find a clear mapping between a Bose gas and a k-SAT instance. A rigorous experimental work helps us find the correct values to set our parameters.

 

Fig. 2. 3-SAT graph and Bose gas. The energy levels identified by the designed algorithm.

The network derived by a given k-SAT instance follows Bose statistics and is able to undergo Bose-Einstein condensation. We plot the fraction of links shared by the most connected node against the ratio of clauses to variables, and we figure out that there is a close correspondence between the phase transition in k-SAT and the critical temperature for Bose-Einstein condensation.

 
Fig. 3. Bose-Einstein condensation (BEC) in 3-SAT. We report on the x-axis the α values (the ratio of clauses to variables) and on the y-axis the percentage of BEC networks found. The gray stripe shows the region where the critical temperature TBE for Bose-Einstein condensation could be located. For α=4.256 there is the phase transition for the 3-SAT problem.

An instance of the K-SAT problem consists of a set V of variables, a collection C of clauses over V such that each clause c belong to C has |c| = K variables (literals). The problem is to find a satisfying truth assignment for C. Random instances of the K-SAT A. van Gelder's K-SAT problem instance generator, mkcnf.c, available by anonymous ftp at ftp://dimacs.rutgers.edu/pub/challenge/satisfiability/contributed/UCSC/instances (Cnfgen.tar.Z) generates a ``random'' constant-clause-length CNF formula and can force formulas to be satisfiable. For accuracy, we perform our tests in the phase transition, where the hardest instances of the problem are located.

Graph Coloring

An instance of the Graph K-Colorability consists of a graph G=(V,E) and a positive integer k less or equal than |V|. Question: Is G k-colorable? Test bed for the Graph Coloring Problem ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/color

V. Cutello, G. Nicosia, M. Pavone, " An Immune Algorithm with Stochastic Aging and Kullback Entropy for the Chromatic Number Problem", Journal of Combinatorial Optimization, 14(1):9-33, 2007.


[Introduction] - [Contacts] - [Research] - [Publications] - [Projects] - [Events] - [Teaching] - [The Giants].


Copyright 2002-2012, Giuseppe Nicosia.
Giuseppe Nicosia, Optimization, Combinatorial Optimization, Numerical Optimization, Non Linear Optimization, Large Scale Optimization, Evolutionary Algorithms, Genetic Algorithms, Immune Algorithms, Artificial Immune Systems, Graph Coloring, String Folding, NP-complete problems, Circuit Optimization, Circuit Design, Design For Yield, Device Optimization, Bioinformatics, Structural Bioinformatics, Protein Folding, Protein Structure Prediction, HP model.