Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / БКГ в ГА: Зачем? / 9 сообщений из 9, страница 1 из 1
08.02.2011, 12:08
    #37103909
KeyKeeper
KeyKeeper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
Здравствуйте.

Сейчас заинтересовался генетическими алгоритмами. Решил попробовать реализовать свой вариант. Исключительно в учебных целях.
В университете преподаватель рекомендовал использовать бинарный код Грея для представления отдельных генов индивида.
Вопрос: почему не использовать обычное двоичное представление чисел? Чем БКГ лучше? Важнейшее свойство БКГ знаю, но не представляю, чем оно может быть полезно в ГА.

Заранее спасибо
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 05:56
    #37105698
Jartisan
Jartisan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
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 Код Грея предпочтительнее обычного двоичного тем, что обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 10:44
    #37106029
Автор:
Автор:
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
KeyKeeperЗдравствуйте.

Сейчас заинтересовался генетическими алгоритмами. Решил попробовать реализовать свой вариант. Исключительно в учебных целях.
В университете преподаватель рекомендовал использовать бинарный код Грея для представления отдельных генов индивида.
Выше написали почему оно может быть лучше в теории.
Попробуй лучше на практике реализовать с БГК и без, увидишь хороши они или нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 13:22
    #37106548
KeyKeeper
KeyKeeper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
Jartisan,
всё это, конечно, хорошо и понятно.
Не ясно другое. В чём выгода от кодирования. Да, два соседних числа будут в БКГ-представлении отличаться в одном разряде. Но это же не говорит обратного. Т.е. имея БКГ-представление числа d и изменив один случайный разряд в нём, мы совсем не обязательно получим "соседнее" для d число (после декодирования). Так в чём же всё-таки смысл?

Анонимному ответчику.
Да, я так и сделаю. Пока не осуществляю перевода в БКГ, хотя (смешной по объёму) код кодировщика в наличии.
Правда, тут сразу встаёт вопрос. Ряд операций в ГА случайны: выбор точки(ек) кроссовера, выбор особей-родителей, выбор потомка из пары после кроссовера, выбор точки мутации и т.д. Как же всё-таки сравнивать реализации ГА с и без кодирования в БКГ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 14:14
    #37106746
Jartisan
Jartisan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
KeyKeeper,

http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs, когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f(x) = x2. Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 16:05
    #37107166
KeyKeeper
KeyKeeper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
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" ? Простите за примитивные вопросы, просто хочется действительно понять.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 16:13
    #37107182
KeyKeeper
KeyKeeper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
Автор:Выше написали почему оно может быть лучше в теории.
Попробуй лучше на практике реализовать с БГК и без, увидишь хороши они или нет.
Набрёл на интересную статью , вывод из которой аналогичен. Для некоторых задач использование БКГ в ГА может приводить к "уходу от глобального экстремума".

Но всё-равно хочется разобраться, как же именно применение кодов Грея влияет на процесс работы ГА. Вечером почитаю док по ссылке.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.02.2011, 19:29
    #37107698
Автор:
Автор:
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
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.
if random() < N%:
  x += случайное число от - 3  до  3  
else 
   заменить биты
как Hamming cliffs'ы перепрыгнутся мнгновенно.

Кстати обрати внимание на
С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.


Несколько лет назад в сети гулял исходник ГА который делал лабиринт для Desktop Tower Defense. Никаких кодов грея и бинарных строк. Там применялись пары (x,y) для башни и кроссовер был "возьмем половину башен отсюда, возьмем половину отсюда и соединим их так, что башни не пересеклись". Мутации оперировали на уровне башен, а не отдельных битов. Максимизировали расстояние, которое проходили монстры от входа до выхода. Работало офигенно.
Исходников жаль уже не достать, но обсуждение и картинки остались
http://www.handdrawngames.com/forum/index.php?topic=1447.0
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.02.2011, 12:15
    #37108687
KeyKeeper
KeyKeeper
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
БКГ в ГА: Зачем?
Автор:В оригинале мутация выглядит так:
К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью pm инвертируется. Эта вероятность обычно очень мала, менее 1%.

При популяции стостоящей из минус 1 и такой мутации ГА не достигнет глобального минимума 0 так как потребуется 16 замен однобитовых замен.

Правильно ли я понял, что использование БКГ направлено на поиск в окрестности экстремума, т.е. БКГ помогает повысить точность решения? Это должно происходить за счёт того, что два соседних числа представленные в БКГ отличаются на 1 бит. В то время как числа в прямой кодировке могут отличаться на x бит (от 1 до общего кол-ва разрядов для представления числа).

Выходит, вероятность "удачной" мутации для описанной ситуации при использовании БКГ будет составлять около
, где -- вероятность мутации, N -- общее количество битов для предствления числа.


А для прямой кодировки эта вероятность будет в лучшем случае составлять
, где n -- количество битов, которые требуется инвертировать, чтобы получить сравнительно лучшее рядом стоящее число.
Формула не учитывает сочетание позиций, которые надо инвертировать, а значит на деле вероятность будет ещё ниже. К сожалению, более точную формулу не напишу сейчас, т.к. в комбинаторике не силён.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / БКГ в ГА: Зачем? / 9 сообщений из 9, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 318ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1343147]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 30ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 29ms
get tp. blocked users:
 1ms
others: 226ms
total:  318ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]