Análise da aprendizagem de ligações em otimização evolutiva (2015)
- Authors:
- Autor USP: MARTINS, JEAN PAULO - ICMC
- Unidade: ICMC
- Sigla do Departamento: SSC
- Subjects: ALGORITMOS GENÉTICOS; MODELOS PARA PROCESSOS ESTOCÁSTICOS; COMPUTAÇÃO EVOLUTIVA
- Keywords: Aprendizagem de ligações; EDAs; EDAs; Linkage-learning; MOEDAs; MOEDAs; Multimodalidade; Multimodality
- Language: Português
- Abstract: A suposta ubiquidade de sistemas decomponíveis foi interpretada por Holland (1975) como o principal motivo para o desempenho dos algoritmos genéticos (Genetic Algorithms (GAs)). A hipótese de Building Blocks (BBs) sugere que algoritmos genéticos mais eficientes poderiam ser implementados, contudo, apenas anos depois essas ideias puderam ser avaliadas experimentalmente no contexto de algoritmos de estimação de distribuição (Estimation of Distribution Algorithms (EDAs)). EDAs utilizam modelos probabilísticos, estimados a partir da população, para inferir características do espaço de busca que poderiam ser utilizadas para implementar operadores de reprodução mais eficazes. Tanto em problemas mono- quanto multi-objetivo, EDAs emergiram sob a premissa de que a eficácia dos operadores de reprodução seria proporcional à representatividade dos modelos probabilísticos utilizados. No entanto, estudos recentes tem demonstrado que a dificuldade em se construir modelos confiáveis pode tornar essa premissa inviável. Ou seja, para certos problemas de otimização os modelos probabilísticos utilizados seriam, em geral, de baixa qualidade e, portanto, não produziriam operadores eficazes. Esta tese trata das limitações encontradas na construção de modelos probabilísticos (linkage learning) sob a perspectiva da multimodalidade dos problemas em questão. A análise teórica considerou problemas aditivamente separáveis, enquanto a generalização das conclusões foi investigada em instâncias do modeloNK-landscapes e do problema da mochila multidimensional (Multidimensional Knapsack Problem (MKP)). Os resultados indicaram que a acurácia dos modelos probabilísticos é se relaciona inversamente ao grau de multimodalidade da função objetivo e que, em casos de extrema multimodalidade a construção de modelos probabilísticos confiáveis pode ser tornar infactível. Este resultado poderia inviabilizar o uso de EDAs no contexto multiobjetivo, devido a intrínseca multimodalidade de tais problemas. No entanto, observou-se que apesar da ausência de estatísticas confiáveis sobre cada uma das funções objetivo, a correlação entre elas se torna estatisticamente observável e útil aos operadores de reprodução na manutenção da diversidade e controle convergência da população
- Imprenta:
- Publisher place: São Carlos
- Date published: 2015
- Data da defesa: 13.05.2015
-
ABNT
MARTINS, Jean Paulo. Análise da aprendizagem de ligações em otimização evolutiva. 2015. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2015. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14092015-140718/. Acesso em: 19 set. 2024. -
APA
Martins, J. P. (2015). Análise da aprendizagem de ligações em otimização evolutiva (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14092015-140718/ -
NLM
Martins JP. Análise da aprendizagem de ligações em otimização evolutiva [Internet]. 2015 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14092015-140718/ -
Vancouver
Martins JP. Análise da aprendizagem de ligações em otimização evolutiva [Internet]. 2015 ;[citado 2024 set. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14092015-140718/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
