Задачи оптимизации

Как уже были отмечено выше, эволюция - это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут большое количество потомков, а благодаря генетическому наследованию, часть потомков не только сохранит высокую приспособленность родителей, но будет иметь и новые свойства. Если эти новые свойства оказываются полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособленности биологического вида в целом. Зная, как решается задача оптимизации видов в природе, применим похожий метод для решения разных реальных задач.

Задачи оптимизации - наиболее распространенный и важный для практики класс задач. Их приходится решать любому из нас или в быту, распределяя свое время между разными делами, или на работе, добиваясь максимальной скорости работы программы или максимальной прибыльности компании - в зависимости от должности. Среди этих задач есть решаемые простым путем, но есть и такие, точное решение которых найти практически невозможно.

Введем обозначения и приведем несколько классических примеров. Как правило, в задаче оптимизации мы можем руководить несколькими параметрами (обозначим их значения через x1, x2,..., xn, целью является максимизация (или минимизация) некоторой целевой функции, f(x1, x2,..., xn), зависящей от этих параметров. Например, если нужно максимизировать целевую функцию "доход компании", тогда управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т.д. Эти параметры связаны между собой - в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства.

Генетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. Известно два основных пути решения таких задач - метод перебора или градиентный метод. Рассмотрим классическую задачу коммивояжера. Суть задачи состоит в нахождении кратчайшего пути прохождения всех городов.

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

Другой способ - градиентный спуск. Выбираем случайные значения параметров, далее значения постепенно изменяются, достигая наибольшей скорости роста целевой функции. Алгоритм может остановиться, достигнув локального максимума. Градиентные методы быстрые, но не гарантируют оптимального решения (поскольку целевая функция имеет несколько максимумов).

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

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