mardi 17 mai 2016

initializing candidate solutions for genetic algorithm to optimize random generated CSPs

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