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.