Как уже было отмечено выше, эволюция — это процесс постоянной оптимизации биологических видов. Теперь мы в состоянии понять, как происходит этот процесс. Естественный отбор гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию мы можем быть уверены, что часть этого потомства не только сохранит высокую приспособленность родителей, но будет обладать и некоторыми новыми свойствами. Если эти новые свойства окажутся полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособляемости биологического вида в целом. Зная, как решается задача оптимизации видов в природе, мы теперь применим похожий метод для решения различных реальных задач.
Задачи оптимизации — наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании — в зависимости от должности. Среди этих задач есть решаемые простым путем, но есть и такие, точное решение которых найти практически невозможно.
Введем обозначения и приведем несколько классических примеров. Как правило, в задаче оптимизации мы можем управлять несколькими параметрами (обозначим их значения через x1, x2, ..., xn, а нашей целью является максимизация (или минимизация) некоторой функции, f(x1, x2, ..., xn), зависящей от этих параметров. Функция f называется целевой функцией. Например, если требуется максимизировать целевую функцию “доход компании”, то управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т. д. Важно отметить, что эти параметры связаны между собой — в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства.
Конечно, математики издавна занимались подобными задачами и разработали несколько методов их решения. В случае, если целевая функция достаточно гладкая и имеет только один локальный максимум (унимодальна), то оптимальное решение можно получить методом градиентного спуска. Идея этого метода состоит в том, что оптимальное решение получается итерациями. Берется случайная начальная точка, а затем в цикле происходит сдвиг этой точки на малый шаг, причем шаг делается в том направлении, в котором целевая функция растет быстрее всего. Недостатком градиентного алгоритма являются слишком высокие требования к функции — на практике унимодальность встречается крайне редко, а для неправильной функции градиентный метод часто приводит к неоптимальному ответу. Аналогичные проблемы возникают и с применением других математических методов. Во многих важных задачах параметры могут принимать лишь определенные значения, причем во всех остальных точках целевая функция не определена. Конечно, в этом случае не может быть и речи о ее гладкости и требуются принципиально другие подходы.
Классический пример такой задачи, известный как “задача коммивояжера” (Traveling Salesman Problem, TSP), формулируется так: коммивояжеру требуется объехать несколько городов, побывав в каждом один раз, и вернуться в исходную точку. Нужно найти кратчайший маршрут.
Самый простой способ найти оптимальное решение — перебрать все возможные значения параметров. При этом не нужно делать никаких предположений о свойствах целевой функции, а задать ее можно просто с помощью таблицы. Однако, чтобы решить таким способом задачу коммивояжера хотя бы для 20 городов, потребуется перебрать около 1019 маршрутов, что совершенно нереально ни для какого вычислительного центра. Таким образом, возникает необходимость в каком-либо новом методе оптимизации, пригодном для практики. В следующем разделе мы покажем, каким образом можно применить механизмы эволюционного процесса к нашим задачам. Фактически мы организуем искусственную эволюцию в специально построенном мире.