Les livres anglaisConsultez tous les livres

Écrit par Marco Dorigo, fondateur des algorithmes de colonie de fourmis, et Thomas Stützle, expert en optimisation, ce livre est une des références dans le domaine des algorithmes de colonie de fourmis dont il donne un aperçu très complet tout en restant accessible pour les néophytes. De bonnes notions en mathématiques discrètes seront néanmoins nécessaires pour bien comprendre certains passages, l'attachement à la formalisation mathématique étant une des caractéristiques de l'ouvrage.

Le premier chapitre met en exergue les liens entre fourmis réelles et artificielles en s'appuyant sur les interactions entre entomologie, mathématiques et informatique. Le deuxième chapitre situe les algorithmes de colonie de fourmis par rapport aux autres métaheuristiques ainsi qu'aux différentes catégories de problèmes auxquels ils s'appliquent, en l'occurrence des problèmes classiques d'optimisation combinatoire, fournissant ainsi aux lecteurs une superbe vue d'ensemble. Le troisième chapitre présente un exemple simple et détaillé d'application des algorithmes de colonie de fourmis au problème du voyageur de commerce ; diverses variantes de l'algorithme sont exposées et des ajouts majeurs, nommément la parallélisation et la recherche locale, sont introduits.

Ces trois premiers chapitres se lisent facilement et avec le chapitre de conclusion donnent les idées principales. Les autres chapitres sont essentiellement des chapitres d'approfondissement. Le quatrième chapitre explore la théorie sous-jacente aux algorithmes de colonie de fourmis, en détaillant entre autres choses les preuves de convergence et en introduisant le concept de recherche par modèle, par opposition à la recherche par solutions. Il n'existe cependant aucune preuve mathématique sur les vitesses de convergence, absence malheureusement assez répandue dans le monde des métaheuristiques en dépit des tentatives. Le cinquième chapitre est un catalogue de problèmes NP-difficiles auxquels ont été appliqués les algorithmes de colonie de fourmis : la mise en place de l'algorithme, autrement dit la définition de la correspondance entre le problème traité et la métaheuristique, puis les résultats sont présentés pour chaque problème. Le sixième chapitre se concentre sur un problème précis, le routage de données, et se penche sur les similarités avec l'apprentissage par renforcement et la méthode de Monte-Carlo, comparaison très pertinente. Les auteurs terminent sur un chapitre de conclusions et perspectives très diverses allant de la parallélisation algorithmique à la division du travail au sein des agents computationnels inspirée par la nature.

En conclusion, ce livre mérite tout à fait son titre de référence du domaine. Ses explications détaillées, aussi bien expérimentales que théoriques, ainsi que ses nombreuses ouvertures rendent sa lecture palpitante. Chaque chapitre s'achève par une très courte bibliographie et des exercices orientés informatique ou mathématiques. À noter que l'ouvrage date toutefois de 2004, ce qui est ancien étant donné la vitesse d'évolution de la recherche dans le domaine des métaheuristiques : il faut donc l'utiliser pour acquérir des bases solides et non comme un état de l'art exhaustif de la recherche actuelle.

Ce livre est une excellente introduction à la programmation génétique. En seulement 150 pages sans compter la bibliographie fournie, il offre une vue complète du domaine et se lit très facilement.

Après avoir présenté les bases de la programmation génétique, les auteurs exposent dans un chapitre entier un exemple simple pour illustrer concrètement le déroulement d'un tel algorithme. Les concepts avancés sont ensuite présentés de façon assez développée pour pouvoir bien les comprendre, mais pas trop pour ne pas noyer le lecteur dans les détails, le livre étant avant tout une introduction.

Chose intéressante, le livre propose également un chapitre théorique, ce qui est appréciable car la programmation génétique est souvent abordée sous un angle empirique, à défaut d'un modèle mathématique sous-jacent très développé, nonobstant les tentatives. Cette approche théorique permet en particulier de donner une piste d'explication mathématique des méthodes pour contrôler le phénomène de bloat, phénomène correspondant à l'augmentation de la taille du code des solutions sans amélioration de leur fitness, ce qui constitue un des problèmes majeurs de la programmation génétique à l'heure actuelle. Les auteurs poursuivent en donnant un aperçu synoptique des applications de la programmation génétique, ce qui permet de voir concrètement dans quels domaines elle a été mise en œuvre.

Le pénultième chapitre est consacré aux conseils pratiques pour mettre en place et mener à bien des expérimentations. C'est un concentré de l'expérience des auteurs, qu'il sera très utile d'avoir sous la main surtout lors des premières expérimentations. Enfin, les auteurs concluent l'ouvrage par une liste de ressources ainsi qu'un exemple de code source implémentant une expérimentation de programmation génétique.

Je conseille donc ce livre à toute personne souhaitant une introduction rapide ou une révision sur la programmation génétique. À noter que, contrairement à d'autres ouvrages tels Essentials of Metaheuristics et Introduction to Evolutionary Computing, ce livre ne permet pas de situer la programmation génétique par rapport aux autres algorithmes d'optimisation, mais se concentre exclusivement sur la programmation génétique. Également, aucun exercice n'est proposé.

Le livre est téléchargeable gratuitement à l'adresse http://www.gp-field-guide.org.uk (licence CC-BY-NC-ND).

3 commentaires

Ce livre était à l'origine une compilation de notes de cours pour des étudiants au niveau licence. Son auteur, Sean Luke, chercheur et professeur à l'Université George Mason, a décidé de le publier sous licence CC-BY-ND, donc disponible gratuitement ici afin de le rendre accessible au plus grand nombre. Sean Luke est également un des auteurs de ECJ, une bibliothèque open source parmi les plus utilisées pour les algorithmes évolutionnistes en Java : le livre peut donc être considéré comme son pendant théorique.

Comme le titre l'indique, le livre traite des métaheuristiques, en se focalisant sur les algorithmes évolutionnistes. Une des caractéristiques appréciables du livre réside dans le fait que l'auteur explique très clairement l'enchaînement et les liens entre les différentes métaheuristiques, en soulignant notamment leurs limites ayant conduit à l'élaboration de nouvelles métaheuristiques, ce qui permet au lecteur de sentir l'évolution de la recherche dans ce domaine. Il montre ainsi l'enchaînement entre l'algorithme du gradient, le recuit simulé, la recherche tabou, les algorithmes évolutionnistes, l'optimisation par essaims particulaires, GRASP et l'algorithme de colonies de fourmis. L'avant-dernier chapitre introduit à l'optimisation de stratégies (policy optimization), en présentant entre autres l'apprentissage par renforcement et les learning classifier systems. Le dernier chapitre intitulé "Miscellany" est une mine d'or contenant des conseils très importants et probablement pas assez respectés sur la méthodologie à suivre pour conduire des expériences ainsi qu'un ensemble de tests usuels pour évaluer une métaheuristique, puis se conclut sur une liste de ressources très utiles (sites Web, livres, librairies, conférences, mailing lists, etc.) pour trouver davantage d'informations.

Chaque algorithme est accompagné d'un pseudocode commenté, soulignant par exemple la particularité de l'algorithme au regard des algorithmes précédents. Les 222 pages du livre contiennent 135 pseudocodes, ce qui montre bien l'accent mis sur l'explication concrète des algorithmes en plus des considérations intuitives ou théoriques. Le livre propose également plus de 70 figures qui permettent de mieux comprendre les algorithmes. Le ton général du livre est direct et les phrases sont formulées de façon très accessible. Pour chaque chapitre, les dépendances avec les chapitres précédents sont indiquées. Tous ces éléments rendent le livre facile et agréable à lire. À noter que le livre ne contient pas d'exercice et ne présente que peu d'applications hormis les exemples abstraits : il faudra donc utiliser ECJ ou une autre bibliothèque pour mettre en œuvre les algorithmes expliqués dans le livre. Le guide d'utilisateur de ECJ est complet et traite sous l'angle technique de la quasi-totalité des concepts du livre touchant aux algorithmes évolutionnistes.

Je conseille donc ce livre à toute personne souhaitant une introduction rapide ou une révision sur les métaheuristiques.

3 commentaires

Dans ce livre, l'auteur et chercheur en intelligence artificielle Moshe Sipper présente un état de l'art de la programmation génétique appliquée aux jeux, domaine dans lequel l'auteur et son groupe de recherche ont gagné de nombreuses récompenses. Loin de réduire l'ouvrage à une simple énumération de résultats, il se concentre sur certains jeux qu'il a personnellement étudiés. À travers ces études de cas, il a réussi à structurer le livre de manière à montrer une progression dans l'utilisation de la programmation génétique : après avoir commencé à l'utiliser en tant que générateur et optimisateur d'heuristique, il l'applique directement aux algorithmes de recherche, tout en introduisant les notions de coévolution ainsi que d'évolution en îles asynchrones.

• les jeux de société : une variante du jeu de dames (lose checkers), les échecs et le backgammon ;
• les jeux de simulation : Robocode et le jeu de course RARS ;
• les casse-têtes : Rush Hour et FreeCell.

Les résultats présentés sont palpitants car hautement compétitifs avec les humains ainsi que les bots existants. Les solutions sont analysées en profondeur, notamment pour essayer d'entrevoir si l'évolution a fait apparaître des phénomènes d'émergence parmi les individus évolués. Une particularité du livre est son attachement à souligner les liens entre les algorithmes évolutionnistes et les principes de biologie moléculaire afin d'acquérir une compréhension plus intime de l'évolution. Tout au long de l'ouvrage, une myriade de conseils précieux sont donnés sur l'utilisation de la programmation génétique.

Bien que l'auteur aurait pu aisément faire publier le livre chez un éditeur classique tel Springer, il a fait le choix de la générosité et a décidé de rendre le livre téléchargeable gratuitement à l'adresse http://www.moshesipper.com/etw (licence CC-BY-ND).

1 commentaire

Utilisé par plus d'une centaine de cours dans le monde et disponible gratuitement en ligne à l'adresse http://www.nltk.org/book (licence CC BY-NC-ND), ce livre offre une excellente introduction au traitement automatique des langues naturelles en expliquant les théories par des exemples concrets d'implémentation. Il se veut donc une introduction pratique au domaine, par opposition à une introduction purement théorique. Chaque chapitre du livre se termine par une série d'exercices classés par ordre de difficulté, mais malheureusement non corrigés.

La particularité principale du livre est qu'il présente de nombreux exemples de code, en se basant sur la bibliothèque open-source et gratuite NLTK (http://www.nltk.org) écrite en Python par notamment les auteurs de ce livre. Très bien documentée, la bibliothèque NLTK offre de nombreuses fonctionnalités de traitement des langues (analyse lexicale, étiquetage grammatical, analyse syntaxique, etc.) tout en interfaçant aussi bien des bases de données tel WordNet que des bibliothèques et logiciels tiers tels l'étiqueteur grammatical Stanford Tagger et le prouveur automatisé Prover9. Un grand nombre de corpus est également disponible via NLTK, ce qui est très appréciable pour mettre en œuvre des processus d'entraînement ainsi que pour réaliser des tests, notamment des tests de performance. Comme le livre présente les nombreuses facettes du traitement automatique des langues naturelles, il parcourt au travers de ses exemples une grande partie des fonctionnalités de NLTK.

La limite principale de la bibliothèque NLTK est les performances de Python en termes de vitesse de calcul. L'utilisation de Python permet toutefois au lecteur de ne pas être trop gêné par la barrière du langage, Python étant à ce jour sans conteste un des langages les plus simples d'accès. Pour ceux n'ayant aucune ou peu d'expérience en Python, certaines sections du livre sont dédiées uniquement à l'explication du langage Python, ce qui permet de rendre l'ouvrage accessible à tout public.

Néanmoins, bien que donnant un aperçu excellent et concret de l'ensemble du traitement automatique des langues naturelles, le focus du livre sur les exemples en Python fait que mécaniquement le livre consacre moins de place aux considérations théoriques. En ce sens, il est un complément idéal au livre de référence Speech and Language Processing (écrit par Daniel Jurafsky et James H. Martin) dont l'approche est beaucoup plus théorique.

Ce livre sur NLTK est réellement bien écrit, il n'est pas nécessaire d'avoir une expérience en traitement automatique du langage pour pouvoir aborder cet ouvrage, il vous apprendra tout ce dont vous avez besoin pour comprendre chaque chapitre. La seule obligation est d'avoir une connaissance du langage Python.

Les exemples sont non seulement simples, mais aussi très utiles, car ce sont des choses dont on pourrait avoir besoin dans une application. J'ai principalement aimé les chapitres sur les extractions d'entités nommées, l'apprentissage pour la création d'un classifieur et l'analyse du sens d'une phrase qui sont particulièrement bien faits et expliqués.

La seule remarque que je ferais est le manque de détails sur toutes les possibilités de création et d'utilisation d'une grammaire via les expressions régulières NLTK ou non.

Ce livre est une des références pour s'initier aux algorithmes évolutionnistes : assez court (à peine 300 pages facilement lisibles) et bien conçu pour une première approche du domaine sans avoir à y investir une quantité de temps considérable, tout en étant plutôt complet et sans se perdre dans des détails inutiles, ce qui donne au lecteur un nombre important de pistes de réflexion essentielles pour une bonne compréhension des différentes problématiques rencontrées le plus souvent dans le domaine.

Il est aussi un des premiers ouvrages présentant une vue d'ensemble sur l'évolution artificielle (EA) et il contient notamment les dernières nouveautés du domaine. Les chapitres alternent introductions théoriques, exemples, algorithmes et exercices, et même si les fondements théoriques ne sont pas négligés, l'accent est davantage mis sur la mise en oeuvre concrète des algorithmes et techniques d'évolution artificielle.

Bref, que ce soit pour découvrir le domaine ou se remettre les idées-clefs en mémoire, je conseille vivement la lecture de ce livre ! Pour les enseignants, des supports de présentation sont disponibles sur le site officiel.

Seul bémol notable, les exercices ne sont pas corrigés et certaines parties potentiellement intéressantes du site officiel sont toujours en construction ou ne sont pas terminées.

Tout d'abord, après avoir présenté dans les grandes lignes le fonctionnement ainsi que les caractéristiques d'un algorithme évolutionniste (chapitres 1 et 2), le livre se penche sur ses quatre variantes usuelles : algorithmes génétiques, stratégies d'évolution, programmation évolutionniste et programmation génétique (chapitres 3 à 6).

• les LCS (Learning Classifier System - chapitre 7), qui sont un système d'apprentissage automatique basé sur le concept d'ensemble de règles conditions-actions et qui permettent d'introduire la notion de coopération parmi les individus d'une même population, contrairement aux algorithmes évolutionnistes classiques dans lesquels les individus sont simplement en compétition. ZCS et XCS sont des variantes ;
• le "parameter control" (chapitre 8), dont l'objectif est d'adapter certains paramètres structurants des algorithmes évolutionnistes, telles la taille de la population ou la probabilité des mutations/croisements, au cours de l'exécution de l'algorithme, contrairement au "parameter tuning" utilisé habituellement, consistant à fixer ces paramètres au début de l'exécution de l'algorithme sans pouvoir les modifier après, ce qui rend l'algorithme beaucoup moins performant ;
• le maintien d'une certaine diversité au sein de la population (chapitre 9), afin de faire face à la convergence vers un optimum local (genetic drift) souvent constaté, à l'instar de la sélection naturelle qui a vu se former des sous-groupes grâce aux contraintes géographiques. On peut de cette manière trouver autant d'optima locaux que de sous-groupes, permettant ainsi d'obtenir de meilleurs résultats sur les problèmes multimodaux en se rapprochant ainsi de l'optimum global ;
• le multiobjectif (chapitre 9), qui repose sur le concept de dominance au sens de Pareto : beaucoup de problèmes ont en effet plusieurs objectifs, les scalariser en un seul objectif comporte des inconvénients, et les résultats montrent que les MOEA (MultiObjective Evoluationary Algorithms) sont en général les meilleurs algorithmes pour résoudre des MOP (MultiObjective Problems) ;
• les algorithmes mémétiques (chapitre 10), qui permettent d'effectuer des améliorations (local search) non génétiques propres à un seul individu, améliorations se basant sur des connaissances expertes spécifiques au problème, en faisant attention à maintenir une certaine diversité au sein de la population. Les résultats ainsi obtenus par rapport à l'EA classique sont généralement meilleurs sur le problème étudié, mais moins bons pour la plupart des autres problèmes.

En troisième partie, les auteurs exposent quelques bases de la théorie sous-jacente à l'EA (chapitre 11), puis expliquent comment y inclure des contraintes, comme par exemple en définissant des pénalités dans la fitness fonction (chapitre 12). Ils présentent également des formes d'évolution (chapitre 13) basées sur la coévolution interactive ou compétitive, formes plus proches de la sélection naturelle où les espèces évoluent ensemble et les critères de sélection sont relatifs (telle l'opposition proies vs prédateurs).

Les auteurs concluent sur les bonnes pratiques de mesure de performance d'une EA (chapitre 14), soulignent que le plus important lors de l'utilisation d'une EA est de trouver une bonne représentation ainsi qu'un choix d'opérateurs de variation et de sélection judicieux, et donnent des pistes de réflexion non étudiées dans le livre, tels les colonies de fourmis ou les systèmes immunitaires artificiels.

Cet ouvrage reprend l'intégralité de la thèse de Chris Okasaki avec tous ses points forts, à commencer par les nouvelles techniques algorithmiques avancées (eliminated amortization, lazy rebuilding, data-structural bootstrapping, implicit recursive slowdown). Les systèmes de numération y sont utilisés comme des moules pour fabriquer des TADs sur le modèle des opérations élémentaires d'incrémentation et d'addition. Le système de typage est poussé aussi loin que possible avec les nested data types (polymorphic recursion), les modules paramétrés et les modules paramétrés récursifs.
En plus du contenu de la thèse qui fait déjà autorité, la valeur ajoutée de ce livre réside dans :

- une introduction à la persistence et au path-copying
- un rappel sur l'implantation des structures de données élémentaires (listes,piles,queues,arbres binaire de recherche, arbres rouge-noir)
- des exercices qui explorent des alternatives connues (arbres de Arne Andersson,...) ou des variantes du mécanisme de mise à jour (batched-rebuilding)
- un répertoire d'implantations des structures de tas, assez consistant (leftist heaps, pairing heaps, binomial heap, skew binomial heap, structural-bootstrapped skew binomial heap) sans être exhaustif (il manque le Braun heap et le maxiphobic heap)

En bref il s'agit d'une référence à posséder absolument.
Un seul regret: l'ouvrage n'a pas la prétention d'être une bible. Il ne fait pas le tour complet du sujet puisque par exemple, ne sont pas abordés les thèmes suivants:

- le Finger-tree
- l'implantation efficace des graphes inductifs
- l'implantation efficace de l'Union-Find persistent

Cependant, pour les personnes intéressées, de la documentation sur ces sujets est facilement trouvable en ligne.