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