1626434812-e667f6b6e7e69d3a0798830a58e9075b (844135), страница 41

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 41)

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

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

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

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

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

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

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

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

То есть в данном случае применяется единое универсальное представление любой задачи. Парадигму генетических алгоритмов предложил Джон Холланд, опубликовавший в начале 60-х годов ее основные положения. А Базы данных Интеллектуальная обработка информа~ии всеобщее признание она получила после выхода в свет в 1975 году его классического труда "Адаптация в естественных и искусственных системах". Эволюционные стратегии, напротив, оперируют объектами„тесно связанными с решаемой задачей.

Каждая из альтернатив решения представляется единым массивом численных параметров, за каждым из которых скрывается, по сути, аргумент целевой функции, Воздействие на данные массивы осуществляется, в отличие от генетических алгоритмов, с учетом их смыслового содержания и направлено на улучшение значений входящих в них параметров. Парадигму эволюционных стратегий предложили в 1973 году Реченбсрг (1. КесЬепЬегц) в своей работе "Эволюционные стратегии: оптимизация технических систем на основе принципов биологической эволюции" и в 1977 году Шефель (Н.-Р.

ЯсЬжеЫ) в работе "Численная оптимизация компьютерных моделей посредством эволюционной стратегии", В основе направления эволюционного программирования лежит идея представления альтернатив в виде универсальных конечных автоматов, способных реагировать на стимулы, поступающие из окружающей среды. Соответствующим образом разрабатывались и операторы воздействия на них. Идеи эволюционного программирования были предложены в 1966 году Фогелем, Оуэнсом и Уолшем (1 3. Гояе1, А.3. О~чепа, МЗ.

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

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

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

Глаеа 8. Генетические алгоритмы 8.2 Основы теории генетических алгоритмов Генетические алгоритмы, являясь одной из парадигм эволюционных вычислений, представляют собой алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора и генетики. Если говорить обобшенно, они объединяют в себе принцип выживания наиболее перспективных особей — решений и структуризированный обмен информацией, в котором присутствует элемент случайности, который моделирует природные процессы наследования и мутации. Дополнительным свойством этих алгоритмов является невмешательство человека в развивающийся процесс поиска. Человек может влиять на него лишь опосредованно, задавая определенные параметры.

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

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

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

Характеристики

Список файлов книги