угадывание строки генетического алгоритма

Я пытаюсь понять, как реализовать генетический алгоритм, и написал простое предположение строки. Мне трудно понять, почему это решение не работает.

Я считаю, что моя проблема в том, что я заселяю свои новые поколения? Новые поколения, похоже, не имеют улучшенных показателей физической подготовки. Я также не уверен, правильно ли я выполняю кроссовер и частоту мутаций. Любая помощь могла бы быть полезна!

POP_SIZE = 300;
CROSSOVER_RATE = 0.7;
MUTATION_RATE = 0.01
GENESET = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"
target = "Hello World"
RAND_NUM = random.random()

def generateBasePopulation(population_size):
    population = dict()

    for _ in range(POP_SIZE):
        gene = generateParent(len(target))
        population[gene] = 0

    return population


def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while(len(newPopulation) <= POP_SIZE):
        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)


    newPopulation[child] = 0
    newPopulation[child_two] = 0
    return newPopulation



def assignFitness(population):
    for x in population:
        population[x] = getFitness(x)


def generateParent(length):
    genes = list("")
    for i in range(0,length):
        random_gene = random.choice(GENESET)
        genes.append(random_gene)
    return(''.join(genes))

def getFitness(candidate):
    fitness = 0
    for i in range(0, len(candidate) - 1):
        if target[i] == candidate[i]:
            fitness += 1
    return(fitness)

def mutate(parent):
    gene_index_to_mutate = random.randint(0, len(parent) - 1)
    mutation_value = random.choice(GENESET)
    genes = list(parent)
    genes[gene_index_to_mutate] = mutation_value
    return(''.join(genes))

def crossover(parentA, parentB):
    if(RAND_NUM < CROSSOVER_RATE):
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)
    return parentA, parentB


def chooseChild(population):
    fitnessSum = sum(population.values())
    pick = random.uniform(0, fitnessSum)
    current = 0
    for pop in population:
        current += population[pop]
        if current >= pick:
            return pop


def main():
    population = generateBasePopulation(POP_SIZE)

    targetNotFound = True

    while(targetNotFound):
        assignFitness(population)
        if target in population:
            print("target found!")
            targetNotFound = False
        if(targetNotFound):
            tempPopulation = generateNewPopulation(population, POP_SIZE)
            population.clear()
            population = tempPopulation

python-3.x python genetic-algorithm evolutionary-algorithm
person keebler    schedule 27.11.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Есть некоторые проблемы с функцией generateNewPopulation.

child_one и child_two упоминаются перед присваиванием

Вам нужно два человека из населения, чтобы выполнить кроссовер. Существует несколько алгоритмов отбора, но для общего представления вы можете начать с формы выбора турнира:

def extractFromPopulation(population):
    best = random.choice(list(population.keys()))

    for _ in range(4):
        gene = random.choice(list(population.keys()))
        if population[gene] > population[best]:
            best = gene

    return best

Здесь давление отбора (range(4)) фиксировано. Это один из параметров, который вы должны настроить в реальном случае.

Теперь у нас есть:

def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while len(newPopulation) <= POP_SIZE:
        child_one = extractFromPopulation(population)
        child_two = extractFromPopulation(population)

    # ...

Код по-прежнему не работает, потому что

новые лица не вставляются в newPopulation

Просто сделайте отступ между двумя строками:

newPopulation[child] = 0
newPopulation[child_two] = 0

(они должны быть частью цикла while)

Пересмотренная функция generateNewPopulation выглядит следующим образом:

def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while len(newPopulation) <= POP_SIZE:
        child_one = extractFromPopulation(population)
        child_two = extractFromPopulation(population)

        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)

        newPopulation[child_one] = 0
        newPopulation[child_two] = 0

    return newPopulation

Функция crossover не может основываться на фиксированном значении RAND_NUM.

Удалите назначение RAND_NUM = random.random() и измените функцию crossover, чтобы использовать новое случайное значение при каждом вызове:

def crossover(parentA, parentB):
    if random.random() < CROSSOVER_RATE:
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)

    return parentA, parentB

Также код неправильно выполняет одноточечное пересечение, поскольку схемы второго родителя не сохраняются.

Вы можете изменить многие детали, чтобы улучшить производительность, но в качестве начального примера этого, вероятно, достаточно (... это работает).

Среднее количество поколений для поиска решения составляет около 158 (в среднем по 200 запускам).

РЕДАКТИРОВАТЬ (спасибо alexis за комментарий)

MUTATION_RATE не используется, и всегда происходит мутация. Функция mutate должна выглядеть примерно так:

def mutate(parent):
    if random.random() < MUTATION_RATE: 
        gene_index_to_mutate = random.randint(0, len(parent) - 1)
        mutation_value = random.choice(GENESET)
        genes = list(parent)
        genes[gene_index_to_mutate] = mutation_value
        return ''.join(genes)

    return parent

Это исправление особенно важно, если вы сохраняете алгоритм выбора колеса рулетки (chooseChild часто не сходится без исправления).

person manlio    schedule 28.11.2017
comment
Я считаю, что в коде OP дети должны быть выбраны с помощью chooseChild(), который определен, но не используется (и выбирает с вероятностью, пропорциональной пригодности, которая должна будет управлять улучшениями). - person alexis; 28.11.2017
comment
@alexis Вы правы, я пропустил эту функцию. Вероятно, в коде OP дети должны выбираться с помощью chooseChild(). В любом случае предложенные изменения должны оставаться в силе. - person manlio; 28.11.2017
comment
@alexis Спасибо за комментарий, возникла еще одна проблема (связанная с процедурой mutation()), но она возникла только при попытке выполнить функцию chooseChild(). - person manlio; 29.11.2017