Dans le cadre de cette thèse, nous nous intéresseons à l'amélioration des techniques de programmation génétique (PG), en particulier nous avons essayer d'améliorer la performance de la PG en cas d'utilisation de grammaire riche, où l'ensemble de terminaux contient plus que nécessaire pour représenter des solutions optimales. Pour cela, nous avons présenté le problème de la sélection d'attributs en rappelant les principales approches, et nous avons utilisé la technique de mesure de poids des terminaux pour affiner la sélection d'attributs. En second lieu, nous présentons des travaux sur un autre algorithme qui s'inspire de la boucle évolutionnaire : l'évolution différentielle (ED), et nous étudions la performance de cette technique sur la branche de la programmation génétique linéaire. Nous présentons et comparons les performances de cette dernière technique sur un ensemble de "benchmarks" classique de la PG. / This thesis mainly deals with genetic programming. In this work, we are interested in improving the overall performance of genetic programming (GP) when dealing with rich grammar when the terminal set is very large. We introduce the problem of attributes selection and in our work we introduce a scheme based on the weight (based on the frequency) to refine the attribute selection. In the second part of this work, we try to improve the evolution engine with the help of the differential evolution (DE) algorithm. This new engine is applied to linear genetic programming. We then present some experiments and make some comparisons on a set of classical benchmarks.

L’image est une des informations les plus importantes dans la vie. Avec le développement rapide des dispositifs d’acquisition d’images numériques par exemple les appareils photo numériques, les caméras de téléphones, les appareils d’imagerie médicale ou les dispositifs d’imagerie satellite..., les besoins de traitement et d’analyse des images sont de plus en plus croissants. Ils concernent les problèmes de l’acquisition, du stockage des images, de l’amélioration ou de l’information d’extraction d’une image,... Dans cette thèse, nous étudions le traitement et l’analyse des problèmes: acquisition comprimée, apprentissage de dictionnaire et débruitage d’images, segmentation d’images. La méthode que nous décrivons se base sur les approches d’optimisation déterministe, nommées la programmation DC (Difference of Convex functions) et DCA (Difference of Convex Algorithms), pour la résolution des problèmes d’analyse d’images cités précédemment. 1. Acquisition comprimée: une technique de traitement du signal pour acquérir et reconstruire un signal respectant les limites traditionnelles du théorème d’échantillonnage de Nyquist–Shannon, en trouvant la solution la plus parcimonieuse d’un système linéaire sous-déterminé. Cette méthode apporte la parcimonie ou la compressibilité du signal lorsqu’il est représenté dans une base ou un dictionnaire approprié qui permet au signal entier d’être déterminé à partir de certains mesures relatives. Dans cette thématique, nous nous intéressons à deux problèmes. Le premier est de trouver la représentation parcimonieuse d’un signal. Le second est la récupération du signal à partir de ses mesures compressées sur une base incohérente ou un dictionnaire. Les deux problèmes ci-dessus conduisent à résoudre un problème d’optimisation non convexe. Nous étudions trois modèles avec quatre approximations pour ces problèmes. Des algorithmes appropriés basés sur la programmation DC et DCA sont présentés. 2. Apprentissage du dictionnaire: Nous avons vu la puissance et les avantages de la représentation parcimonieuse des signaux dans l’acquisition comprimée. La représentation parcimonieuse d’un signal entier dépend non seulement des algorithmes de représentation mais aussi de la base ou du dictionnaire qui sont utilisés dans la représentation. Ainsi conduit un problème critique et les autres applications d’une manière naturelle. Au lieu d’utiliser une base fixe, comme wavelets (ondelettes) ou Fourier, on peut apprendre un dictionnaire, la matrice D, pour optimiser la représentation parcimonieuse d’une large classe de signaux donnés. La matrice D est appelée le dictionnaire appris. Pour ce problème, nous avons proposé un algorithme efficace basé sur DCA qui comprend deux étapes: la première étape - codage parcimonieux; le seconde étape - dictionnaire mis à jour. Une application de ce problème, débruitage d’images, est également considérée. 3. Segmentation d’images: il s’agit de partitionner une image numérique en segments multiples (ensembles des pixels). Le but de la segmentation est de simplifier et/ou de modifier la représentation d’une image en une forme qui est plus significative et plus facile à analyser. Nous avons développé une méthode efficace pour la segmentation d’images via le clustering flou avec la pondération de variables. Nous étudions également une application médicale qui est le problème de comptage de cellules. Nous proposons une combinaison de phase de segmentation et des opérations morphologiques pour compter automatiquement le nombre de cellules. Notre approche donne des résultats prometteurs dans la comparaison avec l’analyse manuelle traditionnelle en dépit de la densité cellulaire très élevée / Image is one of the most important information in our lives. Along with the rapid development of digital image acquisition devices such as digital cameras, phone cameras, the medical imaging devices or the satellite imaging devices..., the needs of processing and analyzing images is more and more demanding. It concerns with the problem of image acquiring, storing, enhancing or extracting information from an image,... In this thesis, we are considering the image processing and analyzing problems including: compressed sensing, dictionary learning and image denoising, and image segmentation. Our method is based on deterministic optimization approach, named the DC (Difference of Convex) programming and DCA (Difference of Convex Algorithms) for solving some classes of image analysis addressed above. 1. Compressed sensing is a signal processing technique for efficiently acquiring and reconstructing a signal, which is breaking the traditional limits of sampling theory of Nyquist–Shannon by finding solutions to underdetermined linear systems. This takes advantage of the signal’s sparseness or compressibility when it is represented in a suitable basis or dictionary, which allows the entire signal to be determined from few relative measurements. In this problem, we are interested in two aspects phases. The first one is finding the sparse representation of a signal. The other one is recovering the signal from its compressed measurements on an incoherent basis or dictionary. These problems lead to solve a NP–hard nonconvex optimization problem. We investigated three models with four approximations for each model. Appropriate algorithms based on DC programming and DCA are presented. 2. Dictionary learning: we have seen the power and the advantages of the sparse representation of signals in compressed sensing. Finding out the sparsest representation of a set of signals depends not only on the sparse representation algorithms but also on the basis or the dictionary used to represent them. This leads to the critical problems and other applications in a natural way. Instead of using a fixed basis such as wavelets or Fourier, one can learn the dictionary, a matrix D, to optimize the sparsity of the representation for a large class of given signals (data). The matrix D is called the learned dictionary. For this problem, we proposed an efficient DCA based algorithm including two stages: sparse coding and dictionary updating. An application of this problem, image denoising, is also considered. 3. Image segmentation: partitioning a digital image into multiple segments (sets of pixels). The goal of segmentation is to simplify and/or change the representation of an image into a form that is more meaningful and easier to analyze. We have developed an efficient method for image segmentation via feature weighted fuzzy clustering model. We also study an application of image segmentation for cell counting problem in medicine. We propose a combination of segmentation phase and morphological operations to automatically count the number of cells. Our approach gives promising results in comparison with the traditional manual analysis in despite of the very high cell density

La communication sans fil joue un rôle de plus en plus important dans de nombreux domaines. Un grand nombre d'applications sont exploitées tels que l'e-banking, l'e-commerce, les services médicaux,….Ainsi, la qualité de service (QoS), et la confidentialité d'information sur le réseau sans fil sont primordiales dans la conception du réseau sans fil. Dans le cadre de cette thèse, nous nous concentrons sur le développement des approches d'optimisation pour résoudre certains problèmes concernant les deux sujets suivants : la qualité de service et la sécurité de la couche physique. Nos méthodes sont basées sur la programmation DC (Difference of convex functions) et DCA (DC Algorithms) qui sont reconnues comme de puissants outils d'optimisation non convexes et non différentiables. Ces outils ont connu de grands succès au cours des deux dernières décennies dans la modélisation et la résolution de nombreux problèmes d'applications dans divers domaines de sciences appliquées. Outre les chapitres d'introduction et de conclusion, le contenu principal de cette thèse est divisé en quatre chapitres: Le chapitre 2 concerne la QoS dans les réseaux sans fil tandis que les trois chapitres suivants étudient la sécurité de la couche physique. Le chapitre 2 considère un critère de QoS qui consiste à assurer un service équitable entre les utilisateurs dans un réseau sans fil. Plus précisement, on doit s'assurer qu'aucun utilisateur ne souffre d'un mauvais rapport signal sur bruit (“signal to noise ratio (SNR)" en anglais). Le problème revient à maximiser le plus petit SNR. Il s'agit donc un problème d'optimisation DC général (minimisation d'une fonction DC sur un ensemble défini par des contraintes convexes et des contraintes DC). La programmation DC et DCA ont été développés pour résoudre ce problème. Tenant compte de la structure spécifique du problème, nous avons proposé une nouvelle décomposition DC qui était plus efficace que la précédente décomposition. Une méthode de résolution basée sur la programmation DC et DCA a été développée. De plus, nous avons prouvé la convergence de notre algorithme. L'objectif commun des trois chapitres suivants (Chapitre 3, 4, 5) est de garantir la sécurité de la couche physique d'un système de communication sans fil. Nous nous concentrons sur l'approche qui consiste à maximiser le taux de secret (“secrecy rate” en anglais). Trois diverses architectures du réseau sans fil utilisant différentes techniques coopératives pour la transmission sont considérées dans ces trois chapitres. Dans le chapitre 3, nous considérons un réseau point-à-point utilisant une technique coopérative de brouillage. Le chapitre 4 étudie un réseau de relais utilisant une combinaison de technique de formation de faisceau ("beamforming technique" en anglais) et de technique de relais coopératifs. Deux protocoles de technique de relais coopératifs, Amplifier-et-Transmettre (“Amplify-and-Forward (AF)'') et Décoder-et-Transmettre (“Decode-and-Forward (DF)'' en anglais), sont considérés. Dans le chapitre 3 et le chapitre 4, nous considérons qu'il y a seulement un espion (“eavesdropper" en anglais) dans le réseau tandis que le chapitre 5 est une extension du chapitre 4 où on peut avoir plusieurs espions. Tous ces problèmes sont des problèmes d'optimisation non-convexes qui peuvent être ensuite reformulés sous forme d'une programmation DC pour lesquels nous développons les méthodes efficaces et robustes basées sur la programmation DC et DCA. Dans les chapitres 3 et 4, nous reformulons les problèmes étudiés sous forme d'un programme DC standard (minimisation d'une fonction DC avec les contraintes convexes). La structure spécifique est bien exploitée afin de concevoir des schémas DCA standard efficaces où les sous-problèmes convexes de ces schémas sont résolus soit explicitement soit de manière peu coûteuse. Les problèmes d'optimisation dans le chapitre 5 sont reformulés comme les programmes DC généraux et les schémas [...] / Wireless communication plays an increasingly important role in many aspects of life. A lot of applications of wireless communication are exploited to serve people's life such as e-banking, e-commerce and medical service. Therefore, quality of service (QoS) as well as confidentiality and privacy of information over the wireless network are of leading interests in wireless network designs. In this dissertation, we focus on developing optimization techniques to address some problems in two topics: QoS and physical layer security. Our methods are relied on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are powerful, non-differentiable, non-convex optimization tools that have enjoyed great success over the last two decades in modelling and solving many application problems in various fields of applied science. Besides the introduction and conclusion chapters, the main content of the dissertation is divided into four chapters: the chapter 2 concerns QoS in wireless networks whereas the next three chapters tackle physical layer security. The chapter 2 discusses a criterion of QoS assessed by the minimum of signal-to-noise (SNR) ratios at receivers. The objective is to maximize the minimum SNR in order to ensure the fairness among users, avoid the case in which some users have to suffer from a very low SNR. We apply DC programming and DCA to solve the derived max-min fairness optimization problem. With the awareness that the efficiency of DCA heavily depends on the corresponding DC decomposition, we recast the considered problem as a general DC program (minimization of a DC function on a set defined by some convex constraints and some DC constraints) using a DC decomposition different from the existing one and design a general DCA scheme to handle that problem. The numerical results reveal the efficiency of our proposed DCA compared with the existing DCA and the other methods. In addition, we rigorously prove the convergence of the proposed general DCA scheme. The common objective of the next three chapters (Chapter 3,4,5) is to guarantee security at the physical layer of wireless communication systems based on maximizing their secrecy rate. Three different architectures of the wireless system using various cooperative techniques are considered in these three chapters. More specifically, a point-to-point wireless system including single eavesdropper and employing cooperative jamming technique is considered in the chapter 3. Chapter 4 is about a relay wireless system including single eavesdropper and using a combination of beamforming technique and cooperative relaying technique with two relaying protocols Amplify-and-Forward (AF) and Decode-and-Forward (DF). Chapter 5 concerns a more general relay wireless system than the chapter 4, in which multiple eavesdroppers are considered instead of single eavesdropper. The difference in architecture of wireless systems as well as in the utilized cooperative techniques result in three mathematically different optimization problems. The unified approach based on DC programming and DCA is proposed to deal with these problems. The special structures of the derived optimization problems in the chapter 3 and the chapter 4 are exploited and explored to design efficient standard DCA schemes in the sense that the convex subproblems in these schemes are solved either explicitly or in an inexpensive way. The max-min forms of the optimization problems in the chapter 5 are reformulated as the general DC programs with DC constraints and the general DCA schemes are developed to address these problems. The results obtained by DCA show the efficiency of our approach in comparison with the existing methods. The convergence of the proposed general DCA schemes is thoroughly shown

Dans la première partie de cette thèse, nous présentons une implémentation du langage fp2 ayant pour modèle les réseaux de Petri. Fp2 est un langage de programmation parallèle base sur la réécriture de termes et les spécifications algébriques. Nous donnons une nouvelle sémantique a fp2, de la famille des sémantiques du vrai parallélisme, et prouvons la correction de cette sémantique par rapport a la sémantique interleaving du langage. Le modèle utilise, les réseaux de Petri, et la nouvelle sémantique donnée au langage permettent une représentation plus compacte de programmes complexes, évitant les problèmes d'explosion combinatoire rencontres avec les implémentations précédentes. Nous évaluons le gain de notre approche, et proposons plusieurs schémas d'interprétation du langage, bases sur cette nouvelle sémantique. La seconde partie de ce travail concerne la définition d'une nouvelle famille d'équivalences comportementales pour les réseaux de Petri. Alors que les équivalences proposées jusqu'alors sont définies entre les marquages, c'est-a-dire entre les états globaux du réseau, nous définissons une relation entre les places du réseau, reprenant une idée proposée par olderog. De nouvelles équivalences, les bisimulations de places, sont proposées a partir de cette définition. Un algorithme efficace (polynomial) permettant de calculer la plus grande bisimulation de places sur un réseau est propose. Nous montrons comment simplifier un réseau en le quotientant par cette plus grande bisimulation, obtenant ainsi un représentant canonique d'une classe d'équivalence de réseaux bisimilaires de places. L'étude de ces équivalences est ensuite étendue aux réseaux avec actions internes

Cette thèse est consacrée à la prise en compte de données incertaines dans les problèmes d'optimisation. On se concentre sur la programmation mathématique sous contraintes probabilistes, dont le but est de trouver la meilleure solution qui sera réalisable avec une probabilité minimale garantie. Par ailleurs, on s'intéresse à la prise en compte de variables de décisions entières, qui sont souvent requises en pratique.<br /><br />Pour résoudre de tels problèmes combinatoires sous contraintes probabilistes, on s'appuie d'abord sur l'optimisation robuste. Les liens théoriques entre ces deux familles de méthodes sont mis en évidence. A partir de modèles robustes appropriés, des algorithmes de résolution heuristique sont définis. On s'intéresse ensuite à la résolution optimale de problèmes combinatoires sous contraintes probabilistes. Des tests numériques illustrent les méthodes présentées et montrent leur efficacité pratique. Enfin, deux applications au domaine des télécommunications sont développées. Elles concernent toutes deux la localisation de fonctions dans un réseau.

.

.

La version classique du problème d'ordonnancement de projet à contraintes de ressources (RCPSP) consiste à trouver un ordonnancement, de durée minimale, des activités d'un projet entrant en compétition sur l'usage de ressources renouvelables, cumulatives et disponibles en quantité limité. <br />La réputation d'extrême difficulté du RCPSP a mené nombre de chercheurs à proposer de nouvelles méthodes de résolution exacte toujours plus performantes pour ce problème. Malgré cela, les instances de tailles réelles, qui se recontrent fréquemment, par exemple dans la gestion de production industrielle, sont encore loins d'être résolues optimalement. Il est donc intéressant, en combinant les acquis des travaux précédents, en particulier en programmation par contraintes (PPC) et en programmation linéaire (PL), de se pencher sur des méthodes exactes innovantes ou encore de développer des procédures d'évaluation par défaut, pour permettre une meilleure estimation de la performance des heuristiques sur le RCPSP. Ce travail de thèse entre dans ce cadre.<br /><br />Dans un premier temps, nous nous attachons au calcul de bornes inférieures pour le RCPSP par relaxation lagrangienne. D'une part, nous cherchons à accélerer le calcul de la borne de Brucker et Knust (obtenue par hybridation de PPC et de génération de colonnes) en résolvant le programme linéaire sous-jacent par relaxation lagrangienne (méthodes de sous-gradient et de génération de contraintes). D'autre part, nous appliquons le même principe de relaxation lagrangienne, sur la formulation linéaire initiale de Mingozzi et al. dont est extraite la relaxation préemptive utilisée par Brucker et Knust. Une partie du problème se réduit alors, comme indiqué par Möhring et al., au calcul d'une coupe minimale dans un graphe.<br /> <br />Nous étudions ensuite, un second type de bornes inférieures, obtenu par des méthodes de coupes basées sur les relaxations continues de deux formulations linéaires entières. Ces programmes linéaires sont au préalable resserés par des techniques éprouvées de propagation de contraintes, dont la règle globale du shaving. L'originalité de notre méthode repose essentiellement dans la génération des coupes qui sont, en grande partie, directement déduites des règles de propagation de contraintes.<br /><br />Enfin, nous proposons une méthode originale de résolution exacte pour le RCPSP, basée sur la procédure de Resolution Search de Chvàtal, une alternative aux méthodes de Branch-and-Bound classiques et qui se rapproche du Dynamic Backtracking en programmation par contraintes. Dans Resolution Search, l'espace de recherche ne se présente pas comme un arbre, puisqu'il s'agit, à chaque fois qu'un noeud terminal est rencontré, de rechercher par backtrakings successifs, les fixations minimales qui font de ce noeud un noeud terminal. L'ensemble des ces fixations est alors stocké de manière intelligente de façon à les exclure de l'espace de recherche. Resolution Search a été initialement développée pour la résolution de programmes linéaires en variables binaires, mais n'a semble-t'il jamais été employée dans le cadre de problèmes spécifiques.<br />Dans le but de prouver son efficacité, nous commencons par l'appliquer basiquement à deux formulations linéaires en variables binaires pour le RCPSP et la comparons à une version tout aussi basique de Branch-and-bound.<br /> Nous en poursuivons l'étude en utilisant des règles de branchement et d'évaluation ayant déjà prouvé leur efficacité dans des implémentations classiques de méthodes arborescentes pour le RCPSP, telles que celles de Brucker et al., Carlier et Latapie, Demeulemeester et Herroelen.

Dans cette thèse, nous nous intéressons à l'adaptation de l'algorithmique aux architectures parallèles. Les plateformes hautes performances actuelles disposent de plusieurs niveaux de parallélisme et requièrent un travail considérable pour en tirer parti. Les superordinateurs possèdent de plus en plus d'unités de calcul et sont de plus en plus hétérogènes et hiérarchiques, ce qui complexifie d'autant plus leur utilisation.Nous nous sommes intéressés ici à plusieurs aspects permettant de tirer parti des architectures parallèles modernes. Tout au long de cette thèse, plusieurs problèmes de natures différentes sont abordés, de manière plus théorique ou plus pratique selon le cadre et l'échelle des plateformes parallèles envisagées.Nous avons travaillé sur la modélisation de problèmes dans le but d'adapter leur formulation à des solveurs existants ou des méthodes de résolution existantes, en particulier dans le cadre du problème de la factorisation en nombres premiers modélisé et résolu à l'aide d'outils de programmation linéaire en nombres entiers.La contribution la plus importante de cette thèse correspond à la conception d'algorithmes pensés dès le départ pour être performants sur les architectures modernes (processeurs multi-coeurs, Cell, GPU). Deux algorithmes pour résoudre le problème du compressive sensing ont été conçus dans ce cadre : le premier repose sur la programmation linéaire et permet d'obtenir une solution exacte, alors que le second utilise des méthodes de programmation convexe et permet d'obtenir une solution approchée.Nous avons aussi utilisé une bibliothèque de parallélisation de haut niveau utilisant le modèle BSP dans le cadre de la vérification de modèles pour implémenter de manière parallèle un algorithme existant. A partir d'une unique implémentation, cet outil rend possible l'utilisation de l'algorithme sur des plateformes disposant de différents niveaux de parallélisme, tout en ayant des performances de premier ordre sur chacune d'entre elles. En l'occurrence, la plateforme de plus grande échelle considérée ici est le cluster de machines multiprocesseurs multi-coeurs. De plus, dans le cadre très particulier du processeur Cell, une implémentation a été réécrite à partir de zéro pour tirer parti de celle-ci.

Les structures d'hospitalisation rencontrent de nombreux problèmes de niveau opérationnel. Cette thèse propose une investigation des problématiques d'aide à la décision pour le pilotage des ressources humaines en HAD. Suite à l'étude des processus d'une structure HAD identifiant les différentes décisions logistiques dans le cadre d'une certification qualité, deux problématiques principales ont été identifiées. L'investigation du premier domaine, a permis de concevoir un outil d'aide à la décision calculant les emplois du temps des infirmiers d'une structure de soins à domicile. Il a été expérimenté pour l'HAD EOVI Drôme nord. Plusieurs modèles de décision ont été comparés à l'aide de deux méthodes de résolution : une résolution par programmation linéaire entière et une résolution par programmation par contraintes. Une deuxième problématique a été étudiée : le circuit du médicament d'une HAD, ceci en collaboration avec l'HAD Soins et Santé de Lyon afin de les aider dans la gestion de leurs livraisons urgentes à partir d'une pharmacie à usage intérieur. L'HAD rencontre en moyenne une quarantaine de livraisons urgentes par jour et ces livraisons coûtent très chers en raison des prestataires externes employés et des frais de taxi éventuels. Un outil d'aide à la décision décliné selon trois stratégies de livraisons différentes (par tranches horaires, par nombre de médicaments à livrer, par nombre de livraisons par tournées) a été développé et a été proposé à l'HAD. Une fois la stratégie choisie, cet outil a été utilisé en exploitant les données réelles de l'HAD pour comparer les coûts entre l'emploi de prestataires externes ou de livreurs salariés. Il a permis de démontrer que l'emploi de livreurs salariés serait nettement plus rentable.