The SAT problem consists of a set of n variables and a set of m clauses. The goal of the SAT problem is to determine whether or not there exists an assignment t of truth values to variables that makes the formula f in CNF satisfiable. Among the extensions to SAT, MAX-SAT is the most known, In this case, a parameter K is given and the problem is to determine if there exists an assignment t of truth values to variables such that at least K clauses are satisfied. SAT can be considerated as a special case of MAX-SAT when K equals the number m of clauses.
Implementation of operator>> (class Problem). This operator reads the problem instance.
istream& operator>> (istream& is, Problem& pbm)
{
int l,n;
is >> pbm._numvar >> pbm._numclause >> pbm._lenclause;
n = pbm._lenclause; pbm._clauses = new int*[pbm._numclause];
// read clauses
for (int i = 0; i < pbm._numclause; i++)
{
pbm._clauses[i] = new int[n];
for(int j = 0; j < n;j++)
{
is >> l;
pbm._clauses[i][j] = l;
}
is >> l;
}
}
Implementation of initialize method (class Solution). This method generates a solution.
void Solution::initialize()
{
for (int i=0;i<_pbm.numvar();i++)
_var[i]=rand_int(0,1);
}
Implementation of fitness method (class Solution). This method calculates the fitness value of the individual.
double Solution::fitness ()
{
double fitness = 0.0;
int acum = 0;
for(int i = 0; i < _pbm.numclause(); i++)
{
int *rl = _pbm.clause(i);
acum = 0;
for(int j = 0; (j < _pbm.lenclause()) && (acum != 1);j++)
{
if( ((rl[j] < 0) && (_var[(int)abs(rl[j])-1] == 0))
|| ((rl[j] > 0) && (_var[rl[j]-1] == 1)) )
acum = 1;
}
fitness += acum;
}
return fitness;
}
There are several basic steps to running this problem solve with the previous skeletons:
1. Install Mallba Library (see How to install Mallba)
2. Change to the maxsat directorycd Mallba/rep/<skeleton>/maxsat
3. Compile skeleton
make
3. Configure algorithm parameters:
3.1 Configure <skeleton>.cfg file. (Optional Step)
3.2 Configure newGASA.cfg file (only for newGASA skeleton)
4. Run problem:
4.1 Sequential Version:make SEQ
4.2 Parallel Version:
4.2.1 Configure Config.cfg file (except newGASA skeleton).
4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
4.2.3 Runmake LAN
or
make WAN
The goal of ONEMAX problem is to maximize the number of 1's in the bitstring
Implementation of initialize method (class Solution). This method generates a solution.
void Solution::initialize()
{
for (int i=0;i<_pbm.dimesion();i++)
_var[i]=rand_int(0,1);
}
Implementation of fitness method (class Solution). This method calculates the fitness value of the individual.
double Solution::fitness ()
{
double fitness = 0.0;
for (int i=0;i<_var.size();i++)
fitness += _var[i];
return fitness;
}
There are several basic steps to running this problem solve with the previous skeletons:
1. Install Mallba Library (see How to install Mallba)
2. Change to the onemax directorycd Mallba/rep/<skeleton>/onemax
3. Compile skeleton
make
3. Configure algorithm parameters:
3.1 Configure <skeleton>.cfg file. (Optional Step)
3.2 Configure newGASA.cfg file (only for newGASA skeleton)
4. Run problem:
4.1 Sequential Version:make SEQ
4.2 Parallel Version:
4.2.1 Configure Config.cfg file (except newGASA skeleton).
4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
4.2.3 Runmake LAN
or
make WAN
This problem consists in finding a value vector x that minimized the following equation (Sphere Function):
This problem is only implemented in ES skeleton.
Implementation of initialize method (class Solution). This method generates a solution. Usually, you do not need this method.
void Solution::initialize()
{
float min = _pbm.minvalue(0);
float rang = _pbm.maxvalue(0) - min;
for (int i=0;i<_pbm.dimension();i++)
{
_variables[i] = (float) (rand01()*rang) + min;
_parameters[i] = (float) rand01()*2.0 - 1.0;
}
for (int i = 0; i < ((_pbm.dimension() * (_pbm.dimension() - 1)) / 2);i++)
_angles[i] = (float) (rand01() * 2 * PI);
}
Implementation of fitness method (class Solution). This method calculates the fitness value of the individual.
double Solution::fitness ()
{
double fitness = 0.0;
for(int i = 0; i < _pbm.dimension(); i++)
fitness += _variables[i]*_variables[i];
return fitness;
}
There are several basic steps to running this problem solve with the ES skeleton:
1. Install Mallba Library (see How to install Mallba)
2. Change to the sphere problem directorycd Mallba/rep/ES/sphere
3. Compile skeleton
make
3. Configure algorithm parameters (ES.cfg file). (Optional Step)
4. Run problem:
4.1 Sequential Version:make SEQ
4.2 Parallel Version:
4.2.1 Configure Config.cfg file.
4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
4.2.3 Runmake LAN
or
make WAN
This problem consists in finding a value vector x that minimized the following equation (Rastrigin Function):
This problem is only implemented in ES skeleton.
Implementation of initialize method (class Solution). This method generates a solution. Usually, you do not need this method.
void Solution::initialize()
{
float min = _pbm.minvalue(0);
float rang = _pbm.maxvalue(0) - min;
for (int i=0;i<_pbm.dimension();i++)
{
_variables[i] = (float) (rand01()*rang) + min;
_parameters[i] = (float) rand01()*2.0 - 1.0;
}
for (int i = 0; i < ((_pbm.dimension() * (_pbm.dimension() - 1)) / 2);i++)
_angles[i] = (float) (rand01() * 2 * PI);
}
Implementation of fitness method (class Solution). This method calculates the fitness value of the individual.
double Solution::fitness ()
{
double fitness = 0.0,acum,aux;
for(int i = 0; i < _pbm.dimension(); i++)
{
aux = (double) _variables[i];
acum = aux*aux - 10*cos(2*PI*aux);
fitness += acum;
}
fitness += (10.0 * _pbm.dimension());
return fitness;
}
There are several basic steps to running this problem solve with the ES skeleton:
1. Install Mallba Library (see How to install Mallba)
2. Change to the rastrigin directorycd Mallba/rep/ES/rastrigin
3. Compile skeleton
make
3. Configure algorithm parameters (ES.cfg file). (Optional Step)
4. Run problem:
4.1 Sequential Version:make SEQ
4.2 Parallel Version:
4.2.1 Configure Config.cfg file.
4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
4.2.3 Runmake LAN
or
make WAN