Incorporando técnicas de mineração de dados a meta-heurísticas populacionais

Abstract

Several real-world problems can be modeled as combinatorial optimization problems. This is are usually complex and large scale problems can not be solved by exact methods , since they would require impractical computational time . Thus, meta-heuristics have been widely used for solving such problems. Two of the major difficulties of these methods are to escape from sub-optimal regions and to avoid premature convergence of the algorithm . To try to solving this problem , we use o hybrid techniques in order to develop strategies that are applicable to many optimization algorithms . This study investigates the efficiency of incorporating of data mining techniques to ant colony and genetic algorithm Population Metaheuristcs in order to guide them to generate new and better solutions. To validate the proposal, we use the Travelling Salesman Problem and the Problem Sets Cover and different versions of the hybrid meta-heuristics are tested and analyzed . The technique chosen to guide the search of new solutions , from the patterns obtained with the Data Mining , was grouping similar solutions in an attempt to reduce the search space in combinatorial optimization problems . The mining algorithms used are the K -means and Ward which use techniques of hierarchical and partitioning respectively. Computational experiments were performed in order to evaluate the use of MD in Meta-Population traditional heuristics . These experiments showed that the use of mined patterns can assist in obtaining good solutions .