Une données structurée peut être décomposée en plusieurs données plus simples, et si nous poussons cette décomposition jusqu'au bout, nous obtenons des données irréductibles qui sont des booléens. C'est pour cela que l'étude principielle des variables aléatoires de type structuré passe nécessairement par l'étude des variables aléatoires booléennes (voir Statistique et variable aléatoire booléenne).
De même un problème transcrit sous forme d'une équation mettant en oeuvre des données et des variables de type structuré, peut être décomposé en une conjonction de problèmes plus simples, mettant en oeuvre des données et des variables de type plus simple, un système d'équations plus simple, et si nous poussons cette décomposition jusqu'au bout, nous obtenons des équations irréductibles qui sont booléennes, et ce système d'équations booléennes peut alors se regrouper en une seul équation booléenne, qui elle-même se regroupe en une seul expression booléenne.
Donc, sans altérer nullement la généralité de la notion de problème, nous pouvons dire que tout problème peut se traduire en une expression booléenne qui est une fonction booléenne d'arité n retournant une valeur booléenne devant être égale à 1, la valeur logique vrai. C'est la définition du problème SAT (problème de SATisfaisabilité booléenne).
On cherche donc les n-uplets de booléens (x0, x1, x2..., xn-1) tel que l'on ait f(x0, x1, x2..., xn-1), c'est à dire l'équation f(x0, x1, x2..., xn-1)=1. La fonction booléenne f définie sur l'ensemble {0,1}^n et ayant comme image l'ensemble {0,1}, constitue l'expression booléenne du problème.
La résolution se fait en explorant les 2^n possibilitées que sont les éléments de {0,1}^n. Mais lorsque n devient grand, et d'autant plus que la complexité de f est grande, l'exploration des 2^n possibilitées devient techniquement impossibles. L'exploration sera donc partielle et devra suivre une heuristique, une stratégie, qui utilisera les connaissances présentes du problème (les résultats obtenus pour ce problème) et les connaissances ancestrales du problème (les résultats antérieurs obtenus pour ce type de problème).
Lorsque f est de complexité non bornée voir non totalement calculable, alors on ne peut pas attendre la fin du calcul de f(x0, x1, x2, x3..., xn-1), et si au bout d'un certain temps, le calcul ne donne toujours pas de résultat, on continura notre analyse sans attendre davantage, en considérant le résultat partiel que constitue la non réponse. Cette non réponse constitura une troisième valeur logique possible, mettant ainsi en oeuvre une logique ternaire.
Mais pour l'instant considérons le cas simple ou f est de complexité bornée.
L'approche est empirique. On teste des n-uplet générés au hasard, puis après, selon un shéma arbitraire et en fonction de probabilités calculées empiriquement.
Tout d'abord nous allons définir la probabilité d'une fonction booléenne f d'arité n. Pour cela, il faut poser un cadre formelle définissant la probabilité, un univers équiprobable de dimension booléenne n appelé Ω = {0,1}n. Cet univers se décompose en un produit de n petits univers Ω = (Ω0, Ω1, Ω2, Ω3..., Ωn-1) où Ωi = {0,1} . Et on associe à chacun de ces petit univers, un nom de variable booléenne x0, x1, x2, x3..., xn-1. Ainsi l'univers Ω possède n variables booléennes libres et structurées en une liste comme suit (x0, x1, x2, x3..., xn-1). De tel sorte que l'on note parfois l'univers comme suit Ω = (x0, x1, x2, x3..., xn-1) en identifiant chaque variable à son univers. En effet qu'est-ce qu'une variable ? si ce n'est un univers, l'univers des différentes valeurs possibles que la variable peut prendre et que nous appellons monde.
L'univers, s'il ne précise pas de poid pour ses différents mondes possibles, est supposé composé de mondes équiprobables. Parceque s'il en était autrement, il faudrait le justifier, et que délors, en l'absence de justification, les mondes sont équiprobables (argument de droit).
Le choix des noms de variables de l'univers n'a pas d'importance, mais on choisie une codification pour pouvoir par la suite coder les expressions. Les variables dans le produit sont numérotées à partir de zéro dans l'ordre du produit. Et on représente le produit de plusieurs univers tels que A, B et C simplement par la liste (A,B,C).
Les mondes de l'univers Ω sont les n-uplet de booléens X = (x0, x1, x2, x3..., xn-1), et sont tous posés équiprobables.
Noter que dans l'expression X = (x0, x1, x2, x3..., xn-1) le symbôle X n'a pas le rôle d'univers mais de variable désignant un monde quelconque de Ω, et que les symbôles x0, x1, x2, x3..., xn-1 n'ont pas le rôle d'univers mais de variables désignant une valeur quelconque parmis les valeurs qui leurs sont possibles, c'est à dire désignant un de leurs mondes possibles qui sont 0 et 1, alors que dans l'expression Ω = (x0, x1, x2, x3..., xn-1), le symbôle Ω joue le rôle d'univers comprenant 2n mondes équiprobables, et les variables x0, x1, x2, x3..., xn-1 jouent le rôle d'univers comprenant chacun deux mondes équiprobables que sont 0 et 1.
A partir de cet univers, on peut calculer la probabilité de tous les évènements. La probabilité de f est par définition la probabilité que f(X)=1. C'est à dire la somme des probabilité des mondes X où f(X)=1.
p(f) = p(f(X)=1)
p(f) = sum( f(X), X∈Ω ) / |Ω|
L'ensemble des booléens {0,1} se plonge implicitement dans l'ensemble des entiers relatifs Z permettant ainsi de les sommer. Puis Z se plonge implicitement dans l'ensemble des nombres rationnels Q, une structure plus riche permettant de définir les probabilités.
L'algorithme cumulatif (dit aussi algorithme Shadok) consiste à chercher au hasard et à accumuler les résultats positifs et négatifs. Et on ne se préoccupe pas d'éviter de faire des essais distincts, car la probabilité de faire deux fois le même essai au hasard est trés faibles.
Les algorithmes évolutifs plus perfectionnés, s'obtiennent par construction en utilisant des probabilitées empiriques, et nous pouvons explorer toutes les constructions possibles. Le principe évolutif consiste à trouver des générateurs qui produisent des solutions, et non à trouver simplement des solutions. Ces générateurs sont choisis au hasard selon un schéma. Et ils sont rangés en fonction des probabilités conditionelles empiriques constatées. C'est une recherche de factorisation programmative probabiliste selon un schéma arbitraire.
Une des plus simples d'entres elles consiste à mimer l'évolution asexué des unicellulaires. On pose de façon arbitraire des petites transformations qui immiteront les mutations du code génétique lors d'une reproduction asexuée. Une petite transformation g appliquée à un n-uplet X va produire un n-uplet g(X) considéré comme une petite mutation de X.
Pour chaque générateur g, on calcule le pronostique de f(g(X)) sachant f(X) et le pronostique de f(g(X)) sachant ¬f(X), qui pour être pertinent doient s'écarter du pronostique de f(X) et de ¬f(X). Puis on analyse d'une manière analogue les générateurs entre eux qui pour être pertinent doivent se différentier les uns des autres afin que la somme de leur contribution soit plus grande que la contribution d'un seul.
On enrichie l'algorithme en introduisant des fonctions discriminantes. Une fonction discriminante d appliquée à X va retourner un booléen et ainsi classifier les valeurs de X en deux classes d-1(0) et d-1(1). On peut alors empiriquement choisir les meilleurs générateurs pour chacune de ces classes.
Ce processus de construction peut se perfectionner et ainsi permettre la factorisation programmative probabiliste en utilisant algorithmes évolutionnaires asexués et schémas dichotomiques.
L'opérateur logique binaire ¬et(.,.) appelé également NAND, qui est commutatif et non associatif, possède la propriété d'engendrer tous les autres opérateurs logiques. Les fonction booléenne d'arité n peuvent donc se programmer avec cette seul opération. Le programme est un terme clos du langage {X0, X1, X2, X3,... Xn-1, ¬et(.,.)}.
Le langage d'opérateurs se transforme en langage de caractères en mettant en oeuvre la logique polonaise. Les parenthèses et les virgules sont enlevées. Par exemple, en utilisant a,b,c au lieu de X1,X2,X3 et le symbole ★ au lieu de ¬et, Le terme clos ¬et(X1,¬et(X2,X3)) se transforme en le terme clos ★(a,★(b,c)) puis se transforme en la chaine de caractères ★a★bc d'alphabet {a, b, c, d..., ★}. Le programme devient ainsi une chaîne de caractères appartenant à {a, b, c, d..., ★}*. Mais toutes les chaines de caractères ne sont pas valides pour définir un programme d'une fonction booléenne.
On définie un moteur qui engendre aléatoirement un tel programme comme suit : On pose la probabilité p de tirer le caractère ★ et la probabilité (1-p)/n de tirer un des n caractères différents de ★. Et on répète le tirage jusqu'à obtenir une chaine de caractère correspondant à un terme clos. Ce moteur possède un seul paramettre qu'est la probabilité p.
---- 22 décembre 2013 ----
L'évaluation se fait simplement avec une pile de même taille ([P0, P1, P2, P3,...], i=0) et en lisant la chaîne de caractère à interpréter de droite à gauche. Par exemple ★a★bc :
On réserve une pile de même taille ([P0, P1, P2, P3, P4], i=0)
On lit "c" et on l'empile : Pi=c, i=i+1
On lit "b" et on l'empile : Pi=b, i=i+1
On lit "★" et on effectue le nand : i=i-1, Pi-1 = ¬et(Pi-1, Pi), cela enlève un élément de la pile.
On lit "a" et on l'empile : Pi=a, i=i+1
On lit "★" et on effectue le nand : i=i-1, Pi-1 = ¬et(Pi-1, Pi), cela enlève un élément de la pile.
On retourne le résultat P0.
Mais le but de l'algorithme change si la proportion de solutions devient importante, les échecs deviennent porteuses d'information, et le but change, il consiste à trouver des générateurs de complexité faible qui produisent des solutions, et non plus simplement des solutions que l'on a déja en abondance. Cela s'apparente à ce que nous pourrions appeler une factorisation programmative probabiliste.La programmation modulaire de cette algorithme se présente ainsi :
Variables |
Type |
Description |
S |
int |
Nombre de tirages |
A |
int |
Nombre de tirages où X est solution |
Fonction |
Entré |
Sortie |
Description |
Rand |
n |
X |
Produit un n-uplet X au hasard selon une graine initialisée préalablement par une fonction système. |
Bool |
X |
f(X) |
Retourne en sortie la valeur booléenne f(X) |
Serveur |
Flux de
sortie n°1 |
Variable partagée |
Description |
Run |
Les solutions X |
S, A |
Recherche indéfiniment les solutions au hasard et les envoie dans la sortie 1 |
Quelque soit X,Y,Z, nous avons :Cela aboutie à la notion de proximité constructive, une distance déterminée (unique si choisie maximale) par un ensemble de couple (g,v) composé d'une fonction construite g et d'une distance choisie v. Ces fonctions g : {0,1}^n -->{0,1}^n sont choisies arbitrairement avec une faible complexité. Un n-uplet g(X) est proche du n-uplet X, il est à une distance de X au plus égale à v.La fiinesse de l'algorithme consiste, pour chaque fonction g, à bien choisire la valeur v en fonction des résultats statistiques obtenue par les essais effectués, de choisire v en fonction du pronostique de g(X) sachant X. La valeur idéale de v est :
d(X,Y) = 0 ssi X=Y
d(X,Y) = d(Y,X)
d(X,Z) <= d(X,Y) + d(Y,Z)
v = - log(P(g(X) sachant X))De tel sorte que la propabilité qu'un n-uplet placé à la distance d'une racine plus petite que v soit supérieur à 2^(-v). La distance ainsi construite traduit la probabilité de rester dans le domaine des solutions. Un n-uplet placé à une distance toute petite d'une solution, possèdera une trés grande probabilité d'être encore une solution. Un n-uplet placé à une distance de 1 d'une solution, possèdera une probabilité 1/2 d'être encore une solution. Un n-uplet placé à une distance de 2 d'une solution, possèdera une probabilité 1/4 d'être encore une solution. Un n-uplet placé à une distance de 3 d'une solution, possèdera une probabilité 1/8 d'être encore une solution. Etc... On définie les valeurs v empiriquement comme suit :
v = - log(PR(g(X) sachant X))où PR(g(X) sachant X) désigne le pronostique de g(X) sachant X c'est à dire le nombre de tirages ou X et g(X) sont solutions divisé par le nombre de tirages où X est solution et où g(X) à été évalué. (Lorsque le nombre est faible une correction apparaît dépendant d'un seuil de probabilité éxigé, voir variable aléatoire booléenne).Les fonctions génératrices peuvent produire des résultats déja connues. Pour évaluer cette propriété reflexive, on définie empiriquement de la même manière un pronostique, le pronostique que gi(X) soit nouveau sachant X, relativement à l'ensemble des résultats déja trouvés. Le calcule de ces deux pronostiques pour chaque fonction gi se fait en comptant dans S[i] les cas où X est solution et où gi(X) à été évalué, dans A[i] les cas où X et gi(x) sont solutions, et dans B[i] les cas où X et gi(x) sont solution et où gi(X) est nouveau. Le pronostique de gi(X) sachant X est égale à A[i]/S[i]
Variables |
Type |
Description |
St |
int |
Nombre de tirages au hasard de X |
S[N] |
int |
Nombre de cas où X est solution et où gi(x) a été évalué |
A[N] |
int |
Nombre de cas où X et gi(x) sont solutions |
B[N] |
int |
Nombre de cas où X et gi(X) sont solutions et où gi(X) a été nouveau |
Fonction |
Entré |
Sortie |
Description |
Rand |
n |
X |
Produit un n-uplet X au hasard selon une graine initialisée préalablement par une fonction système. |
Bool |
X |
f(X) |
Retourne en sortie la valeur booléenne f(X) |
In |
X |
b |
Retourne 1 si X est déja une solution connue, retourne 0 sinon. |
Dep |
X, i |
gi(X) |
Calcule gi(X). |
Demond |
Entré |
Flux de sortie n°1 |
Variable partagée |
Description |
Pas |
X |
Les solutions gi(X) |
|
Pour chaque i si gi(X) alors A[i]++ et si gi(X) n'est pas connue alors B[i]++ et le retourner dans le flux de sortie n°1. |
Run |
|
Les solutions X |
St, S[i], A[i], B[i]
|
Recherche indéfiniment les solutions en en retournant une copie sur le flux de sortie n°1 et en leur appliquant en premier les petites transformations gi, puis si épuissement, par le hasard. |