Искал но что то так и то что мне надо не видел а может и видел но не понял что это оно мне препод сказал надо "генетический алгоритм с одним из кросоверов", а что это значит не понятно. Вот может кто подскажет уже готовый такой вот алгоритм??

Поиск рулит...

да я видел много всего про генетичекские алгоритмы но мне нужен конкретно алгоритм для задачи комивояжора с применением одного из кросссоверов. Где такой алгоритм можно взять?

так никто не может помочь??
у меня не выходит найти. 

Есть очень интересная книга про генетические алгоритмы (метод отжига и т.п.) и про искусственный интелект... Называется что -то типа "Книга Джонс Программирование"

Почитал про ГА и как бы принцып работы стал понятен. Как я понял алгоритм имеет такую структуру: 1. Селекцыя 2. Скрещивание (собственно это и есть кросовер) 3. Мутацыя.  Вот это как бы 3 основных этапа.  Вот так может у когото есть такой ГА?? иди гдето можно скачать для задачи комивояжора. Может есть какойто хороший сайт где было б рассписано как именно работают  Селекцыя, Скрещивание  и Мутацыя. Просто мне например совсем не понятно как работают. Вот например есть у меня 20 хромосомов и какие именно мне надо скрестить из этих 20 что б получить новый хромосом?? Так же по каким правилам осуществлять отбор (Селекцыю). Вотетого всего я так и не видел.      Надо уже вот вот курсач здавать а я всё на месте стою  

никто не подскажет что и как?

Я тоже только книжку почитал. Так что скажу, то что мне вроде понятно. Вам нужно сформулировать что-то вроде количественного "критерия успеха". Для задачи комивояжера критерием должна быть длина пути. Если каждая хромосома сама по себе предлагает решение, то критерий считается для каждой хромосомы. Потом все зависит от выбранного Вами алгоритма (их много) и подставленных в него количественных параметров. Например, можно на каждом шаге отбрасывать 5 худших хромосом и заменять их результатом гибридизации оставшихся. 

Это сообщение отредактировал(а) _Y_ - 3.1.2008, 16:08

_Y_, ну это как бы всё понятно но вот как мне делать ну например скажем схрещивание (кросовер) если у меня есть например 20 хромосомов (каджая хромосома предлагает решение), какую с кокой надо скрестить?. Вотето мне не понятно. То же самое и для мутации к примеру.  

Reptor, Что с чем и как скрещивается, что и как мутирует выбирается генератором случайных чисел. Но возможны варианты - алгоритм-то выбираете Вы. Например, вероятность выбора "партнера" для скрещивания может быть пропорциональна его "успешности".

Добавлено через 14 минут и 13 секунд
Пусть знатоки меня поправят, в моем представлении генетический подход, по сути, развитие метода Монте Карло. Но в Монте Карло идет простой перебор вариантов с отбрасыванием всех, кроме лучшего. Генетические - что-то вроде самообучающегося Монте Карло. Отбрасываюся только самые худшие варианты, а остальные используются как основа для следующего "костебросания".

_Y_, 

да я тоже думал так делать (от безвыходности ситуацыи).



В этом то у меня проблема что я ничего подходящего не видел. Что мне удалось прочитать в инете всё какоето общее. А на книгу совсем времени не осталось.

Где можно почитать про эти алгоритмы (желательно на русском)?

Это ко мне вопрос?  

Я зашел в магазин и купил книжку - почитать в самолете для развлечения:
Melanie Mitchell An Introduction to Genetic Algorithms
Что успел в самолете прочитать - Вам рассказываю  

Так что не стоит на меня надеяться как на знатока.

ЗЫ: Не знаю лучшая это книжка или худшая. Но одно точно - длиннот немало. Одних только экивоков типа "Петр Иваныч сделал то-то, а Иван Петрович посчитал то-то" столько, что тошнить начинает. Уж тем более, если с английским не все гладко - не стоит за нее браться.

Так и есть, но у хороших "особей" в популяции шансы сталь родителями выше, чем у плохих... Т. е вероятность выбора некоторого элемента строиться в  завивсимости от его "качества"(fitness). Причем есть разные подходы к построению этих вероятностей. 

Далее скрещивание выбранных родителей. Алгоритмы скрещивания различны для бинарных векторов, перестановок и т.д. Полученных детей мутируют. Далее обновляют популяцию либо удаляя самых плохих и заменяя их детьми, либо сначала добавляют детей в популяцию, а потом "убивают" плохих.

По какому этапу вопросы? Как скрестить 2е перестановки?

Joss, 

Ну можно и так сказать. Тоесть вопрос был какие имено перестановки скрестить? и какую мутировать? алгоритм выбора перестановок для этих операцый какой?  

Ну, к примеру, есть популяция P = (x1, ..., xN). Нам нужно выбрать из не два элемента-родителя. Это можно сделать по разному. Например, определяем fitness-функцию Ф(x), ставящую каждому элементу популяции в соответствие положительное число. Чем выше fitness элемента, тем выше его вероятность стать родителем. Для каждого эл-та определим эту вероятность: 

В сотверствии с этими вероятностями случайным образом выбирают 2х родителей.

Другой вариант выбора родителей ("турнир"): берем случайным образом несколько элементов популяции(например 4) и лучшего из них выбираем в качестве родителя.