Discussion :

[nayoura]

Bonjour,

je cherche à utiliser un algorithme génétique basique pour optimiser des problèmes combinatoires générés aléatoirement.
J'ai écrit un programme qui génère de façon aléatoire des instances de problèmes , et des solutions candidates à ces problèmes.
Voici le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
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","10","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();
    }   
}

Je veux maintenant écrire l'algorithme génétique qui va optimiser les instances générées.
Ma question est la suivante: Lorsqu'on cherche à utiliser l'AG pour optimiser des problèmes combinatoires (CSPs), est ce que les outputs d'un générateurs aléatoires de CSPs (solutions générées aléatoirement) sont ceux qu'utiliserait l'AG comme population initiale? Donc pas la peine d'écrire des classes Individu, Chromosome, Population (par exp) ..., je dois donc juste ajouter au générateur de CSPs une classe qui fera le traitement (repreduction, croisement et mutation..) ??


Merci !

[francky74]

Bonjour,

Lorsque tu parles d'une classe Individu, fais-tu allusion à un individu au sens d'un être humain ?

Si c'est cela, je pense que tu as besoin de créer une classe individu qui aura pour attribut de type Chromosome, etc ...
Par contre, pour population, peux-tu préciser, s'il te plaît, le sens de ce terme ?
Si c'est la population au sens du peuple, l'individu fait donc partie d'une population et tu devras donc créer une classe population qui contiendra un attribut de type Lis<Individu> -> une liste d'individus car il y a plusieurs individus dans une population