Aprendizagem e busca local em algoritmos meméticos para projeto assistido por computador

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

29/02/2008

RESUMO

O projeto assistido por computador (PAC) é um processo de projeto automatizado, caracterizado pela associação de um modelo matemático e computacional do dispositivo a ser otimizado e uma técnica de busca automática, um método de otimização, adequada para encontrar os valores ótimos para os parâmetros de projeto. Entretanto, este processo de PAC automatizado frequentemente requer muitas consultas ao programa de análise até que um protótipo que satisfaça as especificações e requisitos definidos pelo projetista seja encontrado. Como o programa de análise geralmente utiliza um método numérico caro do ponto de vista computacional, é importante que o método de otimização realize sua tarefa com o mínimo de consultas a esse programa. Nas últimas décadas, algoritmos evolucionários, uma classe especial de métodos de busca global, tem se estabelecido como ferramentas poderosas na solução de problemas de PAC. Porém, recentemente os algoritmos meméticos ou algoritmos híbridos têm recebido uma atenção crescente por parte dos pesquisadores devido ao seu potencial de superar o desempenho de algoritmos evolucionários em diversos contextos. Algoritmos meméticos em geral se beneficiam de operadores de busca local que são acrescidos aos operadores usuais de algoritmos evolucionários. Contudo, no contexto de otimização com variáveis cont´nuas em PAC, o custo computacional de operadores de busca local torna seu uso proibitivo. Este custo pode ser reduzido com o emprego de técnicas de aproximaçãoo de funções, dessa forma, tornando os algoritmos meméticos ferramentas de uso prático em PAC. Os principais objetivos desta tese são investigar, implementar e testar o uso de aproximações locais em um arcabouço de algoritmos meméticos para a solução de problemas de PAC, em particular o projeto de dispositivos eletromagnéticos. Esta tese pretende contribuir para a investigação e desenvolvimento dos algoritmos meméticos, com foco especial em problemas cuja avaliação de funções envolve cálculos complexos e computacionalmente caros. Neste contexto, a complexidade adicional no algoritmo seria claramente justificável. Com este propósito, este trabalho organiza, desenvolve e implementa um arcabouço para otimização evolucionária dedicada a problemas de PAC. Este arcabouço acomoda diversos algoritmos evolucionários disponíveis na literatura para otimização mono e multi-objetivo, incluindo é claro os algoritmos meméticos. Estes algoritmos são unificados em sua implementação através da identificação de uma estrutura comum. Cada algoritmo implementado pode utilizar a busca local baseada em aproximações proposta nesta tese. Este operador utiliza a t´ecnica de interpola¸cao multiqu´adrica para construir uma aproximação local para cada função objetivo e de restrição não linear do problema, e o método de programação quadrática sequencial para resolver a versão local do problema global. Para o operador multi-objetivo, um passo adicional deve ser feito, no qual o problema multi-objetivo é transformado em um problema mono-objetivo com restrições adicionais através da formulação de realização de metas. Esta tese também apresenta uma análise formal de algoritmos meméticos. Esta análise é dividida em duas partes. A primeira parte investiga o efeito do operador de busca local nas propriedades de convergência global de algoritmos evolucionários típicos por meio da teoria de cadeias de Markov. A segunda parte estuda o custo computacional de algoritmos meméticos. Nesta parte, a complexidade computacional dos operadores de busca local é obtida e expressoes para a carga extra da busca local são desenvolvidas. Esta análise conduziu aos seguintes resultados importantes sobre a metodologia de busca local proposta: (i) O algoritmo memético preserva as propriedades de convergência global de algoritmos evolucionários padrão. Quando o algoritmo memético emprega a busca local Lamarckiana e um operador de mutação irredutível, será globalmente convergente se o número de indivíduos selecionados para a busca local for menor do que o tamanho da população, i.e., se <. (ii) O algoritmo memético preserva a complexidade polinomial de algoritmos evolucionários padrão. A complexidade da busca local é dominada por um termo que é quadrático com NL, o número máximo de pontos no conjunto de dados local. (iii) a carga extra da busca local pode ser reduzida se a busca local não for usada em toda geração, o que permite que se empregue valores mais elevados para e nTR, o número de atualizações da região de confiança. Este é o compromisso entre a frequência e a intensidade da busca local. No total seis problemas são discutidos. Três funções analíticas de teste sem restrições; um problema magnetostático irrestrito, o projeto da forma do pólo de um dispositivo magnetizador; e duas versões de um problema magnetostático restrito, o conhecido problema de teste 22. As três funções analíticas de teste são usadas para ilustrar o aumento navelocidade de convergência devido à busca local baseada na aproximação multiquádrica. O problema do magnetizador mostra que a carga extra imposta pela busca local baseada em aproximações é insignificante quando tratamos funções computacionalmente caras. As funções analíticas são rápidas de avaliar, logo o algoritmo memético consumiu mais tempo do que o algoritmo genético, mas esta situação se inverte claramente quando o tempo de avaliação aumenta. A versão mono-objetivo do problema 22 foi usada aqui como um exemplo representativo de problemas de PAC em eletromagnetismo aplicado. Doze algoritmos evolucionários diferentes são combinados com a busca local baseada na aproximação multiquádrica. O experimento mostra que todos os algoritmos evolucion vários testados se beneficiaram do uso do operador de busca local. Esta ´e uma evidência empírica que, para a classe de problemas delimitada nesta tese, os algoritmos evolucionários em geral podem ser bastante melhorados com a sua associação com os operadores de busca local baseados em aproximações. A versão bi-objetivo do problema 22 foi usada para ilustrar o operador de busca local multi-objetivo baseado em aproximação multiquádrica. Os resultados também mostram que todos os três algoritmos meméticos multi-objetivo tiveram um desempenho melhor do que suas versões genéticas. A busca local melhorou não somente a velocidade de convergência medida pela métrica S-metric, mas melhorou também a qualidade dos conjuntos obtidos, considerando as métricas NDCSR e S-metric.

ASSUNTO(S)

engenharia elétrica teses.

ACESSO AO ARTIGO

Documentos Relacionados