By the SAT problem, (2) [Evolution calculation C # implementation]

Abstract: This article tries to discuss a computer scientific problem, SAT problem. And thereby launched, showing some basic ideas for the charm of computer algorithms, analyzing and designing computer algorithms. Finally, a algorithm and program implementation of the evolution calculation of a SAT issue is given.

Keywords: sat problem, combination explosion, climbing method, A algorithm, evolutionary calculation

SAT problem expands (2) [on]

Problem solution

We can now take a closer look at the ideas of evolutionary calculations.

Evolution calculation, or evolutionary calculations, is a supercoming of genetic algorithms, which is characterized by group search strategies and information exchange between individuals in groups. The evolutionary algorithm currently studied mainly has genetic algorithm, evolutionary planning and evolutionary strategies. Although they are similar, these three algorithms have developed independently of each other.

Evolution Calculate the strategy of random search, kinetic information (such as continuous, slightly, etc.) that is not demanding issues, is a solution that solves the prospects of NPC issues. We discussed how to give a solution for a SAT problem this time.

General description of the problem it solves:

J = max f (x), x ∈X, x = (x1, x2, ..., xn) ',

Where f (x) is an evaluation function,

X is a solution,

X is the definition domain.

And it solves the general steps of the problem:

• Chromosome coding and decoding;

• Set the initial population and adaptation function;

• Select the genetic operator to hybridize the hybridization operator of the probability PC and variation operator variant by probability PM;

• Parked strategies.

There are a variety of encoding schemes of chromosomes, and as mentioned in the beginning, SAT issues are binary chromosomes coding are natural and convenient. We use the C # language to implement an algorithm for evolution computing, using binary encoding, the detailed analysis of the design process, and finally attach the examples of analysis and numerical calculations.

The interface of the entire system is as follows:

Figure 6 Software interface for SAT problem plan

Continue to start the model established, for the chromosome group based on logical variable set A, and sentence collection f, we use

PRIVATE STRINGBUILDER [] Satgene

Private int [,] bsentence;

Recommended, the value of | A | N) is represented by VALNUM, and the value (ie M) of | f | is represented by maxnum:

Private int mapnum;

Private int valNum;

In the chromosome group, each chromosome makes the total number of sentences in F is an important sign, and we use score to record the best and worst:

Private int [] score;

Private stringbuilder best;

PRIVATE STRINGBUILDER WORST;

Then the probability of hybridization and variation, and the random number generator:

PRIVATE DOUBLE PC;

Private Double PM;

Private system.random randnum;

These are defined in class SAT, which is initialized by the following constructor:

Public Sat (int N, int Valnum, Double PC, Double PM)

{

//

// TODO: Add constructor logic here

//

Maxnum = n;

VALNUM = VALNUM;

Score = new int [MAXNUM];

Satgenes = New StringBuilder [MAXNUM];

For (int i = 0; i

Satgenes [i] = new stringbuilder (); bsentence = new int [maxnum, valnum];

For (int i = 0; i

For (int J = 0; j

Bsentence [i, j] = 0;

PC = PC;

PM = PM;

RandNum = new random (unchecked (int) DateTime.now.ticks);

}

The chromosome group we initialize by the following procedure:

Public void inInenes ()

{

For (int i = 0; i

For (int J = 0; j

Satgenes [i] .insert (j, randnum.next (1) .tostring ());

}

Then the evolution of the chromosome group, we can design the algorithm in detail.