Нужно ли бинарное кодирование в генетических алгоритмах?

Question

Я занимаюсь изучением использования генетических алгоритмов в архитектуре, где мы используем эволюционный подход для создания тесселяции Voronoi в 3d. Это делается с помощью xVoro ++ для openFrameworks (C++).

Наши хромосомы для геномов - это вектор (список) точек в 3D. Мы реализовали одно- и двухточечный кроссовер и мутацию, которая с определенной вероятностью рандомизирует эти точки. В большинстве примеров, которые я видел, геном кодируется двояко, что, я полагаю, вызовет мутацию и кроссовер, чтобы действовать по-другому.

Итак, мой вопрос заключается в следующем: существуют ли другие преимущества для двоичного кодирования (кроме скорости) и как вы будете обрабатывать такое кодирование/декодирование в C++? Переход от двоичного к списку трехмерных точек.

С наилучшими пожеланиями, Фред

Answer 1

Вы можете использовать реальное кодирование также, но в данном случае важно то, что кроссовер и мутация вы используете. Если ваш кроссовер просто (p1 + p2)/2 или p1 * a + p2 * (1-a), вы не получите хороших результатов.

Хороший оператор кроссовера для реального кодирования был предложен К. Деба в 1995 году Вот это бумага: http://www.complex-systems.com/pdf/09-2-2.pdf

Answer 2

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

Итак, для вашего алгоритма я бы не «модифицировал» что-либо для кроссовера. Вместо этого, для кроссовера, я попытался бы переместить материал или просто взять разные части очков от родителей.

Для мутации может иметь смысл добавить или вычесть небольшое число в точки, тем самым изменив точки (мутацию).

Трудно делать предложения, не зная больше о вашем алгоритме и представлении хромосом.

Answer 3

Я использовал разные ГА в вопросах логистики и финансов. Очень часто я не использую двоичное представление. Первый пример, который я могу дать вам это проблема TSP:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Здесь я использовал стандартное представление: хромосома представляет собой массив из числа, каждое значение представляет собой город.

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