Здравствуйте. Для меня не совсем понятен смысл генетических алгоритмов. Где гарантия, что решение в процессе выращивания будет сходиться к оптимальному? Можно поставить такую задачу, в которой из самого плохого решения (с наименьшим фитнесом) путём одной мутации можно получить самое лучшее. Но если в ходе отбора отсеивать решения с минимальным фитнесом, то это решение вообще не попадёт в последующие популяции. Так что по сути генетический алгоритм - не более, чем случайный перебор возможных решений. Наиболее оптимальные из перебираемых выбираются в качестве конечного решения. Зачем тогда производить скрещивание, отбор, мутации и пр. Брать да генерировать случайные решения - тот же самый результат. В общем закралось у меня сомнение по поводу всех этих недетерминированных методов.. Может книжку хорошую посоветуете?
Ну как бы ГА используются для NP-полных задач, а все, что используется для их решения(и не является полным перебором) работает долго и в конце может выдать 42 ) про мутацию ничего не могу сказать, а вот про остальное.. для скрещивания отбираются наиболее приспособленные особи и в результате скрещивания(если оно корректно реализовано) должна получиться особь с приспособленностью не меньше, чем у своих родителей.. собственно в этом и профит
Чисто по ГА книжек не должно быть, т.к. из теории в ГА, только одна теорема и всё на этом. Сами ГА решают задачу поиска минимума y=F(X). Если интересует как решать класс таких задач, то http://www.google.ru/#&q=методы+оптимизации Коротко по остальным вопросам: Скрещивание нужно для получения нового решения, которое не хуже чем те, из которых оно получено. Отбор нужен для того чтобы ограничить текущую популяцию используя в следующей итерации лучшие решения. Мутация нужна для борьбы с преждевременной сходимостью алгоритма, т.е. борьбы с локальными минимумами
http://www.harrix.org/files/project_standart_ga/Geneticheskii_algoritm_Standart_v_1_5_Release_Candidate.pdf неплохой док.
из дока: я что-то не понимаю?) ведь написано, что с наибольшей вероятностью выбирает наиболее приспособленных спасибо за док
> я что-то не понимаю?) ведь написано, что с наибольшей вероятностью выбирает наиболее приспособленных наибольшая вероятность оставляет шансы попасть в новую популяцию и слабым особям. я имел в виду, что нет тупого отбора особей с лучшим значением функции пригодности, а идёт контролируемый рандом.
Насколько я понял, сходимость решения к оптимальному генетические алгоритмы не гарантируют. По идее, ГА нужно прогонять несколько раз и сравнивать поулчившиеся решения. Если они отличаются не силно, то можно быть в некоторой степени уверенным в оптимальности найдённого решения.
Неплохо бы ещё с разными генераторами случайности. В общем случае алгоритмы, не являющиеся систематическими (а для NP-полных задач это все кроме полного перебора , могут зайти в один из тупиков, причём неоднократно (см. проблему горизонта для шахматных программ, а также локальные экстремумы).
> Насколько я понял, сходимость решения к оптимальному генетические алгоритмы не гарантируют не только ГА, но и все оптимизационные методы
Для непрерывной функции обладающей ровно одним экстремумом ГА гарантирует сходимость на верном решении) Если существует более одного экстремума, то с некоторой вероятностью может быть выбран любой из них
функция селекции особей популяции может использовать несколько стратегий отбора: "Турнирный отбор", "Стратегия элитаризма", и т.д.
