1,126 research outputs found
Preface to Hybrid Metaheuristics - 6th International Workshop, HM 2009
No full textThe International Workshop on Hybrid Metaheuristics was established with the aim of providing researchers and scholars with a forum for discussing new ideas and research on metaheuristics and their integration with techniques typical of other fields. The papers accepted for the sixth workshop confirm that such a combination is indeed effective and that several research areas can be put together. Slowly but surely, this process has been promoting productive dialogue among researchers with different expertise and eroding barriers between research areas.
The papers in this volume give a representative sample of current research in hybrid metaheuristics. It is worth emphasizing that this year, a large number of papers demonstrated how metaheuristics can be integrated with integer linear programming and other operations research techniques. Constraint programming is also featured, which is a notable representative of artificial intelligence solving methods. Most of these papers are not only a proof of concept – which can be valuable by itself – but also show that the hybrid techniques presented tackle difficult and relevant problems
Evaluation of a family of reinforcement learning cross-domain optimization heuristics
No full textIn our participation to the Cross-Domain Heuristic Search Challenge (CHeSC 2011) [1] we developed an approach based on Reinforcement Learning for the automatic, on-line selection of low-level heuristics across different problem domains. We tested different memory models and learning techniques to improve the results of the algorithm. In this paper we report our design choices and a comparison of the different algorithms we developed
Two-level ACO for haplotype inference under pure parsimony
No full textHaplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information enables researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem under certain hypotheses (such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. At present, the main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods, which are adequate only for moderate size instances. In this paper, we present an iterative constructive approach to Haplotype Inference based on ACO and we compare it against a state-of-the-art exact method
A Hybrid Solver for Large Neighborhood Search: Mixing Gecode and EasyLocal++
No full textWe present a hybrid solver (called GELATO) that exploits the potentiality of a Constraint Programming (CP) environment (Gecode) and of a Local Search (LS) framework (EasyLocal++). GELATO allows the user to easily develop and use hybrid meta-heuristic combining CP and LS phases (in particular Large Neighborhood Search). We tested some hybrid algorithms on different instances of the Asymmetric Traveling Salesman Problem: even if only naive LS strategies have been used, our meta-heuristics improve the standard CP and LS methods, in terms of both quality of the solution reached and execution time. GELATO will be integrated into a more general tool to solve Constraint Satisfaction/ Optimization Problems. Moreover, it can be seen as a new library for approximate and efficient searching in Gecode
Non-standard peak values of the Bose-Einstein correlations and their possible interpretation by a metric description of strong interactions
No full textWe critically reanalyze some recent experimental data on the Bose-Einstein (BE) correlations in pion production. We show that there is, in some cases, an experimental evidence for a peak height of the correlation function greater than two, contrarily to the predictions of the "canonical" theory of BE correlations. Although an explanation of such an "anomalous" value can be given by means of suitable phenomenological models, we show that this result is a straightforward consequence of the treatment of BE correlations within the framework of a description of strong interactions in terms of a deformed Minkowski metric
EasyGenetic: A template metaprogramming framework for genetic master-slave algorithms
No full textWe present EasyGenetic, a genetic solver based on template metaprogramming, that enables the user to configure the solver by instantiating template parameters. The framework allows to combine flexibility with efficiency. The framework is mainly designed to be applied to problems for which a master-slave solution strategy can be defined
DNA microsatellite in fruit crops: isolation, length polymorphism, inheritance, somatic stability, and cross-species conservation
No full textHybrid local search techniques for the generalized balanced academic curriculum problem
No full textThe Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching periods satisfying prerequisites and balancing students' load. BACP is included in CSPlib along with three benchmark instances. However, the BACP formulation in CSPLib is actually simpler than the real problem that, in general, universities have to solve in practice. In this paper, we propose a generalized formulation of the problem and we study a set of hybrid solution techniques based on high-level control strategies that drive a collection of basic local search components. The result of the study allows us to build a complex combination of simulated annealing, dynamic tabu search and large-neighborhood search. In addition, we present six new instances obtained from our university, which are much larger and more challenging than the CSPlib ones (the latter are always solved to optimality in less than 0.1 seconds by our techniques). For the sake of possible future comparisons, we make available through the web all the input data, our scores and results, and a solution validator
Towards a highly scalable hybrid metaheuristic for haplotype inference under parsimony
No full textHaplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This piece of information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony) and to solve it using off-the-shelf combinatorial optimization techniques. In this paper, we present and discuss an approach based on hybridization of two metaheuristics, one being a population based learning algorithm and the other a local search. We test our approach by solving instances from common Haplotype Inference benchmarks. Results show that this approach achieves an improvement on solution quality with respect to the application of a single "pure" algorithm
- …
