|
Генетические алгоритмы
Поиск не дал результатов, интересно кто-нибудь из форумчан сталкивался с генетическими алгоритмами(ГА)?
Я вот собираюсь написать первую свою программку по ГА на Java, а именно такую, которая высчитает кратчайщий путь по магазину =)
То есть, магазин большой, как пример возьмём строительный, по которым можно ходить часами, если купить нужно много и не пользоваться помощью персонала.
В начале можно выбрать отделы магазина (электроника, дерево, краска и т.д.), которые покупатель желает посетить. Далее ГА расчитывает минимальный путь, начиная входом/выходом, проходя по всем нужным отделам и заканчивая тем же входом/выходом.
Имеется план магазина, с проходами и рапорядком отделов, расстояние нужно будет самому обозначить.
В ГА я пока новичок, общий принцип работы вроде понял.
Идея пока такая:
Популяция/особи будут выглядеть примерно так:
(0, 4, 10, 8, 6, 5, 0) - где ноль это вход/выход, остальные цифры номера отделов.
Первая популяция создается случайным образом, в размере скажем 100 особей. (не знаю, достаточно этого?)
Далее случайным образом отобрать половину особей на роль отца и матери и произвести скрещивание. Какое именно пока не решил и не особо понятно какое самое эфективное. Пока скажем потомок получит примерно по половине генов матери и отца.
Так же не совсем понятно с мутацией, производить её в некоторых случаях или производить всегда со случайным геном потомка? Точнее с двумя генами, которые при мутации будут меняться местами.
Фитнес-функцию, отбор лучших, определять по длине пути генома. Чем меньше путь, тем лучше геном.
И так на протежении 1000 поколений, после чего выдается лучший найденей путь.
Надеюсь кто-нибудь разбирается в ГА, сможет ответить на некоторые мои вопросы, дать советы.
|