HEURISTICS

Author: PANTRIGO FERNÁNDEZ JUAN JOSÉ.
Year: 2005.
University: REY JUAN CARLOS [www.urjc.es].
Place of defense: ESCUELA SUPERIOR DE CIENCIAS EXPERIMENTALES Y TECNOLOGÍA.
Place of preparation: ESCUELA SUPERIOR DE CIENCIAS EXPERIMENTALES Y TECNOLOGÍA.

Summary: This thesis proposes a new methodology for the development of dynamic optimization algorithms, called particulate filter metaheuristico. The dynamic optimization problems are a generalization of the problems of optimization where the problem of relevant variables change over time. Under these conditions, it is necessary for the optimization algorithms have strategies to adapt to change. Accordingly, the working hypothesis that has been raised in this thesis is that "the combination of adaptive strategies, prediction and optimization increases the efficiency of the search for high quality solutions for dynamic optimization problems." The metaheurísticas are approximate algorithms that have been successfully applied to optimization problems, however, as a rule, these kinds of methods do not consider the possibility that the definition of the problem has changed, and therefore they are not designed to accommodate the dynamics of a system. On the other hand, there is a family of methods called sequential estimation algorithms (or particulate filters), epecializados in problem solving dynamic terms bayesfano. Unfortunately, filters particles without optimization strategies. If the working hypothesis is valid, whether metaheurísticas as particulate filters must play an important role in dynamic optimization. The fundamental problem that arises in dynamic optimization can be summarized in two questions: Do you what history information process is useful and should be taken into account in successive moments? Â and how this information is transferred between successive moments during the dynamic process? Since there are specialized in optimization algorithms and methods aimed at the prediction in dynamic environments, it seems reasonable to address these problems using features of both methodologies. For this reason, the fundamental objective of this thesis has been working "to develop a methodology for the hybridization of estimation methods and sequential metaheuristicas population for its application in solving optimization problems dynamics." This methodology has been called particulate filter meteurístico (metaheuristic particle fll ter-mpf). As examples of application of the methodology proposed algorithms have built five so-called filter particles dispersed with search (search scatter particle fllter - sspf), particulate filter with reencadenamiento trajectory (path rellnking particle filter-prpf) filter particles with algorithms meméticos (memeticalgorithms particle filter-mapf) filter particles with estimated distribution (estimation of distribution algorithm particle fil ter-edapf), and finally particulate filter with local search (local search particle fil ter-lspf), as extending the scope of mpf. The algorithms, developed hanaplicado effectively to dynamic optimization three problems: (i) to track objects articulated in image sequences 2d, (ii) to monitor one or more objects in image sequences 2d for a interfaces for implementation user-based machine vision and (iii) the problem of dynamic traveling salesman. In all these algorithms mpf has shown experimentalemente conduct more efficient and have obtained solutions of higher quality than the algorithms that have been with the company 8 rado to 2c9 less on data sets used.

Author: LUQUE POLO GABRIEL JESÚS.
Year: 2005.
University: MÁLAGA [www.uma.es].
Place of defense: INFORMÁTICA.
Place of preparation: INFORMÁTICA.

Summary: The objective of this thesis is to develop techniques metaheurísticas parallel efficient for solving problems with actual implementation. To do so, initially had conducted a study on the current state of the art in the field of metaheurísticas, focusing mainly in the domain of methods parallel. Once understood the advantages and limitations of the models proposed in the past, and based on this knowledge, there have been various proposals parallel algorithmic extensions of the more efficient models in the literature. These models have been studied in depth both in a theoretical (studying the influence of the main parameters in its convergence) as a pilot, analyzing their behavior on different platforms in parallel. Based on the knowledge acquired in the latter two phases, addressed the resolution of various combinatorial problems with different characteristics but they share as a distinct feature great difficulty and their actual implementation. In particular have been addressed circuit design, labeling lexicon natural language, the problem of assembly of DNA fragments, problems of planning and allocation of workers and other problems in different fields. Among the major contributions that can be ruled out is the improvement in the state of the art of many of the problems abordas (circuit design, labeling lexicon, â |), as well as an increase in knowledge about different aspects of the methods parallel algorithm ( studies on the convergence of the models distributed study of the influence of coupling techniques metaheurísticas parallel ..)..

Author: SEQUEIRA CARDOSO PEDRO JORGE.
Year: 2006.
University: SEVILLA [www.us.es].
Place of defense: E.T.S. DE INGENIERÍA INFORMÁTICA.
Place of preparation: E.T.S. DE INGENIERÍA INFORMÁTICA.

Summary: The study solutions meta-heurísticas based on the paradigm of Ant Colony Optimization (ACO) for the Multiple Objetive Minimum Spanning Trees and combinatorial problems related is the main concern of this investigation. In qualifying commonly validated the complexity of the problems, is classified the problem of Multiple Minimum Spanning Trees as NP-complete. Moreover, as in most of the problems of optimization with multiple objectives, solving a problem Multiple Objetive Minimum Sapnning Trees is a series of compromises in the sense that improving one of the goals is required at least one worsen the other, which is a major concern in a practical sense. In the first part of the investigation, a theoretical analysis of the problem to supplement the results known. This analysis confirms the fact that the actual use of accurate methods for solving problems Multiple Spanning Trees Objetive Minimum applies only in specific circumstances. This means that you use approximation methods should be considered as an alternative to solve the problem. Particularly, proposes two methods based on the paradigm of OCP: Multiple Objetive Network optimization based on an OCP (MONACO) and the Explorer-Depth ANT DANTE. THE MONACO uses a set of traces of fermonas and specific heuristics to bring the entire Pareto. The DANTE is improved MONACO procedure that applies a thorough search based on the best solutions that are obtained in the process, in order to better exploit the area of the search. The proposed methods are tested with problems of multiple targets selected by improving resutlados obtained previously by other authors. To test algorithms and MONACO DANTE on the problem of Multiple Objective Minimum Spanning Trees has been proposed library / repository problems networks with multiple objectives, set out on a series of systematic generators for the networks. The results obtained with MONACO and DANTE are compared with the results obtained with the methods Force Gross and Weighted Average.