Генетические алгоритмы

Question

Я пытаюсь реализовать генетический алгоритм, который вычислит минимум функции Растригин , и у меня возникли некоторые проблемы.
Мне нужно представить хромосому в виде двоичной строки, и поскольку функция Растригина принимает список чисел в качестве параметра, как можно декодировать хромосому в список чисел?
Также Растригин хочет, чтобы элементы в списке были -5.12 <= x (i) <= 5.12, что произойдет, если, когда я сгенерирую хромосому, она выдаст число не в этом интервале?

Answer 1

Вы ищете для реализации генетического алгоритма. Ваша реализация должна быть такой, чтобы она работала для любой общей проблемы минимизации (или максимизации), а не только для функции Rastrigin . Вы можете решить реализовать GA с двоичным кодом или GA с реальным кодом. Оба имеют свои собственные применения и нишевые приложения. Но для вас, я бы предложил реализовать реальный кодированный GA. По вашему вопросу относительно того, что делать, если сгенерированные значения переменных находятся за пределами [-5.12: 5.12], GA с реальным кодом и GA с двоичным кодом будут обрабатывать их по-разному.

Наличие ссылочного кода всегда хорошо, прежде чем приступить к реализации собственной версии. Если вы ищете реализацию C, в разделе исходного кода лабораторной работы есть реализация Real Coded GA, которая широко используется нами и другими для нашей исследовательской работы. Я бы посоветовал вам поиграть с ним и попробовать некоторые из простых задач оптимизации, приведенных там.

Pyevolve - это библиотека Python для генетических алгоритмов и генетического программирования.

Теперь, когда мы поговорили о реализации, ясно ли ваше понимание ГА? Если нет, обратитесь к этому учебному пособию , в котором вводится GA с точки зрения оптимизации. Обратите внимание, что объяснение кроссовера и мутации для бинарно-кодированного GA не переносится автоматически в реальный кодированный GA. Реальный кодированный GA имеет свои тонкости, и вам понадобится время, чтобы прочитать некоторые статьи и понять их. Не спешите, но с полной занятостью вы сможете легко начать движение.

Answer 2

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

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

Если вам действительно нужно использовать двоичную строку, взгляните на Серый код , который является способом кодирования числовых значений в двоичном коде, что делает их более подверженными мутациям.

Answer 3

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

Использование чисел с плавающей запятой позволит вам приблизиться к оптимальному значению, скажем, 1e-10, при использовании ваших типичных 64-битных чисел. Более того, современный эволюционный алгоритм использует адаптивную схему для корректировки шага мутации во время оптимизации. Такой механизм обеспечивает большую скорость сходимости по сравнению с фиксированным шагом мутации. Проверьте это, чтобы увидеть, что типичные эволюционные оптимизаторы достигают с помощью функции Rastrigin: http://coco.gforge.inria.fr/doku.php?id=bbob-2010

Answer 4

Если вам интересно, я сделал реализацию с использованием Pyevolve: http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function Извините за опечатку в названии.

Answer 5

Я предполагаю, что вы программируете на C. Целые числа (int для языка C) могут быть упакованы как массив из 4 байтов / символ (32 бита). так что если ваш массив

char* chrom_as_bytes=(...)

вы можете получить i-е значение, приведя к int *

int ith=3;
value=((int*)chrom_as_bytes)[ith];

если значение не находится в диапазоне -5,12 См. Также статью в Википедии .