ALGORITMOS GENÉTICOS INTRODUÇÃO • São métodos adaptativos que podem ser usados para resolver problemas de busca e otimização. • Na natureza a combinação de boas características provenientes de diferentes indivíduos ancestrais pode produzir descendentes “superindivíduos”, cuja adaptação é muito maior que a de seus ancestrais. • Os algoritmos genéticos usam uma analogia direta com o comportamento natural. INTRODUÇÃO • A cada indivíduo se associa um grau de aptidão, que determina a sua capacidade de competir com os demais membros da população. • Basicamente os algoritmos genéticos tratam problemas de otimização como um processo iterativo de busca da melhor solução dentro do espaço de possíveis respostas para o problema. ALGORITMO GENÉTICO SIMPLES I nício Gerar população i nicial Calcular a f unção de avaliação para os i ndivíduos novos Calcular a f unção de aval iação de c ada i ndivíduo I ncluir os descendentes na nova geração Enquanto não t erminar f aça I nício F im Para ( t amanho da população / 2 ) f aça S e população c onvergiu e ntão Terminou - > verdade I nício S elecionar dois i ndivíduos Real izar o c ruzamento Apl icar mutação nos descendentes f im f im COMO FUNCIONA • Inicia com um conjunto aleatório de soluções iniciais, que constituem a população inicial. • Combinando os melhores representantes dessa população, obtém uma nova, que passa a substituir a anterior, caracterizando-se como a próxima geração. • O mecanismo é repetido. • A cada nova iteração a população é refinada gerando novas e melhores soluções para o problema em questão, culminando com a sua convergência. ALGORITMO GENÉTICO SIMPLES • Os indivíduos componentes da população (possíveis soluções do problema) podem ser representados como um conjunto de parâmetros (denominados genes). • A adaptação de um indivíduo ao problema depende de seu genótipo. • A função de adaptação deve ser projetada para cada problema. ALGORITMO GENÉTICO SIMPLES • A função de avalição ou função fitness associa as características do indivíduo a um número. • No caso de binário indicam a presença ou não de uma determinada característica. OPERAÇÕES BÁSICAS • CrossOver (cruzamento): é uma operação binário que a partir de dois indivíduos produz outros dois novos indivíduos utilizando uma recombinação dos cromossomos. 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 0 0 0 OPERAÇÕES BÁSICAS • Mutação: é uma operação unário que altera um gene de um indivíduo da população. 1 1 0 1 1 0 0 1 1 0 0 1 1 Ponto de cruzamento Novo i ndivíduo 0 0 EXEMPLO • 1 – Aplique algoritmo genético para encontrar uma boa solução para otimizar a função. F(x) = -x2 + 3x + 5 EXEMPLO • 1º passo: Definir a população inicial. • como a solução ótima é menor do que 5, vamos representar no formato binário números maiores que zero e menores do que 5, portanto números de 3 bits. • Universo [o,7] I1 1 1 1 I2 0 0 0 * I 1 e I 2 podem ser escolhidos aleatoriamente, ou não, na população. EXEMPLO • 2º passo: Escolher a função de avaliação. Neste caso utilizaremos a função que será otimizada, pois quanto maior o valor desta função, mais próximo do máximo locar ela estará. EXEMPLO • 3º passo: Avalição dos indivíduos I1 1 1 1 = 7 -> f (7) = -49+21+5 = -23 I2 0 0 0 =0 -> f (0) = -0 + 0 + 5 = 5 EXEMPLO • 4º passo: Cruzamento – seleção do ponto do cruzamento – neste caso escolheu-se o ponto 1 I3 -> 0 I1 1 1 1 I2 0 0 0 -> 1 I4 1 1 = 3 -> f (3) = -9+9+5 = 5 0 0 = 4 -> f (4) = -16+12+5 = 1 EXEMPLO • 5º passo: aplicar a mutação em um indivíduo I3 0 1 1 Ponto de mutação I5 -> 0 1 0 = 2 -> f (2) = -4+6+5 = 7 EXEMPLO • Rank Rank I1 -23 I2 5 I3 5 I4 1 I5 7 Rank I5 7 I2 5 I3 5 I4 1 I1 -23 Como a população não está estável, replicaremos o algoritmo EXEMPLO • 4º passo: Cruzamento – como a população possui 4 elementos, faremos 2 cruzamentos. I6 -> 0 I5 0 1 0 I2 0 0 0 -> 0 I7 1 0 = 2 -> f (2) = -4+6+5 = 7 0 0 = 0 -> f (0) = -0+0+5 = 5 EXEMPLO • 4º passo: Cruzamento – como a população possui 4 ou mais elementos, faremos 2 cruzamentos. I8 -> 0 I5 0 1 0 I3 0 1 1 -> 0 I9 1 1 = 3 -> f (3) = -9+9+5 = 5 1 0 = 2 -> f (2) = -4+6+5 = 7 EXEMPLO • 5º passo: Mutação, o I 8 foi escolhido aleatoriamente I8 0 1 1 Ponto de mutação I 10 -> 0 0 1 = 1 -> f (1) = -1+3+5 = 7 EXEMPLO • Rank após duas gerações Rank I1 -23 I2 5 I3 5 I4 1 I5 7 I6 7 I7 5 I8 5 I9 7 I 10 7 Rank I5 7 I6 7 I9 7 I 10 7 I2 5 I3 5 I7 5 I8 5 I4 1 I1 -23 Entre os quatro melhores, a população se estabilizou em avaliação 7. EXEMPLO • Rank após duas gerações Rank I5 7 I6 7 I9 7 I 10 7 I2 5 I3 5 I5 0 1 0 = 2 -> f (2) = -4+6+5 = 7 I 10 0 0 1 = 1 -> f (1) = -1+3+5 = 7 I7 5 I8 5 I4 1 Assim, o ponto ótimo está entre I 5 = 2 e I 10 = 1 [1,2] I1 -23