|
|
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Сейчас заинтересовался генетическими алгоритмами. Решил попробовать реализовать свой вариант. Исключительно в учебных целях. В университете преподаватель рекомендовал использовать бинарный код Грея для представления отдельных генов индивида. Вопрос: почему не использовать обычное двоичное представление чисел? Чем БКГ лучше? Важнейшее свойство БКГ знаю, но не представляю, чем оно может быть полезно в ГА. Заранее спасибо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.02.2011, 12:08 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
KeyKeeper, http://www.wikiznanie.ru/ru-wz/index.php/%D0%A0%D0%B0%D0%B7%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B3%D0%BE_%D0%B3%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0 * Достоинства: случайные инверсии битов производят (с большей вероятностью) небольшие изменения, нет резких скачков в метрике Хэмминга, соседние числа остаются соседними и после бинаризации * Недостатки: в тех редких случаях, когда изменения являются большими, они значительно больше, чем в бинарном коде, далекие числа могут оказаться соседними после кодирования http://algolist.manual.ru/ai/ga/ga3.php Код Грея предпочтительнее обычного двоичного тем, что обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 05:56 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
KeyKeeperЗдравствуйте. Сейчас заинтересовался генетическими алгоритмами. Решил попробовать реализовать свой вариант. Исключительно в учебных целях. В университете преподаватель рекомендовал использовать бинарный код Грея для представления отдельных генов индивида. Выше написали почему оно может быть лучше в теории. Попробуй лучше на практике реализовать с БГК и без, увидишь хороши они или нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 10:44 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
Jartisan, всё это, конечно, хорошо и понятно. Не ясно другое. В чём выгода от кодирования. Да, два соседних числа будут в БКГ-представлении отличаться в одном разряде. Но это же не говорит обратного. Т.е. имея БКГ-представление числа d и изменив один случайный разряд в нём, мы совсем не обязательно получим "соседнее" для d число (после декодирования). Так в чём же всё-таки смысл? Анонимному ответчику. Да, я так и сделаю. Пока не осуществляю перевода в БКГ, хотя (смешной по объёму) код кодировщика в наличии. Правда, тут сразу встаёт вопрос. Ряд операций в ГА случайны: выбор точки(ек) кроссовера, выбор особей-родителей, выбор потомка из пары после кроссовера, выбор точки мутации и т.д. Как же всё-таки сравнивать реализации ГА с и без кодирования в БКГ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 13:22 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
KeyKeeper, http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs, когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f(x) = x2. Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 14:14 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
JartisanKeyKeeper, http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs, когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f(x) = x2. Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает. Огромное спасибо! Это уже хорошее объяснение. А не могли бы чуточку "разжевать" пример? Я так понял, рассматривается функция . Её требуется минимизировать или максимизировать? И что значит "сойдётся к -1"? Имеется в виду, что большая часть особей будет близка к "x = -1" ? Простите за примитивные вопросы, просто хочется действительно понять. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 16:05 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
Автор:Выше написали почему оно может быть лучше в теории. Попробуй лучше на практике реализовать с БГК и без, увидишь хороши они или нет. Набрёл на интересную статью , вывод из которой аналогичен. Для некоторых задач использование БКГ в ГА может приводить к "уходу от глобального экстремума". Но всё-равно хочется разобраться, как же именно применение кодов Грея влияет на процесс работы ГА. Вечером почитаю док по ссылке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 16:13 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
KeyKeeperЕё требуется минимизировать или максимизировать? И что значит "сойдётся к -1"? Имеется в виду, что большая часть особей будет близка к "x = -1" ? Простите за примитивные вопросы, просто хочется действительно понять. Да, имеется в виду именно то что будет много -1. И они не перейдут в 0. Рассмотрим крайний случай. Пусть вся популяция состоит из -1. -1 представлено как 1111 1111 1111 1111. Для того чтобы попасть в ноль надо заменить 16 бит. Изменение 1,2,3,...14 бит будет недостаточно и лишь ухудшит результат. Например, если последний бит обнулится, то получится -2 (1111 1111 1111 1110). -2^2 = 4. Это хуже чем -1^2 = 1. в грее такой ерунды бы не было и надо было изменить один бит, чтобы попасть в ноль. Но есть момент такой момент: В оригинале мутация выглядит так: К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью pm инвертируется. Эта вероятность обычно очень мала, менее 1%. При популяции стостоящей из минус 1 и такой мутации ГА не достигнет глобального минимума 0 так как потребуется 16 замен однобитовых замен. Но стоит заменить мутацию на Код: plaintext 1. 2. 3. 4. Кстати обрати внимание на С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи. Несколько лет назад в сети гулял исходник ГА который делал лабиринт для Desktop Tower Defense. Никаких кодов грея и бинарных строк. Там применялись пары (x,y) для башни и кроссовер был "возьмем половину башен отсюда, возьмем половину отсюда и соединим их так, что башни не пересеклись". Мутации оперировали на уровне башен, а не отдельных битов. Максимизировали расстояние, которое проходили монстры от входа до выхода. Работало офигенно. Исходников жаль уже не достать, но обсуждение и картинки остались http://www.handdrawngames.com/forum/index.php?topic=1447.0 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.02.2011, 19:29 |
|
||
|
БКГ в ГА: Зачем?
|
|||
|---|---|---|---|
|
#18+
Автор:В оригинале мутация выглядит так: К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью pm инвертируется. Эта вероятность обычно очень мала, менее 1%. При популяции стостоящей из минус 1 и такой мутации ГА не достигнет глобального минимума 0 так как потребуется 16 замен однобитовых замен. Правильно ли я понял, что использование БКГ направлено на поиск в окрестности экстремума, т.е. БКГ помогает повысить точность решения? Это должно происходить за счёт того, что два соседних числа представленные в БКГ отличаются на 1 бит. В то время как числа в прямой кодировке могут отличаться на x бит (от 1 до общего кол-ва разрядов для представления числа). Выходит, вероятность "удачной" мутации для описанной ситуации при использовании БКГ будет составлять около , где -- вероятность мутации, N -- общее количество битов для предствления числа. А для прямой кодировки эта вероятность будет в лучшем случае составлять , где n -- количество битов, которые требуется инвертировать, чтобы получить сравнительно лучшее рядом стоящее число. Формула не учитывает сочетание позиций, которые надо инвертировать, а значит на деле вероятность будет ещё ниже. К сожалению, более точную формулу не напишу сейчас, т.к. в комбинаторике не силён. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.02.2011, 12:15 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=37105698&tid=1343147]: |
0ms |
get settings: |
8ms |
get forum list: |
16ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
149ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
38ms |
get tp. blocked users: |
1ms |
| others: | 249ms |
| total: | 478ms |
| 0 / 0 |
