Optimisation combinatoire et métaheuristiques

[karima]

L’industrie moderne et l’ingénierie se doivent constamment de concevoir des technologies ou produits de plus en plus petits rapides et fiables et cela en respectant un certain budget.
Ces contraintes donnent lieu à des problèmes d’optimisation : on définit une certaine fonction objectif ou fonction de cout que l’on cherche à minimiser ou à maximiser par rapport à tous les paramètres concernés, le but initial étant de trouver la solution optimale.

Il y a deux types de problèmes d’optimisation :
- Les problèmes discrets, exemple : problème du voyageur de commerce où il s’agit de minimiser la longueur de la tournée d’un « voyageur de commerce » qui doit visiter un certain nombre de villes avant de retourner à la ville de départ.
- Les problèmes à variables continues , exemple : la recherche des valeurs à affecter aux paramètres d’un modèle numérique de processus pour que ce modèle reproduise à mieux le comportement réel observé.

Pour certains de ces problèmes, trouver la solution « optimale » demanderait des millions d’années de calcul aux machines les plus rapides (certains problèmes d’optimisation discrets pour lesquels on ne connait pas l’algorithme exact polynomial. Le cas des problèmes dits NP-difficiles, et certains problèmes d’optimisation à variables continues pour lesquels on ne connait pas l’algorithme permettant de repérer un optimum global à coup sûr et en un nombre fini de calculs).

Les algorithmes déterministes n’étant plus d’aucun secours, il a été nécessaire de trouver des méthodes permettant d’approcher la meilleure solution en un temps raisonnable : les Métaheuristiques.

à suivre......