Layout par ressort / Spéciation génétique

Version imprimable

07/04/2006, 23h53
bigquick

Layout par ressort / Spéciation génétique

Salut !

J'arrive avec une question un peu vague... je voudrais connaitre le type d'algorithme qui se cache derrière une page comme celle-ci : musicmap.

L'idée est simple, différents noeuds sont connectés par des poids. L'algorithme (qui s'effectue visiblement par étapes) permet de les disposer dans l'espace afin d'obtenir une repartition correcte. J'imagine qu'une des implémentations possible s'effectue à base de ressorts, mais encore c'est juste une supposition ;)

Est-ce que quelqu'un a quelques connaissances à ce sujet ? Et niveau complexité, qu'est-ce que ça vaut réellement ? Je pensais me servir d'un algorithme de ce type dans le cadre d'algorithmes génétiques, afin de répartir la population et d'effectuer la spéciation (*). Qu'en pensez-vous :?:

Merci !

* : bien sûr je n'établirait pas les poids de toutes les connexion possibles. Je pensais plutôt déterminer le taux de différence entre X individus pris 2 par 2, en faisant attention à ce que chaque individu ait été au moins choisi une fois.
08/04/2006, 01h04
bigquick

Ah, après quelques recherches supplémentaires, j'ai trouvé les liens suivants:

Force directed algorithm
Boost : kamada kawai spring layout (je développe en C++)

Je continue donc à chercher dans cette direction... j'espère qu'il existe des algorithmes relativement efficaces (je ne suis pas trop exigeant) qui ont une complexité raisonnable !
08/04/2006, 01h32
outs

J'ai déjà programmé un algo de ce genre. C'est amusant mais c'est juste une approximation grossière En effet la répartition ne sera bonne que dans des cas simple.

Par contre je en vois pas le rapport avec les agol génétiques. Ce genre d'algo optimise des paramètre par essai/évolution quelles paramètre compte tu otpimiser ?

Il faut déjà que tu comprenne comment les systeme poid/ressort fonctionnent.
08/04/2006, 02h01
bigquick

Le fait que ça soit grossier n'est peut-être pas très grave pour mon cas. Il faudra que j'essaye pour voir si ça convient ;)

Le lien avec les algorithmes génétique, c'est que dans ceux-ci ont fait évoluer une population d'individus, dont les gènes définissent le comportement. A chaque génération, ces individus peuvent se croiser pour créer un "enfant" qui possède un peu des caracteristiques de ses 2 parents. Ce croisement est possible dans tous les cas si le génome reste constant. Dans le cas de l'ajout de nouveaux gènes, on peut définir un taux de compatibilité entre les individus. Des individus trop éloignés finissent par appartenir à 2 espèces différentes, et ne peuvent bien-sûr pas se reproduire entre eux. (*)

Comme il est très délicat de définir où commencent et s'arrêtent les espèces, je pensais opter pour un nuage de points (les individus) représentant l'espace de recherche. Les individus seraient regroupés par compatiblité, de la même manière que le site musicmap regrouppe les artistes similaires.

Qu'en penses-tu ?
Par contre, j'ai seulement quelques notions de physique ... du lycée :) Est-ce vraiment indispensable de tout maitriser des poids / ressorts pour créer un algorithme basique ?

* : Tout ça favorise l'évolution, puisque la sélection naturelle à lieu à l'échelle globale, mais surtout au sein des espèces
08/04/2006, 02h10
outs

(arreter de citer ton cours c'est pénible)

Non pas du tout il n'y a aucune population ni selection d'aucune sorte dans la méthode des poid/ressort. C'est juste une simulation de la tension des ressort et de la position des noeud.

Je te rassure le niveau lycée est largement suffisant pour s'en sortir (si tu cherche sur le net il y a des description necessitant plus de math mais pas besoin d'aller jusque la pour faire un petit algo qui marche)

Je pense qu'il y a effectivement moyen d'utiliser les algo génétiques en plus mais il faut d'abord comprendre l'algo de base. Si tu cherche un peu y'a plein d'exemple en java qui trainent sur le net (cherche Graph layout)

Citation:

... musicmap regrouppe les artistes similaires.

Heu la méthode qu'utilise musicmal pour regroupper les artistes n'a a priori rien a voir avec poid/ressort qui sert juste a faire l'affichage
08/04/2006, 02h16
bigquick

Ah, je crois qu'on s'est mal compris....
Je ne souhaite pas utiliser des algorithmes génétiques pour "aider" la méthodes des ressorts à faire du layout de graphe. Je cherche à appliquer la méthode des ressorts afin de définir les espèces au sein de mon algo génétique.

Et petite précision au passage... je ne cite pas mon cours, je ne suis plus étudiant (c'est juste des recherches personnelles). Mais vu que tu demandais

Citation:

Envoyé par outs

Par contre je en vois pas le rapport avec les agol génétiques. Ce genre d'algo optimise des paramètre par essai/évolution quelles paramètre compte tu otpimiser ?

J'ai essayé d'expliquer mon problème le plus clairement possible... Autant partir sur de bonnes bases non ? ;)

Citation:

Citation:
... musicmap regrouppe les artistes similaires.

Heu la méthode qu'utilise musicmal pour regroupper les artistes n'a a priori rien a voir avec poid/ressort qui sert juste a faire l'affichage

C'est bien de cela que je parle. Quand on choisis un artiste, on voit les artistes similaires s'organiser afin de respecter la règle "proximité = similitude". Non ?

Citation:

Si tu cherche un peu y'a plein d'exemple en java qui trainent sur le net (cherche Graph layout)

OK, j'y vais de ce pas ! Mes premiers recherches m'avaient orienté vers des algos qui ne prennent pas en compte un quelconque poids des arêtes du graphe (notion de proximité). J'espère avoir plus de chances cette fois-ci !
08/04/2006, 02h42
Jedai

Si tu veux une vague piste pour ton algorithme de classification, j'avais trouvé ce sujet très intéressant (surtout les liens auxquel il menait) :)

--
Jedaï
08/04/2006, 09h37
outs

Citation:

C'est bien de cela que je parle. Quand on choisis un artiste, on voit les artistes similaires s'organiser afin de respecter la règle "proximité = similitude". Non ?

Non

Les similarité entre les artites sont précalculé et ne varient pas pendant l'affichage. Poid/ressort n'a rien a voir avec la classification. Ca sert juste a dessiner "joli" le graphe des artistes, toi il te faut un moyen de créer le graphe.
08/04/2006, 12h50
bigquick

Citation:

Envoyé par Jedai

Si tu veux une vague piste pour ton algorithme de classification, j'avais trouvé ce sujet très intéressant (surtout les liens auxquel il menait) :)

--
Jedaï

Merci beaucoup! En effet le sujet à l'air bien complet ! Ca me fait de la lecture pour aujourd'hui ;)

Citation:

Envoyé par outs

Citation:

Envoyé par bigquick

C'est bien de cela que je parle. Quand on choisis un artiste, on voit les artistes similaires s'organiser afin de respecter la règle "proximité = similitude". Non ?

Non

Les similarité entre les artites sont précalculé et ne varient pas pendant l'affichage. Poid/ressort n'a rien a voir avec la classification. Ca sert juste a dessiner "joli" le graphe des artistes, toi il te faut un moyen de créer le graphe.

Décidement, on ne se comprend vraiment pas ! Je n'ai jamais dit que les similarités évoluaient, mais que l'affichage évoluait afin de disposer le graphe de manière "jolie". D'après les explications du site, il y a deux parties:

1. A travers un fomulaire, tout le monde peut ajouter un groupe, ou dire qu'il trouve 2 groupes similaires. Ca doit être la phase de modification du graphe et poids de ses arêtes.
2. Sur la page principale, l'algorithme de layout dispose les artistes afin de refleter ces similitudes (c'est la partie qui m'intéresse).

Par rapport à mon problème, j'ai déjà le moyen de créér le graphe (le taux de compatibilité entre les individus)... je cherche juste comment implémenter la seconde partie.

edit: voilà au passage 2 vidéos que j'ai trouvées et qui illustre parfaitement ce que je cherche :)
Exemple 1 (8mo)
Exemple 2 (17mo)
08/04/2006, 19h36
outs

Citation:

Envoyé par bigquick

Décidement, on ne se comprend vraiment pas !

Oui mais c'est plus clair maintenant...

Au niveau de l'algo en gros:
Comme donnée il te faut
* le graphe
* le poid de chaque arete
* la position des noeud dans le plan
* le vecteur déplacement des noeuds (tjs dans le plan)

L'algo est itératif, a chaque boucle :
* calculer le deplacement des noeud a fonction des autres noeud (les noeud reliés s'attirent les noeud proches non reliée se repoussent)
* mettre a jour la position en fonction du déplacement calculé précédement.

A toi de combler les trous
09/04/2006, 01h41
bigquick

OK, merci pour ces précisions !

Je vais essayer cette approche dans les jours qui viennent. Comme c'est une méthode iterative, j'espère que les résultats seront probants sans trop faire d'iterations... Mais si tout se passe comme dans les vidéos, on dirait que le plus gros du travail est vite fait, les 2/3 restant ne servent qu'à paufiner ;) J'imagine d'ailleurs que l'ago s'arrête lorsque tous les vecteurs déplacement sont inferieurs à un epsilon donné... je vais jouer avec cette valeur pour voir ce que ca donne...

Je vais aussi continuer à me documenter sur les SVM / SOM (présentés dans l'autre thread). J'espère que je trouverai ce qui me convient le mieux !

Merci pour toutes vos réponses :)

edit:
en faisant d'autres recherches, je suis tombé sur ce PDF qui pourra peut-être intéresser d'autres personnes: http://www.csse.monash.edu.au/~bernd...s/cse460-7.pdf

Il présente très rapidement le "spring layout" en pages 14 et 15, et explique la méthode utilisée pour gérer les déplacements (en fonction des forces appliquées), et la condition d'arrêt (energie minimale). Je pensais à quelquechose de plus simple, avec de simples calculs de distance, mais je verrai ce que ça donne...
19/04/2011, 22h42
darkwall_37

Bonjour,

Désolé je déterre un vieux topic.

Je cherche à afficher un graphe sur une sphère, le tout en utilisant un algorithme à base de force.

Le but étant de placer les nœuds du graphe aléatoirement sur la sphère puis de laisser les nœuds se déplacer en fonction des forces qu'ils subissent des autres nœuds, jusqu'à arriver à un état d'équilibre.

Si quelqu'un à des informations ou des tutoriels à présenter je suis preneur.

Je suis un perdu quant au déroulement de tout cela.

Merci d'avance.
21/04/2011, 20h22
pseudocode

Citation:

Envoyé par darkwall_37

Bonjour,

Désolé je déterre un vieux topic.

Je cherche à afficher un graphe sur une sphère, le tout en utilisant un algorithme à base de force.

Le but étant de placer les nœuds du graphe aléatoirement sur la sphère puis de laisser les nœuds se déplacer en fonction des forces qu'ils subissent des autres nœuds, jusqu'à arriver à un état d'équilibre.

Si quelqu'un à des informations ou des tutoriels à présenter je suis preneur.

Je suis un perdu quant au déroulement de tout cela.

Merci d'avance.

En première approximation, tu peux faire les calculs de micro-déplacement des noeuds sans la contrainte de la sphere (donc dans un espace 3D), puis au final repositionner les nœuds sur la sphère par projection.