Forum Programmation.autre Optimisation et Recherche opérationnelle : quel algo ?

Posté par  .
Étiquettes : aucune
0
25
mar.
2006
Salut à tous !

Je me tourne vers vous aujourd'hui, car je suis dans une impasse. Je dois réaliser un projet dans le cadre d'un cours intitulé "Optimisation et recherche opérationnelle".

Comme vous vous en doutez, nous étudions dans cette matière, différentes méthodes d'optimisation. Au programme, nous avons :

- programmation linéaire
- programmation en nombres entiers : méthode des coupes
- application des graphes à la Recherche Opérationnelle : programmation dynamique, recherche arborescente
- méthodes heuristiques : algorithme de descente et du kangourou, recuit simulé, méthode tabou.
- optimisation distribuée : colonie de fourmis, intelligence en essaim
- optimisation de processus stochastiques
- théories des jeux
- algorithme génétique

Pour le moment, nous n'en sommes qu'au premier point, c'est à dire la programmation linéaire. Cependant, les profs nous ont déja donné le sujet de notre projet, et pour cause, il est compliqué et long à réaliser. Nous pouvons utiliser la méthode que nous voulons, du moment que les résultats obtenus sont bons. Nous pouvons même utiliser une méthode qui n'est pas au programme du cours.

Je dois rendre la spécification de ce projet pour le 12 avril. Nous avons eu le sujet cette semaine, et je ne vois meme pas par où commencer...

Je vais quand meme vous parler du sujet :D

Il s'agit d'écrire un programme, dans le langage de notre choix, qui permettra de gérer les emplois du temps de notre école de meilleure façon qu'ils ne le sont actuellement. On fournira 2 fichiers texte au programme. Le premier contient la liste de tous les cours, TD et TP et les jours et horaire de leur plannification. Le second contient la liste des étudiants, et les unité de valeurs (cours) auxquelles il est inscrit.
Le programme devra calculer la meilleure façon de répartir les différents étudiants dans les différents cours, TD et TP, afin qu'il y ait le moins d'incompatibilité possible (2 TD en meme temps par exemple).

Vous pouvez voir le sujet détaillé du projet en suivant ce lien : www.ifrance.com/brigadenord/sujet.pdf

Mon problème est le suivant : je ne sais pas du tout quel algorithme utiliser pour gérer ce problème, étant donné que je n'en connais aucun. J'ai cherché sur internet, mais je ne trouve rien qui explique clairement le fonctionnement d'un des algorithme cité plus haut, et je dois connaitre le fonctionnement de tous, si je veux choisir le plus adapté...

Ma question : est-ce que quelqu'un pourrait me diriger vers un algorithme qu'il sait adapté à ce projet, ou m'expliquer le fonctionnement des algos cité plus haut ?

D'avance merci pour le coup de main.

Nicolas

  • # Algo du simplexe de Dantzig ?

    Posté par  . Évalué à 2.

    Salut,

    J'ai étudié la recherche opérationnelle dans le cadre de mes études au CNAM, et dans la programmation linéaire j'ai surtout étudié l'algorithme du simplexe qui permet soit de maximiser soit de minimer une fonction économique (la fonction Z) à partir d'un ensemble de contraintes qui modélisent ton problème initial.

    Il existe bon nombre d'algorithme, je pense que le mieux est d'abord d'acheter les livres traitant de la recherche opérationelle afin de voir quel est le modèle qui se rapproche le mieux de ta problématique, ensuite se pose la question de l'implémentation et donc de la programmation.

    Je te conseille "précis de la recherche opérationnelle" de chez Dunod que tu trouveras facilement dans la librairie "Arts et Métiers", il existe aussi 3 thomes qui sont des exercices corrigés traitant des 3 grandes parties de la recherche opérationnelle (graphes, PL, files d'attente etc..)

    J'espère que tu y trouveras ton bonheur :-)

    Bon courage

    • [^] # Re: Algo du simplexe de Dantzig ?

      Posté par  . Évalué à 1.

      Malheureusement, je dois rendre la spécification de mon projet pour le 12 avril, et je dois donc décider de la méthode que je vais employer avant. Ca me laisse peu de temps pour lire un livre sur le sujet. Cependant, je note la référence, car cela pourra m'etre utile par la suite :)

      Merci

    • [^] # Re: Algo du simplexe de Dantzig ?

      Posté par  . Évalué à 1.

      Je ne connais pas le domaine, mais dans le Pascalissime numéro 56 (octobre décembre 1993), il y a article présentant la résolution de simplexe avec des réseaux neuronaux
      Google ne donne pas de référence de cet article.

  • # Algo Genetique

    Posté par  . Évalué à 2.

    Bonjour,

    Je serais à ta place je m'orienterais vers un algo génétique(le recuit simulé doit etre bien aussi mais je ne connais pas assez pour te le conseiller :p ).

    Une fois que l'alog est assimilé, ca va assez vite à coder et surtout si l'heuristique ( crossover) est bonne, tu trouveras des resultats satisfaisant en peu de temps(pas LE meilleur résultat).

    En cherchant un peu sur google exalead ou autre tu trouveras beaucoup de renseignement dessus.

    Ce qui sera important ca sera la fonction d'évaluation des entités. Tu pourras meme faire plusieur fonction d'évaluation :D avec une par exemple qui optimise les cours des élèves sur un mimimum de jour (moi jai pas avoir un cours le mercredi pas de cours le jeudi et un cours le vendredi je prefere tout sur deux jours :p ).
    Tu pourras aussi faire une évaluation du genre le moins de cours possible dans la semaine sur tt les eleves donc en clair mettre un maximum d'élève dans un cours pour eviter d'utiliser un deuxieme crenaux :) bref y a plein de possibilité après peut être que le sujet d'impose certaines règles (désolé j ai pas ete voir le lien :p). En tous cas, tous repose sur la fonction d'évaluation.

    Voilà, j'espère que ca va t'aider un peu. Sinon pour le langage prends un langage oriente object ;) .

    • [^] # Re: Algo Genetique

      Posté par  . Évalué à 1.

      Je viens de lire le sujet et donc je ne change pas mon opinion :p et je pense que pour un programmeur moyen, et connaissant dékà le langage qu'il va utiliser et les algo gènes, il doit pas mettre plus d'une semaine(et encore je vois large :)).

      En tous cas c'est marrant comme sujet.

    • [^] # Re: Algo Genetique

      Posté par  (site web personnel) . Évalué à 1.

      Je suis tout a fait d'accord avec cette idée. A mon avis, le problème des emplois du temps est un problème qui doit avoir des solutions satisfaisantes utilisant une algorithmique génétique. Par contre, je ne voit pas en quoi le langage devrait etre absolument orienté objet, l'essentiel est de trouver un langage qui te permet d'exprimer la finalité de ton approche. Il existe pas mal de librairies qui implémentent les fonctionalités de base pour l'algorithmique évolutionniste, perso, je te recommande beagle, codée en C++.

      Pour en revenir à ton problème, "tout est dans le choix Néo", il faut que tu choisisse le mode de développement qui corresponde à ton modèle :

      * exhaustif : tu cherche toutes les solutions et choisi la meilleure (pas conseillé pour ce genre de pb)
      * basé modèle : tu pose le cadre d'un modèle et cherche à optimiser des paramètres (ex : algo géné)
      * basé exemples : tu cherche à faire de la régréssion sur une base d'exemples (ex : réseaux de neurones artificiels)
      * basé connaissance : tu cherche à établir un modèle précis du processus (ex : logique floue, reseau bayesiens ...)
      * basé apprentissage : tu as une entité qui cherche à découvrir son environnement. (ex : SARSA, QLearning)

      Bonne chance ...

      Adhérer à l'April, ça vous tente ?

  • # Un système multi-agent à enchères

    Posté par  . Évalué à 2.

    J'avais réfléchi à un problème un peu similaire et j'avais imaginé un système original.. mais je ne l'ai pas testé (manque de temps) : écrire un système à agent enchérisseurs.

    Chaque étudiant est modélisé par un agent qui possède un certaine nombre de points qui dépend du nombre d'UV où il est inscrit (genre 100 points par UV). A chaque itération, chaque agent participe à des enchères pour "acheter sa place" à un certain horaire (ajouter ou enlever des points) en tentant de maximiser son contentement (louper un minimum de cours/TP/TD). Ainsi, à chaque itération, l'agent gagne des places à certains endroits, et pour cela en perd à d'autres...

    Je pense que cette approche est intéressante, même si elle ne garantie pas de trouver la solution optimale (de toute façon, on ne peut surement pas satisfaire tout le monde) : Chaque itération supplémentaire devrait avoir tendance à stabiliser le système (enfin, selon le comportement des agents...). En gros, tu ne peux pas te planter, mais juste avoir une solution moins optimale que les autres (mais j'en doute... ;-)

    Toute la finesse de la programmation, c'est l'algo de décision de l'agent. Rien n'empêche d'implémenter plusieurs agents et de tester le système selon diverses configurations (que des agents de type A, que des agents de type B, 50% de A et 50% de B, 25% de a et 75% de B)... Et coder un proto assez avançé avec cette solution, ça ne devrait pas prendre plus d'une trentaine d'heures ;-)

    Tu peux même "pousser le bouchon" en proposant à tes profs de modéliser ces agents selon une études (courte) sur le comportement qu'auraient des "étudiants représentatifs" si un système d'enchère était mis en place, pour obtenir des statistiques après simulations (avec des jolis graphiques y tout y tout). Je pense que ça serait très "smart" et il y a de quoi réellement s'éclater! Tes profs devraient aimer.

  • # Merci

    Posté par  . Évalué à 1.

    Merci à tous pour vos éclaircissements et conseils.
    Je vais donc me renseigner sur le net sur les algo génétiques.

    Si vous vous sentez de me faire une explication claire et concise, je suis preneur.

    Et si d'autres personnes voient une meilleure solution qu'un algo génétique, merci de m'en faire part :)

    Bon dimanche à tous.

    Nicolas

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.