Métaheuristique pour un problème d'ordonnancement

**Hypnocrate** · 03/01/2009, 23h05

Bonjour,
Quelle est d'après vous la meilleure métaheuristique adaptée à un problème d'ordonnancement (ou de permutation pour faire simple).
J'hésite entre algo G ou recherche tabou.
Merci.

**ToTo13** · 05/01/2009, 09h06

Bonjour,

pour un algo qui doit trouver la meilleure combinaison, je serai plutôt d'avis d'utiliser une tabou.

**Hypnocrate** · 05/01/2009, 16h04

Merci, c'est aussi mon avis.

**ToTo13** · 05/01/2009, 18h07

Bonsoir,

mais le plus difficile n'est pas de développer l'algo, mais c'est toujours de développer les fonctions spécifiques au problème. Dans le cas de la tabou ce sera surtout la recherche de la meilleure solution et la fonction d'aspiration.

**Hypnocrate** · 05/01/2009, 23h56

Bonsoir,

Qu'est ce que tu appelles fonction d'aspiration?

**ToTo13** · 06/01/2009, 01h10

Bonsoir,

c'est une fonction importante de l'algorithme à appeler plus ou moins régulièrement selon les paramètres.
Cette fonction sert à aspirer certaines solution dans la liste tabou. En effet, certaines solutions rendues tabou (alors qu'elles ont peut être apporté la meilleure solution) ne devraient pas l'être. Pour cela, on construit une fonction d'aspiration qui aspire dans la liste tabou certaines solutions.
Pour ma part j'ai implémenté une méthode tabou qui n'utilise pas cette méthode : ma solution tire la meilleure solution en suivant des probabilités conditionnelles et les durées durant lesquelles les solutions sont tabous sont tirées aléatoirement en fonction de ce qu'apporte la solution. Ces deux façons de faire permettent de ne pas avoir à aspirer des solutions.

Je te conseille de lire un livre qui s'appelle : "Métaheuristiques pour l'optimisation difficile". Ce livre traite de toutes les étapes délicates des différentes métaheuristiques et de leurs différentes implémentations possibles.