Navegando por Assunto "Problemas do caixeiro viajante"

Agora exibindo 1 - 2 de 2

Acesso aberto (Open Access)
Algoritmo genético com interação social nebulosa
(Universidade Federal do Pará, 2012-04-19) TEIXEIRA, Otávio Noura; OLIVEIRA, Roberto Célio Limão de; http://lattes.cnpq.br/4497607460894318
Este trabalho apresenta um nova nova metaheurística híbrida e bioinspirada na natureza, baseada em três pilares fundamentais, que são: os Algoritmos Genéticos; a Teoria dos Jogos; e, a Lógica Nebulosa. Assim, o Algoritmo Genético com Interação Social Nebulosa, ou F-SIGA, é fundamentado e caracterizado por permitir aos indivíduos da população a possibilidade de participar do processo de Interação Social. Essa etapa é anterior ao processo de seleção para a geração dos descendentes, e nela eles podem obter ganhos através das disputas com outros indivíduos. Para isso, cada indivíduo é caracterizado por dois cromossomos, sendo um referente a solução do problema em questão; e, o outro, com a codificação genética da sua estratégia de comportamento. Como ambiente de disputas é utilizado o jogo Dilema do Prisioneiro, nas versões de 2-pessoas e N-pessoas, inclusive com a abordagem nebulosa. Além disso, os indivíduos são avaliados por uma função de fitness que engloba: a representação da solução do problema, os ganhos obtidos nas disputas e, ainda, o Fator de Experiència, que utiliza da experiência adquirida pelo indivíduo também como componente para auxiliar no processo evolutivo da população. Esta característica deu origem ao algoritmo ESIA – não previsto inicialmente – onde apenas as informações obtidas nas Interações Sociais são consideradas na seleção dos indivíduos para a etapa de reprodução. Metodologicamente, o trabalho evoluiu para o surgimento do algoritmo ESIA, que é uma nova classe de Algoritmos Evolucionários baseados em Interação Social. Sendo assim, este trabalho apresenta quatro algoritmos: o SIGA, o NpSIGA, o F-SIGA e o ESIA, com suas fundamentações teóricas e, também, resultados práticos ao aplicá-los à problemas de otimização global, com e sem restrições; e, à instâncias do Problema do Caixeiro Viajante.
Acesso aberto (Open Access)
Algoritmos culturais com abordagem memética e multipopulacional aplicados a problemas de otimização
(Universidade Federal do Pará, 2012-04-20) SILVA, Deam James Azevedo da; OLIVEIRA, Roberto Célio Limão de; http://lattes.cnpq.br/4497607460894318
Em muitos problemas de otimização há dificuldades em alcançar um resultado ótimo ou mesmo um resultado próximo ao valor ótimo em um tempo viável, principalmente quando se trabalha em grande escala. Por isso muitos desses problemas são abordados por heurísticas ou metaheurísticas que executam buscas por melhores soluções dentro do espaço de busca definido. Dentro da computação natural estão os Algoritmos Culturais e os Algoritmos Genéticos, que são considerados metaheurísticas evolutivas que se complementam devido ao mecanismo dual de herança cultura/genética. A proposta do presente trabalho é estudar e utilizar tais mecanismos acrescentando tanto heurísticas de busca local como multipopulações aplicados em problemas de otimização combinatória (caixeiro viajante e mochila), funções multimodais e em problemas restritos. Serão executados alguns experimentos para efetuar uma avaliação em relação ao desempenho desses mecanismos híbridos e multipopulacionais com outros mecanismos dispostos na literatura de acordo com cada problema de otimização aqui abordado.