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 */
74class OpProblem;
76class Metaheuristic;
78class Move;
79
80/* la classe Configuration le champ config comprend la configuration elle-même sous forme de tableau d'entiers
81le champ valuation contient sa valeur pour l'évaluation */
82
86
87{
88public:
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 */
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();
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 */
137public:
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
144variables de la configuration : implanté dans tabconflicts (tableau à une dimension) */
148public:
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
164valeur de chaque variable stockée dans le tableau tabconflicts à deux dimensions (variable, indice de la valeur)*/
169public:
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 */
188class Move {
189public:
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 */
206class CSPMove : public Move {
207public:
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) */
223public:
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,
312max voisins explorés et épuisement voisinage et d'autre part par var_conflict et val_conflict */
316public:
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*/
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*/
347public:
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
364class DynamicSpareneighbor : public NeighborhoodSearch {
365public:
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
372la classe mere : algo de recherche incomplet */
376public:
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)*/
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
393un voisinage et une metaheuristique */
398public:
399 /* longueur de la marche */
402 /* le voisinage */
405 /* la métaheuristique */
408 /* le nombre d'essais de mouvements (pour les stats) */
411 double avgnhtries;
412 double avgsqnhtries;
413 /* nombre de mouvements effectués */
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
434class LSAlgorithmGWW : public LSAlgorithm {
435public:
436 LSAlgorithmGWW(int nbmov);
437 int isfeasible(Move* move);
438};
439
440/* les différentes métaheuristiques */
443public:
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
458implantee à l'aide d'une liste de Move* */
461class TabuSearch : public Metaheuristic {
462public:
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
485class TabuGreedySearch : public TabuSearch {
486public:
487 TabuGreedySearch(int tabul);
488 int acceptance(Move* move, Configuration* config);
489};
490
491class IncrTabuSearch : public TabuSearch {
492public:
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
502class IncrTabuGreedySearch : public IncrTabuSearch {
503public:
504 IncrTabuGreedySearch(int tabul);
505 int acceptance(Move* move, Configuration* config);
506};
507
508/* marche Metropolis : un seul paramètre = temperature */
510class Metropolis : public Metaheuristic {
511public:
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 ;
522le seuil diminue linéairement de thresholdinit à 0*/
523
527public:
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 */
556public:
557 /* temperature initiale */
560 /* pas constant de baisse de temperature */
562 double delta;
563 /* temperature courante */
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
591public:
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é */
607public:
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*/
615public:
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
624et les regroupements de particules */
625
630public:
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) */
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 */
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 */
704public:
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 */
714public:
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 */
729public:
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 */
737public:
738 /* nombre de mauvaises particules à regrouper sur les bonnes */
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) */
751public:
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*/
763public:
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*/
774public:
775 /* taux de baisse du seuil : fraction de la distance entre la pire et la meilleure (entre 0 et 1) */
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 */
786public:
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 */
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 int eqmove(Move *move1)
Definition incopalgo.cpp:1158
virtual Move * computetabumove(Configuration *config)
Definition incop.h:201
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 void allocate_moves()
Definition csproblem.cpp:249
virtual int value2index(int value, int var)
Definition incop.h:302
virtual Move * create_move()
Definition incop.h:262
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 Configuration * create_configuration()
Definition incop.h:287
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
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
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