488 research outputs found
Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems
No full textDe nombreux problèmes d'optimisation combinatoire sont difficiles à résoudre et mettent en échec les méthodes de résolution exactes. Parmi les algorithmes de résolution approchée, les métaheuristiques sont des algorithmes génériques largement étudiés dans la littérature. La capacité d’une métaheuristique donnée à trouver de bonnes solutions varie selon la nature des problèmes traités et selon les données qui les composent, et il est difficile d’étudier efficacement la dynamique de ces algorithmes pour des instances de grandes tailles. L'étude proposée porte sur les métaheuristiques de type recherche locale. Des mécanismes basiques sont étudiés afin d'améliorer la compréhension de leur comportement et d'évaluer leur capacité à trouver de bonnes solutions sur différents types de problèmes. Nous abstrayons plusieurs problèmes d'optimisation, munis d’une relation de voisinage entre solutions, sous forme de paysages de fitness afin d’analyser la dynamique des méthodes selon des caractéristiques générales de ces paysages. Nous étudions la navigation dans ces paysages, en se restreignant en premier lieu aux mouvements strictement améliorants. En particulier, nous proposons le critère d’expansion pour guider la recherche et évaluons sa pertinence pour guider les descentes vers de bonnes solutions. Différentes variantes approchant ce principe sont proposées et évaluées, offrant divers compromis entre efficacité et coût calculatoire permettant d’envisager de les intégrer dans des métaheuristiques plus complexes. Enfin nous étudions des recherches locales à voisinage partiel qui acceptent les mouvements détériorant et montrons que dans ce contexte des règles pivot simples peuvent suffire à obtenir de bons compromis entre intensification et diversification, et ainsi atteindre de très bonnes solutions sur divers paysages.Many combinatorial optimization problems are hard to solve and in many cases, exact approaches are impracticable. Among partial search algorithms, metaheuristics are generic algorithms, widely studied in the literature. Their ability to find good solutions varies in function of the problems’ nature et data composing problem instances, and studying efficiently the dynamics of such algorithms is challenging, especially for large instances. We restrain our metaheuristic study to local search algorithms. Basic mechanisms are studied to improve their understanding and assess their ability to find good solutions. We abstract optimization problems into fitness landscapes, thanks to a neighborhood relation between solutions, in order to analyze the dynamics of methods in function of several landscapes characteristics.We study the navigation on these landscapes, firstly by constraining moves to be strictly improving. In particular, we propose the expansion criterion to guide the search process and assess its relevance to guide climbers through good solutions. Variants approximating this principle are proposed and studied, leading to many trade-offs between the ability to find good solutions and the computational cost making them integrable into more complex metaheuristics. Last, we study partial neighborhood local searches, which accept deteriorating moves. In this context, experiments show that simple pivoting rules are sufficient to attain good trade-offs between intensification and diversification and thus reaching good solutions
Recherches locales à voisinages probabilistes et applications à la bio-informatique
No full textNational audienc
Local search algorithms generation
No full textRésoudre un problème d’optimisation consiste à en trouver les meilleures solutions possibles. Pour y parvenir, une approche commune est d’utiliser des algorithmes spécifiques, en général conçus pour des classes de problèmes précises. Cette approche souffre néanmoins de deux désavantages. D’abord à chaque nouveau type de problème, un nouvel algorithme doit souvent être défini, ce qui est un processus long, nécessitant une connaissance des propriétés du problème en question. Ensuite, si ces algorithmes ne sont testés que sur certaines instances du problème, il est possible qu’ils s’avèrent trop spécifiques et donc finalement moins performants sur l’ensemble des instances de la classe. Dans ce travail de thèse, nous explorons la possibilité de générer automatiquement des algorithmes d’optimisation pour un problème donné. Le processus de génération reste suffisamment générique tan dis que les algorithmes ainsi produits peuvent être très spécifiques afin d’être les plus efficaces possibles. Plus précisément, nous faisons évoluer de simples algorithmes de recherche par voisinage via les fonctions d’évaluation qu’ils utilisent pour explorer l’espace des solutions du problème. Le processus évolutionnaire permet implicitement d’adapter le paysage de recherche à la stratégie de résolution basique, tout en conservant une cohérence avec la fonction objectif initiale du problème à résoudre. Ce processus de génération est testé sur deux classes de problèmes dont les difficultés sont très différentes, et obtient des résultats encourageants. Cette expérimentation est complétée par une analyse du processus de génération et des algorithmes ainsi générés.Solving an optimization problem is about finding the best possible solutions. To achieve this, a common approach is to use specific algorithms, usually designed for specific classes of problems. However, this approach suffers from two disadvantages. First with each new type of problem, a new algorithm often has to be defined, which is a lengthy process, requiring knowledge of the prop- erties of the problem in question. Then, if these algorithms are only tested on certain instances of the problem, it is possible that they turn out to be too specific and therefore ultimately less efficient on all the instances of the class. In this thesis work, we explore the possibility of automatically generating optimization algorithms for a given problem. The generation process remains sufficiently generic while the algorithms thus produced can be very specific in order to be as efficient as possible. More precisely, we develop simple neighborhood search algorithms via the evaluation functions that they use to explore the problem solution space. The evolutionary process implicitly makes it possible to adapt the search landscape to the basic solution strategy, while maintaining consistency with the initial objective function of the problem to be solved. This generation process is tested on two classes of problems whose difficulties are very different, and obtains encouraging results. This experiment is completed by an analysis of the generation process and of the algorithms thus generated
Nouvelles heuristiques de voisinage et mémétiques pour le problème Maximum de Parcimonie
No full textPhylogenetic reconstruction aims at reconstructing the evolutionary history of a set of species, represented by a tree. Among the reconstruction methods, the Maximum Parsimony (MP) problem consists, given a set of aligned sequences to find a binary tree, whose leaves are associated to the sequences and which minimizes the parsimony score. Traditionally, existing resolution approaches of this NP-complete problem apply basic heuristic methods, like greedy algorithms and local search. One of the difficulties concerns the handling of binary trees and the definition of tree neighborhoods. In this thesis, we first focus on an improvement of descent algorithms. We empirically show the limits of the existing tree neighborhoods, and introduce a progressive neighborhood which evolves during the search to limit the evaluation of inappropriate neighbors. This algorithm is combined with a genetic algorithm which uses a specific tree crossover based on topological distances between each pair of leaves. This memetic algorithm shows very competitive results, both on real benchmarks taken from the literature as well as with randomly generated instances.La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement
Nouvelles heuristiques de voisinage et mémétiques pour le problème Maximum de Parcimonie
No full textPhylogenetic reconstruction aims at reconstructing the evolutionary history of a set of species, represented by a tree. Among the reconstruction methods, the Maximum Parsimony (MP) problem consists, given a set of aligned sequences to find a binary tree, whose leaves are associated to the sequences and which minimizes the parsimony score. Traditionally, existing resolution approaches of this NP-complete problem apply basic heuristic methods, like greedy algorithms and local search. One of the difficulties concerns the handling of binary trees and the definition of tree neighborhoods. In this thesis, we first focus on an improvement of descent algorithms. We empirically show the limits of the existing tree neighborhoods, and introduce a progressive neighborhood which evolves during the search to limit the evaluation of inappropriate neighbors. This algorithm is combined with a genetic algorithm which uses a specific tree crossover based on topological distances between each pair of leaves. This memetic algorithm shows very competitive results, both on real benchmarks taken from the literature as well as with randomly generated instances.La reconstruction phylogénétique vise à reconstituer l'histoire évolutive d'un ensemble d'espèces sous forme d'un arbre. Parmi les méthodes de reconstruction, le problème Maximum de Parcimonie (MP) consiste à trouver un arbre binaire dont les feuilles sont associées à des séquences de caractères données, et qui minimise le score de parcimonie. Les méthodes de résolution existantes de ce problème NP-complet s'attachent généralement à appliquer des méthodes heuristiques traditionnelles, comme des algorithmes gloutons et de recherche locale. L'une des diffcultés du problème repose sur la manipulation d'arbres et la définition de voisinages d'arbres.Dans cette thèse, nous nous intéressons en premier lieu à l'amélioration des techniques de résolution du problème MP basées sur un algorithme de descente. Après avoir montré de manière empirique les limites des voisinages existants, nous introduisons un voisinage progressif qui évolue au cours de la recherche afin de limiter l'évaluation de voisins infructueux lors d'une descente. L'algorithme obtenu est ensuite hybridé à un algorithme génétique utilisant un croisement d'arbres spécifique fondé sur les mesures de distance entre chaque couple d'espèces dans l'arbre. Cet algorithme mémétique exhibe des résultats très compétitifs, tant sur des jeux de test tirés de la littérature que sur des jeux générés aléatoirement
Law & Economics Perspectives on Electricity Regulation
No full textThis paper first reviews some of the main contributions of the new institutional economics to the analysis of the process of competitive transformation of network industries. It shows that neoinstitutional analysis is complementary to the microeconomics of rational pricing, since it accounts for the decisive role of an institutional framework adapted to new transactions. It emphasizes the importance of the political reform process, which draws on the conditions of attractiveness and feasibility to define an initial reorganization of property rights in these industries. The paper then analyzes in this light some of the main challenges ahead for electricity regulation: the question of investment in generation capacities and the link to long term contracts, the regulation of wholesale market power, the support to Renewable Energy Sources for Electricity (RES-E) and the design of new regulatory authorities.Electricity Markets; New Institutional Economics; Law & Economics
Auto-adaptative Migration Policies in Island-Based Genetic Algorithms
No full textDate du colloque : 2010International audienc
Chercher moins pour trouver mieux : de l'intérêt de la descente stochastique pour la résolution de problèmes combinatoires
No full textInternational audienceAu sein des algorithmes de recherche locale, les méthodes de descente font rarement l'objet d'études expérimentales dédiées. Cependant, ces techniques de recherche sont à la base d'un grand nombre de métaheuristiques modernes et peuvent avoir une influence non négligeable quant à la capacité d'un algorithme à atteindre de bonnes solutions de l'espace de recherche. L'an passé, nous avons comparé des descentes basées sur différentes règles pivot (premier ou meilleur améliorant) et différentes politiques de gestion de la neutralité (descente stricte, stochastique, ou stricte avec perturbations neutres), puis comparé empiriquement leur efficacité sur des paysages de recherche de type NK-landscapes, de différentes tailles et enregistrant différents niveaux de rugosité et de neutralité. Nous étendons cette année cette étude à des paysages de recherche issus de problèmes combinatoires académiques (MAXSAT, QAP, Flow-shop), après avoir introduit des indicateurs de caractérisation des paysages de recherche. Dans une large étude expérimentale, nous montrons que la stratégie du meilleur améliorant est plus efficace sur les paysages lisses et/ou de petites tailles mais est rapidement dominée par la stratégie du premier améliorant sur les paysages plus rugueux et/ou plus grands. Parallèlement, nous indiquons que la descente stochastique, qui accepte indifféremment des voisins neutres tout au long de la recherche (même avant d'avoir atteint un optimum local), permet non seulement une convergence plus rapide de la recherche, mais surtout d'atteindre la plupart du temps des optimums locaux de meilleure qualité. Enfin, une étude sur les NKr-landscapes montre que la création artificielle de plateaux (en arrondissant les valeurs fitness), permet d'atteindre de bien meilleures solutions qu'à partir du paysage originel. En effet, lisser la fonction d'évaluation permet d'éviter d'être piégé trop tôt dans des optimums locaux.</p
A Dynamic Island-Based Genetic Algorithms Framework
No full textThis work presents a dynamic island model framework for helping the resolution of combinatorial optimization problems with evolutionary algorithms. In this framework, the possible migrations among islands are represented by a complete graph. The migrations probabilities associated to each edge are dynamically updated with respect to the last migrations impact. This new framework is tested on the well-known 0/1 Knapsack problem and MAX-SAT problem. Good results are obtained and several properties of this framework are studied
- …
