TL;DR
Neste post eu quero mostrar a utilização de um framework para computação evolucionária chamado DEAP(Distributed Evolutionary Algorithms in Python). Como o nome já diz é uma lib de algoritmos evolucionários que podem ser rodados de forma distribuidas. Ah, e é em Python! =)
Descobri esse framework quando fui buscar uma solução(em Python) que me auxiliasse em alguns trabalhos da disciplina de Computação Evolucionária que estava fazendo no mestrado. Confesso que no inicio demorei para pegar o jeito, pois a biblioteca tem uma forma peculiar de definir os operadores e funções. Porém depois de compreendido, não quis outra vida! se torna natural pensar nas soluções. Just sit and code!
O que coloco abaixo é um Toy Problem sugerido pelo professor da disciplina. O notebook que eu fiz pode ser encontrado nesse link e tem praticamente o conteudo abaixo(que exportei para colocar aqui no blog)
Você gerencia uma fábrica de garrafas plásticas que tem apenas uma máquina extrusora. Esta máquina pode funcionar até 60 horas por semanda, isto é, 6 dias por semana com jornada de 10 horas por dia. A máquina é capaz de produzir dois tipos de garrafas plásticas: tipo "leite" e tipo "suco". Toda a produção semanal de garrafas plásticas é armazenada temporariamente num depósito. No domingo toda a produção é despachada para os compradores e o depósito é esvaziado completamente.
A linha de produção leva 6 horas para produzir 100 garrafas tipo leite e 5 horas para produzir 100 garrafas tipo suco. Cada Carrafa tipo leite ocupa 10 unidades cúbicas de espaço no depósito, enquanto que a garrafa de tipo suco ocupa 20 unidades cúbicas. O depósito tem capacidade máxima de 15000 unidades cúbicas.
A contribuição no lucro final da empresa por garrafa tipo leite é de 5 unidades monetárias e por garrafa tipo suco é de 4,5. O departamento de vendas tem contratos de fornecimento capazes de absorver toda a produção possível de garrafas tipo suco, porém tem compradores somente para 800 garrafastipo leite por semana.
Você deve estabelecer qual é o plano de produção mais adequado para maximizar o lucro total da empresa, isto é, quantas garrafas tipo Leite e quantos tipoo Suco devem ser produzidas semanalmente.
O DEAP fornece várias bibliotecas que facilitam o trabalho e deverão ser importadas:
- base:
- creator:
- tools:
- algorithms:
Outras blibliotecas auxiliares serão utilizadas nesse tutorial:
- random:
- numpy:
https://gist.github.com/5c3430149ccbc5e432a2a845543e9c79
Como se trata de um problema de maximização criamos essa função conforme a especificação do DEAP
https://gist.github.com/66d5e97f254a8932933f8c2ff901ff8c
Cada problema necessita uma forma particular de modelar o individuo, bem como a população deve ser gerada. Sendo assim os passos que devemos fazer no DEAP são:
- Definir estrutura do individuo(list, set, etc)
- Definir a função que irá gerar os alelos
- Definir a função que irá gerar os individuos
- Definir a função que irá gerar a popuulação
https://gist.github.com/28670affa2a09c55550c14fd042f7657
Essa função ao contrário das outras que são produzidas quase que parametricamente, deve ser impllementada manualmente. Nela é onde o individuo receberá o valor de fitness que corresponde à modelagem funcional do problem. Para o caso deste exemplo em questão temos:
https://gist.github.com/dcd65db029bb94c7207df82dd5bc924c
Para o DEAP são considerados como operadores:
- evaluate: operador para realizar o cálculo de fitness do indivíduo
- mate: operador para realizar cross over de indivíduos
- mutate: operador para realizar a mutação dos
- select: operador para selecionar os melhores de uma geração para outra
Cada um desses operadores deve ser registrado. Seguindo a documentação do DEAP, damos um nome para o operador, seguido da função que ele irá realizar, seguido dos parametros dessa função
https://gist.github.com/03af53c919c2f69e673cfe9bd92f0e6f
Dependendo de cada caso, podemos desejar mostrar relatórios específicos. Para esse problema, criamos duas funçõs. Uma para imprimir os dados de um indivíduo e outra para plotar o gráfico das evoluções das gerações.
https://gist.github.com/1a17ac547766d39c8839bccc73c300f8
Depois de definir toda a estrutura do nosso problema e o comportamento, faz-se necessário implementar o algoritmo que irá rodar. Essa implementação é composta dos parametros do Algoritmo Genético e a logica que manipula a população.
No exemplo abaixo utilizamos uma implementação já fornecida pelo DEAP: o eaSimple que é um algoritmos do livro “Evolutionary Computation 1 : Basic Algorithms and Operators”(cap.7). Neste exemplo também optei poro trazer uma implementação mais enxuta sem mostrar os stats monitorados no console, de modo apenas focarmos no processo como um todo do AG.
https://gist.github.com/6ca33fb96c2d24ff034b62a977a197f3
gen nevals std min avg max
0 70 0.279164 -0.794191 0.222211 0.5251
1 53 0.137051 -0.182224 0.365127 0.521669
2 57 0.104841 -0.18801 0.433291 0.527247
3 62 0.0855094 -0.102859 0.466715 0.5277
4 61 0.0348315 0.347647 0.498005 0.527777
5 58 0.0463223 0.270386 0.501738 0.527926
6 52 0.0528416 0.130146 0.498091 0.527926
7 50 0.169755 -0.666382 0.48663 0.527952
8 44 0.0118609 0.458677 0.524036 0.527952
9 58 0.0480039 0.144649 0.519095 0.527978
10 61 0.0011975 0.523538 0.527375 0.527978
11 58 0.000187768 0.527242 0.527867 0.527978
12 60 0.00671136 0.476925 0.52684 0.527978
13 58 1.28367e-05 0.527926 0.527958 0.527978
14 50 0.000147406 0.527242 0.527935 0.527978
15 62 1.45458e-05 0.527864 0.527974 0.527978
16 46 1.11022e-16 0.527978 0.527978 0.527978
17 53 1.11022e-16 0.527978 0.527978 0.527978
18 58 5.37505e-05 0.527525 0.527971 0.527978
19 52 0.000526875 0.523538 0.527914 0.527978
20 66 1.11022e-16 0.527978 0.527978 0.527978
21 58 1.11022e-16 0.527978 0.527978 0.527978
22 60 1.11022e-16 0.527978 0.527978 0.527978
23 61 1.11022e-16 0.527978 0.527978 0.527978
24 58 1.11022e-16 0.527978 0.527978 0.527978
25 64 0.000424759 0.524464 0.527917 0.527978
26 60 1.11022e-16 0.527978 0.527978 0.527978
27 58 1.11022e-16 0.527978 0.527978 0.527978
28 52 0.00452791 0.494315 0.527231 0.527978
29 60 1.11022e-16 0.527978 0.527978 0.527978
30 64 0.0210769 0.350363 0.52544 0.527978
31 56 1.11022e-16 0.527978 0.527978 0.527978
32 56 1.11022e-16 0.527978 0.527978 0.527978
33 57 1.11022e-16 0.527978 0.527978 0.527978
34 48 1.11022e-16 0.527978 0.527978 0.527978
35 56 1.11022e-16 0.527978 0.527978 0.527978
36 52 1.11022e-16 0.527978 0.527978 0.527978
37 58 1.11022e-16 0.527978 0.527978 0.527978
38 52 0.0177761 0.391521 0.525117 0.527978
39 62 1.11022e-16 0.527978 0.527978 0.527978
40 56 1.11022e-16 0.527978 0.527978 0.527978
41 52 1.11022e-16 0.527978 0.527978 0.527978
42 62 0.000416938 0.524464 0.527927 0.527978
43 54 0.000107501 0.527072 0.527965 0.527978
44 64 0.00171128 0.513557 0.527772 0.527978
45 52 1.11022e-16 0.527978 0.527978 0.527978
46 58 0.00519679 0.48418 0.527341 0.527978
47 54 0.00133758 0.516706 0.527817 0.527978
48 64 1.11022e-16 0.527978 0.527978 0.527978
49 56 0.0312358 0.264753 0.524217 0.527978
50 54 0.0316754 0.261049 0.524164 0.527978
51 52 1.11022e-16 0.527978 0.527978 0.527978
52 50 1.11022e-16 0.527978 0.527978 0.527978
53 54 1.11022e-16 0.527978 0.527978 0.527978
54 56 1.11022e-16 0.527978 0.527978 0.527978
55 66 1.11022e-16 0.527978 0.527978 0.527978
56 56 1.11022e-16 0.527978 0.527978 0.527978
57 54 1.11022e-16 0.527978 0.527978 0.527978
58 52 0.0140437 0.409631 0.526287 0.527978
59 45 0.0312358 0.264753 0.524217 0.527978
60 62 1.11022e-16 0.527978 0.527978 0.527978
Individuo:[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0]
Quantidade de garrafas de leite: 672
Quantidade de garrafas de suco: 394
Lucro: 5133.0
Por hoje é isso. Espero que essa dica tenha ajudado a facilitar a sua vida.
Até mais!