POO: Recuit_Simule

[invitecef73ce6]

Bonjour à tous!

J'ai eu l'occasion d'étudier la technique d'optimisation du recuit simulé sur un plan mathématique. ( --> donc théorique! ). Or je voulais créer un petit programme pour démontrer l'efficacité pratique de cette méthode et, n'étant pas un pro en programmation, je bloque sur le code!
Je n'arrive pas à traduire mon problème en langage informatique, peut-être que vous pourrez m'y aider...

Voici le projet :

Il s'agit de placer 25 composants éléctroniques dans des places prédéterminées. Les composants sont reliés entre eux d'une facon prédéterminée ( voir schéma plus bas ) et le but de l'optimisation est de trouver la configuration qui minimise les connections entre les composants. La seule "opération" autorisée pour trouver la solution optimale est la permutation de deux composants. La solution optimale est connue à l'avance ( il s'agit uniquement de démontrer l'efficacité du recuit simulé ).

Voici le schéma : les chiffres représentent les composants.

1-2-3-4-5
6-7-8-9-10
11-12-13-14-15
16-17-18-19-20
21-22-23-24-25

Même si les chiffres de sont pas alignés, il faut se représenter un carré comme ci dessous : les 1 représentent les composants ( pas de distinctions entre les composants )

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

J'ai représenté au dessus la solution optimale, ce qui me permet d'expliquer comment les composants sont reliés :
le 1 est relié avec le 6 et le 2, le 2 est relié avec le 1 le 3 et le 7, le 3 est relié avec le 2 le 4 et le 8 etc.

Je précise ( comme dans le titre du topic ) que j'utilise un langage orienté objet!

Alors, je représente les composants et les places disponibles par deux arrays de points ( je représente les composants par des points ). Pour les permutations, je sélectionne au hasard deux indexes de l'array des composants et j'inverse leur contenu.
Mais j'ai un problème pour relier et calculer le coût ( la longueur ) total des connections d'une manière efficace... C'est à dire que la seule technique que j'ai trouvé est de considérer chaque composant et de spécifier ce que j'ai dit plus haut : le composant 1 est relié au 2 et au 6 etc. pour chaque composant! N'y aurait-il pas un moyen de calculer le cout total à l'aide d'un loop? Je n'ai pas trouvé comment...

J'espère avoir été clair, j'ai fait mon possible!

Merci pour votre aide!
-----

[invite4cfbfb28]

Bonjour

Je ne connais rien à la technique que vous décrivez n'étant pas dans le domaine des mathématiques. Cependant ce que je comprends de votre simulation c’est que vous voulez obtenir l'arrangement optimal (càd: avec le moins de liens possible) sur l'ensemble du montage ?

Si je comprend toujours bien, la solution donnée 1-2-3-4-5 ... est la réponse et est totalement optimisée ? Donc aucune permutation ne serait possible dans ce cas-ci ? Aussi, serait-il possible d'avoir un exemple d'échantillon de départ (avant optimisation) pour aider à ma compréhension ?

Maintenant, pour ce qui est de la programmation, je crois que la façon de résoudre ce problème passe plus par une fonction récursive (càd : fonction qui s'appelle elle-même) que par une boucle. Peut-être même qu’il serait possible de résoudre le problème en plaçant les éléments dans un arbre de données et d’effectuer les permutations sur cet arbre.

J'ai de la misère à me représenter un échantillon de départ, a lui appliquer une permutation et déterminer que cette permutation est la bonne chose à faire pour arriver à la solution optimale.

Si vous pouvez m'éclairer un peu sur ces points peut-être serais-je plus en mesure de composer un algorithme de départ.

Bonne journée

[invitecef73ce6]

D'accord, alors disons que le programme commence par générer une configuration de départ. Donnons pour exemple totalement arbitraire celle ci ( il existe 25! configurations différentes ) :

6-8-17-13-10
21-2-15-24-22
11-1-5-14-25
9-23-18-12-7
3-19-4-20-16

Encore une fois, les chiffres sur ce schéma ne sont pas alignés mais devraient l'être comme ceci :

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Dans cette configuration aléatoire, le 1 est toujours relié avec le 6 et le 2 etc. et l'on voit donc bien que la longueur totale des connections dépasse largement celle de la configuration optimale présentée dans mon premier message.
Disons qu'une distance de 10cm sépare chaque composant, alors la configuration optimale donne un cout total de 400cm.

Est-ce plus clair comme ceci?

Le but est ensuite, à partir de la configuration générée de manière aléatoire, d'effectuer des permutations de composants jusqu'à obtenir la configuration optimale. Cependant, tester les 25! possibilités serait trop long, on peut donc optimiser le système.

Pour le faire, j'utilise la méthode du recuit simulé. Il s'agit d'instaurer un paramètre ( la température ) qui sera décérmenté progressivement. Voici le pseudo-code du recuit simulé:

1: On donne une configuration initiale quelconque
2: On donne une température initiale T
3: while Le système n’est pas figé do
4: On fait une modification élémentaire du système qui nous donne une variation
d’énergie deltaE
5: if deltaE <= 0 then
6: Modification acceptée
7: else
8: Modification acceptée avec la probabilité exp −deltaE/T
9: end if
10: if Equilibre thermodynamique then
11: Diminution lente de T
12: end if
13: end while

Je n'ai pas de problème pour implanter le code du recuit, mais pour calculer le cout total des connections ( la fonction à optimiser finalement ) c'est plus délicat...

[invite4cfbfb28]

Merci pour les explications ça aide à ma compréhension. Ils me reste quelques points à préciser.

Encore une fois, les chiffres sur ce schéma ne sont pas alignés mais devraient l'être comme ceci :

Utilisons ceci à la place (01, 02...):

06-08-17-13-10
21-02-15-24-22
11-01-05-14-25
09-23-18-12-07
03-19-04-20-16

il existe 25! configurations différentes

Comment arrivez-vous à ce chiffre? Je vois plus de 25 configurations possibles. Seulement en déplaçant 1 composant et en ne touchant pas aux autres ont a déjà 25 configurations. En considérant le tableau comme une suite linéaire (1,2,3,4,5,6,7,8,9...) on obtient 325 possibilités. En éliminant les arrangements symétriques cela fait au moins 163 configurations possibles. (Je ne garantis le résultat mais ce nombre me semble logique)

Ceci étant dit, que ce soit 25 ou 163, je suis d'accord avec le fait qu'on ne puisse pas évaluer toutes les configurations.

J'utilise la méthode du recuit simulé. Il s'agit d'instaurer un paramètre ( la température ) qui sera décérmenté progressivement

Si j'ai bien compris la méthode du recuit simulé ne sera appliqué que sur la solution finale optimisée afin d'approuver la configuration?

Je n'ai pas de problème pour implanter le code du recuit, mais pour calculer le cout total des connections ( la fonction à optimiser finalement )

À vu d'oeil pour évaluer la longueur totale des liens entre les composants pour une configuration donnée je fera ceci:

1) Comme nous ne voulons pas additionner 2 fois la longueur d'un lien, il faut premièrement déterminer l'ensemble des liens à évaluer. Cet ensemble pourrait être le suivant:

{{01,02},{01,06},{02,03},{02,0 7},{03,04},{03,08},{04,05},{04 ,09},{05,10},
{06,07},{06,11},{07,08},{07,12 },{08,09},{08,13},{09,10},{09, 14},{10,15},
{11,12},{11,16},{12,13},{12,17 },{13,14},{13,18},{14,15},{14, 19},{15,20},
{16,17},{16,21},{17,18},{17,22 },{18,19},{18,23},{19,20},{19, 24},{20,25},
{21,22},{22,23},{23,24},{24,25 }}

Ici j'ai pris tous les liens vers le bas et vers la droite sans considérer ceux vers la gauche et le haut. De cette façon j'élimine les dédoublements. Ex: ne pas calculer 01-02 ET 02-01.

2) Ensuite il faut pour chaque liens de l'ensemble précédant calculer la longueur du lien avec une formule comme celle-ci:

Pour 2 composants aux coordonnées (x1, y1) et (x2,y2)
longueur_lien = Math.abs(x2-x1) + Math.abs(y2-y1)

3) Ensuite il faut incrémenter la valeur de chaque lien dans une variable et on obtient la longueur totale de l'ensemble des liens de la configuration à la fin de la boucle.


Maintenant j'aimerais apporter quelques remarques...

- Ici nous n'utilisons aucun des principes de la POO.

- L'ensemble des coordonnées que j'ai donné plus haut pourrait sûrement être construit par un algorithme, mais considérant un tableu de 5X5 le fait de définir l'ensemble en extension simplifie la chose.

- Je ne sais pas si le fait de permuter les éléments de façon aléatoire est la meilleure façon d'arriver au résultat optimal. Si la solution optimale est toujours une solution avec une longueur de lien totale de 400cm (soit 40 liens de 10 cm), je crois qu'on pourrait réaliser un algorithme plus précis pour rapprocher les composants de façon plus logique les uns des autres. Je doute même que le fait de permuter de façon aléatoire puisse mener à la solution optimale dans un temps raisonnable. On peut facilement imaginer que plusieurs permutations devront rendre le schéma moins optimal pendant certaine permutation pour ensuite le réorganiser vers un arrangement plus optimal. Ce cas ne pourrait pas être réalisable par un algorithme aléatoire vu qu'une permutation "perdante" serait refusée...


J'espère avoir bien saisit le problème cette fois-ci. En espérant avoir été clair...

[A voir en vidéo sur Futura]

[Jack]

bonsoir,

je crois qu'il fallait lire factorielle de 25 (25!).

Ca remonte à loin pour moi, mais ça resemble à s'y méprendre au "problème du voyageur de commerce". Celui-ci doit se rendre dans toutes les villes d'une liste en effectuant une distance minimale.

Je ne pense pas qu'il soit possible de trouver un algorithme qui puisse trouver la solution exacte en un temps raisonnable.

Voila les 3 algorithmes (extraits du compte rendu) que j'avais mis en oeuvre dans mon projer à l'époque. Les machines étaient des 286 à 12MHz et on pouvait raisonnablement aller jusqu'à 25 villes.

Algo N°1:
Nous avons développé en premier lieu l'algorithme des minimums successifs car il nous semblait le plus simple et permettait d'effectuer un parcours complet.
Partant d'une ville de départ fixée nous recherchons parmi les N-1 autres villes à visiter celle qui se trouve à la distance la plus proche, puis à partir de cette dernière nous répètons la même démarche en recherchant la ville suivante parmi celles non encore parcourues; et ceci jusqu'à ce que toutes les villes soient visitées. Pour connaître la distance totale nous ajoutons successivement toutes les distances minimales ainsi que la distance séparant la dernière ville visitée de celle de départ, ceci pour refermer le parcours.
Ce parcours étant fortement lié à la ville de départ nous avons lancé cette recherche successivement à partir de chacune des N villes en ne retenant à la fin que le meilleur des N parcours. Cependant il est indépendant de l'ordre suivant lequel on scrute les différentes étapes possibles.

Algo N°2:
Dans cet algorithme nous avons considéré un parcours existant sur N villes et nous avons cherché le meilleur chemin traversant une ville supplémentaire. Nous avons calculé la distance totale du parcours en insérant cette ville entre toutes celles déjà reliées. Le meilleur résultat définit ainsi le meilleur parcours sur N+1 villes. Donc partant de 2 villes nous avons appliqué cette démarche en insérant successivement toutes les villes que le voyageur devait traverser. Le parcours étant fortement lié à la ville de départ nous avons lancé cette recherche successivement à partir de chacune des N villes en ne retenant à la fin que le meilleur des N parcours. De plus cet algorithme reste fortement lié à l'ordre suivant lequel on scrute les différentes étapes possibles. Ainsi pour un même jeu d'essai, de l'ordre suivant lequel seront rangées les villes résulteront plusieurs trajets différents.

Algo N°3:
Nous avons développé cet algorithme de manière à déboucher systématiquement sur le meilleur résultat. Pour cela l'algorithme explore tout les chemins possibles. En partant d'une ville quelconque il va la relier à toutes les autres non encore parcourues et appliquer à nouveau ce raisonnement récursivement à chacune de ces dernières jusqu'à ce que toutes les liaisons soient effectuées.
A chaque liaison il calcule la distance parcourue et il stoppe la recherche dès que cette distance dépasse celle d'un parcours déjà trouvé.
De plus pour accélérer la recherche d'un premier parcours il prend comme distance minimale de départ, celle rendue par l'un des deux algorithmes précédents.
Pour la même raison, le parcours se fera en profondeur d'abord de manière à diminuer cette distance minimale le plus vite possible durant la recherche.

A+

[invitecef73ce6]

Hello!

Effectivement, il s'agit d'un problème similaire à celui du voyageur de commerce.
Il existe effectivement plusieurs algorithmes pour le résoudre : recuit simulé, colonie de fourmis, algorithmes évolutionnaires, algorithmes génétiques etc.

Pour ce problème de composants, je choisis le recuit simulé.

En effet, il fallait lire 25 factoriel ( pour placer le premier composant j'ai 25 possibilités, 24 pour le deuxième, 23 pour le troisième... donc finalement total_des_configurations: 25*24*23*22*21*...*2*1 = 25!)

Si j'ai bien compris la méthode du recuit simulé ne sera appliqué que sur la solution finale optimisée afin d'approuver la configuration?

Non, pas exactement. Le recuit simulé est la méthode d'optimisation! Je vais tenter de détailler plus le pseudo code :

1: On donne une configuration initiale quelconque ( on place les composants de manière aléatoire. C'est la première configuration. )

2: On donne une température initiale T ( disons 1000 degrés par exemple )

3: while Le système n’est pas figé do
4: On fait une modification élémentaire du système qui nous donne une variation
d’énergie deltaE ( la modification élémentaire est la permutation de deux éléments ) ( la variation d'énergie deltaE est la différence entre le cout avant et après la permutation )
5: if deltaE <= 0 then
6: Modification acceptée ( parce que la configuration après la permutation est meilleure que celle avant la permutation )
7: else
8: Modification acceptée avec la probabilité exp −deltaE/T ( même si la configuration après la permutation est moins bonne que celle avant la permutation, elle a une chance d'être acceptée. Cela permet d'éviter de figer le système sans avoir trouvé la solution optimale )
9: end if
10: if Equilibre thermodynamique ( après un certain nombre d'itération, plus aucune configuration n'est acceptée à cette température ) then
11: Diminution lente de T ( par exemple T:= 0.99T )
12: end if
13: end while

Voila, ça c'est pour la partie recuit.

1) Comme nous ne voulons pas additionner 2 fois la longueur d'un lien, il faut premièrement déterminer l'ensemble des liens à évaluer. Cet ensemble pourrait être le suivant:

{{01,02},{01,06},{02,03},{02,0 7},{03,04},{03,08},{04,05},{04 ,09},{05,10},
{06,07},{06,11},{07,08},{07,12 },{08,09},{08,13},{09,10},{09, 14},{10,15},
{11,12},{11,16},{12,13},{12,17 },{13,14},{13,18},{14,15},{14, 19},{15,20},
{16,17},{16,21},{17,18},{17,22 },{18,19},{18,23},{19,20},{19, 24},{20,25},
{21,22},{22,23},{23,24},{24,25 }}

Donc il va falloir écrire tous les couples
Ben si je dois m'y résoudre, je le ferai! Pour 25 pièces ça va encore! Par contre, je ne pourrais pas augmenter le nombre de composants facilement!

- L'ensemble des coordonnées que j'ai donné plus haut pourrait sûrement être construit par un algorithme, mais considérant un tableu de 5X5 le fait de définir l'ensemble en extension simplifie la chose.

Ah alors finalement je ne vais peut-être pas devoir écrire tous les couples...

- Ici nous n'utilisons aucun des principes de la POO.

Ce n'est pas un problème, une fois que j'ai compris comment faire je pourrai le traduire en groupant routines et attributs, de facon à ce que le langage de programmation le comprenne

Merci pour vos aides!

[invite4cfbfb28]

Oui on devait lire 25! et moi je me suis trompé et j'ai calculé 25+24+23... au lieu de 25*24*23 Donc mon nombre de possibilités étaient très en dessous.

J'imagine que dans les systèmes que vous voulez optimiser, la solution optimale n'est "évidemment pas" la solution où la distance minimale est de 400cm (pour 10cm par lien). Si c'est le cas, je ne vois pas le but de rechercher la solution vu que nous l'avons a priori. Prenant pour acquis ce fait, évidemment la recherche de la solution la moins énergivore pour le système est tout un casse-tête.

On peut voir une analogie entre cette recherche de shéma minimum et la configuration des atomes entre eux pour obtenir un arrangement moins énergétique. Peut-être que les genres de chimie ou de physique conaissent un algorithme ou une façon efficace d'explorer rapidement les différentes configurations?

Il y a aussi une autre avenue qui est d'utiliser un langage de programmation fonctionnelle comme Haskell. Je ne suis vraiment pas expert dans ce genre de programmation mais de ce que j'en ai appris c'est qu'il sagit de définir un ensemble de "faits" (comme les liens entre les villes ou les composantes) et d'interroger le système avec des fonctions algébriques. Ce genre de language permet de résoudre très facilement ce genre de problème d'optimisation (ex: vol le plus cours en avion ). Évidemment ce genre de language à ses limites car ils fonctionnent par arbre de résolution et il est fréquent que le système partent en boucle... Cependant il y a des façons de détecter ces anomalies pour arriver à nos fins.

Problème intéressant en tous les cas !

Bonne chance!

[invitecef73ce6]

Si, la solution optimale est bien 400cm ( avec 10 cm entre chaque composant ). Le but du programme n'est pas de trouver la meilleure solution ( vu qu'on l'a ! ) mais de démontrer l'efficacité du recuit simulé, qui est apparement un algorithme bien adapté pour ce genre de problème!

Je vais essayer de voir ce que je trouve sur les arbres en programmation!

Je vais aussi m'interesser à Haskell. En revenche, je ne l'utiliserai pas pour ce problème comme le recuit simulé est ma méthode de résolution!

En tout cas, merci beaucoup!