miq75

C'est bien à LISP ou SCHEME que je pensais. />/>/>
J'ai un peu répondu sur un souvenir de cours, mais je viens de relire l'OP, je vais donc essayer de re-contextualiser ma réponse. En fait, ce type de langage (fonctionnelle) est intéressant pour faire évoluer les programmes : la régularité dans la syntaxe permet d'échanger deux bouts de code sans générer des syntax error. Je m'explique :
...

Attention, les deux exemples que tu donne dans les 2 langages n'ont pas du tout la même portée.
Pour ce code en lisp:

gen_1 : (x (+ 3 5) capteur_mesure)
gen_2 : (ET obstacle_dist avancer_dist)

Ce code implique que x soit un fonction dont une des arité est 2 et que ET soit une fonction d'arité variable (en lisp c'est le cas, toute la parenthèse est sommée) et permuter le premier composant plantera si l'arité de la fonction x n'est pas bonne.

on a ce code en c, en utilisant tout le sucre syntaxique que permet c:

gen 1 : x(3 + 5, capteur_mesure)
gen 2 : obstacle_dist & avancer_dist

ou, ce qui est strictement équivalent et tout aussi correct syntaxiquement en c

gen 1 : x(add(3, 5), capteur_mesure)
gen 2 : et(obstacle_dist, avancer_dist)

Ce code implique les mêmes contraintes syntaxiques que le code précédent en lisp, mis à part la position des parenthèses et l'ordre des mots du langage. Et oui, ça le rends plus compliqué à manipuler que celui en Lisp (du moins dans celui de la première versrion), mais en même temps de forcer à permuter dans des morceaux de syntaxe équivalents (par exemple les paramètres de 2 fonctions) peut donner un meilleur contrôle sur ce que tu fait, ça dépends de comment tu gère tes permutations, et même en lisp tu n'a pas intérêt à le faire de manière totalement aléatoire, mais à les diriger pour maintenir la consistance du programme. Donc c'est discutable, ce qui est mieux. Je pense que c'est un choix personnel après.

Ensuite, l'exemple que tu donne de code en C est instranscriptible directement en lisp (la seconde ligne n'existe pas comme brique élémentaire, affecter, puis muter une var est impossible en lisp). Attention, on peut faire en lisp un programme équivalent à celui en C qui utilisera ton extrait en C, mais on passe alors à un paradigme de liste splitée et de la réccurence, comme pour tout ce qui n'est pas trivial comme opération dans ces langages. La puissance syntaxique n'étant pas la même, c'est difficile de comparer la pertinence du sous ensemble du programme traité. En fait, on ne joue pas avec les mêmes briques élémentaires. Après, c'est peut être intéressant aussi de ne pas avoir de variables a manipuler... Là encore, c'est à voir.

Enfin, le problème de c, c'est surtout que ce code ne fonctionnera pas sans avoir construit la déclaration des variables idoine avant, mais c'est un problème que tu n'aurais pas par exemple, en python, tout en gardant tout le reste (plus le garbage collecting, etc...).

L'ordre de la notation – préfixe (opérateur var var - par ex LISP ou SCHEME), postfixe (var var opérateur - comme FORTH ou RPL) ou infixe (var opérateur var - comme les maths) – ne change pas la complexité structurelle en fait, ton arbre aura toujours le même nombre de nœuds, c'est l'ordre des branches au sein de l'arbre et leur sens de lecture qui change.

Sortir la parenthèse – (func, arg1, arg2) au lieu de func(arg,arg2) – en revanche, ça peut peut-être faciliter la génération plus automatique du code parce que tu généralise ta notation. Du coup un nœud commencera par "(".

Enfin, utiliser un langage fonctionnel, c'est à dire remplacer des variables par des données fixes, ça implique parfois d'avoir au lieu d'une variable plusieurs données, ou une syntaxe accumulant la même donnée (la liste manipulée). Ce qui est intéressant c'est que tu sors effectivement de la linéarité artificielle de l'exécution du code, ta structure est donc un peu plus libre, mais tu risque de devoir plus charger ton arbre de compilation pour un résultat équivalent.
en scheme :

(define (map f lst)
    (cond ((null? lst) lst)
          (else (cons (f (car lst))
                      (map f (cdr lst))))))

en python :

def map(func, liste):
    res = []
    for elt in liste:
        res.append(func(elt))
    return res

ou (plus pythonique mais strictement équivalent)

def map(func, liste):
    return [func(elt) for elt in liste]

en c++ :

template < class InputIterator, class OutputIterator, class UnaryOperator >
  OutputIterator transform ( InputIterator first1, InputIterator last1,
                             OutputIterator result, UnaryOperator op )
{
  while (first1 != last1)
    *result++ = op(*first1++);  // or: *result++=binary_op(*first1++,*first2++);
  return result;
}

En python ou on C, tu passes par une boucle et tu remplace chaque élément par le résultat de la fonction.
En scheme (le fonctionnel), tu doit faire un appel récursif sur chaque elt de la liste séparé de la liste, donc tu : sépare un élément de la liste, calcule le reste de la liste séparée récursivement, et recolle la liste. Ça me parait un tantinet plus complexe comme arbre de compilation, même si ça supprime effectivement le besoin des nœuds de type 'for' ou 'while' en les remplaçant par des récurrences.


Je ne suis pas certain que tu y gagnes au final.

En revanche, ça peut être intéressant de regarder les langages fortement mais non déclarativement typés, comme le Caml. Imagine la surcharge de devoir gérer la cohérence entre le type d'une var lors de sa déclaration et lors de son usage, alors que tu peut utiliser des typages dynamiquement calculés. Bref, c'est à voir et à soigneusement étudier avant de commencer à te plonger dans du code.

Après, je ne connait que le principe des algo gens et n'en ait jamais programmé moi-même, alors je me trompe peut-être du tout au tout, hein, je ne fais que donner mon humble avis sur comment je commencerais. />

Alors je vais te parler un peu de compilation (programmation de compilateurs):
Un programme vu par un compilateur, c'est un arbre d'instructions dont chaque bloc de code (typiquement les fonctions, ce qui est dans les clauses if, then et else, et ce qui est dans les boucles) est un nœud et dont les branches d'un même nœud sont ordonnées. Toi, ça te paraît linéaire, parce que tu le lit dans un fichier texte qui est linéaire, mais pas pour le compilateur ou l'interpréteur. Et je ne parle pas non plus de la complexité de l'exécution d'un programme, qui est encore un problème différent.

Bref, un simple

if A or B then {
   foo
   bar
}

c'est déjà un arbre avec 4 feuilles (A, B, foo, bar) et 3 nœuds (if-then, or, {}). La complexité de cet arbre augmente assez vite (et encore je n'ai pas défini foo et bar, qui sont probablement eux-même des arbres). C'est ce genre de choses que tu devra manipuler si tu veut faire un "programme" génétique. Pas question par exemple de dire "tiens, choisi 20 instructions parmi celles-là". Le 20 est lui même une chose qui devra être testée mais surtout rendue cohérente avec la recherche.

Si je prends un langage au hasard, par exemple python qui possède une notation relativement allégée par rapport à d'autres et que je compte le nombre de "statement", c'est à dire de mots du langage, j'en ai facilement 20. Les opérateurs y'en a facilement 30, et encore je ne parle pas de l'analyse syntaxique des noms de variable et de fonctions. Bref, un pool de 50 composants qui articulent le programme, plus les variables. Soit 50 type de possibilité pour chaque nœud (un 'or', qui possède une arité de 2 peut contenir 2 feuilles aussi bien que 2 nœuds qui peuvent être n'importe quelle expression bien construite du langage, un '.' bien que son arité soit 1 peut faire appel à n'importe quel attribut ou propriété d'un objet...).

Donc pour un nœud, 50 possibilité de valeur du nœud à multiplier par l'arité du type de nœud et encore à multiplier par la complexité des possibles expressions bien construites qui en découlent...

Je ne cherche pas à te décourager, mais à te faire réaliser la complexité de ce à quoi tu t'attelles. Faire une recherche aléatoire mais dirigée dedans est possible, mais c'est très complexe. Tu devra probablement le faire sur un langage que tu aura construit toi-même, ce qui veut dire un langage qui n'est pas forcément complet...

Après, y'a des astuces pour gérer moins d'instructions, comme par exemple de ne placer les opérateurs logiques que dans les clauses if. Mais ne perds pas de vue que tu auras 2 complexités à gérer, celle de l'univers dans lequel tes créatures évoluerons, et celle du langage qui supportera ton programme génétique.

À mon avis, commence par très petit pour le simulateur et pour le langage, puis quand tu auras un truc qui complet qui tournera (un programmateur génétique ET le simulateur qu'il utilise) alors tu pourra chercher à augmenter les capacités du langage, avant d'augmenter celles de l'espace de simulation. Courage !

Alors tu es bien dans le paradigme de l'intelligence dans le comportement collectif mais pas de l'évolution d'individus intelligents (ce qui n'étais pas clair vu que tu partait de l'intelligence humaine, qui est individuelle).

Le système que tu décrit me fait plus penser à un système de tableau noir qu'à de la programmation génétique. Une liste de règles (ce que tu appelles méthodes élémentaires) posées et appliquées selon un ordre et un poids. L'ordre et le poids pouvant évoluer avec l'apprentissage. Si ton algo n'est qu'une liste de commandes, sans structures de boucles et de tests, ce n'est plus a proprement parler un programme (bien que le système qui gère cela soit lui un algo gen).

Il existe déjà des systèmes qui permettent de fournir (entre autres) tous les composants de la simulation d'agents basée sur de telles règles (par exemple DIMA, du lip6 (en java), j'y ai intégré un système pour gérer les règles durant mon DEA), mais a ma connaissance ils n'intègrent pas encore les algos gen comme sélecteurs de priorités/poids. Cela dit ils te faciliteraient grandement le travail pour tes simulations, tu devrais y jeter un coup d'œil !

Et sinon, et ça n'a rien à voir :
J'ai entendu hier une émission sur la façon dont les abeilles communiquaient entre elles dans la ruche sur leurs zones de butinage. C'était comme un apprentissage, avec un individu faisant une danse codée traduisant pour les autres la position du cite intéressant, sa richesse, son danger, etc... Bref, un beau système multi-agents. Et comme dans tout système d'apprentissage, y'a une part d'exploration (certaines abeilles) et une part d'exploitation (certaines abeilles collectent). C'est souvent un point problématique dans un système d'apprentissage, comment déterminer la part d'exploration par rapport à celle d'exploitation. Et j'ai trouvé la solution des abeilles très élégante, parce qu'adaptable. Ce sont les butineuese les plus vieilles de la ruche, qui, passées un certain âge, deviennent exploratrices (et donc celles qui ont le mieux survécues aux péripéties de la collecte toute une vie d'abeille durant.

Bref, à noter : dans un système d'apprentissage ou les individus peuvent mourir à des ages différents, pour résoudre le problème de la part d'exploration par rapport à la part d'exploitation, faire exploiter tous les individus dans leur jeunesse, puis faire explorer les individus à partir d'un peu avant qu'ils n'atteignent l'espérance de vie moyenne de la population.

Vu ton projet, il est possible que ça te serve.