Delta xis

Você já imaginou estudar inteligência artificial e biologia ao mesmo tempo? Bem, é o que conseguimos fazer ao estudar este algoritmo. Usa menos tempo de processamento porque, bem, usa uma tática semelhante à dos cromossomos. A programação dinâmica aproveita respostas já exploradas pelo algoritmo da memória para solucionar os mesmos problemas.

Tradicionalmente, este assunto é abordado com o exemplo do problema da mochila. Quantas coisas é possível carregar em uma mochila? Uma mochila pesada necessariamente contém as coisas mais importantes para seu cotidiano? Uma mochila entulhada de cacarecos necessariamente fica pesada? É aqui que entram os conceitos de valores e pesos. Ouso dizer que poderíamos até deixar a metáfora da mochila de lado, por um instante, e usar uma relacionada às compras no supermercado. E repito as perguntas acima.

Eu, em particular, sem perceber, aplicava um pouco os conceitos de algoritmo genético ao guardar as compras em meu carro sem saber. Como não uso sacolas, guardo tudo em caixas ou sacolas de feira. Cada produto tem um valor e um peso, e não posso guardá-los a esmo, então guardo as compras sempre de forma categorizada. Latas e garrafas são as primeiras coisas a serem guardadas no fundo da caixa, seguido de alimentos vendidos em pacotes, e as coisas mais leves, como ovos, frutas e verduras, ficam por último na caixa. Agora, quando eu levo uma caixa de leite com 12 unidades, aí tenho um peso grande demais para ser combinado com outros produtos. Como o objetivo do algoritmo genético é que nossa mochila tenha o máximo valor possível, é preciso tomar a decisão: o valor da caixa de leite compensa em relação ao valor dos outros víveres que estou levando?

Um cromossomo é a combinação de possibilidades que será apresentada entre um conjunto de soluções. Pode ser representado por string, e vou poupá-los do vício do programador-alfabeto: moch[i] = 1 indica que o objeto foi incluído na mochila; moch[i] = 0 indica o oposto. Agora, lembre-se do conceito de índice, que as linguagens de programação usam. O primeiro item começa com 0, e nesse algoritmo não é diferente. Quando vemos um cromossomo representado pela string “1001”, sabemos que os itens 0 e 3 foram incluídos na mochila, e os itens 1 e 2, não.

A função de avaliação, ou fitness, indica a qualidade da solução proposta por um cromossomo. Consiste na soma dos valores dos elementos incluídos na mochila. Uma pequena alteração é feita caso o peso dos elementos incluídos ultrapasse o limite da mochila: atribuímos o valor 1, ou outro valor baixo, ao valor de avaliação, para evitar descartar o cromossomo (pois seus descendentes ainda podem fornecer uma boa solução) e reduzir o número de descendentes nas gerações seguintes.

Voltemos à metáfora das compras do supermercado: você gosta de um salgadinho, mas o valor dele está alto demais. Compensa comprometer a economia feita com outros produtos só para levar esse mimo carregado de sódio? Seria possível reduzir seu valor levando, por exemplo, uma quantia menor dele?

E a analogia com biologia não para por aí: temos também o crossover. Novos cromossomos podem ser gerados com fusão (desculpem a cacofonia) das características de outros dois cromossomos. Em outras palavras, pegue sua faca de cozinha, corte um bolo e combine esta fatia em outro. Sim, é só isso que o crossover faz. Por exemplo, se você possui dois cromossomos, 10011 e 01000, com ponto de corte 3, os novos cromossomos ficam assim:

Cromossomos-pai
10011 🔪100🔪11
01000🔪010🔪00
Cromossomos-filho
10000 👉 100 (do primeiro pai) 👉 00 (do segundo pai)
01000 👉 010 (do segundo pai) 👉 11 (do primeiro pai)

E é isso.

Nota: todo o cálculo será feito pelo algoritmo, então esta parte pode soar teórica demais. A seleção dos pais que vão passar pelo processo de crossover é feita por sorteio, utilizando-se o fitness de cada cromossomo para direcionar o processo. Para isso, cria-se uma lista com o valor da soma do fitness de todos os cromossomos, incluindo o cromossomo naquele ponto. Em seguida, um número aleatório é gerado entre 0 e a soma de todos os valores de avaliação, e escolhemos o cromossomo que tem a posição da lista em que o número aleatório é menor do que a soma naquela posição e maior do que o da posição anterior. Chamamos esse método de roleta viciada, visto que a lista age como uma roleta que, em vez de ter seus encaixes igualmente espaçados, tem seus encaixes espaçados proporcionalmente ao valor do fitness de cada cromossomo.

Os cromossomos que foram gerados por crossover e mutação serão usados como população para a nova geração. Esse processo é um ciclo, e no algoritmo definimos condições para encerramento do ciclo, como a definição de um número máximo de ciclos.