toulbar2
incop.h
1 #ifndef INCOP_H_
2 #define INCOP_H_
3 
4 /* Les définitions des classes de la partie algorithme + OpProblem */
7 #include <climits>
8 #include "core/tb2types.hpp"
9 
10 /* struct Long */
11 /* { */
12 /* long long p; */
13 
14 /* Long() : p(0) {} */
15 /* Long(const Long &l) : p(l.p) {} */
16 /* Long(const long long v) : p(v) {} */
17 /* double to_double() const {return (double) p;} */
18 
19 /* Long &operator=(const Long &r) { */
20 /* p = r.p; */
21 /* return *this; */
22 /* } */
23 /* Long &operator+=(const Long &r) { */
24 /* p += r.p; */
25 /* return *this; */
26 /* } */
27 /* Long &operator-=(const Long &r) { */
28 /* p -= r.p; */
29 /* return *this; */
30 /* } */
31 /* const Long operator-() const {return Long(-p);} */
32 /* friend const Long operator+(const Long& left, const Long& right) { */
33 /* return Long(left.p + right.p); */
34 /* } */
35 /* friend const Long operator-(const Long& left, const Long& right) { */
36 /* return Long(left.p - right.p); */
37 /* } */
38 /* friend const Long operator*(const Long& left, const Long& right) { */
39 /* return Long(left.p * right.p); */
40 /* } */
41 /* friend const Long operator/(const Long& left, const Long& right) { */
42 /* return Long(left.p / right.p); */
43 /* } */
44 /* friend bool operator==(const Long& left, const Long& right) { */
45 /* return (left.p == right.p); */
46 /* } */
47 /* friend bool operator!=(const Long& left, const Long& right) { */
48 /* return (left.p != right.p); */
49 /* } */
50 /* friend bool operator<=(const Long& left, const Long& right) { */
51 /* return (left.p <= right.p); */
52 /* } */
53 /* friend bool operator>=(const Long& left, const Long& right) { */
54 /* return (left.p >= right.p); */
55 /* } */
56 /* friend bool operator<(const Long& left, const Long& right) { */
57 /* return (left.p < right.p); */
58 /* } */
59 /* friend bool operator>(const Long& left, const Long& right) { */
60 /* return (left.p > right.p); */
61 /* } */
62 /* friend ostream& operator<<(ostream& os, const Long &r) { */
63 /* os << r.p; */
64 /* return os; */
65 /* } */
66 /* friend istream& operator>>(istream& is, Long& r) { */
67 /* is >> r.p; */
68 /* return is; */
69 /* } */
70 /* }; */
71 //#define LONG_MAX LONG_LONG_MAX
72 
73 /* les classes "abstraites" utilisées dans les paramètres des méthodes */
74 class OpProblem;
76 class Metaheuristic;
77 class NeighborhoodSearch;
78 class Move;
79 
80 /* la classe Configuration le champ config comprend la configuration elle-même sous forme de tableau d'entiers
81 le champ valuation contient sa valeur pour l'évaluation */
82 
86 
87 {
88 public:
89  int nbvar;
90  int trynumber;
91  /* les valeurs courantes des variables : implanté sous forme de tableau d'entiers*/
93  int* config;
94  /* la valeur de la configuration */
96  Long valuation;
97  int var_conflict_size;
98  /* les variables participant à un conflit : implanté sous forme de vecteur */
100  vector<int> var_conflict;
101  set<int> set_var_conflict;
102  /* indicateur si la configuration a été regroupée (pour GWW) */
105  virtual ~Configuration();
106  Configuration();
107  Configuration(int nbvar);
108  /* copie d'une configuration config2 dans this*/
110  virtual void copy_element(Configuration* config2);
111  /* initialisation à 0 de la structure de données des conflits */
113  virtual void init_conflicts();
114  /* stockage de l'augmentation des conflits de (var,val) de incr */
116  virtual void incr_conflicts(int var, int val, int index, Long incr);
117 
118  /* stockage du nombre des conflits nbconf de (var,val) */
120  virtual void set_conflicts(int var, int val, int index, Long nbconf);
121 
122  /* nombre de conflits de (var,val) stocké */
124  virtual Long get_conflicts(int var, int val, int index);
125  /* nombre de conflits de (var,val) , au besoin recalculé */
127  virtual Long get_conflicts_problem(OpProblem* problem, int var, int val);
128 
129  /* mise à jour des conflits après avoir effectué le mouvement move*/
131  virtual void update_conflicts(OpProblem* problem, Move* move);
132 };
133 
134 /* CSPConfiguration : pour les CSP */
137 public:
138  int domainsize;
139 
140  CSPConfiguration(int nbvar, int domsize);
141 };
142 
143 /* L'incrémentalité avec stockage de la participation à l'évaluation des valeurs courantes des
144 variables de la configuration : implanté dans tabconflicts (tableau à une dimension) */
148 public:
149  Long* tabconflicts;
150  IncrCSPConfiguration(int nbvar);
151  IncrCSPConfiguration(int nbvar, int nbcol);
153  void copy_element(Configuration* config2);
154  void init_conflicts();
155  void incr_conflicts(int var, int val, int index, Long incr);
156  void set_conflicts(int var, int val, int index, Long nbconf);
157  Long get_conflicts(int var, int val, int index);
158  Long get_conflicts_problem(OpProblem* problem, int var, int val);
159  virtual void set_variableconflicts(int var, int nbconf);
160  void update_conflicts(OpProblem* problem, Move* move);
161 };
162 
163 /* l'incrémentalité totale : participation à l'évaluation de chaque
164 valeur de chaque variable stockée dans le tableau tabconflicts à deux dimensions (variable, indice de la valeur)*/
169 public:
170  int tabconflictsize;
171  Long** tabconflicts;
172 
173  FullincrCSPConfiguration(int nbvar, int domainsize);
175  void copy_element(Configuration* config2);
176  void init_conflicts();
177  void incr_conflicts(int var, int val, int index, Long incr);
178  void set_conflicts(int var, int val, int index, Long nbconf);
179  /* nombre de conflits de (var,val) stocké : utilisation de l'indice de la valeur index*/
181  Long get_conflicts(int var, int val, int index);
182  Long get_conflicts_problem(OpProblem* problem, int var, int val);
183  void update_conflicts(OpProblem* problem, Move* move);
184 };
185 
186 /* classe Move */
188 class Move {
189 public:
190  Long valuation;
191  Move();
192  virtual ~Move() { ; };
193  /* le test d'égalité d'un mouvement (utilisé pour la recherche d'un mouvement dans la liste taboue)*/
195  virtual int eqmove(Move* move1);
196  /* copie du mouvement move1 dans this */
198  virtual void copymove(Move* move);
199  /* le mouvement a mettre dans la liste taboue */
201  virtual Move* computetabumove(Configuration* config) { return 0; };
202 };
203 
204 /* classe CSPMove : un mouvement pour les CSP : variable , valeur */
206 class CSPMove : public Move {
207 public:
208  int variable;
209  int value;
210  CSPMove();
211  ~CSPMove() { ; };
212  int eqmove(Move* move);
213  void copymove(Move* move);
214  /* le mouvement stocké tabou est le mouvement inverse du mouvement effectué */
217 };
218 
219 /* classe racine des problèmes d'optimisation (minimisation) */
222 class OpProblem {
223 public:
224  /* la meilleure configuration trouvée */
227  /* nombre de variables */
229  int nbvar;
230  /* taille maximum des domaines */
233  /* borne inférieure donnée au départ : sert de condition d'arrêt quand elle est atteinte */
236  /* le mouvement courant */
239  /* le premier mouvement faisable essayé dans le voisinage*/
242  /* le meilleur mouvement essayé */
245  OpProblem(){};
246  virtual ~OpProblem(){};
247  /* exécution d'un mouvement (modification de la configuration courante) */
249  virtual void move_execution(Configuration* configuration, Move* move);
250  /* mise à jour de la structure des conflits (cas IncrCSPConfiguration) */
252  virtual void incr_update_conflicts(IncrCSPConfiguration* configuration, Move* move){};
253  /* mise à jour de la structure des conflits (cas FullincrCSPConfiguration) */
255  virtual void fullincr_update_conflicts(FullincrCSPConfiguration* configuration, Move* move){};
256  /* création des 3 objets Move (currentmove,bestmove,firstmove) */
258  virtual void allocate_moves();
259  /* création d'un mouvement (la classe du mouvement dépend du problène) : méthode implantée dans les sous-classes */
262  virtual Move* create_move() { return 0; };
263  /* ajustement des paramètres du voisinage (quand la taille du voisinage est supérieure à maxneighbors) */
265  virtual void adjust_parameters(Configuration* configuration, int& maxneighbors, int& minneighbors){};
266  /* prochain mouvement du voisinage à tester */
268  virtual void next_move(Configuration* configuration, Move* move, NeighborhoodSearch* nbhs){};
269  /* affectation aléatoire des variables d'une configuration */
271  virtual void random_configuration(Configuration* configuration){};
272  /* analyse da la meilleure solution */
274  virtual void best_config_analysis(){};
275  /* ecriture de la meilleure solution */
277  virtual void best_config_write(){};
278 
279  /* vérification de la meilleure solution (recalcul de son coût) */
281  virtual void best_config_verification();
282  /* initialisation d'une population de taille populationsize */
284  virtual void init_population(Configuration** population, int populationsize){};
285  /* création d'une configuration (la classe exacte dépend du problème) */
287  virtual Configuration* create_configuration() { return 0; };
288  /* calcul de la participation à l'évaluation de l'affectation (var,val) */
290  virtual Long compute_conflict(Configuration* configuration, int var, int val) { return 0; };
291  /* évaluation d'une configuration */
293  virtual Long config_evaluation(Configuration* configuration) { return 0; };
294  /* évaluation d'un mouvement move sur une configuration */
296  virtual Long move_evaluation(Configuration* configuration, Move* move) { return 0; };
297  /* passage de l'indice dans le domaine à la valeur */
299  virtual int index2value(int index, int var) { return index; };
300  /* passage d'une valeur à son indice dans le domaine de la variable */
302  virtual int value2index(int value, int var) { return value; };
303  /* calcule l'ensemble des variables en conflit de la configuration*/
305  virtual void compute_var_conflict(Configuration* configuration){};
306  virtual int tabuindex(Move* move, Configuration* configuration) { return 0; };
307  virtual int tabuinverseindex(Move* move, Configuration* configuration) { return 0; };
308  virtual int nbtabuindex() { return 0; };
309 };
310 
311 /* Le voisinage paramétré d'une part par min voisins explorés,
312 max voisins explorés et épuisement voisinage et d'autre part par var_conflict et val_conflict */
316 public:
317  /* nombre minimum de voisins explorés */
320  /* nombre maximum de voisins explorés */
323  /* indicateur de comportement quand le voisinage est épuisé sans qu'un voisin n'ait été accepté :
324  0 stagnation, 1 on effectue le 1er mouvement faisable, k on effectue le meilleur mouvement faisable parmi k mouvements essayés non acceptés*/
327  int finished;
328  /* indicateur de restriction aux variables en conflit (0 pas de restriction, 1 restriction) */
331  /* indicateur de restriction aux meilleures variables d'une variable (0 pas de restriction, 1 restriction) */
334  double nbhrate;
335  NeighborhoodSearch(int maxneigh, int minneigh, int finish, int var_conf, int val_conf, double nbbr);
336  int returnbestmove();
337  void adjust_neighborhood(Configuration* configuration, OpProblem* problem, int& maxneigh, int& minneigh, int nbmoves);
338  virtual void dynamicmaxneighbors(int& maxneigh, int& minneigh, int nbmoves);
339  virtual void initsearch();
340  virtual void spareneighboradjust(Configuration* config, Move* move) { ; }
341  virtual ~NeighborhoodSearch(){};
342 };
343 
344 /* Voisinage avec réglage dynamique du paramètre max-voisins*/
347 public:
348  DynamicNeighborhoodSearch(int maxneigh, int minneigh, int finish, int var_conf, int val_conf, double nbbr);
349  /* valeur initiale du parametre maxneighbors */
352  /* valeur initiale du parametre minneighbors */
355  /* période de réajustement du paramètre */
358  void initsearch();
359  /* ajustement des paramètres minneighbors et maxneighbors */
361  void dynamicmaxneighbors(int& maxneigh, int& minneigh, int nbmoves);
362 };
363 
364 class DynamicSpareneighbor : public NeighborhoodSearch {
365 public:
366  DynamicSpareneighbor(int maxneigh, int minneigh, int finish, int var_conf, int val_conf, double nbbr);
367  void spareneighboradjust(Configuration* config, Move* move);
368  int nbmovesdown;
369 };
370 
371 /* Les Algorithmes
372 la classe mere : algo de recherche incomplet */
376 public:
377  string methodname;
378  /* un seuil peut être utilisé pour empêcher des mouvements de coût supérieur au seuil
379  (utilisé dans les recherches locales des marches de GWW)*/
381  Long threshold;
382  virtual ~IncompleteAlgorithm(){};
383  /* marche d'une particule */
385  virtual void randomwalk(OpProblem* problem, Configuration* configuration);
386  virtual void initthreshold(Configuration** population, int popsize) { ; };
387  /* exécution de l'algorithme sur une population (réduite à une particule pour une recherche locale) */
389  virtual void run(OpProblem* problem, Configuration** population);
390 };
391 
392 /* la classe des algos de marche aléatoire paramétrée par longueur marche
393 un voisinage et une metaheuristique */
398 public:
399  /* longueur de la marche */
402  /* le voisinage */
405  /* la métaheuristique */
408  /* le nombre d'essais de mouvements (pour les stats) */
410  int nhtries;
411  double avgnhtries;
412  double avgsqnhtries;
413  /* nombre de mouvements effectués */
415  int nbmoves;
416  LSAlgorithm(int nbmov);
417  ~LSAlgorithm();
418  /* faisabilité d'un mouvement (sous ou au niveau du seuil pour marche de GWW) */
420  virtual int isfeasible(Move* move);
421  void randomwalk(OpProblem* problem, Configuration* configuration);
422  /* algorithme d'exploration du voisinage pour sélectionner et effectuer un mouvement à partir de la configuration courante
423  Effectue le mouvement et renvoie 1 si un mvt a ete effectué et 0 si aucun mouvement ne l'a été*/
426  virtual int configurationmove(OpProblem* problem, Configuration* configuration);
427  void initthreshold(Configuration** population, int popsize);
428  void run(OpProblem* problem, Configuration** population);
429  /* test de meilleur trouvé (renvoie 1 si un meilleur absolu est trouvé)*/
431  int test_bestfound(Move* move);
432 };
433 
434 class LSAlgorithmGWW : public LSAlgorithm {
435 public:
436  LSAlgorithmGWW(int nbmov);
437  int isfeasible(Move* move);
438 };
439 
440 /* les différentes métaheuristiques */
443 public:
444  virtual ~Metaheuristic(){};
445  /* mise à jour des données de la métaheuristique juste avant qu'un mouvement soit effectué */
447  virtual void executebeforemove(Move* move, Configuration* configuration, OpProblem* problem);
448  /* initialisation des données de la métaheuristique */
450  virtual void reinit(OpProblem* problem);
451  /* condition d'acceptation d'un mouvement : renvoie 1 si le mouvement est accepté */
453  virtual int acceptance(Move* move, Configuration* config);
454  virtual void adjustparameter(int parameter) { ; };
455 };
456 
457 /* marche avec liste taboue : parametree par longueur de la liste : cette liste de mouvements est
458 implantee à l'aide d'une liste de Move* */
461 class TabuSearch : public Metaheuristic {
462 public:
463  /* longueur maximale de la liste taboue */
466  /* liste taboue : traitée comme une file */
468  list<Move*> move_list;
469  TabuSearch(int tabul);
470  /* acceptation d'un mouvement : non tabou (le critère d'aspiration est dans l'algo de recherche du voisin) */
472  int acceptance(Move* move, Configuration* config);
473  /* test de non présence dans la liste taboue : la présence d'un mvt est faite avec eqmove */
475  int nontabumove(Move* move);
476  /* mise à jour de la liste taboue qui est traitée comme une file de longueur maximale tabulength */
478  void executebeforemove(Move* move, Configuration* configuration, OpProblem* problem);
479  /* réinitialisation : la liste taboue est vidée */
481  void reinit(OpProblem* problem);
482  void adjustparameter(int length);
483 };
484 
485 class TabuGreedySearch : public TabuSearch {
486 public:
487  TabuGreedySearch(int tabul);
488  int acceptance(Move* move, Configuration* config);
489 };
490 
491 class IncrTabuSearch : public TabuSearch {
492 public:
493  IncrTabuSearch(int tabul);
494  int nbiter;
495  vector<int> tabutime;
496  OpProblem* currentproblem;
497  int acceptance(Move* move, Configuration* config);
498  void executebeforemove(Move* move, Configuration* configuration, OpProblem* problem);
499  void reinit(OpProblem* problem);
500 };
501 
502 class IncrTabuGreedySearch : public IncrTabuSearch {
503 public:
504  IncrTabuGreedySearch(int tabul);
505  int acceptance(Move* move, Configuration* config);
506 };
507 
508 /* marche Metropolis : un seul paramètre = temperature */
510 class Metropolis : public Metaheuristic {
511 public:
512  double temperature;
513  Metropolis(double temp);
514  /* la formule classique de Metropolis d'acceptation d'un mouvement détériorant
515  l'évaluation : probabilité p = exp (-evaluationdelta/temperature) */
517  int acceptance(Move* move, Configuration* config);
518  void adjustparameter(int parameter);
519 };
520 
521 /* l'acceptation à seuil : un mouvement ne doit pas détériorer l'évaluation plus que le seuil courant ;
522 le seuil diminue linéairement de thresholdinit à 0*/
523 
527 public:
528  /* seuil initial */
531  /* pas de baisse du seuil */
533  double delta;
534  /* valeur courante du seuil */
536  double thresholdaccept; // le seuil tel que géré par TA
537  /* constructeur : 2 arguments seuil initial maxthreshold et nombre de pas,
538  le pas constant delta de baisse du seuil est calculé*/
541  ThresholdAccepting(double maxthreshold, int walklength);
542  /* condition d'acceptation : être sous ou au niveau du seuil */
544  int acceptance(Move* move, Configuration* config);
545  /* le seuil est diminué de delta */
547  void executebeforemove(Move* move, Configuration* configuration, OpProblem* problem);
548  /* le seuil est initialisé à thresholdinit */
550  void reinit(OpProblem* problem);
551 };
552 
553 /* le recuit simulé : descente linéaire de température de inittemperature à 0 */
556 public:
557  /* temperature initiale */
560  /* pas constant de baisse de temperature */
562  double delta;
563  /* temperature courante */
565  double temperature;
566  int walklength;
567  /* Constructeur : 2 arguments : température initiale et longueur de marche */
570  SimulatedAnnealing(double initialtemperature, int walklength);
571  /* acceptation en fonction de la temperature : formule classique du recuit simulé
572  probablité d'acceptation d'un mouvement détériorant l'évaluation :
573  probabilité = exp (-evaluationdelta/temperature) */
574 
577  int acceptance(Move* move, Configuration* config);
578  /* la température est baissée de delta */
580  void executebeforemove(Move* move, Configuration* configuration, OpProblem* problem);
581  void reinit(OpProblem* problem);
582  void adjustparameter(int parameter);
583 };
584 
585 /* marche hybride tabou + pourcentages d'acceptation selon sens des mouvements */
588 // liste taboue
589 
591 public:
592  /* probabilité d'acceptation d'un mauvais */
594  float Pd;
595  /* probabilité d'acceptatiion d'un mouvement de même coût que le courant */
597  float P0;
598  TabuAcceptingrate(int tabul, float Pd, float P0);
599  /* critère d'acceptation : non tabou et pourcentages d'acceptation suivant sens du mouvement (détériorant, neutre, améliorant) */
601  int acceptance(Move* move, Configuration* config);
602 };
603 
604 /* marche aléatoire : tout voisin faisable est accepté */
606 class RandomSearch : public Metaheuristic {
607 public:
608  RandomSearch();
609  int acceptance(Move* move, Configuration* config);
610 };
611 
612 /* marche gloutonne : on accepte un voisin de cout inférieur ou égal à la configuration courante*/
614 class GreedySearch : public Metaheuristic {
615 public:
616  GreedySearch();
617  int acceptance(Move* move, Configuration* config);
618 };
619 
620 //-------------------------------------------------------------------------------------------------
621 
622 /* les algos de type GWW
623  les différentes sous classes diffèrent par la gestion du seuil
624 et les regroupements de particules */
625 
630 public:
631  /* nombre de particules */
634  /* indicateur de marche uniquement si la particule a été regroupée
635  (utile pour GWW de base, sans recherche locale, uniquement) (1 oui, 0 non) */
639  /* indicateur de baisse du seuil au dernier mouvement de la marche (pour essayer d'empecher la particule d' etre redistribuée) (1 oui, 0 non) */
643  /* indicateur d'élitisme : remet-on le meilleur individu dans la population à chaque regroupement (1 oui, 0 non) */
645  int elitism;
646  /* indicateur d'arrêt de la marche en cas de stagnation (1 oui, 0 non) */
649  /* le décrément du seuil (calculé par thresholdcomputedelta) */
652  /* le nombre d'iterations max : utile quand pas de seuil (NothresholdGWWAlgorithm) */
655  /* le nombre de changements de seuil (pour les statistiques) */
658  /* le nombre total d'essais de mouvements entre 2 regroupements (pour les statistiques)*/
661  /* le nombre total de mouvements entre 2 regroupements (pour les statistiques)*/
664  /* l'algorithme de recherche locale utilisé */
667  /* destructeur */
668  ~GWWAlgorithm();
669  /* recherche locale sur l'ensemble de la population */
671  virtual void populationrandomwalk(OpProblem* problem, Configuration** population);
672  /* le nombre de particules au seuil (pour les statistiques), la population étant déjà triée à l'appel */
674  virtual int nb_threshold_population(Configuration** population);
675  /* une recherche locale pour une particule */
677  void randomwalk(OpProblem* problem, Configuration* configuration);
678  /* initialisation du seuil */
680  void initthreshold(Configuration** population, int popsize);
681  /* méthode de baisse du seuil (le delta a déjà été calculé)*/
683  virtual void thresholdupdate();
684  /* méthode de calcul du décrément du seuil */
686  virtual void thresholdcomputedelta(Configuration** population);
687  /* déroulement de l'algorithme */
689  void run(OpProblem* problem, Configuration** population);
690  /* regroupement des mauvais individus sur les bons */
692  virtual void regrouping(Configuration** population);
693  /* en cas d'élitisme, on remet le meilleur dans la population */
695  void populationkeepbest(OpProblem* problem, Configuration** population);
696  /* incremente le compteur de changements de seuil (pour les statistiques) */
698  virtual void thresholdchangesupdate();
699 };
700 
701 /* Classe abstraite : GWW avec seuil */
704 public:
705  void thresholdupdate();
706  void thresholdchangesupdate();
707  void initthreshold(Configuration** population, int popsize);
708  int nb_threshold_population(Configuration** population);
709 };
710 
711 /* GWW standard : descente du seuil avec taux fixe */
714 public:
715  /* taux de baisse du seuil */
718  /* seuil minimum (correspond en général à une borne inférieure connue) */
721  void regrouping(Configuration** population);
722  StandardGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, double thresdescent, Long threshmin);
723  void thresholdcomputedelta(Configuration** population);
724 };
725 
726 /* GWW descente du seuil au moins au niveau du pire */
729 public:
730  void thresholdcomputedelta(Configuration** population);
731  FastStandardGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, double thresdescent, Long threshmin);
732 };
733 
734 /* GWW avec descente su seuil en tuant un nombre donné de particules à chaque fois */
737 public:
738  /* nombre de mauvaises particules à regrouper sur les bonnes */
740  int nbkilled;
741  AdaptiveGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, int nbkilled);
742  void regrouping(Configuration** population);
743  void thresholdcomputedelta(Configuration** population);
744 };
745 
746 /* GWW avec descente du seuil au plus bas des valeurs de seuil obtenues par AdaptiveGWWAlgorithm et FastStandardGWWAlgorithm
747  (un nombre de particules et un taux) */
751 public:
752  /* taux de descente du seuil */
755  int nbmaxkilled;
756  FastAdaptGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, int nbkilled, int maxkilled, double thresholddescent);
757  void thresholdcomputedelta(Configuration** population);
758 };
759 
760 /* GWW avec descente du seuil en fonction du médian de la population*/
763 public:
764  /* taux de baisse du seuil : fraction de la distance entre la pire et la médiane (entre 0 et 1) */
767  MedianAdaptGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, double mediandescent);
768  void thresholdcomputedelta(Configuration** population);
769 };
770 
771 /* GWW avec descente du seuil en fonction du meilleur de la population*/
774 public:
775  /* taux de baisse du seuil : fraction de la distance entre la pire et la meilleure (entre 0 et 1) */
778  double bestdescent;
779  BestAdaptGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop, double bestdescent);
780  void thresholdcomputedelta(Configuration** population);
781 };
782 
783 /* GWW sans seuil : 2 paramètres : nombre de tués à chaque itération, nombre d'itérations */
786 public:
787  NothresholdGWWAlgorithm(int population_size, int grtest, int lastmove, int elitisme, int stop,
788  int killed, int nbiter);
789  void regrouping(Configuration** population);
790  /* nombre de particules à regrouper à chaque itération */
792  int nbkilled;
793 };
794 #endif /* INCOP_H_ */
Definition: incop.h:736
int nbkilled
Definition: incop.h:740
Definition: incop.h:773
double bestdescent
Definition: incop.h:778
Definition: incop.h:136
Definition: incop.h:206
Move * computetabumove(Configuration *config)
Definition: incopalgo.cpp:1149
Definition: incop.h:87
virtual void incr_conflicts(int var, int val, int index, Long incr)
Definition: incopalgo.cpp:222
virtual Long get_conflicts_problem(OpProblem *problem, int var, int val)
Definition: incopalgo.cpp:225
int * config
Definition: incop.h:93
virtual void copy_element(Configuration *config2)
Definition: incopalgo.cpp:321
virtual void init_conflicts()
Definition: incopalgo.cpp:221
virtual void update_conflicts(OpProblem *problem, Move *move)
Definition: incopalgo.cpp:230
virtual Long get_conflicts(int var, int val, int index)
Definition: incopalgo.cpp:224
virtual void set_conflicts(int var, int val, int index, Long nbconf)
Definition: incopalgo.cpp:223
vector< int > var_conflict
Definition: incop.h:100
Long valuation
Definition: incop.h:96
int regrouped
Definition: incop.h:104
Definition: incop.h:346
int initmaxneighbors
Definition: incop.h:351
int adjustperiod
Definition: incop.h:357
void dynamicmaxneighbors(int &maxneigh, int &minneigh, int nbmoves)
Definition: incopalgo.cpp:438
int initminneighbors
Definition: incop.h:354
Definition: incop.h:750
double thresholddescent
Definition: incop.h:754
Definition: incop.h:728
Definition: incop.h:168
Long get_conflicts(int var, int val, int index)
Definition: incopalgo.cpp:299
Definition: incop.h:629
virtual void thresholdcomputedelta(Configuration **population)
Definition: incopalgo.cpp:778
void initthreshold(Configuration **population, int popsize)
Definition: incopalgo.cpp:852
int lastmovedescent
Definition: incop.h:642
void run(OpProblem *problem, Configuration **population)
Definition: incopalgo.cpp:722
int total_nbmoves
Definition: incop.h:663
Long thresholddelta
Definition: incop.h:651
int regrouptest
Definition: incop.h:638
int elitism
Definition: incop.h:645
int populationsize
Definition: incop.h:633
virtual void thresholdchangesupdate()
Definition: incopalgo.cpp:863
void randomwalk(OpProblem *problem, Configuration *configuration)
Definition: incopalgo.cpp:679
LSAlgorithm * walkalgorithm
Definition: incop.h:666
virtual int nb_threshold_population(Configuration **population)
Definition: incopalgo.cpp:708
int nomovestop
Definition: incop.h:648
virtual void thresholdupdate()
Definition: incopalgo.cpp:837
int total_nhtries
Definition: incop.h:660
int thresholdchanges
Definition: incop.h:657
virtual void populationrandomwalk(OpProblem *problem, Configuration **population)
Definition: incopalgo.cpp:874
void populationkeepbest(OpProblem *problem, Configuration **population)
Definition: incopalgo.cpp:766
int nbiteration
Definition: incop.h:654
virtual void regrouping(Configuration **population)
Definition: incopalgo.cpp:890
Definition: incop.h:614
Definition: incop.h:375
Long threshold
Definition: incop.h:381
virtual void run(OpProblem *problem, Configuration **population)
Definition: incopalgo.cpp:356
virtual void randomwalk(OpProblem *problem, Configuration *configuration)
Definition: incopalgo.cpp:351
Definition: incop.h:147
Definition: incop.h:397
virtual int configurationmove(OpProblem *problem, Configuration *configuration)
Definition: incopalgo.cpp:525
int test_bestfound(Move *move)
Definition: incopalgo.cpp:372
int walklength
Definition: incop.h:401
Metaheuristic * mheur
Definition: incop.h:407
int nhtries
Definition: incop.h:410
int nbmoves
Definition: incop.h:415
NeighborhoodSearch * nbhsearch
Definition: incop.h:404
virtual int isfeasible(Move *move)
Definition: incopalgo.cpp:628
Definition: incop.h:762
double mediandescent
Definition: incop.h:766
Definition: incop.h:442
virtual void reinit(OpProblem *problem)
Definition: incopalgo.cpp:963
virtual int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:973
virtual void executebeforemove(Move *move, Configuration *configuration, OpProblem *problem)
Definition: incopalgo.cpp:968
Definition: incop.h:510
int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:992
Definition: incop.h:188
virtual void copymove(Move *move)
Definition: incopalgo.cpp:1136
virtual Move * computetabumove(Configuration *config)
Definition: incop.h:201
virtual int eqmove(Move *move1)
Definition: incopalgo.cpp:1158
Definition: incop.h:315
int finished
Definition: incop.h:327
int maxneighbors
Definition: incop.h:322
int minneighbors
Definition: incop.h:319
int var_conflict
Definition: incop.h:330
int val_conflict
Definition: incop.h:333
Definition: incop.h:785
int nbkilled
Definition: incop.h:792
Definition: incop.h:222
int nbvar
Definition: incop.h:229
virtual void best_config_write()
Definition: incop.h:277
virtual void move_execution(Configuration *configuration, Move *move)
Definition: csproblem.cpp:197
virtual void init_population(Configuration **population, int populationsize)
Definition: incop.h:284
virtual void compute_var_conflict(Configuration *configuration)
Definition: incop.h:305
virtual void fullincr_update_conflicts(FullincrCSPConfiguration *configuration, Move *move)
Definition: incop.h:255
Move * currentmove
Definition: incop.h:238
virtual void next_move(Configuration *configuration, Move *move, NeighborhoodSearch *nbhs)
Definition: incop.h:268
virtual void adjust_parameters(Configuration *configuration, int &maxneighbors, int &minneighbors)
Definition: incop.h:265
int domainsize
Definition: incop.h:232
virtual void random_configuration(Configuration *configuration)
Definition: incop.h:271
Move * firstmove
Definition: incop.h:241
Move * bestmove
Definition: incop.h:244
virtual Long config_evaluation(Configuration *configuration)
Definition: incop.h:293
virtual Long compute_conflict(Configuration *configuration, int var, int val)
Definition: incop.h:290
virtual void best_config_verification()
Definition: csproblem.cpp:257
virtual Move * create_move()
Definition: incop.h:262
virtual Configuration * create_configuration()
Definition: incop.h:287
virtual void allocate_moves()
Definition: csproblem.cpp:249
virtual int value2index(int value, int var)
Definition: incop.h:302
virtual void best_config_analysis()
Definition: incop.h:274
virtual Long move_evaluation(Configuration *configuration, Move *move)
Definition: incop.h:296
Long lower_bound
Definition: incop.h:235
virtual int index2value(int index, int var)
Definition: incop.h:299
virtual void incr_update_conflicts(IncrCSPConfiguration *configuration, Move *move)
Definition: incop.h:252
Configuration * best_config
Definition: incop.h:226
Definition: incop.h:606
Definition: incop.h:555
double temperature
Definition: incop.h:565
double inittemperature
Definition: incop.h:559
double delta
Definition: incop.h:562
void executebeforemove(Move *move, Configuration *configuration, OpProblem *problem)
Definition: incopalgo.cpp:1114
int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:1103
SimulatedAnnealing(double initialtemperature, int walklength)
Definition: incopalgo.cpp:89
Definition: incop.h:713
Long thresholdmin
Definition: incop.h:720
double thresholddescent
Definition: incop.h:717
Definition: incop.h:590
float P0
Definition: incop.h:597
int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:1185
float Pd
Definition: incop.h:594
Definition: incop.h:461
int nontabumove(Move *move)
Definition: incopalgo.cpp:1050
list< Move * > move_list
Definition: incop.h:468
int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:1028
int tabulength
Definition: incop.h:465
void reinit(OpProblem *problem)
Definition: incopalgo.cpp:1010
void executebeforemove(Move *move, Configuration *configuration, OpProblem *problem)
Definition: incopalgo.cpp:1059
Definition: incop.h:526
void reinit(OpProblem *problem)
Definition: incopalgo.cpp:1095
int acceptance(Move *move, Configuration *config)
Definition: incopalgo.cpp:1084
ThresholdAccepting(double maxthreshold, int walklength)
Definition: incopalgo.cpp:82
double thresholdinit
Definition: incop.h:530
double thresholdaccept
Definition: incop.h:536
void executebeforemove(Move *move, Configuration *configuration, OpProblem *problem)
Definition: incopalgo.cpp:1089
double delta
Definition: incop.h:533
Definition: incop.h:703