|
|
Les problèmes d'optimisation combinatoire, du domaine académique ou du monde réel, sont en majorité NP-difficiles. Leur résolution est donc toujours limitée par les capacités des ressources matérielles utilisées (puissance de calcul, mémoire).
Dans le cadre du projet national ACI-GRID "Défis en Optimisation Combinatoire sur Grilles", nous nous attachons à produire des prototypes de logiciels parallèles pour la résolution d'applications en Optimisation Combinatoire de très grande taille, au delà des limites actuelles. Ces prototypes doivent être capables d'exploiter au niveau applicatif, de manière transparente et efficace, les énormes capacités mémoire et calcul offertes par la globalisation des ressources informatiques commes les Grilles (grappes de grappes).
A cet effet, nous avons développé un environnement de programmation nommé ParadisEO (http://www.lifl.fr/~cahon/paradisEO/) (1, 2). Il s'agit d'une plate-forme logicielle dédiée à la conception de métaheuristiques hybrides et/ou coopératives dans un environnement parallèle et/ou distribué.
Cette plate-forme fait actuellement l'objet d'une intégration avec Athapascan 2 (http://www-id.imag.fr/Logiciels/ath1/) (3). Il s'agit d'une interface de programmation pour les applications parallèles permettant la construction distribuée et à la volée du flot de données associé à l'exécution d'un programme. Elle exploite efficacement les architectures de type grappe avec différents niveaux de parallélisme et contrôle l'espace mémoire requis. L'ordonnancement est géré de manière transparente, et dynamique pour l'utilisateur qui se base sur une sémantique indépendante de l'infra-structure de calcul et du nombre de ressources utilisées.
Nous couplerons prochainement ParadisEO avec la plate-forme BOB++ (http://www.prism.uvsq.fr/~blec/Research/BOBO/) (4) appliquée aux méthodes de résolution exactes de type parcours arborescent. Il est en effet montré que les solutions optimales trouvées par les méthodes exactes servent d'étalon pour mesurer l'efficacité des méthodes approchées tandis que ces dernières constituent d'excellentes bornes pour élaguer des branches des méthodes exactes, et ainsi réduire considérablement le temps de calcul. Parmi les problèmes applicatifs, nous nous intéressons dans ce projet essentiellement à la La radio-téléphonie mobile.
Bibliographie:
(1) "ParadisEO. A Framework for Parallel and Distributed Biologically Inspired Heuristics."
S. Cahon, E-G. Talbi and N. Melab,
Nature Inspired Distributed Computing Workshop, in IEEE IPDPS2003 (Int. Parallel and Distributed Processing Symposium),
Nice, France. April 2003.
(2) "ParadisEO. a Framework for the Flexible Design of Parallel and Distributed Hybrid Metaheuristics."
S. Cahon, N. Melab and E-G Talbi,
Special Issue on Parallel Computing,
Elsevier Science. A paraître fin 2003.
(3) "Athapascan 1: Interface genérique pour l'ordonnancement dans un environnement d'exécution
parallèle."
Cavalheiro, Gerson-Geraldo-Homrich,
Institut National Polytechnique de Grenoble, France
Thèse de doctorat en informatique,
Novembre 1999
(4) "BOB: une Plate-forme Unifiée de Développement pour les Algorithmes de type Branch-and-Bound".
Mohamed Benaichouche, Van-Dat Cung, Salah Dowaji, Bertrand Le cun, Thierry Mautor and Catherine Roucairol,
"Université de Versailles - Laboratoire PRiSM",
May 1995.
|
La métaheuristique d’Optimisation par Colonies de Fourmis (OCF) a fait l’objet de plusieurs travaux durant le
s dernières années. Quelques-uns d’entre eux portent sur la parallélisation de cet algorithme sur des a
rchitectures à passage de messages, mais peu de travaux ont été recensés sur des architectures à mémoire partagée.
Comme ces dernières deviennent de plus en plus populaires, il est intéressant de développer des algorithmes pouvant
s’exécuter sur de tels ordinateurs. Dans cette communication, nous présentons comment différentes stratégies de p
arallélisation de la métaheuristique OCF peuvent être implantées sur des architectures à mémoire partagée et nous comparons
la performance de celles-ci avec les approches à passage de messages retrouvées dans la littérature.
Le problème du Voyageur de Commerce (VC) étant utilisé dans la plupart des travaux de parallélisation de l’OCF, n
ous utilisons celui-ci afin de présenter une comparaison aussi équitable que possible.
L'implantation des algorithmes développés est effectuée avec OpenMP sur deux types d’ordinateurs à mémoire partagée,
c’est-à-dire la SGI Origin3800 (CC-NUMA) et la IBM SP3 (SMP).
|
Le problème Happynet est défini comme suit: Soit un graphe simple G non orienté avec des poids entiers $w_{vu}$ sur ses arêtes $vu \in E(G)$, trouver une fonction s : V(G) --> {-1,1} telle que $\forall v \in V(G)$: v soit heureux dans G, i.e. telle que $\sum_{u \in \Gamma(v)} s(v)s(u)w_{uv}$ >= 0. Il est facile de voir {Pap} que Happynet a toujours une solution, quelle que soit l'entrée. Cependant, on ne connait aucun algorithme polynomial pour ce problème qui est complet pour la classe PLS (voir {JPY} pour une définition). Dans cet article, nous présentons une heuristique pour trouver une solution approchée à une instance de Happynet , dans le sens que l'on s'intéresse au cas plus général où une partie des sommets est heureux.
A toute instance de Happynet : I , nous allons associer un jeu non-coopératif HappyGame(I) dont les joueurs correspondent aux sommets du graphe d'entrée, l'ensemble des stratégies pour chaque joueur $v$ est le ${\cal \Sigma}(v) = \{-1,1\}$ et la fonction de rémunération, la même pour tout joueur, est 1 avec une probabilité $p$ égale au pourcentage des sommets heureux (et 0 avec probabilité $1-p$), $s(v)$ étant la stratégie de $v$. Le résultat de HappyGame(I) correspond à une solution approchée de I.
Notre heuristique consiste en l'exécution répétée de HappyGame(I) par des automates de Tsetlin {Tse}, {Nar} qui décident leur stratégie selon leur état intérieur et changent ce dernier en fonction de leur rémunération. Il a été montré {Tse}, {Klei} que dans le cas des jeux de type ``majorité'' {Ste}, o\`u tout joueur $v$ a les mêmes deux stratégies possibles (disons, $\{-1,1\}$) et la probabilité de rémunération est une fonction $\phi$ du pourcentage des joueurs ayant choisi 1 vers [0,1] et $\exists \rho : \phi(\rho)\geq \frac{1}{2}$, il existe des classes des automates de Tsetlin qui, après un nombre suffisant de répétitions du jeu, finiront par ``converger'' vers un choix de stratégies maximisant $\phi$. Dans HappyGame(I) il est question de trouver un choix Pareto-optimum de stratégies, qui correspond à une solution de l'instance.
Dans les expérimentations que nous avons menées (avec deux familles d'automates de Tsetlin et plusieurs variantes de la fonction de rémunération) sur des instances aléatoires, on constate que le taux d'approximation pour les solutions obtenues se trouve entre $0,67$ et $0,9$, selon l'expérimentation, pour $n^2$ répétitions du jeu ($n$ étant la taille de l'instance). Il faut aussi noter l'interêt a priori d'une réalisation en parallèle de notre heuristique, étant donné que les automates peuvent agir en parallèle, et que par conséquent chaque exécution de HappyGame(I) peut se faire en temps constant si l'on dispose d'un nombre suffisant de processeurs.
Bibliographie:
{Nar} K.S. Narendra, M.A. Thathatchar, Learning automata: An Introduction.
Prentice Hall, 1989.
{Pap} C.H. Papadimitriou, Computational complexity. Addison-Wesley, 1994.
{JPY} D.S. Johnson, C.H. Papadimitriou, M.Yannakakis,
How easy is local search? In Proc. 26th FOCS, 1985, 39-42.
{Ste} M.Kearns, Y.Mansour, Efficient Nash Computation in Large Population Games with Bounded Influence,
In Proc. UAI, 2002.
{PSY} C.H.Papadimitriou, A.Schäffer, M.Yannakakis,
On the complexity of local search. In Proc. 22nd STOC, 1990, 439-445.
{Tse} M.L.Tsetlin, Automaton Theory and Modeling of biological Systems,
Monographs series on Mathematics in Science and Engineering Vol.102, Academic Press, 1973.
{Klei} B.Tung, L.Kleinrock, Finite State Automata to Produce Self-Optimization and Conrol.
IEEE Trans. on Parallel and Distributed Processing 7(4), 439-448, 1996.
|
Les contraintes ouvertes constituent un nouveau champ d'investigation mélant les systèmes multi-agents, la programmation distribuée, la révision de connaissances et les CSP dynamiques. Nous présentons ici un cadre théorique général dans lequel ces problèmes peuvent être modélisés. Il est trop tôt pour proposer un algorithme de résolution distribué mais nous proposons une discussion sur les aspects de répartition associés.
|
|
This paper presents a new network flow formulation for the problem of protein 3D structure prediction by threading. The protein
threading problem (PTP) is widely recognized as one of the most important challenges in computational biology. Several integer
programming models based on this formulation are proposed and compared. Their properties allow efficient decomposition and
application of parallel branch-and-cut algorithm significantly reducing the running time. The efficiency of our approaches
is confirmed by extensive computational experiments.
The numerical results presented in this section are obtained by using ILOG CPLEX 7.1 Callable Library
(one of the most powerful LP and MIP solvers currently available)
and MPI communication library on a cluster of 16 2 * Pentium III 1Ghz 512Mb Linux PCs connected by Myrinet network.
Keywords:
Protein Threading; Network Optimization; Integer Programming; Linear Programming; Large Scale Problems; Parallel Algorithms .
|
Le problème de Langford est un problème d'ordonnancement qui consiste à déterminer
(ou compter) les permutations de "cubes" qui satisfont certaines conditions.
Il s'agit d'un problème NP-complet dont seules les 20 premières instances ont été
résolues informatiquement (un résultat théorique détermine pour chaque instance si elle
est satisfiable ou non).
On peut aborder ce problème de différentes façons, par exemple en le modélisant sous forme
de CSP. Nous avons choisi de reprendre la méthode de Miller, méthode constructive,
et la méthode de Godfrey, méthode algébrique spécifique (cette dernière permet de déterminer
le nombre des solutions sans les expliciter ; c'est elle qui a permis de battre le dernier
record en date). Nous avons amélioré les efficacités de ces deux méthodes puis les avons
parallélisées en mémoire partagée en utilisant Open MP.
Nous avons en patriculier étudié l'équilibre de charge pour la méthode de Miller, en comparant
les ordonnancements statique, modulo et dynamique proposés par OpenMP, avec des équivalents que
nous avons recodés à la main, et avons envisagé des ordonnancements dynamiques de type
client-serveur et serveur initiative.
|
|