Введение
Эволюционные
методы являются приближенными методами решения задач оптимизации и структурного
синтеза. Большинство эволюционных методов основано на статистическом подходе к
исследованию ситуаций и итерационном приближении к искомому решению.
Эволюционные
вычисления составляют один из разделов искусственного интеллекта. При
построении систем ИИ по данному подходу основное внимание уделяется построению
начальной модели, и правилам, по которым она может изменяться
(эволюционировать). Причем модель может быть составлена по самым различным
методам, например, это может быть и нейронная сеть и набор логических правил. К
основным эволюционным методам относятся методы отжига, генетические, поведения
"толпы" (PSO), колонии муравьев (ACO), генетического программирования.
В
отличие от точных методов математического программирования эволюционные методы
позволяют находить решения, близкие к оптимальным, за приемлемое время, а в
отличие от других эвристических методов оптимизации характеризуются существенно
меньшей зависимостью от особенностей приложения (т.е. более универсальны) и в
большинстве случаев обеспечивают лучшую степень приближения к оптимальному
решению. Универсальность эволюционных методов определяется также применимостью
к задачам с неметризуемым пространством управляемых переменных (т.е. среди
управляемых переменных могут быть и лингвистические величины, т.е. не имеющие
количественного выражения).
В
методе отжига (Simulated Annealing) имитируется процесс минимизации
потенциальной энергии тела во время отжига деталей. В текущей точке поиска
происходит изменение некоторых управляемых параметров. Новая точка принимается
всегда при улучшении целевой функции и лишь с некоторой вероятностью при ее
ухудшении.
Важнейшим
частным случаем эволюционных методов являются генетические методы и алгоритмы.
Генетические алгоритмы основаны на поиске лучших решений с помощью наследования
и усиления полезных свойств множества объектов определенного приложения в
процессе имитации их эволюции.
Свойства
объектов представлены значениями параметров, объединяемых в запись, называемую
в эволюционном методе хромосомой. В генетическом алгоритме оперируют
подмножеством хромосом, называемом популяцией. Имитация генетических принципов
- вероятностный выбор родителей среди членов популяции, скрещивание их
хромосом, отбор потомков для включения в новые поколения объектов на основе
оценки целевой функции - ведет к эволюционному улучшению значений целевой
функции (функции полезности) от поколения к поколению.
Среди
эволюционных методов находят применение также методы, которые в отличие от
генетического алгоритма оперируют не множеством хромосом, а единственной
хромосомой. Так, метод дискретного локального поиска (его англоязычное название
Hillclimbing) основан на случайном изменении отдельных параметров (т.е.
значений полей в записи или, другими словами, значений генов в хромосоме).
Такие изменения называют мутациями. После очередной мутации оценивают значение
функции полезности 
(Fitness Function) и результат
мутации сохраняется в хромосоме только, если улучшилась.
При
"моделировании отжига" результат мутации сохраняется с некоторой
вероятностью, зависящей от полученного значения .
В
методе PSO (Particles Swarm Optimization) имитируется поведение множества
агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента.
Метод
колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих
длину своих маршрутов на пути от муравьиной кучи до источника пищи.[]
TimeBiology