1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

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

Тема в разделе "WASM.A&O", создана пользователем maksim_, 20 окт 2010.

  1. maksim_

    maksim_ New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2009
    Сообщения:
    263
    Здравствуйте. Для меня не совсем понятен смысл генетических алгоритмов. Где гарантия, что решение в процессе выращивания будет сходиться к оптимальному? Можно поставить такую задачу, в которой из самого плохого решения (с наименьшим фитнесом) путём одной мутации можно получить самое лучшее. Но если в ходе отбора отсеивать решения с минимальным фитнесом, то это решение вообще не попадёт в последующие популяции. Так что по сути генетический алгоритм - не более, чем случайный перебор возможных решений. Наиболее оптимальные из перебираемых выбираются в качестве конечного решения. Зачем тогда производить скрещивание, отбор, мутации и пр. Брать да генерировать случайные решения - тот же самый результат.

    В общем закралось у меня сомнение по поводу всех этих недетерминированных методов.. Может книжку хорошую посоветуете?
     
  2. juggler

    juggler New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2009
    Сообщения:
    18
    Ну как бы ГА используются для NP-полных задач, а все, что используется для их решения(и не является полным перебором) работает долго и в конце может выдать 42 )

    про мутацию ничего не могу сказать, а вот про остальное.. для скрещивания отбираются наиболее приспособленные особи и в результате скрещивания(если оно корректно реализовано) должна получиться особь с приспособленностью не меньше, чем у своих родителей.. собственно в этом и профит
     
  3. 100gold

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    Чисто по ГА книжек не должно быть, т.к. из теории в ГА, только одна теорема и всё на этом. Сами ГА решают задачу поиска минимума y=F(X). Если интересует как решать класс таких задач, то http://www.google.ru/#&q=методы+оптимизации

    Коротко по остальным вопросам:
    Скрещивание нужно для получения нового решения, которое не хуже чем те, из которых оно получено.
    Отбор нужен для того чтобы ограничить текущую популяцию используя в следующей итерации лучшие решения.
    Мутация нужна для борьбы с преждевременной сходимостью алгоритма, т.е. борьбы с локальными минимумами
     
  4. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    отбор не выбирает лучших особей :)
     
  5. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    http://www.harrix.org/files/project_standart_ga/Geneticheskii_algoritm_Standart_v_1_5_Release_Candidate.pdf

    неплохой док.
     
  6. juggler

    juggler New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2009
    Сообщения:
    18
    из дока:
    я что-то не понимаю?) ведь написано, что с наибольшей вероятностью выбирает наиболее приспособленных

    спасибо за док
     
  7. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    > я что-то не понимаю?) ведь написано, что с наибольшей вероятностью выбирает наиболее приспособленных
    наибольшая вероятность оставляет шансы попасть в новую популяцию и слабым особям.
    я имел в виду, что нет тупого отбора особей с лучшим значением функции пригодности, а идёт контролируемый рандом.
     
  8. maksim_

    maksim_ New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2009
    Сообщения:
    263
    Насколько я понял, сходимость решения к оптимальному генетические алгоритмы не гарантируют. По идее, ГА нужно прогонять несколько раз и сравнивать поулчившиеся решения. Если они отличаются не силно, то можно быть в некоторой степени уверенным в оптимальности найдённого решения.
     
  9. baldr

    baldr New Member

    Публикаций:
    0
    Регистрация:
    29 апр 2010
    Сообщения:
    327
    Неплохо бы ещё с разными генераторами случайности. В общем случае алгоритмы, не являющиеся систематическими (а для NP-полных задач это все кроме полного перебора :derisive:, могут зайти в один из тупиков, причём неоднократно (см. проблему горизонта для шахматных программ, а также локальные экстремумы).
     
  10. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    > Насколько я понял, сходимость решения к оптимальному генетические алгоритмы не гарантируют
    не только ГА, но и все оптимизационные методы :)
     
  11. 100gold

    100gold New Member

    Публикаций:
    0
    Регистрация:
    26 фев 2010
    Сообщения:
    165
    Для непрерывной функции обладающей ровно одним экстремумом ГА гарантирует сходимость на верном решении) Если существует более одного экстремума, то с некоторой вероятностью может быть выбран любой из них
     
  12. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.922
    функция селекции особей популяции может использовать несколько стратегий отбора:
    "Турнирный отбор", "Стратегия элитаризма", и т.д.