Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Ces travaux portent sur l'optimisation de structures stratifiées en utilisant un algorithme génétique. Un programme d'optimisation est développé et est ensuite appliqué à la résolution d'une série de problèmes d'optimisation pour lesquels les variables de design peuvent appartenir soit à un domaine discret soit à un domaine continu. Tout d'abord, il est question de problèmes où le nombre de plis, le matériau et l'épaisseur des plis sont fixés. Les variables de design sont alors l'orientation de chaque pli qui peut prendre, dans un premier cas, des valeurs discrètes (0ʻ, ł45ʻ, 90ʻ) puis des valeurs continues (de 0ʻ à 90ʻ). Deuxièmement, il est question de problèmes pour lesquels le nombre de plis et le matériau des plis deviennent des variables de design qui s'ajoutent alors à l'orientation des plis. Dans ces cas, la valeur des variables de design (matériaux et orientations) est choisie dans une liste de valeurs. / L'objectif de ces problèmes est, en premier lieu, la minimisation du poids ou du coût de la structure sous différentes contraintes et finalement, la minimisation du poids et du coût simultanément avec une formulation multi-objectifs. L'algorithme génétique développé utilise une stratégie multi-élitiste et empêche la présence d'individus identiques dans la population. Finalement, un algorithme génétique hybride, combinant l'algorithme génétique et une recherche locale, est développé et ensuite testé sur ces mêmes problèmes. Cette hybridation de l'algorithme résulte en une diminution du temps de calcul exigé et en une amélioration substantielle des résultats.

En tant qu'algorithmes d'apprentissage automatique à la pointe de la technologie, les réseaux de neurones profonds nécessitent de nombreux exemples pour bien fonctionner sur une tâche d'apprentissage. La collecte et l'annotation de multiples échantillons nécessitent un travail humain important et c'est même impossible dans la plupart des problèmes du monde réel tel que l'analyse de données biomédicales. Dans le contexte de la vision par ordinateur, la classification d'images à quelques plans vise à saisir la capacité humaine à apprendre de nouveaux concepts avec peu de supervision. À cet égard, l'idée générale est de transférer les connaissances des catégories de base avec plus d'encadrement vers des classes nouvelles avec peu d'exemples. En particulier, les approches actuelles d'apprentissage à quelques coups pré entraînent un modèle sur les classes de base disponible pour généraliser aux nouvelles classes, peut-être avec un réglage fin. Cependant, la généralisation du modèle actuel est limitée en raison de certaines hypothèses lors de la préformation et de restrictions lors de l'étape de mise au point. Cette thèse vise à assouplir trois hypothèses des modèles d'apprentissage à quelques plans actuels et nous proposons un apprentissage de représentation pour la classification d'images à quelques plans. Tout d'abord, le gel d'un modèle préformé semble inévitable dans la phase de réglage fin en raison de la forte possibilité de surentraînement sur quelques exemples. Malheureusement, l'apprentissage par transfert avec une hypothèse de modèle gelé limite la capacité du modèle puisque le modèle n'est pas mis à jour avec aucune connaissance des nouvelles classes. Contrairement au gel d'un modèle, nous proposons un alignement associatif qui permet d'affiner et de mettre à jour le réseau sur de nouvelles catégories. Plus précisément, nous présentons deux stratégies qui détectent et alignent les nouvelles classes sur les catégories de base hautement liées. Alors que la première stratégie pousse la distribution des nouvelles classes au centre de leurs catégories de base associées, la seconde stratégie effectue une correspondance de distribution à l'aide d'un algorithme d'entraînement contradictoire. Dans l'ensemble, notre alignement associatif vise à éviter le surentraînement et à augmenter la capacité du modèle en affinant le modèle à l'aide de nouveaux exemples et d'échantillons de base associés. Deuxièmement, les approches actuelles d'apprentissage à quelques coups effectuent le transfert de connaissances vers de nouvelles classes distinctes sous l'hypothèse uni modale, où tous les exemples d'une seule classe sont représentés par un seul cluster. Au lieu de cela, nous proposons une approche d'apprentissage de l'espace des caractéristiques basée sur le mélange (MixtFSL) pour déduire une représentation multimodale. Alors qu'un précédent travail basé sur un modèle de mélange d'Allen et al. citeallen2019infinite est basé sur une méthode de clusters classique de manière non différentielle, notre MixtFSL est un nouveau modèle multimodale de bout en bout et entièrement différentielle. MixtFSL capture la multimodale des classes de base sans aucun algorithme de clusters classique à l'aide d'un cadre en deux étapes. La première phase s'appeler formation initiale et vise à apprendre la représentation préliminaire du mélange avec une paire de fonctions de perte. Ensuite, l'étape suivante progressive, la deuxième étape, stabilise la formation avec un cadre de formation de type enseignant-élève utilisant une fonction de perte unique. Troisièmement, contrairement aux techniques actuelles à quelques prises de vue consistant à représenter chaque exemple d'entrée avec une seule entité à la fin du réseau, nous proposons un extracteur d'entités d'ensemble et des ensembles d'entités correspondantes qui assouplissent l'hypothèse typique basée sur une seule entité en raisonnant sur des ensembles d'entités. Ici, nous émettons l'hypothèse que l'hypothèse d'une seule caractéristique est problématique dans la classification d'images à quelques prises de vue puisque les nouvelles classes sont différentes des classes de base préformées. À cette fin, nous proposons nouvel extracteur de caractéristiques d'ensemble d'apprentissage profond basé sur les réseaux de neurones hybrides convolution-attention. De plus, nous suggérons trois métriques ensemble à ensemble non paramétriques pour séduire la classe de l'entrée donnée. Cette thèse utilise plusieurs indicateurs standards publiés dans la littérature sur l'apprentissage en peu d'exemples et l'ossature de réseau pour évaluer les méthodes que nous proposons. / As the current state-of-the-art machine learning algorithms, deep neural networks require many examples to perform well on a learning task. Gathering and annotating many samples requires significant human labor, and it is even impossible in most real-world problems such as biomedical data analysis. Under the computer vision context, few-shot image classification aims at grasping the human ability to learn new concepts with little supervision. In this respect, the general idea is to transfer knowledge from base categories with more supervision to novel classes with few examples. In particular, the current few-shot learning approaches pre-train a model on available base classes to generalize to the novel classes, perhaps with fine-tuning. However, the current model's generalization is limited because of some assumptions in the pre-training and restrictions in the fine-tuning stage. This thesis aims to relax three assumptions of the current few-shot learning models, and we propose representation learning for few-shot image classification. First, freezing a pre-trained model looks inevitable in the fine-tuning stage due to the high possibility of overfitting on a few examples. Unfortunately, transfer learning with a frozen model assumption limits the model capacity since the model is not updated with any knowledge of the novel classes. In contrast to freezing a model, we propose associative alignment that enables fine-tuning and updating the network on novel categories. Specifically, we present two strategies that detect and align the novel classes to the highly related base categories. While the first strategy pushes the distribution of the novel classes to the center of their related base categories, the second strategy performs distribution matching using an adversarial training algorithm. Overall, our associative alignment aims to prevent overfitting and increase the model capacity by refining the model using novel examples and related base samples. Second, the current few-shot learning approaches perform transferring knowledge to distinctive novel classes under the uni-modal assumption, where all the examples of a single class are represented with a single cluster. Instead, we propose a mixture-based feature space learning (MixtFSL) approach to infer a multi-modal representation. While a previous mixture-model-based work of Allen et al. [1] is based on a classical clustering method in a non-differentiable manner, our MixtFSL is a new end-to-end multi-modal and fully differentiable model. MixtFSL captures the multi-modality of base classes without any classical clustering algorithm using a two-stage framework. The first phase is called initial training and aims to learn preliminary mixture representation with a pair of loss functions. Then, the progressive following stage, the second stage, stabilizes the training with a teacher-student kind of training framework using a single loss function. Third, unlike the current few-shot techniques of representing each input example with a single feature at the end of the network, we propose a set feature extractor and matching feature sets that relax the typical single feature-based assumption by reasoning on feature sets. Here, we hypothesize that the single feature assumption is problematic in few-shot image classification since the novel classes are different from pre-trained base classes. To this end, we propose a new deep learning set feature extractor based on the hybrid convolution-attention neural networks. Additionally, we offer three non-parametric set-to-set metrics to infer the class of the given input. This thesis employs several standard benchmarks of few-shot learning literature and network backbones to evaluate our proposed methods.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / L’objet principale de cette thèse est l’étude théorique et la conception d’algorithmes d’apprentissage concevant des classificateurs par vote de majorité. En particulier, nous présentons un théorème PAC-Bayes s’appliquant pour borner, entre autres, la variance de la perte de Gibbs (en plus de son espérance). Nous déduisons de ce théorème une borne du risque du vote de majorité plus serrée que la fameuse borne basée sur le risque de Gibbs. Nous présentons également un théorème permettant de borner le risque associé à des fonctions de perte générale. À partir de ce théorème, nous concevons des algorithmes d’apprentissage construisant des classificateurs par vote de majorité pondérés par une distribution minimisant une borne sur les risques associés aux fonctions de perte linéaire, quadratique, exponentielle, ainsi qu’à la fonction de perte du classificateur de Gibbs à piges multiples. Certains de ces algorithmes se comparent favorablement avec AdaBoost. / The main purpose of this thesis is the theoretical study and the design of learning algorithms returning majority-vote classifiers. In particular, we present a PAC-Bayes theorem allowing us to bound the variance of the Gibbs’ loss (not only its expectation). We deduce from this theorem a bound on the risk of a majority vote tighter than the famous bound based on the Gibbs’ risk. We also present a theorem that allows to bound the risk associated with general loss functions. From this theorem, we design learning algorithms building weighted majority vote classifiers minimizing a bound on the risk associated with the following loss functions : linear, quadratic and exponential. Also, we present algorithms based on the randomized majority vote. Some of these algorithms compare favorably with AdaBoost.

Les problèmes de satisfaction de contraintes sont parmi les problèmes fréquents qu'on trouve dans des domaines variés tels que la recherche opérationnelle et l'intelligence artificielle. Dans un problème de satisfaction de contraintes, on cherche à assigner aux variables des valeurs de telle sorte que toutes les contraintes fournies en entrée soient satisfaites. Chaque contrainte est une paire contenant un tuple de variables et une relation définissant les combinaisons de valeurs autorisées pour ce tuple. Ce problème est NP-complet, donc il est important d'identifier des cas particuliers résolubles en temps polynomial. Dans ce travail, on s'intéresse à une approche dite algébrique pour découvrir des classes de problèmes de satisfaction de contraintes traitables efficacement. On se base sur le résultat prouvé par Dalmau "en 2006" qui donne un algorithme polynomial pour une classe assez vaste de problèmes. On analyse et implémente un cas particulier de cet algorithme qui permet de résoudre des instances de 2-SAT. Cette implementation nous aidera à faire des expérimentations et à en apprendre plus sur la nature de l'algorithme de Dalmau et son comportement en pratique.

Cette thèse porte sur les problèmes de prise de décisions séquentielles sous incertitudes dans un système mono ou multi-agents. Les processus décisionnels de Markov offrent un modèle mathématique permettant à la fois de formaliser et de résoudre de tels problèmes. Il existe de multiple travaux proposant des techniques efficaces pour la résolution des processus décisionnels de Markov. Néanmoins, trois facteurs, dits malédictions, limitent grandement le passage à l'échelle de ces techniques. Le premier facteur, la malédiction de la dimension, est le plus connu. Il lie la complexité des algorithmes au nombre d'états du système dont la croissance est exponentielle en fonction des attributs des états. Le second facteur, la malédiction de l'historique, a été identifié plus récemment. Il lie la complexité des algorithmes à la dimension exponentielle de l'espace des historiques à prendre en compte afin de résoudre le problème. Enfin, le dernier facteur, là malédiction de la distributivité, est identifié dans cette thèse. Il lie la complexité des algorithmes à la contrainte du contrôle distribué d'un système, résultant sur une complexité doublement exponentielle. À travers nos contributions, nous proposons une réponse à chacune des trois malédictions. Nous atténuons à la fois la malédiction de la dimension et la malédiction de l'historique en exploitant les dépendances causales soit entre états soit entre historiques. Suivant cette idée, nous proposons une famille d'algorithmes exacts et approximatifs, nommée programmation dynamique topologique, visant à résoudre les processus décisionnels de Markov complètement ou partiellement observables. Ces algorithmes permettent de réduire considérablement le nombre de mises à jour d'un état ou d'un historique. Ainsi, lorsque les problèmes sont munis d'une structure topologique, la programmation dynamique topologique offre une solution efficace. Pour pallier aux effets de la malédiction de la distributivité, nous avons proposé d'étendre la planification centralisée au cadre du contrôle distribué. Nous proposons une analyse formelle des problèmes de contrôle distribué des processus décisionnels de Markov sous le regard de la planification centralisée. De cette analyse, de nombreux algorithmes de planification centralisée ont vu le jour. Parmi eux, figure point-based incremental pruning (PBIP), l'algorithme approximatif pour la résolution des processus de Markov décentralisés, le plus efficace à ce jour.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019 / La compréhension du lien entre les caractéristiques génomiques d’un individu, le génotype, et son état biologique, le phénotype, est un élément essentiel au développement d’une médecine personnalisée où les traitements sont adaptés à chacun. Elle permet notamment d’anticiper des maladies, d’estimer la réponse à des traitements et même d’identifier de nouvelles cibles pharmaceutiques. L’apprentissage automatique est une science visant à développer des algorithmes capables d’apprendre à partir d’exemples. Ces algorithmes peuvent être utilisés pour produire des modèles qui estiment des phénotypes à partir de génotypes, lesquels peuvent ensuite être étudiés pour élucider les mécanismes biologiques sous-jacents aux phénotypes. Toutefois, l’utilisation d’algorithmes d’apprentissage dans ce contexte pose d’importants défis algorithmiques et théoriques. La haute dimensionnalité des données génomiques et la petite taille des échantillons de données peuvent mener au surapprentissage; le volume des données requiert des algorithmes adaptés qui limitent leur utilisation des ressources computationnelles; et finalement, les modèles obtenus doivent pouvoir être interprétés par des experts du domaine, ce qui n’est pas toujours possible. Cette thèse présente des algorithmes d’apprentissage produisant des modèles interprétables pour la prédiction de phénotypes à partir de génotypes. En premier lieu, nous explorons la prédiction de phénotypes discrets à l’aide d’algorithmes à base de règles. Nous proposons de nouvelles implémentations hautement optimisées et des garanties de généralisation adaptées aux données génomiques. En second lieu, nous nous intéressons à un problème plus théorique, soit la régression par intervalles, et nous proposons deux nouveaux algorithmes d’apprentissage, dont un à base de règles. Finalement, nous montrons que ce type de régression peut être utilisé pour prédire des phénotypes continus et que ceci mène à des modèles plus précis que ceux des méthodes conventionnelles en présence de données censurées ou bruitées. Le thème applicatif de cette thèse est la prédiction de la résistance aux antibiotiques, un problème de santé publique d’envergure mondiale. Nous démontrons que nos algorithmes peuvent servir à prédire, de façon très précise, des phénotypes de résistance, tout en contribuant à en améliorer la compréhension. Ultimement, nos algorithmes pourront servir au développement d’outils permettant une meilleure utilisation des antibiotiques et un meilleur suivi épidémiologique, un élément clé de la solution à ce problème. / A thorough understanding of the relationship between the genomic characteristics of an individual (the genotype) and its biological state (the phenotype) is essential to personalized medicine, where treatments are tailored to each individual. This notably allows to anticipate diseases, estimate response to treatments, and even identify new pharmaceutical targets. Machine learning is a science that aims to develop algorithms that learn from examples. Such algorithms can be used to learn models that estimate phenotypes based on genotypes, which can then be studied to elucidate the biological mechanisms that underlie the phenotypes. Nonetheless, the application of machine learning in this context poses significant algorithmic and theoretical challenges. The high dimensionality of genomic data and the small size of data samples can lead to overfitting; the large volume of genomic data requires adapted algorithms that limit their use of computational resources; and importantly, the learned models must be interpretable by domain experts, which is not always possible. This thesis presents learning algorithms that produce interpretable models for the prediction of phenotypes based on genotypes. Firstly, we explore the prediction of discrete phenotypes using rule-based learning algorithms. We propose new implementations that are highly optimized and generalization guarantees that are adapted to genomic data. Secondly, we study a more theoretical problem, namely interval regression. We propose two new learning algorithms, one which is rule-based. Finally, we show that this type of regression can be used to predict continuous phenotypes and that this leads to models that are more accurate than those of conventional approaches in the presence of censored or noisy data. The overarching theme of this thesis is an application to the prediction of antibiotic resistance, a global public health problem of high significance. We demonstrate that our algorithms can be used to accurately predict resistance phenotypes and contribute to the improvement of their understanding. Ultimately, we expect that our algorithms will take part in the development of tools that will allow a better use of antibiotics and improved epidemiological surveillance, a key component of the solution to this problem.

La prise de décision dans un environnement partiellement observable est un sujet d'actualité en intelligence artificielle. Une façon d'aborder ce type de problème est d'utiliser un modèle mathématique. Notamment, les POMDPs (Partially Observable Markov Decision Process) ont fait l'objet de plusieurs recherches au cours des dernières années. Par contre, résoudre un POMDP est un problème très complexe et pour cette raison, le modèle n'a pas été utilisé abondamment. Notre objectif était de continuer les progrès ayant été réalisé lors des dernières années, avec l'espoir que nos travaux de recherches seront un pas de plus vers l'application des POMDPs dans des applications d'envergures. Dans un premier temps, nous avons développé un nouvel algorithme hors-ligne qui, sur des problèmes tests, est plus performant que les meilleurs algorithmes existants. La principale innovation vient du fait qu'il s'agit d'un algorithme stochastique alors que les algorithmes traditionnels sont déterministes. Dans un deuxième temps, nous pouvons également appliquer cet algorithme dans des environnements en-lignes. Lorsque ceux-ci revêtent une certaine particularité, notre algorithme est beaucoup plus performant que la compétition. Finalement, nous avons appliqué une version simplifiée de notre algorithme dans le cadre du projet Combat Identification du RDDC-Valcartier. / Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.

Ce mémoire présente une nouvelle méthode d'analyse des courbes de voltampérométrie cyclique. Cette méthode utilise deux algorithmes distincts afin de permettre la caractérisation automatique et précise des pics gaussiens d'oxydoréduction qui sont liés à la concentration des molécules en solution. En premier lieu, des améliorations significatives sont apportées à un algorithme de suppression de la courbe de fond qui fonctionne par approximation polynomiale itérative. Avec les améliorations proposées, l'algorithme isole les pics d'oxydoréduction à partir des mesures de voltampérométrie cyclique automatiquement. La variation de l'amplitude des pics en fonction de la concentration est alors mieux conservée et les erreurs d'estimation sont diminuées par rapport à l'algorithme initial. Ensuite, le développement d'un algorithme qui permet de caractériser des pics gaussiens basé sur l'algorithme de deuxième ordre MUSIC est présenté. Cet algorithme est adapté de manière à caractériser avec une haute précision le nombre, la position, la largeur et l'amplitude des pics d'oxydoréduction. Finalement, les performances de cet algorithme sont comparées à celles d'autres algorithmes similaires à l'aide de courbes simulées et expérimentales. L'algorithme proposé permet une meilleure caractérisation des pics sans chevauchement ainsi que des pics déformés. Il permet aussi de diminuer la fréquence des fausses détections et d'obtenir une haute précision de la mesure de position, et ce même lorsque les signaux sont bruités. / This master's thesis describes a new method for analyzing cyclic voltammetry curves for an efficient peak detection and automatic baseline substraction. This method uses two distinct algorithms for a precise characterization of Gaussian redox peaks which are correlated with molecules' concentration in a solution. First, significant improvements are made to an existing algorithm that uses iterative polynomial approximations to suppress the baseline automatically from the voltammetric curves. With these enhancements, the algorithm extracts redox peaks from cyclic voltammetry measurements automatically and allows a better representation of the variation of peak's amplitude according to concentration. In addition, the approximation errors are reduced compared to the initial algorithm. Then, the development of an algorithm for characterizing Gaussian peaks based on the MUSIC second-order algorithm is presented. This algorithm is adapted to characterize the number, position, width and amplitude of redox peaks with high accuracy. Finally, the performances of this algorithm are compared with those of other similar algorithms using simulated and experimental curves. The suggested algorithm leads to a better characterization of non-overlapping peaks as well as distorted peaks. It also reduces the frequency of false detections and allows the precise measurement of peaks' positions in noisy signals.

Un bloc de bits est équilibré s’il contient un nombre de bits à 0 égal à celui des bits à 1. Les codes équilibrés (Balanced Codes, BC) sont largement appliqués dans plusieurs domaines. Par exemple, ils sont utilisés pour réduire le bruit dans les systèmes VLSI (Tabor, 1990). Dans le domaine de la télécommunication, ils sont utilisés dans la synchronisation et la transmission des données par fibre optique (Bergmann et al., 1986). Leur utilisation dans le domaine de l’identification par radiofréquence (RFID) permet d’augmenter les taux de transfert de données via les canaux RFID (Durgin, 2015). Étant donnée leur importance, plusieurs travaux de recherche ont été menés pour optimiser leur construction. Knuth fut le premier à trouver une méthode simple et rapide pour l’élaboration des codes équilibrés (Knuth, 1986). Il a introduit un algorithme très simple pour générer les codes équilibrés sans l’utilisation des tables de correspondance. Cependant, cet algorithme ajoute presque le double de la redondance minimale nécessaire pour la création des codes équilibrés. Une partie de cette redondance est due à la multiplicité d’encodage (ME) de cet algorithme. Plusieurs chercheurs ont essayé de réduire la redondance de l’algorithme de Knuth (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). Dans les derniers travaux de Al-Rababa’a et al. (2013), les auteurs ont réussi à éliminer la redondance créée par ME et pourtant un écart par rapport au seuil minimal subsiste. Ce travail présente une alternative à l’algorithme de Knuth pour créer les codes équilibrés sans surplus de redondance. Nous proposons un algorithme nommé « Pacman » ¹ basé sur les permutations et les nombres entiers à précision limitée. En effet, le processus de codage de cet algorithme peut être assimilé à un Pacman qui consomme et produit des blocs d’informations d’une façon cyclique. Au cours de ce travail, nous allons montrer analytiquement et expérimentalement que la redondance introduite par notre technique est particulièrement faible, que les résultats sont nettement meilleurs que ceux des travaux antérieurs et que les complexités temporelle et spatiale utilisées sont linéaires. ¹. Inspiré de la marque de commerce PAC-MAN de l’entreprise BANDAI NAMCO. / A block of m bits is said to be balanced if it contains an equal number of zeros and ones. Note that m has to be an even number. Balanced codes (BC) have applications in several domains. For example, they are used to reduce noise in VLSI systems (Tabor, 1990). In telecommunication, they are used in synchronization and data transmission by optical fibers (Bergmann et al., 1986). Their use in the field of radio frequency identification (RFID) can help to boost data transfer rate through RFID channels (Durgin, 2015). Given their importance, several research works have been carried out to optimize their construction. Knuth was the first to find a simple and fast method to create balanced codes (Knuth, 1986). He introduced a very simple algorithm to generate balanced codes without using lookup tables. However, Knuth’s balanced codes incur redundancy that is almost twice the one attested by the lower bound. A part of this redundancy is due to the multiplicity of encoding (ME) of this algorithm. Improvements to the Knuth’s algorithm are discussed in several research works (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). In the last one (Al-Rababa’a et al., 2013), redundancy created by ME was eliminated and yet there is still some gap that needs to be closed. This work presents an alternative to Knuth’s algorithm for creating balanced codes without unwanted redundancy overhead. We propose an algorithm called "Pacman" ² that is based on permutations and limited-precision integers. Indeed, the coding process of this algorithm can be assimilated to a special Pacman that consumes and produces pills of information in a cyclical manner. In the presented work, we prove analytically and experimentally that our algorithm closes the mentioned redundancy gap while preserving a favorable compromise between calculation speed and memory consumption. ². Inspired by the trademark PAC-MAN of BANDAI NAMCO.