Надо уже вот вот курсач здавать а я всё на месте стою | Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Генетические алгоритмы |
| Автор: Reptor 5.12.2007, 19:09 |
| Искал но что то так и то что мне надо не видел а может и видел но не понял что это оно мне препод сказал надо "генетический алгоритм с одним из кросоверов", а что это значит не понятно. Вот может кто подскажет уже готовый такой вот алгоритм?? |
| Автор: Akina 5.12.2007, 19:25 |
| http://www.google.ru/search?hl=ru&q=%22%D0%B3%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%22+crossover+&lr= |
| Автор: Reptor 6.12.2007, 20:55 |
| да я видел много всего про генетичекские алгоритмы но мне нужен конкретно алгоритм для задачи комивояжора с применением одного из кросссоверов. Где такой алгоритм можно взять? |
| Автор: Reptor 7.12.2007, 20:06 |
| так никто не может помочь?? у меня не выходит найти. |
| Автор: shyr1k 12.12.2007, 13:34 |
| Есть очень интересная книга про генетические алгоритмы (метод отжига и т.п.) и про искусственный интелект... Называется что -то типа "Книга Джонс Программирование" |
| Автор: Reptor 28.12.2007, 22:10 |
| Почитал про ГА и как бы принцып работы стал понятен. Как я понял алгоритм имеет такую структуру: 1. Селекцыя 2. Скрещивание (собственно это и есть кросовер) 3. Мутацыя. Вот это как бы 3 основных этапа. Вот так может у когото есть такой ГА?? иди гдето можно скачать для задачи комивояжора. Может есть какойто хороший сайт где было б рассписано как именно работают Селекцыя, Скрещивание и Мутацыя. Просто мне например совсем не понятно как работают. Вот например есть у меня 20 хромосомов и какие именно мне надо скрестить из этих 20 что б получить новый хромосом?? Так же по каким правилам осуществлять отбор (Селекцыю). Вотетого всего я так и не видел. Надо уже вот вот курсач здавать а я всё на месте стою |
| Автор: Reptor 3.1.2008, 15:20 |
| никто не подскажет что и как? |
| Автор: _Y_ 3.1.2008, 16:06 |
| Я тоже только книжку почитал. Так что скажу, то что мне вроде понятно. Вам нужно сформулировать что-то вроде количественного "критерия успеха". Для задачи комивояжера критерием должна быть длина пути. Если каждая хромосома сама по себе предлагает решение, то критерий считается для каждой хромосомы. Потом все зависит от выбранного Вами алгоритма (их много) и подставленных в него количественных параметров. Например, можно на каждом шаге отбрасывать 5 худших хромосом и заменять их результатом гибридизации оставшихся. |
| Автор: Reptor 3.1.2008, 16:57 |
| _Y_, ну это как бы всё понятно но вот как мне делать ну например скажем схрещивание (кросовер) если у меня есть например 20 хромосомов (каджая хромосома предлагает решение), какую с кокой надо скрестить?. Вотето мне не понятно. То же самое и для мутации к примеру. |
| Автор: _Y_ 4.1.2008, 11:43 |
| Reptor, Что с чем и как скрещивается, что и как мутирует выбирается генератором случайных чисел. Но возможны варианты - алгоритм-то выбираете Вы. Например, вероятность выбора "партнера" для скрещивания может быть пропорциональна его "успешности". Добавлено через 14 минут и 13 секунд Пусть знатоки меня поправят, в моем представлении генетический подход, по сути, развитие метода Монте Карло. Но в Монте Карло идет простой перебор вариантов с отбрасыванием всех, кроме лучшего. Генетические - что-то вроде самообучающегося Монте Карло. Отбрасываюся только самые худшие варианты, а остальные используются как основа для следующего "костебросания". |
| Автор: Reptor 4.1.2008, 12:35 | ||||
_Y_,
да я тоже думал так делать (от безвыходности ситуацыи).
В этом то у меня проблема что я ничего подходящего не видел. Что мне удалось прочитать в инете всё какоето общее. А на книгу совсем времени не осталось. Где можно почитать про эти алгоритмы (желательно на русском)? |
| Автор: _Y_ 4.1.2008, 22:06 | ||
Это ко мне вопрос?  Я зашел в магазин и купил книжку - почитать в самолете для развлечения: Melanie Mitchell An Introduction to Genetic Algorithms Что успел в самолете прочитать - Вам рассказываю  Так что не стоит на меня надеяться как на знатока. ЗЫ: Не знаю лучшая это книжка или худшая. Но одно точно - длиннот немало. Одних только экивоков типа "Петр Иваныч сделал то-то, а Иван Петрович посчитал то-то" столько, что тошнить начинает. Уж тем более, если с английским не все гладко - не стоит за нее браться. |
| Автор: Joss 5.1.2008, 13:07 | ||
Так и есть, но у хороших "особей" в популяции шансы сталь родителями выше, чем у плохих... Т. е вероятность выбора некоторого элемента строиться в завивсимости от его "качества"(fitness). Причем есть разные подходы к построению этих вероятностей. Далее скрещивание выбранных родителей. Алгоритмы скрещивания различны для бинарных векторов, перестановок и т.д. Полученных детей мутируют. Далее обновляют популяцию либо удаляя самых плохих и заменяя их детьми, либо сначала добавляют детей в популяцию, а потом "убивают" плохих. По какому этапу вопросы? Как скрестить 2е перестановки? |
| Автор: Reptor 5.1.2008, 15:02 | ||
Joss,
Ну можно и так сказать. Тоесть вопрос был какие имено перестановки скрестить? и какую мутировать? алгоритм выбора перестановок для этих операцый какой? |
| Автор: Joss 5.1.2008, 19:18 | ||||
Ну, к примеру, есть популяция P = (x1, ..., xN). Нам нужно выбрать из не два элемента-родителя. Это можно сделать по разному. Например, определяем fitness-функцию Ф(x), ставящую каждому элементу популяции в соответствие положительное число. Чем выше fitness элемента, тем выше его вероятность стать родителем. Для каждого эл-та определим эту вероятность:
В сотверствии с этими вероятностями случайным образом выбирают 2х родителей. Другой вариант выбора родителей ("турнир"): берем случайным образом несколько элементов популяции(например 4) и лучшего из них выбираем в качестве родителя. |
| Автор: Joss 5.1.2008, 23:32 | ||
Забыл написать по поводу выбора функции фитнеса... Если решается задача на минимум, т.е. f(x) -> min, то можно ввести т. о.:
где worst - самое плохое решение за всю эволюцию. Теперь по поводу скрещивания для перестановок. Пусть мы выбрали 2х родителей: p1=(a b c d e f g h i), p2=(f c b h e a g d i). Выбираем 2 случайные точки, которые поделят наши перестановки на 3 части: a b . c d e f . g h i f c . b h e a . g d i И начинаем строить ребенка с конца. Последние 3 элемента берем от 2го родителя: _ _._ _ _ _.g d i Среднюю часть берем у 1го родителя. Если какой-то элемент уже есть в перестановке, то добавляем другой, отсутсвующий, с сохранением относительного порядка: _ _.с _ _ _.g d i _ _.с e _ _.g d i // d уже есть, берем e _ _.с e f _.g d i // e уже есть, берем f _ _.с e f h.g d i // f уже есть, берем h Первые элементы - от 2го: b _.с e f h.g d i // f уже есть, берем b b a.с e f h.g d i // c уже есть, берем a Получили ребенка: (b a с e f h g d i). После этого подвергаем его мутации: Вариант 1: выбираем 2 случайные позиции и инвертируем среднюю часть: b.a с e.f h g d i b.e с a.f h g d i При этом изменяться 2 ребра Вариант 2: выбираем 2 случайные позиции и меняем местами элементы в этих позициях b a с e f h g d i ^ ^ b a с d f h g e i Поменялись 4 ребра. Эта мутация более сильная. |
| Автор: _Y_ 6.1.2008, 17:20 |
| Я вот задумался, а как, в случае бинарных хромосом обходятся с кодированием значений не равных двум в степени? Например, если у величины три возможных значения, то одним битом ее не закодируешь, а двухбитная кодировка даст четвертое значение (11) недопустимое для этой величины? Все, что сам придумал - результаты мутаций дающие величину 11 признавать изначально дохлыми и мутировать заново. Но есть наверное какой-то более разумный подход? |
| Автор: Joss 6.1.2008, 20:05 |
| _Y_, не совсем понял о чем речь... Если задача на бинарных векторах, то значенния генов либо 0, либо 1. Если же хромосома представляет собой вектор вещественных чисел либо что-то другое, то и оператор мутации реализуется по другому |
| Автор: _Y_ 6.1.2008, 21:52 |
| Joss, в книжке, которую я читал было что-то вроде такого: "первые два бита кодируют такое-то свойство, последующие четыре бита кодируют то-то, последующие..." ну и так далее. До векторов вещественных чисел я не дочитал (пока, надеюсь). То есть, имеются какие-то свойства с конечным числом значений. Их значения кодируются не битами, а бинарными последовательностями. Вот и непонятно, как быть с моим вопросом в этом случае. |
| Автор: Joss 8.1.2008, 19:03 |
| Думаю, можно в целевой функции штрафовать за выход из допустимой области, и такие решения будут отпадать сами-собой в процессе эволюции. |
| Автор: _Y_ 9.1.2008, 11:21 |
| Joss, Спасибо, значит, как я и предполагал, хромосомы с выходящими за рамки допустимых значений вариантами генов просто признаются "нежизнеспособными". А я-то надеялся, что есть решение красивее. |
| Автор: _Y_ 15.1.2008, 17:37 |
| Еще вопрос возник в ту же тему. Положим, у меня есть бинарная хромосома 1000001000000000110000.......... При этом я заранее знаю, что число единиц в ней гораздо меньше, чем число нулей. Понятное дело, что хромосомы со слишком большим числом единиц отловятся функцией фитнеса. Но! При этом будет жраться немеряно времени на производство полудохлых потомков. Думаю, можно изначально задать разную вероятность мутаций 0->1 и 1->0, но не уверен в грамотности такого решения. А может есть что-то еще грамотнее? |
| Автор: _Y_ 17.1.2008, 18:01 | ||
Дочитал книжку до конца. Пожалуй пятую главу рекомендовать можно - в ней описание подходов к выбору конкретных алгоритмов. |
