Это необходимо с двоичным кодированием в генетических алгоритмах?
Я делаю проект, исследующий использование генетических алгоритмов в архитектуре, где мы используем эволюционный подход для создания тесселяции Вороного в 3d. Это делается с помощью ofxVoro ++ для openFrameworks (c ++).
Наши хромосомы для геномов — это вектор (список) точек в 3D. Мы реализовали одно- и двухточечный кроссовер и мутацию, которая рандомизирует эти точки с определенной вероятностью. В большинстве примеров, которые я видел, геном кодируется в двоичном формате, что, как я полагаю, приведет к тому, что мутация и кроссовер будут действовать по-разному.
Поэтому мой вопрос заключается в следующем: есть ли другие преимущества для двоичного кодирования (кроме скорости) и как бы вы справились с таким кодированием / декодированием в c ++? Переход от двоичного к списку 3d-точек.
С наилучшими пожеланиями,
Фред
Решение
Вы также можете использовать реальное кодирование, но в этом случае важно, какой кроссовер и мутацию вы используете. Если ваш кроссовер просто (p1 + p2) / 2 или p1 * a + p2 * (1-a), вы не получите хороших результатов.
Хороший оператор кроссовера для реального кодирования был предложен К. Дебом в 1995 году. Вот статья: http://www.complex-systems.com/pdf/09-2-2.pdf
Другие решения
Кроссовер и мутация разные операторы. Кроссовер использует существующие генетические. Мутация вводит новый генетический материал в популяцию. Не зная больше информации о вашем алгоритме, рандомизация точек звучит как мутация. Мутация обычно выполняется в очень низкий процент времени (возможно, 1%), где кроссовер может быть довольно высоким (50%).
Так что по вашему алгоритму я бы не «модифицировал» ничего для кроссовера. Вместо этого, для кроссовера, я бы попытался изменить положение материала или просто взять разные части очков у родителей.
Для мутации может иметь смысл добавить или вычесть небольшое количество к точкам, таким образом модифицируя точки (мутация).
Трудно делать предложения, не зная больше о вашем алгоритме и представлении хромосомы.
Я использовал разные GA в вопросах логистики и финансов. Очень часто я не использую двоичное представление.
Первый пример, который я могу привести, это проблема TSP:
https://en.wikipedia.org/wiki/Travelling_salesman_problem
Здесь я использовал стандартное представление: хромосома — это массив целых чисел, каждое значение представляет город.
Таким образом, это зависит от типа проблемы, которую вы пытаетесь решить, если вы можете найти способ реализовать GA без двоичного представления, вам не нужно ничего корректировать.
Кроме того, я предпочитаю естественное представление, потому что его легче понять при отладке кода, если ваш GA работает так, как вы хотите.