Trepar em paralelo

O algoritmo trepa-colinas convencional melhora iterativamente uma solução olhando na sua vizinhança. Sabemos que um dos problemas maiores desta abordagem consiste na elevada probabilidade de o algoritmo convergir para um máximo local. Uma forma de tentar minorar esse problema é permitir que o algoritmo recomece de tempos a tempos a partir de um novo ponto escolhido aleatoriamente. Uma outra solução consiste em ter um conjunto de indivíduos a evoluir em paralelo,. Dito de outra forma, cada indivíduo da população evolui com base num trepa colinas convencional. A implementação desta versão não coloca muitos problemas.

import random
import operator
import copy

def paralell_hc(population_size, problem,max_iter):
    population = random_pop(problem, population_size)
    population = fitness_pop(population)
    for i in range(max_iter):
        for index,individual in enumerate(population):
            candidate,fit_candidate = individual
            # look for the first best
            for pos in range(len(candidate)):
                next_neighbor = neighbor(candidate,pos)
                cost_next_neighbor = fitness(next_neighbor)
                if cost_next_neighbor >= fit_candidate: # maximization
                    candidate = next_neighbor
                    fit_candidate = cost_next_neighbor
                    break
            population[index] = [candidate,fit_candidate]
    population.sort(key = operator.itemgetter(1))  
    return population

Notar que todos os indivíduos tentam evoluir e de forma autónoma. O trepa colinas individual é muito simples e escolhe a cada passo o primeiro vizinho melhor que o progenitor, caso exista.

Execute-se

Os algoritmos de inspiração biológica são algoritmos estocásticos. Significa isso, dentre outras coisas, que duas execuções consecutivas do mesmo algoritmo, mesmo com a mesma parametrização e população inicial dá, em geral, resultados diferentes. Daí que seja necessário executar os algoritmos várias vezes a analisar os resultados obtidos do ponto de vista estatístico, por exemplo, indicado os valores médios e o desvio padrão. Podemos alterar o nosso código acrescentando em particular uma nova função responsável pelas várias execuções e armazenamento dos resultados.

import matplotlib.pyplot as plt
from random import random,randint, shuffle, uniform,sample
from operator import itemgetter
from math import sqrt
from copy import deepcopy

def run(numb_runs,numb_generations,size_pop, size_cromo, prob_mut,prob_cross,selection,recombination,mutation,survivors, fit_func, phenotype,elite,t_size):
    best,average = sea(numb_generations,size_pop, size_cromo, prob_mut,prob_cross,selection,recombination,mutation,survivors, fit_func, phenotype,elite,t_size)
    best_of_best = [best]
    average_of_average = [average] 
    for i in range(numb_runs-1):
        best,average = sea(numb_generations,size_pop, size_cromo, prob_mut,prob_cross,selection,recombination,mutation,survivors, fit_func, phenotype,elite,t_size)
        best_of_best.append(best)
        average_of_average.append(average)
    best_by_gener = list(zip(*best_of_best))
    average_by_gener = list(zip(*average_of_average))
    data_best = [max(elem) for elem in best_by_gener]
    data_average = [sum(elem)/len(elem) for elem in average_by_gener]
    display(data_best, data_average)

Como se pode observar a função run chama o algoritmo evolucionário várias vezes, e espera que este devolva os valores do melhor indivíduo em cada geração e a média da qualidade dos indivíduos da população, também aqui em cada geração.

Por outro lado, a visualização é feita de modo simples, estando implementada para o caso concreto dos números de João Brandão.

def display(best,average):
    x = list(range(len(best)))
    plt.title('João Brandão using a Simple EA.')
    plt.xlabel('Generation')
    plt.ylabel('Fitness')
    plt.grid(True)
    plt.plot(x,best, label='Best')
    plt.plot(x,average, label='Average')
    plt.legend(loc='lower right')
    plt.show()

Estes gráficos são muito informativos e devemos aprender a interpretá-los. Dizem-nos, por exemplo, quantas gerações foram necessárias em média para alcançar a melhor solução; quando o valor do melhor e a média estão muito juntas significa uma perda de diversidade da população (e se isso acontece muito cedo indicia convergência prematura); se o melhor e a média estão muito afastados pode querer dizer que tivemos sorte a encontrar um elemento muito bom (o que pode acontecer por o problema ser muito difícil).

Ver para crer

Os algoritmos evolucionários são processos estocásticos que fazem uma procura paralela no espaço das soluções candidatas. Aprende-se muito sobre o funcionamento destes algoritmos vendo o modo como a qualidade dos indivíduos evolui ao longo das gerações. Esta breve nota destina-se a exemplificar de modo simples como se pode usar o módulo matplotlib do python para visualizar o resultado das execuções destes algoritmos.

O caso mais simples de gráfico é aquele em que temos os dados e mandamos fazer o gráfico correspondente. Não precisamos de muito:

import matplotlib.pyplot as plt

def visual_1(data):
    plt.plot(data)
    plt.show() 

Podemos começar com a cosmética, dando um título ao gráfico, nomes aos eixos, incluir uma grelha, acrescentar uma legenda, desenhar mais do que uma função, salvar o ra imagem num ficheiro:

import matplotlib.pyplot as plt

def visual_5(data_1,data_2):
    x = list(range(1,len(data_1)+1))
    plt.title('Two plots ')
    plt.grid(True)
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.plot(x,data_1, label= 'Log')
    plt.plot(x,data_2,label= 'Sqrt')
    plt.legend(loc='lower right')
    plt.savefig('/Users/ernestojfcosta/tmp/matplotlib_test.png')
    plt.show() 

Podemos controlar o aspecto das linhas:

def visual_6(data_1,data_2):
    x = list(range(1,len(data_1)+1))
    plt.title('Two plots ')
    plt.grid(True)
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.plot(x,data_1, 'r-o',label= 'Log')
    plt.plot(x,data_2,'g-.v',label= 'Sqrt')
    plt.legend(loc='lower right')
    plt.savefig('/Users/ernestojfcosta/tmp/matplotlib_test.png')
    plt.show() 

Nos exemplos acima os dados foram calculados antes de chamar a função de visualização. Mas podemos ter soluções diferentes. Por exemplo, podemos ter como argumento a função e o intervalo de valores de ‘X’ e o incremento:

def display_3(f, x_min, x_max, delta=0.001):
    """Compute values and display."""
    x = list(drange(x_min, x_max,delta))
    y = [f(i) for i in x]
    plt.title(f.__name__)
    plt.grid(True)
    plt.xlabel('X')
    plt.ylabel('Y= '+f.__name__ + '(X)')
    plt.plot(x,y, 'r')
    plt.show()
    
 def drange(start,stop,step=0.1):
    """ range for floats."""
    number = start
    while number < stop:
        yield number
        number += step

Veja-se o modo como se obtém o título do gráfico. Note-se ainda o uso de drange para gerar valores com um intervalo delta definido pelo utilizador. Para os leitores conhecedores de python podemos não usar drange se passarmos para arrays disponibilizados pelo módulo numpy:

import matplotlib.pyplot as plt
import numpy as np

def visual_22(data):
    plt.title('One more example...')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.plot(data)
    plt.show() 

if __name__ == '__main__':
    data_6 = [i**2 for i in np.arange(1,10,0.01)]
    visual_22(data_6)

Também podemos fazer gráficos 3D ... mas isso custa um pouco mais. Vejamos um casos ilustrativo.

from mpl_toolkits.mplot3d import Axes3D
from matplotlib import cm
import matplotlib.pyplot as plt
import numpy as np

def rastrigin():
    fig = plt.figure()
    fig.suptitle('Rastrigin', fontsize=18, fontweight='bold')
    ax = Axes3D(fig)
    
    
    X = np.arange(-5.12, 5.12, 0.1)
    Y = np.arange(-5.12, 5.12, 0.1)
    
    X, Y = np.meshgrid(X, Y)
    Z = 10*(X**2 - 10* np.cos(2*3.14159*X)) + 20*(Y**2 - 10* np.cos(2*3.14159*Y))
    
    ax.plot_surface(X, Y, Z, rstride=1,cstride=1,cmap=cm.jet)
    ax.legend()
    plt.show()

if __name__ == '__main__':
    rastrigin()

Agora o leitor interessado só tem que de consultar o manual do Matplotlib para ver a multiplicidade de possibilidades.