CNF-SAT Epistasis Generator for Evolutionary Algorithms

/************************************************************
;                                                           *
;  William M. Spears					    *
;  Navy Center for Applied Research in AI                   *
;  Naval Research Laboratory                                *
;                                                           *
;  The software below is the property of the Department of  *
;  the Navy. Permission is hereby granted to copy all or    *
;  any part of the program below for free distribution,     *
;  however, this header is required on all copies.          *
;                                                           *
; File: lsat.c                                              *
; Code to create Random L-SAT CNF satisfiability problems.  *
; See D. Mitchell, B. Selman, & H. Levesque, "Hard and Easy *
; Distributions of SAT Problems", AAAI Conference, San Jose,*
; CA, 1992, 459--465.                                       *
;************************************************************/

/* This is an attempt to code up the Random L-SAT problem generator
   of Mitchell et. al.  This creates Boolean expressions in CNF, with
   L literals per clause.  A clause if filled by choosing L variables
   (w/ replacement) uniformly from the set of all variables, and
   negating those variables with 50% probability.  In the Mitchell
   et. al. paper I believe the variables are chosen w/o replacement
   (for each clause), but this is probably not very important, especially
   when using a large number of variables. This code is written to be
   used with my GA code called GAC, but should be simple enough to modify.*/

/* This can be used as a generator of epistatic problems - the greater
   the number of clauses the greater the epistasis.  For more details see
   "Using Problem Generators to Explore the Effects of Epistasis" by
   K. De Jong, M. Potter, and W. Spears, in the proceedings of the 1997
   ICGA conference. */

/* If you find any bugs or problems with this generator, please let
   me know at wspears arobase cs.uwyo.edu. */

#define MAX_CLAUSE_LENGTH 10
#define MAX_CLAUSES 50000

int nclauses;      /* The number of clauses in the expression */
int nvars;         /* The number of Boolean variables */
int clause_length; /* This is the number of literals per clause */

/* c_list[i][] will have a list of variables for clause i. 
   A negative entry means the variable is negated. */

int c_list[MAX_CLAUSES][MAX_CLAUSE_LENGTH];

/* Create the CNF Boolean expression.  Call this before calling the GA.
   You will need to call srandom() with some seed value, before calling
   this function. */

void initialization()
{
       int j, k;

       for (j = 1; j <= nclauses; j++) {
	 for (k = 1; k <= clause_length; k++) {
	   if (random()&01 == 1) {
	     c_list[j][k] = random() % nvars + 1;
	   }
	   else {
 	     c_list[j][k] = -(random() % nvars + 1);
	   }
	 }
       }

}

/* This is the evaluation function.  In GAC individuals are
   stored in a 2D array c[][].  This code evaluates the ith
   individual c[i][]. Fitness values are between 0.0 and 1.0.
   The fitness is 1.0 if the expression is satisfied. */

double myeval (i)
int i;
{
       int j, k, satisfied;
       double temp;

       satisfied = 0;
       for (j = 1; j <= nclauses; j++) {
	 for (k = 1; k <= clause_length; k++) {
	   if (((c_list[j][k] > 0) && c[i][c_list[j][k]]) ||
	       ((c_list[j][k] < 0) && !c[i][-c_list[j][k]]))
	       {
		 satisfied++;
		 break;
	       }
	 }
       }
       temp = (double)satisfied/(double)nclauses;
       return(temp);
}