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

Question

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

Answer 1

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

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

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

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

Answer 2

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

char* chrom_as_bytes=(...) 

ваш может получить I-го значения литья в междунар *

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

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

См. Также статью в Wikipedia.

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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