Brevet FR2846180A1 — publié le 20040423

La présente invention concerne d'une manière générale l'optimisation mathématique de fonctions qui ne peuvent être résolus analytiquement ou par une méthode heuristique connue. Les algorithmes génétiques sont particulièrement adaptés à ce type d'optimisation car ce sont des méthodes pouvant fonctionner sans hypothèse 15 forte de régularité. Une technique d'optimisation pour ce type de problème est le calcul évolutionnaire dont par exemple une description se trouve dans l'article intitulé " Evolutionnary Algorithms " de Thomas Bâck, ACM SIGBIO Newsletter, pp. 26-31, 1992. Le calcul évolutionnaire (en anglais: evolutionary computation) est une technique de recherche appliquée à des problèmes qui, d'une part ne peuvent pas être formulés mathématiquement de manière continue et d'autre part n'ont pas un jeu de solutions possibles suffisamment réduit pour pouvoir être énuméré. Le calcul évolutionnaire fait ainsi partie des techniques aléatoires, et plus spécifiquement fait partie des techniques de recherche aléatoire dite guidée, c'est-à-dire qui ont une fonction globale ou locale à optimiser. Si, dans une approche analytique, on cherche à concevoir une unique solution pour résoudre un problème, le calcul évolutionnaire considère 30 un jeu de solutions et fait évoluer ce jeu de solution selon des règles qui sont calquées sur l'évolution de la vie: reproduction, mutation et sélection. L'idée principale est que des individus multiples peuvent explorer des stratégies différentes et combiner leur capacité pour converger vers une solution efficace. La reproduction permet la combinaison, la mutation permet l'exploration et la sélection permet la convergence. Le calcul évolutionnaire utilise des fonctions qui sont les suivantes: la génération, qui produit une population initiale d'individus, l'évaluation, qui mesure la performance de chaque individu vis à vis du problème à résoudre, - la sélection, qui sélectionne un sous-ensemble d'individus parmi la 10 population courante, - la reproduction, qui produit un nouveau jeu d'individus. La reproduction utilise la combinaison de deux individus sélectionnés et la mutation du nouvel individu en résultant. La mutation est l'introduction d'une légère différence dans l'individu enfant résultant de la combinaison, et - le remplacement, qui remplace les individus dont la performance est la plus faible vis à vis du problème à résoudre, par des individus enfants générés par la reproduction. Ces fonctions sont utilisées de manière itérative jusqu'à ce qu'un critère de convergence soit satisfait. Par exemple, le document US 4 697 242 décrit une application qui utilise des algorithmes génétiques pour un programme électronique qui permet d'apprendre et de découvrir un langage. Le document US 4 935 877 décrit quant à lui un algorithme évolutionnaire qui met en jeu des solutions composées de fonctions et 25 d'arguments qui forment un programme. On fait évoluer les programmes pour trouver une solution à un problème donné. Cette technique est connue sous le nom de programmation génétique (d'après l'anglais: genetic programming). De manière générale, la convergence d'un algorithme évolutionnaire nécessite un long temps de calcul. L'invention s'applique particulièrement au domaine de la compression avec perte de signaux numériques. Les signaux numériques considérés ici sont de nature quelconque, par exemple des images fixes, de la vidéo, du son, des données informatiques. Dans la suite, on considère plus particulièrement le codage et le décodage d'une image fixe. Dans ce contexte, certains modes de codage utilisent un parcours établi parmi un ensemble d'échantillons numériques. Par exemple, les demandes de brevet français no 01 06933 et 01 13922 concernent de tels modes de codage. Pour que le codage soit efficace, c'est-à-dire qu'il présente un bon 1o rapport débit-distorsion, il est nécessaire de déterminer le parcours de manière adaptée. Il existe des techniques pour déterminer un parcours parmi un ensemble d'échantillons. Ces techniques sont connues sous le nom de techniques de résolution du problème du voyageur de commerce. Là encore, le temps de calcul pour trouver le parcours peut être long. La présente invention vise à fournir un procédé et un dispositif d'optimisation d'une fonction qui permettent de trouver une valeur proche de la solution optimale d'un problème posé, plus rapidement que selon la technique antérieure. A cette fin, l'invention propose un procédé d'optimisation d'une fonction, caractérisé en ce qu'il comporte les étapes de: - détermination d'une population initiale de solutions de la fonction, - évaluation des solutions de la population initiale, en fonction d'un 25 critère d'évaluation, - séparation de la population en un groupe d'exploration et en un groupe d'optimisation locale, en fonction du résultat de l'évaluation des solutions, - application d'un opérateur génétique disruptif sur le groupe 3o d'exploration, de manière à former des secondes solutions, - application d'un opérateur génétique constructif sur le groupe d'optimisation locale, de manière à former des troisièmes solutions, - formation d'une seconde population comportant au moins les secondes et troisièmes solutions, - évaluation des solutions de la seconde population, en fonction du critère d'évaluation, - sélection des meilleures solutions de la seconde population, selon le critère d'évaluation, pour former une troisième population. L'invention permet de trouver une valeur proche de la solution optimale d'un problème posé, plus rapidement que selon la technique 10 antérieure. Selon une caractéristique préférée, le procédé comporte la réitération des étapes de séparation à sélection jusqu'à ce qu'un critère d'arrêt soit satisfait. Ainsi, la solution est améliorée à chaque itération. 15 Selon une caractéristique préférée, la séparation de la population comporte la formation du groupe d'optimisation locale par la sélection de solutions parmi les meilleures selon le critère d'évaluation. Ce groupe de solution permet de converger vers la solution optimale. Selon une caractéristique préférée, la séparation de la population comporte la formation du groupe d'exploration par la sélection de solutions parmi les moins bonnes selon le critère d'évaluation. Ce groupe de solution permet d'explorer l'espace des solutions et évite de converger trop rapidement 2 5 vers une solution optimale qui pourrait n'être qu'un optimum local. Selon une caractéristique préférée, l'opérateur génétique disruptif comporte une mutation. Selon une caractéristique préférée, l'opérateur génétique constructif 30 comporte un croisement, une mutation, une duplication ou la combinaison des trois. Ces opérateurs donnent de bons résultats expérimentaux et sont simples à mettre en oeuvre. Selon une caractéristique préférée, la seconde population comporte en outre le groupe d'optimisation locale. En effet, ce groupe comporte de 5 " bonnes " solutions au sens du critère d'évaluation, il est donc intéressant de les conserver. Selon des caractéristiques préférées alternatives, le critère d'arrêt est satisfait si l'évaluation de la meilleure solution de la troisième population satisfait un critère prédéterminé ou si la troisième population n'évolue plus 10 d'une itération à l'autre ou encore si une durée prédéterminée de traitement est atteinte. Selon une caractéristique préférée, le procédé est appliqué à la formation d'un parcours parmi des coefficients d'un signal, les solutions étant des parcours possibles, et il comporte la sélection de la meilleure solution dans 15 la troisième population. Plus particulièrement le procédé selon l'invention s'applique à la formation d'un parcours parmi des coefficients d'une image numérique. Selon une caractéristique préférée, le critère d'évaluation d'un parcours est une minimisation d'un cot de codage du signal, le codage 2 0 utilisant le parcours considéré. Corrélativement, l'invention concerne un dispositif d'optimisation d'une fonction, caractérisé en ce qu'il comporte: - des moyens de détermination d'une population initiale de solutions 25 de la fonction, - des moyens d'évaluation des solutions de la population initiale, en fonction d'un critère d'évaluation, - des moyens de séparation de la population en un groupe d'exploration et en un groupe d'optimisation locale, en fonction du résultat de 3 o l'évaluation des solutions, - des moyens d'application d'un opérateur génétique disruptif sur le groupe d'exploration, de manière à former des secondes solutions, - des moyens d'application d'un opérateur génétique constructif sur le groupe d'optimisation locale, de manière à former des troisièmes solutions, - des moyens de formation d'une seconde population comportant au moins les secondes et troisièmes solutions, - des moyens d'évaluation des solutions de la seconde population, en fonction du critère d'évaluation, - des moyens de sélection des meilleures solutions de la seconde population, selon le critère d'évaluation, pour former une troisième population. Le dispositif selon l'invention comporte des moyens de mise en 10 oeuvre des caractéristiques précédemment présentées. Le dispositif selon l'invention présente des avantages analogues à ceux précédemment présentés. L'invention concerne aussi un appareil numérique incluant le dispositif selon l'invention ou des moyens de mise en oeuvre du procédé selon 15 l'invention. Cet appareil numérique est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur. Les avantages du dispositif et de l'appareil numérique sont identiques à ceux précédemment exposés. Un moyen de stockage d'information, lisible par un ordinateur ou par 20 un microprocesseur, intégré ou non au dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention. Un programme d'ordinateur lisible par un microprocesseur et comportant une ou plusieurs séquence d'instructions est apte à mettre en oeuvre les procédés selon l'invention. Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels: - la figure 1 est un mode de réalisation d'un dispositif mettant en 30 oeuvre l'invention, - la figure 2 représente un dispositif de codage selon l'invention, - la figure 3 représente un mode de réalisation de procédé de codage selon l'invention, - la figure 4 représente un modèle d'amplitude utilisé selon la présente invention, - la figure 5 représente un mode de réalisation de codage d'emplacement inclus dans le procédé de la figure 3, - les figures 6 et 7 représentent des exemples d'application d'opérateurs génétiques disruptifs à des génomes, - les figures 8 et 9 représentent des exemples d'application 10 d'opérateurs génétiques constructifs à des génomes. Selon le mode de réalisation choisi et représenté à la figure 1, un dispositif mettant en oeuvre l'invention est par exemple un microordinateur 10 connecté à différents périphériques, par exemple une caméra numérique 107 15 (ou un scanner ou tout moyen d'acquisition ou de stockage d'image) reliée à une carte graphique et fournissant des informations à traiter selon l'invention. Le dispositif 10 comporte une interface de communication 112 reliée à un réseau 113 apte à transmettre des données numériques à traiter ou inversement à transmettre des données traitées par le dispositif. Le dispositif 20 10 comporte également un moyen de stockage 108 tel que par exemple un disque dur. Il comporte aussi un lecteur 109 de disque 110. Ce disque 1 10 peut être une disquette, un CD-ROM ou un DVD-ROM, par exemple. Le disque 110 comme le disque 108 peuvent contenir des données traitées selon l'invention ainsi que le ou les programmes mettant en oeuvre l'invention qui, une fois lu par 25 le dispositif 10, sera stocké dans le disque dur 108. Selon une variante, le programme permettant au dispositif de mettre en oeuvre l'invention, pourra être stocké en mémoire morte 102 (appelée ROM sur le dessin). En seconde variante, le programme pourra être reçu pour être stocké de façon identique à celle décrite précédemment par l'intermédiaire du réseau de communication 30 113. Le dispositif 10 est relié à un microphone 111. Les données à traiter selon l'invention seront dans ce cas du signal audio. Ce même dispositif possède un écran 104 permettant de visualiser les données à traiter ou de servir d'interface avec l'utilisateur qui peut ainsi paramétrer certains modes de traitement, à l'aide du clavier 114 ou de tout autre moyen (souris par exemple). L'unité centrale 100 (appelée CPU sur le dessin) exécute les instructions relatives à la mise en oeuvre de l'invention, instructions stockées dans la mémoire morte 102 ou dans les autres éléments de stockage. Lors de la mise sous tension, les programmes de traitement stockés dans une mémoire non volatile, par exemple la ROM 102, sont transférés dans la mémoire vive 10 RAM 103 qui contiendra alors le code exécutable de l'invention ainsi que des registres pour mémoriser les variables nécessaires à la mise en oeuvre de l'invention. De manière plus générale, un moyen de stockage d'information, lisible par un ordinateur ou par un microprocesseur, intégré ou non au 15 dispositif, éventuellement amovible, mémorise un programme mettant en oeuvre le procédé selon l'invention. Le bus de communication 101 permet la communication entre les différents éléments inclus dans le micro-ordinateur 10 ou reliés à lui. La représentation du bus 101 n'est pas limitative et notamment l'unité centrale 100 20 est susceptible de communiquer des instructions à tout élément du microordinateur 10 directement ou par l'intermédiaire d'un autre élément du microordinateur 10. En référence à la figure 2, un mode de réalisation de dispositif de 25 codage 2 selon l'invention est destiné à coder un signal numérique dans le but de le compresser. Le dispositif de codage est intégré dans un appareil, qui est par exemple un appareil photographique numérique, un caméscope numérique, un scanner, une imprimante, un photocopieur, un télécopieur, un système de gestion de base de données ou encore un ordinateur. Une source d'image 1 fournit une image numérique IM au dispositif de codage 2, qui comporte un circuit de transformation 21, un circuit de détermination de parcours de codage 22 et un circuit de codage entropique 23. Le fonctionnement du dispositif de codage et plus particulièrement du circuit de détermination de parcours de codage 22 sera détaillé dans la suite. Le dispositif selon l'invention comporte: - des moyens de détermination d'une population initiale de parcours, 5 - des moyens d'évaluation des parcours de la population initiale, en fonction d'un critère d'évaluation, - des moyens de séparation de la population en un groupe d'exploration et en un groupe d'optimisation locale, en fonction du résultat de l'évaluation des parcours, - des moyens d'application d'un opérateur génétique disruptif sur le groupe d'exploration, de manière à former des seconds parcours, - des moyens d'application d'un opérateur génétique constructif sur le groupe d'optimisation locale, de manière à former des troisièmes parcours, - des moyens de formation d'une seconde population comportant au 15 moins les seconds et troisièmes parcours, - des moyens d'évaluation des parcours de la seconde population, en fonction du critère d'évaluation, - des moyens de sélection des meilleurs parcours de la seconde population, selon le critère d'évaluation, pour former une troisième population. Le dispositif de codage fournit un fichier contenant des données représentant l'image compressée à des moyens de transmission et/ou de mémorisation 3. Ces moyens sont classiques et ne seront pas décrits ici. 2 5 La figure 3 représente un mode de réalisation de procédé de codage d'une image, selon l'invention. Ce procédé est mis en oeuvre dans le dispositif de codage et comporte des étapes El à E7. Le procédé comporte globalement une transformation du signal à coder, puis la détermination d'un modèle d'amplitude des coefficients issus de 30 la transformation. Les emplacements de ces coefficients sont ensuite codés selon une méthode qui utilise un parcours établi parmi les coefficients. Un tel procédé de codage est décrit par exemple dans la demande de brevet français no 01 06933 ou dans les demandes de brevets français n0 02 00330 et 02 00332 déposées par la demanderesse. Le procédé est réalisé sous la forme d'un algorithme qui peut être 5 mémorisé en totalité ou en partie dans tout moyen de stockage d'information capable de coopérer avec le microprocesseur. Ce moyen de stockage est lisible par un ordinateur ou par un microprocesseur. Ce moyen de stockage est intégré ou non au dispositif, et peut être amovible. Par exemple, il peut comporter une bande magnétique, une disquette ou un CD-ROM (disque 10 compact à mémoire figée). L'étape El est une transformation linéaire ou non linéaire d'une image numérique IM à traiter selon l'invention. L'image a par exemple une taille de 512 x 512 pixels. Dans le mode préféré de réalisation de l'invention, la transformation 15 est une décomposition en sous-bandes de fréquences. Le signal est décomposé en sous-bandes de fréquence à plusieurs niveaux de résolution par une transformation en ondelettes discrètes dite DWT (d'après l'anglais Discrete Wavelet Transform) à M niveaux de résolution. Il est à noter que la sous-bande basse peut être codée selon le 20 procédé décrit ci-après ou de façon classique par prédiction linéaire. D'autres types de transformation peuvent être utilisés, par exemple la transformation en cosinus discrète dite DCT ou la transformation de Fourier ou encore une transformation non-linéaire comme une transformation morphologique. L'étape suivante E2 est la sélection d'une première sous-bande résultant de la décomposition précédente. Les sous- bandes sont considérées une par une. L'étape suivante E3 est un classement des coefficients de la sousbande courante. Le signe des coefficients est tout d'abord codé de manière 30 indépendante. Les coefficients sont ensuite considérés en valeur absolue et sont classés du plus grand au plus petit. L'étape suivante E4 est la détermination d'une fonction d'approximation de la suite des coefficients classés. Cette fonction est par exemple une exponentielle décroissante définie par un jeu de paramètres qui sont déterminés par régression. La figure 4 représente un exemple de modèle d'amplitude A. A chaque valeur entière k en abscisse correspond une valeur A(k) fournie par le modèle d'amplitude. La valeur A(k) est une approximation de l'amplitude du kme coefficient classé par ordre décroissant. L'étape suivante E5 est le codage des emplacements des coefficients. Cette étape comporte la détermination d'un parcours parmi les coefficients de la sous-bande courante de sorte que le cot de codage de ce parcours soit minimal. Le parcours comporte un coefficient initial et la liste des 15 vecteurs joignant les autres coefficients. Chaque coefficient du parcours différent du coefficient initial est représenté par un vecteur décrivant son emplacement par rapport au coefficient précédent dans le parcours. Il est à noter que le parcours ne passe pas forcement par tous les coefficients de la sous-bande courante. En effet, il est possible de ne coder qu'une partie des 20 coefficients et de mettre les autres coefficients à la valeur zéro lors du décodage ultérieur. Une fois le parcours déterminé, les coordonnées du coefficient initial sont codées par un codage binaire et les vecteurs sont codés par un codage entropique. L'étape E5 est détaillée dans la suite. Elle se situe dans le domaine des techniques de résolution du problème de voyageur de commerce. Plus particulièrement, il s'agit du problème du voyageur de commerce variable dans le temps. En effet, le cot associé au passage d'un échantillon à un autre dépend du parcours déjà effectué, puisque la distorsion de décodage d'un 30 échantillon dépend du rang auquel il est décodé et le débit dépend du vecteur engendré et des vecteurs déjà présents dans le parcours effectué. La forme codée d'une sous-bande de l'image comporte un modèle d'amplitude qui fournit une approximation de l'amplitude des coefficients et un parcours qui fournit une suite ordonnée des emplacements des coefficients. L'emplacement du kème coefficient de cette suite est déterminé par le parcours 5 et son amplitude est déterminée par l'ordonnée correspondant à l'abscisse k selon le modèle d'amplitude. L'étape suivante E6 est un test pour déterminer si la sous-bande courante est la dernière sous-bande de l'image à coder. Si la réponse est négative, cette étape est suivie de l'étape E7 à l1 laquelle une sous-bande suivante est considérée. L'étape E7 est suivie de l'étape E3 précédemment décrite. Si la réponse est positive à l'étape E6, alors les données codées subissent un codage entropique connu en soi, tel que codage d'Huffman ou codage arithmétique, et le codage de l'image est terminé. 15 La figure 5 représente un mode de réalisation de l'étape E5 de codage des emplacements des coefficients. Ce codage comporte des étapes E51 à E60. Ce codage comporte globalement la détermination d'un parcours 20 parmi les coefficients et le codage des coefficients en fonction du parcours. Un parcours comporte un coefficient de la sous-bande, dit coefficient initial, et une liste de vecteurs joignant au moins une partie des autres coefficients. La détermination du parcours est optimisée selon l'invention. On considère une population de solutions qui définissent chacune un 25 parcours possible parmi les coefficients. Une solution possible est décrite par un génome. Un génome est ici une liste de Q+1 indices, o Q est le nombre de points dans la sous-bande de fréquence considérée. Les coefficients de la sous-bande sont considérés de gauche à droite et de haut en bas dans la sous-bande. Chaque coefficient de la 30 sous-bande est associé à un indice en fonction de cet ordre de lecture. Un indice supplémentaire X est réservé au point d'arrêt du parcours. Au-delà de ce point, les coefficients ne sont plus codés. Ainsi, par exemple, le parcours des points 1-5-8-10-4 dans une image de dix points peut être codé de la façon suivante: (1 58104X23679). L'ordre des points après le point d'arrêt X n'a aucune importance. Pour un ensemble de points à parcourir de taille donnée, des chemins de longueurs différentes dans cet ensemble sont représentés par les génomes de longueur fixe. L'étape E51 est une initialisation de la population des génomes. 10 Pour cela, un tirage aléatoire est réalisé pour déterminer pL solutions. En variante, il est possible de choisir au moins une partie des génomes de la population initiale. L'étape suivante E52 est une évaluation réalisée par une fonction d'adaptation qui mesure la performance de chaque génome précédemment 15 déterminé. Pour cela, un cot de codage R + k.D est calculé pour chaque chemin représenté par un génome. Le cot de codage représente un compromis entre débit et distorsion. Le cot de codage d'un signal S est ici la fonction C(S) = R(S) + X.D(S), dans laquelle R(S) représente le débit de transmission de la forme 20 codée du signal S, D(S) représente la distorsion générée dans le signal reconstruit après codage et décodage, par rapport au signal d'origine et X; est un paramètre de réglage entre compression et distorsion. Il est à noter que la minimisation de la fonction C(S) sur le signal S est équivalente à la minimisation de la fonction C(S) sur chaque élément d'une 25 partition du signal, en particulier sur chaque échantillon du signal. Cela est du au fait que la distorsion et le débit sont respectivement additifs. L'étape suivante E53 est une sélection ou séparation de la population en deux groupes. Pour cela, on considère un coefficient P compris dans l'intervalle fermé [0, 1]. La population de Ii génomes est alors divisée en 30 un groupe d'optimisation locale comportant P.Ft génomes et un groupe d'exploration comportant (1-P).pt génomes. Il est à noter qu'un même génome ne peut appartenir aux deux groupes. En revanche, si deux génomes sont identiques, il est possible qu'ils se trouvent chacun dans un groupe différent. De préférence, le groupe d'optimisation locale comporte les P.pi 5 meilleurs génomes de la population, au sens de l'évaluation précédemment effectuée. Les meilleurs génomes sont les génomes qui produisent les cots de codage les plus faibles. En variante, les génomes du groupe d'optimisation locale sont déterminés par un tirage aléatoire selon lequel la probabilité d'être sélectionné augmente en fonction de la performance du génome. Le groupe d'optimisation locale permet de trouver une solution optimum, mais qui peut n'être qu'un optimum local si la recherche est limitée à ce groupe. Le groupe d'exploration comporte les (1-P).It autres génomes. Ce groupe permet au contraire d'explorer tout l'espace de recherche de manière à 15 ce que l'algorithme ne converge pas trop rapidement et que la solution ne soit pas un optimum local. L'étape E53 est suivie des étapes E54 et E55. A l'étape E54, un opérateur génétique disruptif est appliqué sur le groupe d'exploration. Cet opérateur comporte une mutation qui est appliquée à 20 tous les génomes du groupe d'exploration. Par exemple, l'opérateur disruptif est une mutation qui provoque de grands sauts dans l'espace de recherche. La mutation " Scramble Mutation " décrite par P. Larranaga, C. M. H. Kuijpers et R.H. Murga dans " Tackling the travelling Salesman Problem with Evolutionary Algorithms: Representation and 25 Operators ", page 36, satisfait ce critère. Ce document est accessible dans la base de données de " Scientific Literature Digital Library " à l'adresse internet: http://citeseer.ni.nec.com/2 10802.html. Un exemple d'application de la mutation " Scramble Mutation " est 30 représenté à la figure 6. Cette mutation sélectionne aléatoirement une partie 61 d'un génome donné 60 et la retire de celui-ci. Les index de la partie retirée 61 sont réordonnés aléatoirement et sont ensuite réintroduit dans le génome initial pour former un second génome 62. En variante, l'opérateur disruptif comporte une ou plusieurs applications de la mutation appelée " Exchange mutation " et qui consiste à échanger l'emplacement de deux index choisis aléatoirement dans le génome. La figure 7 représente l'application de cette mutation à un génome 70. Les index 8 et 3 sont échangés ce qui produit un nouveau génome 71. A l'étape E55, un opérateur génétique constructif est appliqué sur le 10groupe d'optimisation locale. Cet opérateur comporte un croisement suivi d'une mutation. Un croisement est un opérateur stochastique binaire qui combine une ou plusieurs caractéristiques de deux génomes parents de façon aléatoire de manière à générer un ou des nouveaux génomes. En variante, le croisement est replacé par une duplication des génomes parents, c'està-dire une recopie 15 de ceux-ci. Chacun des génomes du groupe d'optimisation locale est un génome parent et est utilisé une seule fois. En variante, les génomes parents sont sélectionnés par tirage aléatoire. L'opérateur de croisement est appliqué à deux génomes parents. 2 0 Une mutation est ensuite appliquée aux deux génomes générés par le croisement. Par exemple, on utilise le croisement appelé " Order crossover " décrit par P. Larranaga, C. M. H. Kuijpers et R.H. Murga dans " Tackling the travelling Salesman Problem with Evolutionary Algorithms: Representation and 25 Operators ", pages 24-25. Ce croisement est représenté à la figure 8. Deux points de coupure 82 sont sélectionnés aléatoirement à l'intérieur de chacun des génomes parents 80 et 81. Chaque génome généré 83, 84 reçoit les index de l'un des 30 génomes parents 80, 81 entre les points de coupure. Puis les autres positions reçoivent les valeurs d'index de l'autre parent qui sont différentes de celles déjà affectées et dans l'ordre o elles apparaissent dans l'autre parent à partir du second point de coupure. Selon un autre exemple, on utilise le croisement appelé " The position based crossover " décrit par P. Larranaga, C. M. H. Kuijpers et R.H. 5 Murga dans "Tackling the travelling Salesman Problem with Evolutionary Algorithms: Representation and Operators ", page 26. Ce croisement est représenté à la figure 9. Des positions sont sélectionnées aléatoirement dans les génomes parents 90 et 91. Il s'agit ici des deuxième, troisième et sixième positions. Un génome généré 92, 93 reçoit à ces positions les valeurs d'index situées aux mêmes positions de l'un des parents. Les autres positions reçoivent les valeurs d'index de l'autre parent qui sont différentes de celles déjà affectées et dans l'ordre o elles apparaissent dans l'autre parent. Deux génomes sont ainsi générés. Pour la mutation qui suit le croisement, on utilise l'opérateur décrit précédemment ou en variante, on utilise l'opérateur de mutation appelé " Insertion mutation " décrit par P. Larranaga, C. M. H. Kuijpers et R.H. Murga dans " Tackling the travelling Salesman Problem with Evolutionary Algorithms: Representation and Operators ", page 34. Cet opérateur sélectionne aléatoirement un index dans un génome, le retire du génome et le réinsère à un position déterminée aléatoirement. Selon une variante de l'étape E55, les opérateurs de croisement, mutation et duplication sont appliqués aléatoirement aux génomes parents. Chaque opérateur a une probabilité d'être choisi. Le choix de l'opérateur à 25 appliquer est fait pour chaque couple à reproduire. L'étape suivante E56 est la réunion du groupe d'optimisation locale, de la population résultant de l'optimisation locale et de la population résultant de l'exploration. Le groupe d'optimisation locale contient par construction des 30 génomes performants au sens de l'évaluation réalisée à l'étape E52. La population résultant de l'optimisation locale est susceptible de contenir des génomes performants, en raison des opérateurs choisis et des génomes parents. La population résultant de l'exploration comporte des génomes qui sont susceptibles de réorienter la recherche de l'optimum vers une autre zone de l'espace de recherche. En variante, le groupe d'optimisation locale n'est pas inclus dans la 5 nouvelle population, ce qui permet de réduire la taille mémoire nécessaire pour mémoriser les données en cours de traitement. L'étape suivante E57 est une évaluation de la population courante. Cette étape est analogue à l'étape E52 précédemment décrite. Elle a pour résultat une performance pour chaque génome, établie en fonction d'un critère 10 qui est ici un cot de codage. L'étape suivante E58 est une sélection pour ne conserver que j génomes. On utilise ici une sélection appelée tirage à la roulette décrite dans l'ouvrage " Evolutionary Computation 1: Basic Algorithms and operators " de John Grefensette, " the Institute of Physic Publishing, Bristol et Philadelphia ", 15 édité par T. Back, B. Fogel et T. Michalewicz, pages 175-176. Cette méthode assigne à chaque génome une probabilité d'être sélectionné qui est proportionnelle à sa performance. En variante, on peut utiliser une sélection appelée " rankedselection ", décrite dans l'ouvrage précédent aux pages 187 à 194. Cette 20 sélection ordonne les génomes de la population selon leur performance. La probabilité de sélection dépend alors du rang du génome dans la population. En outre, dans toutes les variantes, le meilleur génome est systématiquement gardé dans la nouvelle population. L'étape suivante E59 est un test pour déterminer si un critère d'arrêt 25 est satisfait. Le critère d'arrêt est par exemple: - la performance du meilleur génome est satisfaisante pour le problème à résoudre, - il y a convergence et la population n'évolue plus d'une itération à l'autre, 3 0 - une durée limite de traitement a été atteinte. Le critère d'arrêt peut aussi être une combinaison de plusieurs critères. Lorsque que l'un des critères est vérifié, il y a arrêt du traitement. Tant que le critère d'arrêt n'est pas satisfait, le traitement est réitéré et pour cela l'étape E59 est suivie de l'étape E53 précédemment décrite. Lorsque le critère d'arrêt est satisfait, le meilleur génome au sens de la performance est sélectionné à l'étape E60. Dans l'exemple choisi, ce génome représente un parcours parmi un ensemble d'échantillons. Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier. REVENDICATIONS 1. Procédé d'optimisation d'une fonction, caractérisé en ce qu'il comporte les étapes de: - détermination (E51) d'une population initiale de solutions de la fonction, - évaluation (E52) des solutions de la population initiale, en fonction 10 d'un critère d'évaluation, séparation (E53) de la population en un groupe d'exploration et en un groupe d'optimisation locale, en fonction du résultat de l'évaluation des solutions, - application (E54) d'un opérateur génétique disruptif sur le groupe 15 d'exploration, de manière à former des secondes solutions, application (E55) d'un opérateur génétique constructif sur le groupe d'optimisation locale, de manière à former des troisièmes solutions, formation (E56) d'une seconde population comportant au moins les secondes et troisièmes solutions, - évaluation (E57) des solutions de la seconde population, en fonction du critère d'évaluation, - sélection (E58) des meilleures solutions de la seconde population, selon le critère d'évaluation, pour former une troisième population. 2. Procédé selon la revendication 1, caractérisé en ce qu'il comporte la réitération des étapes de séparation (E53) à sélection (E58) jusqu'à ce qu'un critère d'arrêt soit satisfait. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que la 3 0 séparation (E53) de la population comporte la formation du groupe d'optimisation locale par la sélection de solutions parmi les meilleures selon le critère d'évaluation. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la séparation (E53) de la population comporte la formation du groupe d'exploration par la sélection de solutions parmi les moins bonnes selon le critère d'évaluation. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que l'opérateur génétique disruptif comporte (E54) une mutation. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que l'opérateur génétique constructif comporte (E55) un croisement, une mutation, une duplication ou la combinaison des trois. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que la seconde population comporte (E56) en outre le groupe d'optimisation locale. 8. Procédé selon l'une quelconque des revendications 1 à 7, 20 caractérisé en ce que le critère d'arrêt (E59) est satisfait si l'évaluation de la meilleure solution de la troisième population satisfait un critère prédéterminé. 9. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que le critère d'arrêt (E59) est satisfait si la troisième 25 population n'évolue plus d'une itération à l'autre. 10. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que le critère d'arrêt (E59) est satisfait si une durée prédéterminée de traitement est atteinte. 30 11. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce qu'il est appliqué à la formation d'un parcours parmi des coefficients d'un signal, les solutions étant des parcours possibles, et en ce qu'il comporte la sélection (E60) de la meilleure solution dans la troisième population. 12. Procédé selon la revendication 11, caractérisé en ce qu'il est appliqué à la formation d'un parcours parmi des coefficients d'une image numérique. 13. Procédé selon la revendication 11 ou 12, caractérisé en ce que 10 le critère d'évaluation d'un parcours (E52, E53) est une minimisation d'un cot de codage du signal, le codage utilisant le parcours considéré. 14. Dispositif d'optimisation d'une fonction, caractérisé en ce qu'il comporte (22): - des moyens de détermination d'une population initiale de solutions de la fonction, - des moyens d'évaluation des solutions de la population initiale, en fonction d'un critère d'évaluation, - des moyens de séparation de la population en un groupe 20 d'exploration et en un groupe d'optimisation locale, en fonction du résultat de l'évaluation des solutions, - des moyens d'application d'un opérateur génétique disruptif sur le groupe d'exploration, de manière à former des secondes solutions, des moyens d'application d'un opérateur génétique constructif sur 25 le groupe d'optimisation locale, de manière à former des troisièmes solutions, - des moyens de formation d'une seconde population comportant au moins les secondes et troisièmes solutions, - des moyens d'évaluation des solutions de la seconde population, en fonction du critère d'évaluation, - des moyens de sélection des meilleures solutions de la seconde population, selon le critère d'évaluation, pour former une troisième population. 15. Dispositif selon la revendication 14, caractérisé en ce que les moyens de séparation à sélection sont adaptés à réitérer leur fonctionnement jusqu'à ce qu'un critère d'arrêt soit satisfait. 16. Dispositif selon la revendication 14 ou 15, caractérisé en ce que les moyens de séparation de la population sont adaptés à former le groupe d'optimisation locale par la sélection de solutions parmi les meilleures selon le critère d'évaluation. 17. Dispositif selon l'une quelconque des revendications 14 à 16, caractérisé en ce que les moyens de séparation de la population sont adaptés à former le groupe d'exploration par la sélection de solutions parmi les moins bonnes selon le critère d'évaluation. 18. Dispositif selon l'une quelconque des revendications 14 à 17, caractérisé en ce qu'il est adapté à mettre en oeuvre un opérateur génétique disruptif qui comporte une mutation. 19. Dispositif selon l'une quelconque des revendications 14 à 18, 20 caractérisé en ce qu'il est adapté à mettre en oeuvre un opérateur génétique constructif qui comporte un croisement, une mutation, une duplication ou la combinaison des trois. 20. Dispositif selon l'une quelconque des revendications 14 à 19, 25 caractérisé en ce que les moyens de formation de la seconde population sont adaptés à la former de sorte qu'elle comporte en outre le groupe d'optimisation locale. 21. Dispositif selon l'une quelconque des revendications 14 à 20, 30 caractérisé en ce qu'il est adapté à mettre en oeuvre un critère d'arrêt qui est satisfait si l'évaluation de la meilleure solution de la troisième population satisfait un critère prédéterminé. 22. Dispositif selon l'une quelconque des revendications 14 à 20, caractérisé en ce qu'il est adapté à mettre en oeuvre un critère d'arrêt qui est satisfait si la troisième population n'évolue plus d'une itération à l'autre. 23. Dispositif selon l'une quelconque des revendications 14 à 20, caractérisé en ce qu'il est adapté à mettre en oeuvre un critère d'arrêt qui est satisfait si une durée prédéterminée de traitement est atteinte. 24. Dispositif selon l'une quelconque des revendications 14 à 23, caractérisé en ce qu'il est adapté à former un parcours parmi des coefficients d'un signal, les solutions étant des parcours possibles, et en ce qu'il comporte des moyens de sélection de la meilleure solution dans la troisième population. 25. Dispositif selon la revendication 24, caractérisé en ce qu'il est adapté à former un parcours parmi des coefficients d'une image numérique. 26. Dispositif selon la revendication 24 ou 25, caractérisé en ce qu'il est adapté à mettre en oeuvre un critère d'évaluation d'un parcours qui est une 20 minimisation d'un cot de codage du signal, le codage utilisant le parcours considéré. 27. Dispositif d'optimisation selon l'une quelconque des revendications 14 à 26, caractérisé en ce que les moyens de détermination, 25 évaluation, séparation, application, formation et sélection sont incorporés dans: - un microprocesseur (100), - une mémoire morte (102) comportant un programme pour traiter les données, et 3 0 - une mémoire vive (103) comportant des registres adaptés à enregistrer des variables modifiées au cours de l'exécution dudit programme. 28. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte des moyens adaptés à mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 13. 29. Appareil de traitement (10) d'une image numérique, caractérisé en ce qu'il comporte le dispositif selon l'une quelconque des revendications 14 à 27.