Блог

Я написал простой генетический алгоритм, предназначенный для выполнения подгонки. То есть, учитывая некоторый ввод f(x) , я могу решить для x , не зная f (и, на самом деле, an f(x) даже не обязательно существовать). Мой процесс выглядит следующим образом:

1. Я генерирую некоторые начальные точки, равномерно распределенные по известному интервалу решения 0,1 .
2. Затем я повторяю, пока не достигну некоторого максимального количества поколений. С каждой итерацией я:

   а) Отсортируйте текущий набор точек по минимальной ошибке (ошибка RSS), сохраните их в parents списке

   б) Сохраните первый 500 и добавьте несколько случайно выбранных точек из начального списка

   c) 1/2 точек из parents списка, который я «размазываю», генерируя новую распределенную точку, взятую из гауссова со средним значением, заданным выбранной точкой

   d) Теперь я заполняю оставшиеся «пустые слоты» в parents списке, создавая «дочерние элементы». Дочерние элементы создаются путем случайного выбора двух точек из parents списка и получения их среднего значения ( (male female)/2 ).

   e) Наконец, я устанавливаю начальный список равным родительскому списку и возвращаюсь к a)

В конце я сортирую список в последний раз и выбираю первый элемент, который будет решением.

Смотрите код ниже

В итоге я получаю несколько приемлемое решение. Кажется, что он на удивление быстро переходит к окрестности решения, но затем не может добиться значительного прогресса оттуда. Я все еще получаю лучшие (и более быстрые) результаты, используя грубую силу. Итак, я хотел бы улучшить свой алгоритм.

Пара замечаний:

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

Я также знаю, что существуют методы лучше / проще / быстрее / etc (вероятно). Меня просто интересует тема.

Мой код:

         initial = []

        # Generate random initial test points
        for i in range(5000):
            initial.append(random.uniform(0,1))

        for i in range(max_generations):
            # Sort according to some error function
            initial.sort(key = error_func)

            # Keep the "best" 500
            parents = initial[:500]

            # Throw in a few random points
            for i in range(randint(10,100)):
                parents.append(initial[randint(0,len(parents) - 1)])

            # "Mutate" half the parents
            for individual in parents:
                if randint(0,1):
                    individual = random.gauss(individual, 1E-5)

            children = []

            while len(children) < (5000 - len(parents)):
                # Randomly pick a male and female
                male = parents[randint(0, len(parents) - 1)]
                female = parents[randint(0, len(parents) - 1)]

                # Produce a child
                children.append((male   female) / 2) 

            parents.extend(children)
            initial = parents

     initial.sort(key = error_func)
     print(initial[0])
 

Некоторые моменты, которые я рассматриваю:

1. Я знаю, что существует несколько различных способов, которыми генетические алгоритмы выбирают «наиболее подходящие» точки (отдельные лица / участники / и т. Д.). Возможно, есть лучший способ, чем просто сортировка по наименьшей ошибке?
2. Как правило, лучше иметь больше отправных точек или больше итераций / поколений?

Цели

# 1: повышение точности и точности # 2: повышение скорости, с которой найдено «хорошее» решение

Генетический алгоритм должен работать в системе. Итак, вы должны указать некоторые критические точки перед реализацией. Они:

1. Размер популяции (количество хромосом в каждом поколении)
2. Оператор выбора
3. Оператор кроссовера
4. Частота ошибок
5. Политика мутаций
6. Условие завершения (на основе пригодности или на основе генерации)

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

Основная проблема в генетическом алгоритме — монотонность. Если вы не можете обеспечить разнообразие, скорее всего, вы застряли в локальных точках оптимума. Решение заключается в выборе удобных операторов «выбора» и «пересечения».

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