Эволюционные методы

Эволюционные методы (ЭМ) являются приближенными (эвристическими) методами решения задач оптимизации и структурного синтеза. Большинство ЭМ основано на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению.

Эволюционные вычисления составляют один из разделов искусственного интеллекта. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, например, это может быть и нейронная сеть и набор логических правил. К основным эволюционным методам относятся методы отжига, генетические, поведения "толпы" (PSO), колонии муравьев (ACO), генетического программирования.

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

В методе отжига (Simulated Annealing) имитируется процесс минимизации потенциальной энергии тела во время отжига деталей. В текущей точке поиска происходит изменение некоторых управляемых параметров. Новая точка принимается всегда при улучшении целевой функции и лишь с некоторой вероятностью при ее ухудшении.

Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы. Генетические алгоритмы (ГА) основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции.

Свойства объектов представлены значениями параметров, объединяемых в запись, называемую в ЭМ хромосомой. В ГА оперируют подмножеством хромосом, называемом популяцией. Имитация генетических принципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению.

Среди ЭМ находят применение также методы, которые в отличие от ГА оперируют не множеством хромосом, а единственной хромосомой. Так, метод дискретного локального поиска (его англоязычное название Hillclimbing) основан на случайном изменении отдельных параметров (т.е. значений полей в записи или, другими словами, значений генов в хромосоме). Такие изменения называют мутациями. После очередной мутации оценивают значение функции полезности (Fitness Function) и результат мутации сохраняется в хромосоме только, если улучшилась. При "моделировании отжига" результат мутации сохраняется с некоторой вероятностью, зависящей от полученного значения .

В методе PSO (Particles Swarm Optimization) имитируется поведение множества агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента.

Метод колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих длину своих маршрутов на пути от муравьиной кучи до источника пищи.