Dilema do prisioneiro
Por: Alexandre Azevedo Oliveira • 30/11/2015 • Pesquisas Acadêmicas • 599 Palavras (3 Páginas) • 419 Visualizações
Emprego de algoritmo Genético para resolução do problema do prisioneiro- CIC260
Alexandre Azevedo Oliveira - 28920
Sumário
Conteúdo
Introdução
Implementação
Resultados
Introdução
A linguagem escolhida para a implementação do algoritmo genético foi java devido à questão de familiaridade. IDE Eclipse apresenta complementos que podem ser baixados para auxiliar a criação de algoritmos genéticos, mas como a intenção era implementar uma rede neural do início, não foram utilizados. Apesar de simples, o problema pode ser modelado de diferentes formas, portanto, a modelagem do problema será apresentada na seção que trata sobe a implementação.
Implementação
A implementação foi realizada utilizando a IDE Eclipse, sem o auxílio de ferramentas específicas para trabalhar com algoritmos genéticos.
A classe Jogador possui um atributo do tipo inteiro chamado pontos, cujo valor é zero sempre que um novo objeto do tipo jogador é instanciado. Outro atributo da classe jogador é o atributo do tipo ArrayList cromossomo, uma lista de tamanho definido pela variável ngenes, no programa principal, cujos elementos são 0 ou 1. O atributo cromossomo representa o conjunto de jogadas realizadas por um jogador. Caso uma determinada posição da lista tenha valor 0, indica que nessa determinada jogada, o jogador toma a decisão de trair seu comparsa; caso seja 1, indica que o jogador decidiu cooperar. Ao instanciar um objeto do tipo Jogador, a lista é gerada de forma aleatória.
No programa principal, a variável njogadores indica o número de objetos do tipo Jogador que devem ser instanciados. Após criar os jogadores, um laço de repetição realiza as jogadas de todos os jogadores entre si, através do método jogar. O método jogar compara todos as posições de todos dois determinados jogadores e atribui as pontuações a cada jogador, de acordo com a tabela proposta pelo enunciado. Após isso, é realizada a seleção, com o método selecao(), que descarta os jogadores com a menor pontuação. Em seguida,o método cruzamento() cria dois novos jogadores a partir de dois já existentes: a partir de um ponto aleatório, que divide os dois jogadores iniciais em duas partes, a primeira parte do primeiro jogador e a segunda parte do segundo jogador constituem um novo jogador, e outro jogador é gerado unindo a segunda parte do primeiro jogador com a primeira parte do segundo. Em seguida, os jogadores que não foram descartados na seleção são cruzados dois a dois, gerando dois novos jogadores. A variável mut controla a frequência das mutações, que ocorrem através da função mutacao(), onde, após o cruzamento, um determinado jogador pode ter uma posição de seu atributo cromossomos alterada de 0 para 1 ou de 1 para 0. Após isso, a pontuação dos jogadores é zerada e o processo é repetido, tantas vezes quanto a variável ngeracoes indicar.
Ao final da execução, o melhor elemento é apresentado.
Resultados
Ao executar o programa, com os mais variados números de genes, gerações e jogadores, os jogadores vencedores, em sua maioria, possuem um grande número de zeros (jogadas em que o jogador trai o parceiro) e um pequeno número de uns (jogadas em que o jogador coopera com o parceiro), como por exemplo: 001000000000000010001000000000 e 010000000000100000000000000000.
...