Discussion :

[Alexandre`]

Bonjour,
J'essai de me renseigner sur la génération d'emploi du temps avec des algorithmes de type génétique et réseau de neurone.

C'est un domaine un peu inconnu donc j'ai lu quelques papiers qui ne mentionne jamais ce type d'exemple (il ressort souvent le "voyageur...").

Je voulais savoir si c'était quelque chose d'inaccessible voir irréalisable... Sinon si quelqu'un avait quelques infos là dessus : un nom d'algo, d'un chercheur, de thèses ou autres.

Merci pour votre aide.

[mamelouk]

Salut,

Je suppose que tu dois parler de la planification de taches avec contraintes? (génération automatique de diagramme de gantt etc ?)

Ils font beaucoup ce genre de choses au LAAS à Toulouse (appliqué à de la robotique mais les algo sont génériques).

Si c'est bien ca que tu cherche je peut regarder mes cours pour me rappeler des noms d'algo. Ce nom pas des algos génétiques ni réseau de neurones qui sont utilisés donc c'est normal que tu ne trouve de référence à ce problème dans ces technos.



A+

[borisd]

Tu peux essayer "timetabling" comme mot clé sur un moteur de recherche si l'anglais ne te fait pas trop peur. Voici des exemples de ce qu'on trouve avec "genetic timetabling" sur google :
http://www.mft.hu/hallg/200107.pdf
http://www.stats.ox.ac.uk/~kostuch/T...iles/frame.htm
Malheureusement la plupart des articles sont payants...

Les conférences PATAT sont consacrées à la résolution des problèmes de planification grâce à tout type d'approches. Tu peux chercher l'inspiration dans leur actes (ceux de 2006 par exemple :
http://www.asap.cs.nott.ac.uk/patat/...roceedings.pdf)

[Rakken]

Si tu veux génerer des emplois du temps, plutôt que de t'orienter vers des algo génétique ou neuronaux, je pense que tu devrait aller voir la programation par contrainte (ppc de son ptit nom).

C'est, je pense tout a fait adapté à la génération d'emplois du temps.

--
Rakken

[Alexandre`]

Salut, merci pour ta réponse,
enfait je voudrais mêler personnes, lieux pour générer un emploi du temps.

Donc des contraintes seraient issus de chacun de ces 2 éléments (personne : disponibilité. Lieux : places, etc.)

Edit : J'avais commencé mon post y'a 2 heures, alors il y a eu pas mal de réponses entre temps.

Merci pour toutes ces réponses. Je vais voir de quoi il en retourne ! Merci.

[mamelouk]

Si tu veux génerer des emplois du temps, plutôt que de t'orienter vers des algo génétique ou neuronaux, je pense que tu devrait aller voir la programation par contrainte (ppc de son ptit nom).

C'est, je pense tout a fait adapté à la génération d'emplois du temps.

--
Rakken

Tiens ca me rappelle qu'à notre tp de csp on avait justement programmé un générateur d'emploi du temps - d'après mes souvenirs c'était tout de meme assez compliqué, mais pourquoi pas. Il existe des moteurs de satisfaction de contraintes gratuit ? (open source si possible ??)

[Rakken]

Tu peux toujours regarder par là :
http://choco.sourceforge.net/
http://sourceforge.net/projects/cassowary/

Par contre, je ne les ai pas testé. La ppc que j'ai pu étudier en cour était sur un logiciel commercial (vaguement développé par le prof d'ailleurs ) dont j'ai complètement oublié le nom.

--
Rakken

[Alexandre`]

Merci pour vos réponses, j'ai de quoi lire

[palm007]

Bonjour,
Moi aussi je cherche une solution a ce probleme depuis des mois
c'est vrais que ca ressembl au problem du voyageur mai il ya une grande difference .
on ne peut pas utiliser l'algorithme genitique a cause de probleme de degradation de la population ...le hasard ici ne fait pas evoluer la population ....je l'ai essaiyer mai aucune bonne resultat!
j'ai etudier aussi quelque type de reseau de neuron .le problem ici c'est comment on fait l'apprentissage du reseau , si en arrive a definir le entrees et les sorties.
j'ai essaye un petit exemple qui fait son aprentissage on suivant une affectation par un algorithme simple .mon but etait de faire apprendre au reseau comment affecter les seances ?
puis l'algorithme refait son travail mais le reseau choisi les places !
malheuresement actuellemnt pas de bonne resultat encorp...
ceci a cause du grand nombre d'entre (1500).
un bonne apprentissage necessite un tres grand nombre des cas et un bonne coeifficient d'aprentissage ....ceci apparament demande des jours et des jours ...pour surmenter ce probleme j'ai diminuer le nobre d'etiration .....
vous savez ....je pense que vais abonndonner cet idée.....
ce probme est une vrai casse tete...

[borisd]

Un grand nombre de solutions plus ou moins heureuses suivant le problème exact sont possibles (encore une fois, "timetabling", "university timetabling" ou "automated timetabling" sous Google donne pas mal de pistes).

Si vraiment tu cherches une solution relativement simple et sans recherche documentaire, voici un moyen qui peut devenir assez efficace selon le paramétrage qui en est fait (algorithme de liste + méthode de voisinage) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
- affecter toutes les personnes, lieux, cours... au premier moment où ils sont disponibles et où ils respectent toutes les contraintes (non-ubiquité, disjonction,...), en les choisissant dans un ordre donné (par exemple, les personnes ou les salles ayant l'emploi du temps le plus difficile (le moins de temps dispo) en premier...)
- parcourir toutes les affectations faites deux par deux, et regarder ce qui se passe si on les échange (que se passe-t-il si je mets le prof 1 qui était en salle B015 de 16h à 17h à la place du prof 2 qui était en B016 de 10h à 12h ?). S'il est possible de les échanger et que ça parait mieux (il faut ainsi définir ce qui paraît "bien"), permuter les deux (et recalculer les bouts d'emploi du temps qui peuvent devoir être décalés...)

Tu peux envisager beaucoup de manières de permuter des éléments (seulement les profs, seulement les salles, tout d'un coup, prendre un cours et l'insérer entre deux autres au lieu de permuter...) ; il faut tester et voir ce qui fonctionne le mieux dans ton cas.
Ce genre de méthode peut être beaucoup amélioré en utilisant des méthodes type "tabou" ("recherche tabou et planification" sous Google par exemple).

[palm007]

merci a vous !!!
grace a vous simple indication je commence a trouver des bonne piste ...
je commence a collecter des information sur la fonction de fitness qui un facteur majeur de reussite du produit
et aussi il me reste a choisire la bonne manier de faire le croisement entre les des parent jr vais eassayer qlq methode et voire le resultat ....
a pris avoir lus plusier doc je pense actellemnt qu j suis sur la bonne piste ..
il me reste aussi a decouvrir les autre methode tabou et autre pour savoir de qoi il sagit et peut etre qu'on peut encore ameliore les resultat grace a une combinaison entre 2 algo geneti et tabou ou genetic et neuron ou autre methode d'optimisation hybride .....
je commence ce travail seul depuis des annee et je comme a faire des serieuse que ces jours grace a vous aide et indication merci a vous tous et ace forum.....
a bientot

[ratrout]

j'ai a programmer un emploi du temps d'une ecole comme sujet de memoire.je dois utiliser java,et la programmation par contrainte. alors qu'en pensez vous de choco. est-ce que vous avez une meilleur idee? est-ce qu'il ya un exemple d'emploi de temps qui pourra m'aider. j'ai vraiment besoin de votre aide pour continuer. merci d'avance.

[Darklingg]

Bonjour,

Pour répondre au premier post, c'est effectivement possible d'utiliser un algorithme génétique pour ce genre de problème.

J'ai eu plus de succès en utilisant la programmation génétique que la programmation par contraintes quand le problèmes devenait vraiment gros.
( par exemple quand il y a tellement de contraintes que l'on ne peut plus trop les lister )

Pour l'algorithme génétique, tu considères une population d'emplois du temps et tu calcul pour chacun une erreur.

Plus ta fonctions d'erreur sera précise, plus tu auras de succès ( mais plus elle sera compliquée ).

Pour un problème de plusieurs milliers de groupes d'utilisateurs et plusieurs dizaines de milliers d'utilisateurs, ça converge asser vite pour que ce soit applicable dans une application industrielle.
Plus gros, je ne sais pas... je n'ai jamais testé.

Pour les réseau de neurone, je ne connais pas d'application efficace à ce genre de problème.
En revanche, je réfléchis à une idée qui semble prometteuse...
Mais il faudra attendre quelques mois!

[ratrout]

A votre avis, est ce que la programmation par contrainte et surtout la librairie choco ne peut pas resoudre mon probleme qui est la programmation de l'horaire d'une ecole (primaire-complementaire). c'est obligatoire de la remplacer par la programmation genetique ou quoi. je ne comprends pas. j'ai pas trop de temps. je me sens perdue. merci de me repondre le plus tot possible pourque je sache continuer.

[Rakken]

Oui, la ppc peut résoudre ton problème.
Choco, je ne connais pas.
Non, tu n'es pas obligé de "remplacer par la programmation genetique". En fait, sauf si c'est un exercice scolaire, tu n'es obligé de rien du tout. Pour un cas suffisament simple, tu peux même te coder un truc sur mesure, a la main (tu peux aussi pour un cas compliqué, mais c'est nettement plus dur ^^).

La création d'emploi du temps via la ppc est un des thèmes de base, c'est presque un cas scolaire j'ai envie de dire. Si tu veux faire ca, commence par apprendre vraiment ce que c'est que la programmation par contrainte, c'est éventuellement assez particulier et il faut un certain entrainement avant d'être capable de transformer un ennoncé en contrainte judicieuse.

[ratrout]

je n'ai pas tres bien compris.et je ne sais pas si je n'etais pas precise.j'ai besoin de resoudre un emploi de temps d'une ecole de 25 classes et une trentaine de profs (cadres ou non) .alors trop de contraintes lourds et legers.j' aime bien savoir si je suis sur le bon chemin en appliquant la programmation par contrainte et la lib choco ou dois je passer a l'algo genetique et autre quand il y a trop de contraintes et de preferences.jai a programmer ce type en minimum de temps et avec une meilleure methode autre que le langage classique pour meriter d' etre un sujet de memoire d'ingenieur.
en fait j'ai lu un peu un article sur le timetabling en alg genetique , mais je prefere continuer en programmtion par contrainte si cest possible.car j'ai deja fait trop de recherche la dessus.
merci de me repondre rapidement et de m'aiguiller .