Geum.ru

История появления эволюционных алгоритмов

Вид материалаДокументы

Содержание


Три задачи генетического алгоритма
Подобный материал:
1   2   3   4   5   6   7   8   9

Три задачи генетического алгоритма



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


задача быстрой локализации одного оптимального значения,


задача определения нескольких (или всех) глобальных экстремумов,


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


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

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

Для решения второй задачи, очевидно, вопросу "исследования" пространства поиска должно уделяться гораздо большее внимание. Оно достигается за счет другого сочетания параметров и достаточно большой численности популяции, при этом ГА сможет выделить несколько (или даже все) глобальные экстремумы. В качестве примера решения такой задачи приведем экспериментальные данные, полученные при поиске максимумов двумерной функции Растригина. Параметры генетического алгоритма, использовавшиеся для максимизации этой функции, такие же, как и для решения других тестовых задач (см. комментарий к таблице 1.) Итак, средние показатели процесса поиска по 50 испытаниям, в скобках для сравнения приведены результаты, опубликованные в [6]:


среднее значение приспособленности - 80.694,


число вычислений функции - 652 (1282), что составляет порядка 15 поколений,


частота локализации всех 4 точек глобального экстремума равна 1 (в [6] локализовывался один максимум).

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

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


ЗАДАЧИ



4 Примеры реальных задач

Оптимальное распределение инвестиций

Задача. Имеется инвестиционный капитал, который нужно распределить среди 10 проектов. Для каждого проекта задана функция зависимости прибыли от объема вложения. Требуется найти наиболее прибыльный вариант распределения капитала, при условии, что заданы минимальный и максимальный объем инвестиций для каждого проекта.

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

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


5 Недостатки традиционных технологий


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

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


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


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


Если одна из функций нелинейна, то симплекс-метод неприменим, и остается два традиционных пути решения этой задачи.

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

Второй путь - провести полный перебор вариантов инвестирования. Если каждая из 10 функций задана в 100 точках, то придется проверить около 1020 вариантов, что потребует не менее нескольких месяцев работы современного компьютера.

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

6 Новые технологии


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


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