Раздел 10

Основные понятия теории генетических алгоритмов

Эволюционные вычисления и традиционные методы оптимизации.

Принятие решений – каждодневная деятельность человека, часть его повседневной жизни. В течение дня по различным ситуациям человек принимает в среднем 10000 решений [51]. Простые, привычные решения на уровне бытовых проблем человек принимает легко, часто автоматически, не задумываясь. В сложных и ответственных случаях он обращается к друзьям, родственникам, опытным и знающим людям за подтверждением своего решения, несогласием с ним или за советом: каким могло бы быть другое решение. Такой же подход к принятию решений сохранялся многие столетия и в области профессиональной деятельности человека, когда темп изменения окружающей среды был невелик и новые явления возникали “по очереди”, а не одновременно. И для адекватного реагирования на те или иные ситуации достаточно было учитывать один-два важных фактора, не рассматривая все их множество.

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

Принятие решения а большинстве случаев заключается в генерации всех возможных альтернативных решений, их оценке и выборе лучшей среди них. Принять “правильное” решение – значит выбрать такой вариант из числа возможных, в котором с учетом всех разнообразных факторов и противоречивых требований будет оптимизирована некая общая ценность, то есть решение будет в максимальной степени способствовать достижению поставленной цели.

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

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

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

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

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

На сегодняшний день можно выделить три основных типа методов поиска оптимальных решений [52]:

§ методы, основанные на математических вычислениях,

§ перечислительные методы, вычислительные методы,

§ методы, использующие элемент случайности.

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

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

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

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

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

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

Эволюционные вычисления – термин, обычно используемый для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного процесса [53]. Основное преимущество эволюционных вычислений в этой области заключается в возможности решения многомодальных (имеющих несколько локальных экстремумов) задач с большой размерностью за счёт сочетания элементов случайности и детерминированности точно, как это происходит в природной среде.

Детерминированность этих методов заключается в моделировании природных процессов отбора, размножения и наследования, происходящих по строго определенным правилам. Основным правилом при этом является закон эволюции: “выживает сильнейший”, который обеспечивает улучшение находимого решения. Другим важным фактором эффективности эволюционных вычислений является моделирование размножения и наследования. Рассматриваемые варианты решений могут по определенному правилу порождать новые решения, которые будут наследовать лучшие черты своих “предков”.

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

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

§ Генетические алгоритмы.

§ Эволюционные стратегии.

§ Эволюционное программирование.

Основное отличие генетических алгоритмов заключается в представлении любой альтернативы решения в виде битовой строки фиксированной длины, манипуляции с которой производятся в отсутствии всякой связи с её смысловой интерпретацией. То есть в данном случае применяется единое универсальное представление любой задачи. Парадигму генетических алгоритмов предложил Джон Холланд, опубликовавший в начале 60-х годов её основные положения. А всеобщее признание она получила после выхода в свет в 1975 году его классического труда “Адаптация в естественных и искусственных системах”.

Эволюционные стратегии, напротив, оперирует объектами, тесно связанными с решаемой задачей. Каждая из альтернатив решения представляется единым массивом,численных параметров, за каждым из которых скрывается, по сути, аргумент целевой функции. Воздействие на данные массивы осуществляется, в отличие от генетических алгоритмов, с учетом их смыслового содержания и направлено на улучшение значений входящих в них параметров.Парадигму эволюционных стратегий предложили в 1973 году Реченберг (I. Rechenberg) в своей работе “Эволюционные стратегии: оптимизация технических систем на основе принципов биологической эволюции” и в 1977 году Шефель (H.-P. Schwefel.) в работе “Численная оптимизация компьютерных моделей посредством эволюционной стратегии”.

В основе направления эволюционного программирования лежит идея представления альтернатив в виде универсальных конечных автоматов, способных реагировать на стимулы, поступающие из окружающей среды. Соответствующм образом разрабатывались и операторы воздействия на них. Идеи эволюционного программирования были предложены в 1966 году Фогелем, Оуэнсом и Уолшем (L.J. Fogel, A.J. Owens,M.J. Walsh) в работе “Построение систем искусственного интеллекта путем моделирования эволюции”.

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

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

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