Генетический алгоритм минимизации функции с использованием дискретных значений

Question

Я пытаюсь найти оптимальную комбинацию из 6 дискретных значений, которые принимают любое число от 2 до 16, что возвращает мне минимальное значение функции функции = 1 / x1 + 1 / x2 + 1 / x3 ... 1 / xn

Ограничение состоит в том, что значение функции должно быть меньше 0,3

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

import random 
from operator import add

def individual(length, min, max):
    'Create a member of the population.'
    return [ random.randint(min,max) for x in xrange(length) ]

def population(count, length, min, max):
    """
    Create a number of individuals (i.e. a population).

    count: the number of individuals in the population
    length: the number of values per individual
    min: the minimum possible value in an individual's list of values
    max: the maximum possible value in an individual's list of values

    """
    ##print 'population',[ individual(length, min, max) for x in xrange(count) ]
    return [ individual(length, min, max) for x in xrange(count) ]

def fitness(individual, target):
    """
    Determine the fitness of an individual. Higher is better.

    individual: the individual to evaluate
    target: the target number individuals are aiming for
    """

    pressure = 1/sum(individual)

    print individual
    return abs(target-pressure)

def grade(pop, target):
    'Find average fitness for a population.'
    summed = reduce(add, (fitness(x, target) for x in pop))
    'Average Fitness', summed / (len(pop) * 1.0)
    return summed / (len(pop) * 1.0)

def evolve(pop, target, retain=0.4, random_select=0.05, mutate=0.01):
    graded = [ (fitness(x, target), x) for x in pop]
    print 'graded',graded
    graded = [ x[1] for x in sorted(graded)]
    print 'graded',graded
    retain_length = int(len(graded)*retain)
    print 'retain_length', retain_length
    parents = graded[:retain_length]
    print 'parents', parents 
    # randomly add other individuals to
    # promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random.random():
            parents.append(individual)
    # mutate some individuals
    for individual in parents:
        if mutate > random.random():
            pos_to_mutate = random.randint(0, len(individual)-1)
            # this mutation is not ideal, because it
            # restricts the range of possible values,
            # but the function is unaware of the min/max
            # values used to create the individuals,
            individual[pos_to_mutate] = random.randint(
                min(individual), max(individual))
    # crossover parents to create children
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:

        male = random.randint(0, parents_length-1)
        female = random.randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = len(male) / 2
            child = male[:half] + female[half:]
            children.append(child)        
    parents.extend(children)
    return parents

target = 0.3
p_count = 6
i_length = 6
i_min = 2
i_max = 16
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
    p = evolve(p, target)
    print p
    fitness_history.append(grade(p, target))

for datum in fitness_history:
    print datum

Ожидаемые результаты представляют собой комбинацию значений между 2 и 16, которая возвращает минимальное значение.функции при соблюдении ограничения на то, что функция не может быть больше 0,3.

Answer 1

Порядок, в котором вы выполняете эвристику, очень необычен для генетического алгоритма. Как правило, genetic algorithm следует за шагами:

1. Выберите N * 2 Родителей, используя колесо рулетки или турнир
2. Сократите N * 2 родителей до N детей с помощью кроссовера
3. видоизменяют некоторых из этих детей N
4. Создайте следующее поколение, используя смену поколений, возможно, с элитарностью (сохраняя лучшее решение от старого населения)
5. Повтор 1

Другой немного другой подход называется evolution strategy (ES), но он также работает по-другому. Ни один из известных мне эволюционных алгоритмов не использовал кроссовер в конце. В ES кроссовер используется для расчета центроида индивидуума населения и использовать его в качестве базы для мутации. Все мутанты центроида затем образуют следующее поколение. В ES также следующее поколение формируется с использованием только нового поколения (выбор через запятую - требует пересчета текущего родительского поколения) или с использованием старого и нового поколения (плюс выбор). ES выполняет

1. Рассчитать решение центроида от населения
2. Создание решений для лямбда-потомков путем мутации центроида (как правило, в ES вы можете регулировать «силу мутации» в ходе поиска)
3. Замените следующее поколение (мю-решения), используя лямбда-потомство или лямбда-потомство + мю-решения, отсортировав и взяв лучшие
4. Повтор 1

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

Также не принято вводить в поиск случайных людей. Вы уверены, что вам нужно сохранить разнообразие для вашей проблемы? Это дает лучшие результаты, чем без, или, может быть, дает вам еще худшие результаты? Простая альтернатива состоит в том, чтобы обнаружить сходимость и выполнить перезапуск всего алгоритма, пока не достигнете критерия остановки (тайм-аут, количество сгенерированных индивидуумов и т. Д.).

Кроссовер и мутация в порядке. Однако в одноточечном пересечении обычно выбирается точка пересечения случайным образом.

Еще одно наблюдение: функция пригодности в вашем описании и функция, реализованная в вашем коде, не совпадают.

1/(x1 + x2 + ... + xn)

не равно

1/x1 + 1/x2 + ... + 1/xn