Problème inverse de l'automate fini et algorithmes génétiques

Algorithmes génétiques appliqués à la factorisation de mots.

Morphismes et factorisations de mots

Le monoïde libre et les morphismes sont décrits à la page : Monoïde libre. Une application écrite en javascript permet de jouer avec les morphismes de construire des mots, en particulier les suites ou mots de Prouhet-Thue-Morse, de Fibonacci, ou encore la 'Look and Say sequence'.
Inversement, on peut se demander comment trouver un morphisme, le plus simple possible, qui permettrait de construire un mot donné, à partir de sa première lettre, en appliquant un même morphisme plusieurs fois.
Si le mot est fini, il existe évidemment au moins les morphisme triviaux : 1ère lettre -> le mot, mais il y en a peut-être d'autres.

L'idée d'écrire cette page vient de la lecture de l'article 'Inverse problems for finite automata: a solution based on genetic algorithms' de B. Leblanc, E. Lutton, and J.-P. Allouche.
(Le programme ci-dessous s'inspire de la première partie de l'article, de la page 1 à la page 5).

Le programme

On propose un mot à l'application, seuls les 80 premiers caractères seront utilisés (pour éviter un trop long temps d'exécution).
Le programme détermine l'alphabet utilisé et construit aléatoirement une population initiale de 10 morphismes.
Les générations suivantes sélectionneront les morphismes les mieux adaptés.
Les solutions sont les morphismes s qui fixent le mot A donné : s(A) = AB.

[Premier exemple]  Les étapes dans l'utilisation de l'application sont : 1 - choix d'un mot (ici un mot de Fibonacci 1011010110110101101011...), 2 - construction de la population initiale, 3 - évolution de la population pour tenter d'obtenir une factorisation.
Le nombre de générations, le nombre d'individus créés, l'alphabet et le mot à atteindre seront affichés sur les premières lignes. Ensuite, sur deux lignes chaque fois, le morphisme, sa valeur (fitness f) et le mot qu'il permet de construire.
Lorsque f > 80 le morphisme trouvé est une solution, dans l'exemple ci-dessous le 73ième individu parmi les 80 créés est une solution :
	  Générations : 10 calculs f : 80 (73) Alphabet : 1 0
	  10110101101101011010110110101101101011010110110101101...
	  -----------------------------
	  1->10 0->1 80.33333333333333
	  10110101101101011010110110101101101011010110110101101...

L'application


Adaptation comme nombre de caractères exacts :   (1) au début du mot    (2) sur tout le mot

Taille population     Longueur maxi morphismes     Longueur mot    



A - Inscrivez d'abord le mot ici :   

     de n =    génération(s)

Exemples

Créer le mot à factoriser

D'abord choisir un mot ou le créer à l'aide d'un morphisme.
Alphabet    Morphisme      
Dans ce dernier cas, écrire séparément ci-dessous l'alphabet et les images des lettres par le morphisme, le bouton [Mot] permet ensuite d'obtenir un mot de 80 lettres au moins.
- Créer la population : bouton [Initialiser].
- Faire évoluer la population pour tenter de factoriser le mot : bouton [Évoluer].
(On aimerait que le programme détermine un morphisme s aussi simple que possible et non trivial tel que s : A -> AB, le mot A étant un préfixe de son image s(A) = AB).

Quelques mots à essayer de factoriser

(Pour obtenir les générations suivantes, cliquer sur le bouton [Évoluer]).
Mot de Prouhet-Thue-Morse | Initialiser | Évoluer |.
Mot | Initialiser | Évoluer |.
Rudin-Shapiro | Initialiser | Évoluer |.
L'un des mots de la suite 'Look and Say sequence' | Initialiser | Évoluer |.
Mot de Kolakovski | Initialiser | Évoluer |.
Racine carrée de 2 en base 2 (chiffres à droite de la virgule) | Initialiser | Évoluer | Le mot infini ni rationnel, ni transcendant n'est pas factorisable (Loxton et van der Poorten).
La fraction 3/5 mais écrite en base 2 : 11/101 = .100110011001... (chiffres 0 1 seulement) | Initialiser | Évoluer | la fraction est un rationnel, son développement est périodique de période 1001, une factorisation (évidente) est ...
La fraction 9/17 mais écrite en base 3 (chiffres 0 1 2) | Initialiser | Évoluer | Le quotient est un rationnel, son écriture.
Tribonacci : | 1 -> 12, 2 -> 13, 3 -> 1 | Évoluer |.
Morphisme : | 2 -> 231, 1 -> 21, 3 -> 13 | Évoluer |.
(Automaton 1) : | 2 -> 234, 1 -> 61, 3 -> 52, 4 -> 234, 5 -> 6551, 6 -> 433 | Évoluer |.
(Automaton 2) : | 2 -> 24, 1 -> 11116, 3 -> 5, 4 -> 35, 5 -> 2341, 6 -> 666 | Évoluer |.
Morphisme : | 1 -> 1000, 0 -> 11 | Évoluer |.
Morphisme : | 1 -> 123, 2 -> 13, 3 -> 2 | Évoluer |.
Morphisme : | o -> ooI; I -> IoI | Évoluer |.
Morphisme : | 0 -> 012, 1 -> 0, 2 -> 21 | Évoluer |.
Morphisme : | 0 ->01, 1 -> 2, 2 -> 4, 3 -> 34, 4 -> 5, 5 -> 1 | Évoluer |.
Morphisme : | 0 ->01, 1 -> 0 | Évoluer |.
Morphisme : | 0 ->01, 1 -> 100 | Évoluer |.
Morphisme : | 0 ->010, 1 -> 110 | Évoluer |.
Morphisme : | 0 -> 02, 1 -> 12, 2 -> 10 | Évoluer |.
Morphisme : | 0 -> 01, 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 0 | Évoluer |.
Intersections des lignes 1 horizontale et 0 verticale du quadrillage par la droite D: y = ax
de pente irrationnelle a =            


Suite des valeurs de n × t mod. k, avec n entier variable, t réel fixé et k>1 entier fixé
k =    t =           

Liens

19 Inverse problems for finite automata: a solution based on genetic algorithms. B. Leblanc, E. Lutton, and J.-P. Allouche. Lecture Notes in Computer Science (Artificial Evolution, 1997, Eds. J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers) 1363 (1998), pp. 157-166. (Prétirage/Preprint)
3 Finite automata and morphisms in assisted musical composition. J.-P. Allouche and T. Johnson. Journal of New Music Research 24 (1995), 97-108 et le supplément
les automates finis en mathematiques par Jean-Paul Allouche (MATh.en.JEANS en 1995)
Quasicrystals Uwe Grimm
Fibonacci Chain Steffen Weber. Their ratio L/S is tau=(SQRT(5)+1)/2=1.61803..
Une caractérisation simple des nombres de Sturm C. Allauzen. Journal de Théorie des Nombres de Bordeaux Volume 10 fasc. 2 (1998)
Sequences with subword complexity 2n Günter Rote.
Mots infinis, suites doubles et pavages Laurent Vuillon.
QuasiTiler by Eugenio Durand. QuasiTiler draws Penrose tilings and their generalizations. (Geometry of Quasicrystals).
Pages de liens sur : Fibonacci (nombre d'or), Apériodique (quasicristaux), Polytopes, Algorithmes génétiques, Pavages du plan, Automates.
Mots à deux dimensions représentés par des pavages de Truchet.



















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014