TIPE sur l'IA et la recherche opérationnelle

Brainstorming

a marqué ce sujet comme résolu.

Salut tout le monde !

Cette année je dois commencer à préparer mon TIPE en vue de le passer l'année prochaine. Cette année (au mois de Juin) il fera simplement l'objet d'une évaluation interne à l'établissement, mais la possibilité de le poursuivre pour l'année suivante (ou de changer de sujet) est laissée à mon choix.

Cette année le thème est « Structures : organisation, complexité, dynamique »

C'est, comme chaque année, assez vague et libre à l'interprétation.

Je viens ici pour voir si vous n'aviez pas quelques idées à me proposer sur lesquelles je pourrais partir.
J'en ai pas mal, mais la présentation ne dure que 10mn, et il faut bien faire un choix et s'y tenir à un moment.

Je pensais à faire quelque chose sur l'intelligence artificielle et la recherche opérationnelle :

  • PVC avec les algorithmes génétiques, ou les algorithmes des colonies de fourmis. Mais j'ai peur que ce soit trop "académique", à moins de tenter une hybridation de différentes méta-heuristiques (puis de les comparer), ça semble en vogue.
  • Apprentissage et prédiction au moyen d'un réseau bayésien. Mais n'ayant aucune connaissance en probabilités, j'ignore si vous le me conseillez (dans l’éventualité où je serais prêt à les acquérir, sachant que j'ai un niveau L1 en math). Et puis il faut trouer un sujet d'application sympa.
  • Une IA basée sur les méthodes de Monte Carlo (UCT) pour le jeu de Hex : là le gros du boulot est déjà fait donc j'ai peur que ce soit un peu ennuyant et moins instructif.
  • Une IA plus conventionnelle : alpha-beta, etc… reste à trouver un jeu sympa, j'avais pensé à l’échiquier de Machiavel pour l'aspect stratégique ET coopératif. Mais là il se peut que ça devienne brutalement trop difficile et trop long (ne serait-ce que pour exposer les règles du jeu).
  • Résolution de problème d'ordonnancement à l'aide de méta-heuristiques
  • IA combinant différentes méthodes pour jouer à des jeux (en version très simplifiée) du type Civilisation (temps discret, espace discret, déterministe), mais une fois encore peut-être trop ambitieux.
  • Réseau de neurones artificiels : là c'est du fantasme puisque j'y comprend rien de toutes façons.

Je sais que l'IA lorsque c'est mal traité ça devient vite le sujet casse-gueule qui tourne trop vite "exposé scolaire wikipédien" ou implémentation bébête d'un truc académique (genre min-max sur Morpion ou A* sur Taquin).

Vous auriez des suggestions de problèmes qui feraient un sujet satisfaisant, à la portée d'un étudiant (en temps de travail comme en niveau mathématique) et qui en même temps ne soit pas trop académique, un peu original (ou en tout cas faisant appel à des développements récents n'ayant pas intégrés tout les manuels) ?

Merci !

+0 -0

Je ne connais pas les principes de TIPE, mais un alpha-beta me semble beaucoup trop simple pour un TIPE, même s'il est appliqué à un autre jeu. Ca reste un algorithme qui déjà été revisité des centaines de fois et donc n'apporte peu d'intérêt, sinon être capable d'évaluer une configuration de jeu, tâche compliqué comme pour le jeu de Go.

Concernant les réseaux de neuronnes, je sais qu'en implémentant un perceptron, c'est assez facile de faire quelque chose de puissant : reconnaissance de caractères par exemple. Malheureusement je n'ai pas de documentation sur le sujet, donc renseigne-toi.

Je connais beaucoup moins les méthodes de Monte-Carlo, mais comme l'algorithme d'alpha-beta, tu risques de tomber sur du classique qui va t'apporter assez peu.

Maintenant, sur les heuristiques et méta-heuristiques, il y a beaucoup de choses et de nombreuses pistes à explorer. Mais là aussi, il peut-être dangereux de recoder un algorithme sur un problème classique.

En ce qui concerne la recherche opérationnelle, tu vas rapidement tomber sur le simplexe qui a été vu et revu. Pour aller plus loin, cela va te demander beaucoup de travail.

Je ne connais pas du tous le TIPE, donc ce qui va suivre sont des suggestions peut-être foireuses :

  • Si tu choisis les heuristiques et méta-heuristiques (MH), trouve un problème original sur lequel tu vas appliquer tes algorithmes. Ne te cantonne pas à une MH, ainsi tu pourras faire des comparaisons. En particulier, tu peux étendre ta recherche aux SAT-solveurs

-Si tu choisis la RO, c'est un peu plus compliqué à mon avis. Tu vas certainement coder des méthodes déjà connues à des problèmes assez théoriques. Pour avoir quelque chose d'intéressant, ça risque de te demander beaucoup d'effort

  • Tu peux potentiellement étendre ta recherche aux jeux combinatoires. Regarde les livres de Conway sur le sujet "Winning ways for you mathematical plays". Sinon cherche le jeu "Hackenbush" c'est assez rigolo, tu vas rapidement tomber sur les nombres surréels.

Voici d'autres pistes qui pourraient t'intéresser :

  • L'intelligence artificielle ne concerne pas que les jeux tour par tour. Des chercheurs s'intéressent notamment à Starcraft par le biais d'une API : BWAPI. C'est très difficile d'avoir des IAs intéressantes et ça fait l'objet de nombreux papiers. D'ailleurs il exisite des concours pour ces IAs (par exemple AIIDE). Il y a certainement beaucoup de choses à faire sur le sujet (créer une IA cependant c'est trop dur je pense).

  • Un problème intéressant qui n'a toujours pas été résolu s'appelle Eternity II. Il existe de nombreuses façon d'aborder ce problème, SAT-Solver, MH par exemple. Ca peut être intéressant de voir s'il est possible de trouver des nouvelles approches pour ce problème. L'étude d'un tel problème par de MH peut t'amener à te poser différentes questions de recherches actuelles : Tunner une MH (optimiser les paramètres), visualisation de l'espace de recherche.

  • Hanabi est un jeu de société coopératifs aux règles assez simples. Concevoir une IA pour ce jeu peut-être intéressant (notamment dans la version difficile). Quelles sont les déductions que tu puisses faire ? Quelles sont les heuristiques à mettre en place etc…

  • Des gens s'intéressent à faire des IA génériques, c'est à dire qu'elles ne sont pas faites pour un jeu spécifique mais elle doivent s'adapter en fonction. Cela donne lieu à des compétition : http://www.gvgai.net/ . Le sujet est plutôt récent donc il y a certainement des choses intéressantes à faire.

Voilà, ça te donne d'autres pistes à regarder. Si jamais Eternity II ça te tente, j'ai eu l'occasion de bosser rapidement dessus, donc contacte-moi si tu veux en savoir plus.

+0 -0

Réseau de neurones artificiels : là c'est du fantasme puisque j'y comprend rien de toutes façons.

C'est dommage car c'est probablement un bon sujet. Bon je ne connais pas les TIPE mais ce sujet a l'avantage de permettre facilement une notion d’interdisciplinarité (en comparant neurones artificiels et biologiques), le titre du TIPE colle parfaitement (un réseau de neurones est structuré, peut résoudre des problèmes complexes et on doit pouvoir rattacher la notion d'apprentissage au coté dynamique puisque le réseau va s'adapter aux données), c'est sympa a programmer et en même temps il y a un tas de libs qui peuvent permettre de servir de référence, certains problèmes se résolvent très efficacement avec les réseaux de neurones (comme la reconnaissance de texte manuscrit) et, enfin, si il y a eu une baisse d'interet dans les années 90, depuis 2005 et les articles de G. Hinton sur l'apprentissage par des machines de Boltzmann restreintes (et grâce à l'augmentation de la puissance de calcul disponible), le sujet est re-devenu largement à la mode et ce sont ces methodes qui aujourd'hui donnent les meilleurs résultats dans beaucoup de domaine. Alors sur ces sujets je pense pas qu'il serait question de les re-implémenter mais ça peut faire une belle partie "perspective" en expliquant avec les mains comment ils fonctionnent.

C'est quoi que tu ne comprend pas dans les RN ?

+0 -0

C'est quoi que tu ne comprend pas dans les RN ?

Le "pourquoi ça marche" avant tout.
Si on me donnait un problème, je serais incapable de coder le réseau de neurone adapté pour le résoudre. Quelle topologie choisir ? Quels paramètres choisir ? Quelles entrées ? Quelle sortie ?

+0 -0

Quelle topologie choisir ? Quels paramètres choisir ? Quelles entrées ? Quelle sortie ?

Le choix de la topologie est toujours un problème ouvert en réalité. Les entrées et sorties dépendent du domaine mais il y a en général des possibilités logiques. Le reste est ouvert et il n'y a pas de réponse général. Pour le paramétrage par contre on utilise généralement un apprentissage.

+0 -0

Je pense que les RN sont un mauvais choix car la theorie derriere va etre au dela ce qui est aborde en CPGE je pense, et que tu n'as pas trop le temps malheureusement pour t'y mettre serieusement. De fait, zapper la theorie va t'etre probablement repproche pour un TIPE.

EDIT: Quoique si tu te sens a l'aise pour faire (je veux dire manipuler un peu et comprendre) un peu de calcul aux derivees partielles, ca se tente.

+0 -0

Je pensais à faire quelque chose sur l'intelligence artificielle et la recherche opérationnelle :

Algue-Rythme

Le problème des sujets sur "l'intelligence artificielle" c'est qu'ils cristallisent pas mal de fantasmes, et que tu ne sais pas trop comment ton jury va réagir. Les réseaux de neurones, en particulier, sont à mon avis un très mauvais sujet : pas parce que les maths derrière sont compliquées (ça, tu as le temps de t'y intéresser) mais parce que c'est un sujet qui a bénéficié d'un engouement et d'une exposition très exagérés.

Concrètement, tout ce qu'on a c'est un modèle de calcul assez imprévisible, dont on ne sait pas bien comment il fonctionne, et qui a tout basé sur le marketing ("ça fonctionne comme dans le cerveau humain donc c'est forcément de l'intelligence !"). Je ne suis pas en train de dire que c'est un modèle qui ne fonctionne pas dans la pratique, hein ; je dis juste que c'est un sujet qui demande beaucoup de recul scientifique, un recul que toi et tes profs n'ont pas.

Quitte à t'intéresser à des techniques à la mode et qui marchent bien, regarde les machines à vecteurs de support, un modèle avec une théorie mathématique solide (et pas des espèces de comparaisons fantasmées avec une conception du cerveau humain qui ferait pâlir n'importe quel biologiste).

Cela étant dit : je remarque que, en matière d'apprentissage, tu mentionnes exclusivement des techniques d'apprentissage supervisé. As-tu envisagé l'apprentissage non-supervisé, par exemple le clustering ou les arbres de décision ? Concrètement, les méthodes de fouille de données sont parfois un peu ad-hoc et rarement aussi efficaces que les méthodes supervisées, mais au moins on comprend bien comment elles fonctionnent, et les théorèmes derrière sont clairs (et à la limite du programme de spé, comme attendu pour un TIPE).

(Edit : ça dépend un peu des méthodes, évidemment. Toutes ne sont pas aussi jolies et/ou efficaces.)

Hanabi est un jeu de société coopératifs aux règles assez simples. Concevoir une IA pour ce jeu peut-être intéressant (notamment dans la version difficile). Quelles sont les déductions que tu puisses faire ? Quelles sont les heuristiques à mettre en place etc…

+1 pour Hanabi, qui mérite vraiment que l'on s'y intéresse. Si tu choisis ce sujet, j'ai le formalisme théorique et l'interlocuteur idéaux pour travailler (n'oublie pas que c'est fortement conseillé d'avoir des contacts sérieux pour ton TIPE).

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte