Vários problemas do mundo real podem ser modelados como problemas de otimização
combinatória. Em geral são problemas complexos e de larga escala, não podendo ser
resolvidos por métodos exatos, pois os mesmos necessitariam de tempo computacional
impraticável. Desse modo, as meta-heurísticas têm sido amplamente empregadas
para a resolução de tais problemas. Duas das principais dificuldades destes métodos
são escapar das regiões sub-ótimas e evitar a convergência prematura do algoritmo.
Para tentar solucionar estes problema, propõe-se o uso de técnicas híbridas buscando
desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização.
O presente trabalho investiga a eficiência da incorporação de técnicas de Mineração
de Dados (MD) as Meta-heurísticas Populacionais Colônia de Formiga e Algoritmo
Genético com o intuito de guiá-las a gerar novas e melhores soluções. Para a validação
da proposta, serão utilizados o Problema do Caixeiro Viajante e diferentes versões das
meta-heurísticas híbridas serão testadas e analisadas.
A técnica escolhida para guiar a obtenção de novas soluções, a partir dos padrões
obtidos com a Mineração de Dados, foi o de Agrupamento de soluções similares, na
tentativa de reduzir o espaço de busca em problemas de otimização combinatória. O
algoritmos de mineração utilizados são o K-Means e o Ward que utilizam técnicas de
particionamento e hierárquico respectivamente.
Experimentos Computacionais foram realizados com o objetivo de avaliar o uso
de MD em Meta-heurísticas Populacionais tradicionais, atai como Algoritmo Genético
e Colonia de Formiga. Estes experimentos mostraram que a utilização de padrões minerados
podem auxiliar na obtenção de boas soluções em relação as técnicas tradicionais
|
