Комментарии 4
мы убедились генетический алгоритм при большом объеме популяции имеет преимущество над алгоритмом полного перебора по времени работы
нет, не убедились
Профессор читает лекцию по математике ...
Выписывает на доске длиннющую,совершенно необозримую формулу и заявив: "Отсюда с очевидностьюследует..." выписывает еще более громоздкую формулу. Вдруг, на минутузадумывается, потом, извинившись, выходит из аудитории. Примерно черезполчаса возвращается и, небрежно бросив на кафедру кипу исписанной бумаги, заявляет: "Да, это действительно очевидно" и продолжает лекцию.
Отбор по новизне, кстати, намного эффективнее, чем естественный. Ну кроме быстросходимых задач.
Вставлю свои 5 копеек.
О ГА уже написано немало на хабре. Здесь же статья ознакомительная на уровне реферата. Статья ради статьи. Стоило что-то новое или под интересным углом рассказать эту матчасть.
Естественный отбор избирает только лучшие решения
Нет, не только. Этот подход быстро приводит к стагнации популяции. Это лишь один из способов отбора - элитарный. Не забывайте, ГА - вероятностный алгоритм, и в классической модели отбор вероятностен - вероятность отбора индивида пропорциональна его приспособленности. То есть даже лучшему индивиду в популяции может не повезти с малой вероятностью.
4.
При количестве особей в популяции более 20 алгоритм полного перебора имеет экспоненциальный рост времени на поиск решения, время работы генетического алгоритма продолжает увеличиваться линейно [7]
Серьезно? Цитировать студента? Писать реферат на основе другого реферата студента неудачная идея, тем более, о фундаментальных вещах.
Утверждение - бред сивой кобылы. Извините за жесткость, но это так. Как кол-во особей генетическом алгоритма влияет на сложность совершенного другого алгоритма??? Или термины особь и популяция каким-то образом затесались в брутфорсе? Абсолютно бессвязное предложение. Для сравнения временных сложностей алгоритмов (ВСА) не нужно писать статьи и ссылаться на студентов. Доподлинно известно с незапамятных времен, что ВСА бруфорса - экспоненциальная (или факториальная), а ВСА ГА - полиномиальная, чаще n^2 - и то если условие останова четкое. Иначе брутфорс может оказаться быстрее, так как его время конечно, а ГА, не достигнув оптимума, может застрять на веки вечные в локальном оптимуме.
Для поддержания мощности популяции в приемлемых масштабах используют оператор селекции, удаляющего из популяции столько же индивидов старшего поколения, сколько было добавлено новых
Число потомков равно числу родителей, тогда мы просто по этой логике удаляем всех родителей? А как же утверждение "Естественный отбор избирает только лучшие решения" - получается удаляем родителей, даже если потомки недостойные?
Приведенный пример - не пример. Пример должен раскрывать алгоритм, а не вуалировать формулами. Надо было привести применение ГА на какой-то понятной задаче.
В заключении отметим, что мы рассмотрели принципы работы генетического алгоритма, убедились, что генетический алгоритм при большом объеме популяции имеет преимущество над алгоритмом полного перебора по времени работы
Нет, не убедились. Не привели опять-таки пример применения, доказывающий утверждение. И вообще, если размер популяции - триллион?! Будет быстрее на примере скажем задачи сборки пятнашек или задача коммивояжера с 25 городами? Спойлер - нет. В этом реферате в принципе отсутствует исследование зависимости времени работы от объема популяции.
Роль генетических алгоритмов в вопросах моделирования