Учебная работа № 1229. Непрерывные генетические алгоритмы

Учебная работа № 1229. Непрерывные генетические алгоритмы

Курсовая работа По дисциплине: «Теория систем и системный анализ»

Выполнила тудентка 3 курса 1 группы Специальности ПИУ Антипина Г.С.

Государственный университет управления

Москва 2006

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

Примерами таких задач могут являться:

Прогнозирование курсов валют;

Прогнозирование спроса;

Прогнозирование дохода компании;

Прогнозирование уровня безработицы;

Оптимизация расписаний;

Оптимизация плана закупок, плана инвестиций;

Оптимизация стратегии развития.

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

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

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

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

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

В частности, рассмотрим проблемы, возникающие при решении этой задачи:

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

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

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

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

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

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

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

Теория алгоритмов. Задача коммивояжера.

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.

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

Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных.

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

В рамках классической теории осуществляется классификация задач по классам сложности (Pсложные, NPсложные, экспоненциально сложные и др.).

К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга).

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

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

Задача коммивояжёра (коммивояжёр — бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз, в таком случае выбор осуществляется среди гамильтоновых циклов[1] .

Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра.

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

Задача коммивояжёра есть NPполная задача[2] . Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

В следующем разделе мы перейдём к рассмотрению генетических алгоритмов.

Генетические алгоритмы. Общее описание. Математический аппарат.

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Представление объектов.

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

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Кодирование признаков, представленных целыми числами

Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:

Двоичное кодирование			Кодирование по коду Грея
Десятичный код	Двоичное значение	Шестнадцатеричное значение	Десятичный код	Двоичное значение	Шестнадцатеричное значение
0	0000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

Таблица 1. Соответствие десятичных кодов и кодов Грея.

Таким образом, при кодировании целочисленного признака мы разбиваем его на тетрады и каждую тетраду преобразуем по коду Грея.

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

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

Кодирование признаков, которым соответствуют числа с плавающей точкой

Самый простой способ кодирования, который лежит на поверхности – использовать битовое представление. Хотя такой в

Учебная работа № 1229. Непрерывные генетические алгоритмы