Генетические алгоритмы
 

Поиск не дал результатов, интересно кто-нибудь из форумчан сталкивался с генетическими алгоритмами(ГА)?

Я вот собираюсь написать первую свою программку по ГА на Java, а именно такую, которая высчитает кратчайщий путь по магазину =)
То есть, магазин большой, как пример возьмём строительный, по которым можно ходить часами, если купить нужно много и не пользоваться помощью персонала.
В начале можно выбрать отделы магазина (электроника, дерево, краска и т.д.), которые покупатель желает посетить. Далее ГА расчитывает минимальный путь, начиная входом/выходом, проходя по всем нужным отделам и заканчивая тем же входом/выходом.
Имеется план магазина, с проходами и рапорядком отделов, расстояние нужно будет самому обозначить.

В ГА я пока новичок, общий принцип работы вроде понял.

Идея пока такая:

Популяция/особи будут выглядеть примерно так:

(0, 4, 10, 8, 6, 5, 0) - где ноль это вход/выход, остальные цифры номера отделов.

Первая популяция создается случайным образом, в размере скажем 100 особей. (не знаю, достаточно этого?)

Далее случайным образом отобрать половину особей на роль отца и матери и произвести скрещивание. Какое именно пока не решил и не особо понятно какое самое эфективное. Пока скажем потомок получит примерно по половине генов матери и отца.

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

Фитнес-функцию, отбор лучших, определять по длине пути генома. Чем меньше путь, тем лучше геном.

И так на протежении 1000 поколений, после чего выдается лучший найденей путь.


Надеюсь кто-нибудь разбирается в ГА, сможет ответить на некоторые мои вопросы, дать советы.

Насколько я понимаю, генетические алгоритмы применяются там, где "истина гдето рядом". :cool:

На пример, распознавание символов, которые каждый раз с разными шумами.

А тут задача с набором конкретных расстояний. Её можно решить обычными математическими методами. На пример, перебор всех возможных комбинаций.

ЗЫ.
Это стандартная задача, которой уже лет сто :cool:
Спроси у гугла
задача коммивояжера код программы
travelling salesman program code

EvroStandart, конечно ГА можно использовать в разных случаях, но я много где читал что именно в таких задачах коммивояжера ГА показывает очень хорошие результаты, не всегда оптимальные, но очень хорошие в плане скорость-качество.
Именно не перебором. Скажем если у меня 12 отделов, то это 12! = 479.001.600 разных комбинаций.

В любом случае мне нужна сейчас именно эта программа, реализованная с помощью ГА :)

big boss,
http://www.codeproject.com/Articles/...-Salesman-Prob
http://www.obitko.com/tutorials/gene...sp-example.php
http://www.cscjournals.org/csc/manus...e6/IJBB-41.pdf
http://ai-depot.com/Articles/51/TSP.html
Думается, алгоритм на Си (первая ссылка) переделать на Яву не очень сложно...