Get best of the week

Génération de nombres pseudo-aléatoires à l'aide d'un automate cellulaire: règle 30

Les générateurs de nombres pseudo-aléatoires donnent des nombres de façon déterministe, mais généralement ces nombres semblent non périodiques (aléatoires). Au moins dans la plupart des cas, l'utilisation de ces numéros se produit généralement. Le générateur prend une valeur initiale (idéalement un vrai nombre aléatoire) et génère une séquence de nombres, fonctionnant en fonction de la valeur initiale et / ou du nombre précédent de la séquence. De tels nombres sont pseudo-aléatoires (et non pas de vrais nombres aléatoires) du fait que si la valeur initiale transmise au générateur est connue, ces nombres peuvent être générés à nouveau de manière algorithmique. De vrais nombres aléatoires sont générés à l'aide de matériel spécial ou de certains phénomènes physiques - fluctuations du pouls dans le volume sanguin, pression atmosphérique, bruit thermique, processus quantiques, etc.



Il existe de nombreuses façons de générer des nombres pseudo-aléatoires. Par exemple, l' algorithme Blum - Blum - Shub , la méthode du carré moyen , la méthode de Fibonacci avec retards . Aujourd'hui, nous parlerons de la génération de nombres aléatoires à l'aide de la règle 30 , qui utilise une approche ambiguë impliquant l'utilisation d'un modèle d' automate cellulaire . Cette méthode a réussi de nombreux tests de nombres aléatoires standard et a été utilisée dans Mathematica pour générer des nombres entiers aléatoires.

Automate cellulaire


Avant d'aborder le sujet de la règle 30, prenons un peu de temps dans les automates cellulaires. Un automate cellulaire est un modèle discret constitué d'une grille régulière de cellules de toute dimension. Chacune des cellules du réseau peut être dans un ensemble fini d'états. De plus, pour chaque cellule, un concept de «quartier» est défini. Au voisinage d'une certaine cellule, par exemple, toutes les cellules situées à une distance ne dépassant pas 2 de celle-ci peuvent entrer. Il existe des règles qui déterminent la façon dont les cellules interagissent entre elles et passent à la génération (état) suivante. Ces règles sont principalement représentées par des fonctions mathématiques (programmables), qui dépendent de l'état actuel des cellules et de l'état de leurs voisins.


Description de l'automate cellulaire La

description de l'automate cellulaire de la figure précédente vous permet de découvrir que chaque cellule peut être dans l'un des deux états finaux -0(montré en rouge) et1(montré en noir). Chaque cellule passe à la génération suivante, prenant un nouvel état résultant de l'application de l'opérationXORà ses 8 voisins. La première génération (état initial) du réseau est définie de manière aléatoire. Le fonctionnement de cet automate cellulaire est illustré ci-dessous.




Automate cellulaire basé sur XOR en action L'idée d'un automate cellulaire est née dans les années 40 grâce à Stanislav Ulam et John von Neumann . Les automates cellulaires ont trouvé des applications en informatique, mathématiques, physique, dans la théorie des systèmes complexes, en biologie théorique et dans les problèmes de modélisation de la microstructure des milieux et des matériaux. Dans les années 1980, Stephen Wolfram a mené une étude systématique d'un automate cellulaire unidimensionnel (il est aussi appelé automate cellulaire élémentaire), sur lequel se base la règle 30.

Règle 30


La règle 30 est un automate cellulaire élémentaire (unidimensionnel) dans lequel chaque cellule peut résider dans l'un des deux états finaux: 0(cellules rouges dans la figure ci-dessous) et 1(cellules noires). Le voisinage de la cellule est représenté par ses deux voisins les plus proches situés à gauche et à droite de celle-ci. L'état suivant (génération) d'une cellule dépend de son état actuel et de l'état de ses voisins. Les règles de transition des cellules vers l'état suivant sont illustrées dans la figure suivante.


Règle 30

Ces règles de transition vers un nouvel état de cellules peuvent être simplifiées sous la formeleft XOR (central OR right).

Nous sortons les cellules de l'automate sous la forme d'un réseau bidimensionnel, dont chaque ligne représente une génération (état). Lorsque la prochaine génération (état) de cellules est calculée, elle s'affiche sous le dernier état connu. Chaque ligne contient un nombre fini de cellules qui, en fin de compte, «bouclent».


Règle 30 en action

Le schéma ci-dessus découle de l'état initial (ligne 0) lorsqu'une cellule a un état1(noir) et que toutes les cellules qui l'entourent ont un état0(rouge). L'état des cellules de la génération suivante (ligne 1) est calculé selon la règle ci-dessus. La grille verticale représente le temps, et les intersections de lignes et de colonnes représentent l'état d'une cellule particulière à un stade particulier du développement du système.


Génération t et génération t + 1

Au fur et à mesure que le motif se développe, des triangles rouges de différentes tailles y apparaissent souvent, mais, en général, un motif distinct ne peut pas être reconnu dans la structure résultante. Le fragment ci-dessus du réseau est fait à un moment choisi arbitrairement dans le temps. Ici, vous pouvez voir le chaos et l'apériodicité. Cette propriété est la règle 30 et est utilisée pour générer des nombres pseudo-aléatoires.

Génération de nombres pseudo-aléatoires


Comme déjà mentionné, la règle 30 montre un comportement apériodique et chaotique. En conséquence, son application conduit à la création de motifs complexes et, semble-t-il, aléatoires selon des règles simples et bien définies. Pour générer des nombres aléatoires en utilisant la règle 30, la colonne de réseau centrale est utilisée, à partir de laquelle une séquence de nbits aléatoires est sélectionnée , à partir de laquelle le nnombre aléatoire souhaité est généré . Le nombre aléatoire suivant est généré à l'aide des nbits suivants de la colonne.


Génération de nombres aléatoires à l'aide de la règle 30

Si vous commencez toujours à sélectionner des cellules à partir de la première ligne, la séquence de nombres générée sera toujours prévisible. Et ce n'est pas ce dont nous avons besoin. Afin de créer des nombres pseudo-aléatoires, nous allons utiliser une valeur initiale aléatoire (par exemple, l'heure actuelle), ignorer le nombre de lignes correspondant, puis sélectionner des séquences à partir desnlignes et créer des nombres aléatoires en fonction d'eux.

Les nombres pseudo-aléatoires générés à l'aide de la règle 30 ne sont pas cryptographiquement sécurisés, mais ils conviennent aux simulations - jusqu'à ce que nous utilisions des valeurs initiales inappropriées comme0.

L'un des principaux avantages de l'application de la règle 30 pour générer des nombres pseudo-aléatoires est que vous pouvez créer de nombreux nombres aléatoires en mode parallèle en sélectionnant de manière aléatoire plusieurs colonnes de longueur n bits. Voici un exemple d'une séquence pseudo-aléatoire de nombres de 8 bits générés par ce procédé en utilisant la valeur initiale 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

De plus, la valeur initiale peut être utilisée pour définir l'état initial du modèle (ligne n ° 0). En conséquence, les nombres pseudo-aléatoires peuvent être obtenus simplement en choisissantnbit de la colonne centrale, en commençant à la ligne zéro. Cette approche est plus efficace, mais elle dépend fortement de la qualité de la valeur initiale. Une valeur initiale mal sélectionnée peut entraîner l'apparition de nombres bien prédits. Une démonstration de cette approche peut être trouvée ici .

La règle 30 dans le monde réel


La règle 30 peut être vue dans la nature, sous la forme d'un motif sur la coquille du textile Conus de l' espèce gastéropode . La gare de Cambridge North est encadrée par des panneaux représentant les résultats évolutifs d'un modèle construit à l'aide de la règle 30.

Sommaire


Si vous trouvez la règle 30 intéressante, je vous recommande d'écrire votre propre simulation à l'aide de la bibliothèque p5 . Cet algorithme peut être implémenté sous une forme assez générale, ce qui permettra au même programme de générer des modèles pour différentes règles - 90, 110, 117, etc. Les modèles générés à l'aide de diverses règles sont très intéressants. Si vous le souhaitez, vous pouvez passer au niveau suivant. Vous pouvez étendre le modèle à trois dimensions et explorer l'évolution des motifs. Je pense que la programmation peut apporter beaucoup de plaisir si elle a une composante visuelle.

C'est incroyable lorsque deux domaines scientifiques apparemment sans rapport, les automates cellulaires et la cryptographie, se combinent pour créer quelque chose de surprenant. Bien que l'algorithme décrit ici ne soit plus largement utilisé en raison de l'émergence d'algorithmes plus efficaces, il nous encourage à utiliser de manière créative les automates cellulaires.

Chers lecteurs! Quels générateurs de nombres pseudo aléatoires utilisez-vous?

More articles:


All Articles