I am absolute beginner and I've got rather theoretical questions about optimization of CSPs (Constraint Satisfaction Problems) with genetic algorithms.
If I want to use a genetic algorithm to optimize randomly generated CSPs , do I have to: 1. generate random instances of CSPs 2. generate random solutions to these instances 3. use these solutions as chromosomes forming the initial population of the GA 4. perform the GA ...
I Implemented this code to which generates randomly cretaed CSPs' instances and their solutions:
package essai;
import java.util.Random;
public class Generator {
int N, D, C, T, NbIt,NbSol;
int[] sol;
GConstraint [] ctrs;
//Creates a new Generator object and insert a randomly generated solution
//Return Generator object which is a CSP instance
public Generator (int n, int d, int c, int t, int it, int NbCdt){
N=n; //we give the number of varibles in the problem
D=d; //we give the max domain size or number of values for each variable
C=c; //we give the number of constraints in the problem
T=t; //we give the number of allowed tuples or compatible pairs of values for every constraint
NbIt=it; //we give the number of iterations
NbSol=NbCdt;
sol=new int[n]; //sol[]=build_in solution for CSP (at least one solution)
ctrs = new GConstraint[c]; //object of class GConstraint : we instantiate the table of all the constraints
for(int i=0; i<c; i++){
ctrs[i]=new GConstraint(t); //all the problem constraints
}
//setSolution();
// setConstraints();
// adjustConstraints();
}
// Set a set of constraints randomly
// Make sure i & j in Cij and no Cji in the same set
public void Initialize(){
for (int h =0;h<NbIt;h++){
System.out.println("Instance " +h);
int c1, c2;
Random r = new Random(System.currentTimeMillis());
for(int i=0; i<C; i++){
while(true){
c1=(int) (r.nextDouble()*(double)N);
c2=(int) (r.nextDouble()*(double)N);
if(c1 < c2 && checkConstraint(c1, c2)) break;
}
System.out.print(""+ctrs[i].I+" "+ctrs[i].J+" ");
ctrs[i].I=c1;
ctrs[i].J=c2;
for(int j=0; j<T; j++){
ctrs[i].p1[j]=(int) (r.nextDouble()*(double)D);
ctrs[i].p2[j]=(int) (r.nextDouble()*(double)D);
if(j==T-1)
System.out.print("("+ctrs[i].p1[j]+" "+ctrs[i].p2[j]+")\n");
else System.out.print("("+ctrs[i].p1[j]+" "+ctrs[i].p2[j]+") ");
}
}
for(int f=0;f<NbSol;f++){
Random rd = new Random(System.currentTimeMillis());
int sum =0;
//System.out.print("Sln cdt "+f+": ");
for(int m=0; m<N; m++){
sol[m]=(int) (rd.nextDouble()*(double)D);
System.out.print(sol[m]+" ");
// sum+=sol[m];
}
System.out.println("");
//System.out.println("\n la somme est " + sum);
}
}
}
// Check if constraint Cij exists or not
// @param c1 index i in Cij
// @param c2 index j in Cij
// Return false if Cij exists, true otherwise
private boolean checkConstraint(int c1, int c2){
boolean flg=true;
for(int i=0;i<C;i++){
if(c1==ctrs[i].I && c2==ctrs[i].J) {flg=false; break;}
}
return flg;
}
//main function which reads parameters and generates CSPs
public static void main(String[] args) {
String [] param = {"5","10","4","4","5","5"};
int N, D, C, T, nb_it, nb_cdt;
N=Integer.parseInt(param[0]);
D=Integer.parseInt(param[1]);
C=Integer.parseInt(param[2]);
T=Integer.parseInt(param[3]);
nb_it=Integer.parseInt(param[4]);
nb_cdt=Integer.parseInt(param[5]);
Generator g = new Generator (N, D, C, T, nb_it,nb_cdt);
g.Initialize();
}
}
Then, can I use those solutions as initial chromosomes for a genetic algorithm as explained below?
The output of this code is like:
Instance 0:
0 0 (0 3) (7 1) (8 3) (7 3)
0 0 (2 4) (0 3) (1 5) (0 1)
0 0 (4 3) (9 0) (0 9) (1 6)
0 0 (1 9) (0 6) (3 8) (6 8)
1 4 9 2 6
1 2 7 1 4
1 4 3 9 8
1 9 6 5 7
1 0 1 3 1
Instance 1:
0 2 (0 2) (9 6) (9 7) (6 2)
0 3 (0 4) (4 9) (5 5) (3 2)
2 3 (2 3) (2 3) (4 1) (9 0)
1 4 (9 7) (5 0) (5 9) (8 9)
1 1 6 0 3
1 1 6 0 3
1 1 6 0 3
1 1 6 0 3
1 6 9 7 2
Instance 2:
0 4 (9 7) (2 2) (7 7) (5 3)
0 2 (1 1) (5 6) (2 6) (7 2)
0 1 (1 0) (1 5) (0 0) (4 7)
2 4 (8 7) (2 8) (0 7) (3 8)
1 6 9 7 2
1 7 4 4 5
1 7 4 4 5
1 7 4 4 5
1 7 4 4 5
Instance 3:
0 3 (3 7) (6 2) (3 4) (6 7)
0 4 (5 8) (1 1) (0 8) (0 7)
3 4 (3 6) (3 4) (1 0) (9 7)
1 3 (4 0) (7 4) (0 8) (1 5)
1 3 6 1 9
1 8 9 8 8
1 8 9 8 8
1 8 9 8 8
1 0 5 5 2
Instance 4:
2 4 (7 7) (7 0) (5 5) (2 6)
1 2 (3 7) (5 3) (8 1) (8 7)
0 1 (0 3) (6 0) (0 4) (9 1)
0 2 (3 6) (7 1) (5 4) (4 7)
1 8 3 5 0
1 8 3 5 0
1 5 6 6 5
1 7 2 4 9
1 7 2 4 9
Can you explain to me why: 1. the code generates always, for the first instance, constraints for the variable "0", which is not logical? 2. there are many redundant solutions?
Thanks !
Aucun commentaire:
Enregistrer un commentaire