Модели и алгоритмы принятия решений на основе генетического поиска

Постановка задачи.9.

ГЛАВА 1. Анализ генетических алгоритмов в контексте методов функциональной оптимизации.10.

1.1. Методы функциональной оптимизации.10.

1.1.1. Детерминированные методы.10.

1.1.2. Вероятностные методы.12.

1.2.

Введение

в генетические алгоритмы.12.

1.2.1. История появления и развития ГА.12.

1.2.2. Описание генетического алгоритма.16.

1.2.3. Классификация ГА.18.

1.2.4. Символьная модель ГА.25.

1.2.5. Работа классического ГА.28.

1.2.6. Теорема схем (шим).30.

1.3. Применимость ГА.34.

1.4. Анализ идеи и принципов операторов ГА.35.

1.5. Выводы.37.

ГЛАВА 2. Теоретическое исследование ГА.39.

2.1. Обобщенная модель ГА.39.

2.2. Модели операторов ГА.39.

2.2.1. Операторы отбора и замещения.•.39.

2.2.2. Оператор скрещивания.42.

2.2.3. Оператор мутации.44.

2.3. Предложение по модификации оператора мутации.45.

2.4. Условная оптимизация на основе ГА.48.

2.5. Многокритериальная оптимизация на основе ГА.50.

2.6. Выводы.57.

ГЛАВА 3. Разработка инструментария для исследования свойств ГА.59.

3.1. Разработка функциональной схемы.59.

3.2. Выбор программного средства.61.

3.3. Разработка структур данных и оценка емкостной сложности алгоритма. 63.

3.4. Разработка методов задания целевой функции.67.

3.5. Разработка алгоритма оптимизации, оценка вычислительной сложности .69.

3.6. Разработка алгоритма кластеризации.72.

3.7. Оценка быстродействия.74.

3.8. Системы поддержки принятия решений и ГА.77.

3.9. Выводы.81.

ГЛАВА 4. Проведение численного эксперимента.82.

4.1. Технология постановки численного эксперимента.82.

4.2. Планирование эксперимента.84.

4.3. Исследование направлений оптимизации.86.

4.3.1. Оценка поиска на максимум ЦФ.86.

4.3.2. Оценка поиска на минимум ЦФ.89.

4.3.3. Оценка приведения ЦФ к заданному значению.92.

4.4. Оценка целочисленной оптимизации.94.

4.5. Исследование условной оптимизации.95.

4.6. Исследование настраиваемых параметров ГА.97.

4.6.1. Исследование различных стратегий отбора.97.

4.6.2. Оценка влияния вероятности скрещивания.100.

4.6.3. Оценка влияния вероятности мутации.103.

4.7. Исследование эволюционирования при смене ЦФ.106.

4.8. Исследование оптимизации разрывных функций.108.

4.9. Исследование работы ГА с модифицированным оператором мутации. 110.

4.10. Многокритериальная оптимизация.113.

4.11. Решение задачи коммивояжера.115.

4.11.1. Постановка задачи.115.

4.11.2. Кодирование хромосом.116.

4.11.3. Разработка TSP-генетических операторов.116.

4.11.4. Результаты решения задач большой размерности.120.

4.11.5. Экспериментальная оценка вычислительной сложности алгоритма .128.

4.12. Выводы.132.

ГЛАВА 5. Технологическое прогнозирование производства труб из сплава Э110 .134.

5.1. Актуальность задачи.134.

5.2. Пассивный эксперимент.135.

5.3. Сравнительный анализ регрессионного анализа на основе метода наименьших квадратов и ГА.136.

5.4. Производство труб из сплава Э110 в России.138.

5.5. Исходные данные и прогнозные модели.141.

5.6. Анализ результатов.143.

5.7. Выводы.152.

ВЫВОДЫ.153.

Выводы по диссертации.153.

Основные результаты.155.

Направления дальнейшей работы.157.

СПИСОК ИСТОЧНИКОВ.158.

ПРИЛОЖЕНИЯ.168.

ПРИЛОЖЕНИЕ 1. Существующие пакеты оптимизации на основе ГА.168.

Evolver (Palisade Corp.).168.

GeneHunter (WARD Systems Group).173.

ПРИЛОЖЕНИЕ 2. Тестовые функции для исследования оптимизации на основе ГА.176.

ПРИЛОЖЕНИЕ 3. Данные для решения задачи коммивояжера.183.

ПРИЛОЖЕНИЕ 4. Руководство пользователя.184.

ПРИЛОЖЕНИЕ 5. Исходные данные по решению задачи технологического прогнозирования производства труб из сплава Э110.200.

ПРИЛОЖЕНИЕ 6. Акт № 981−04/2415 от 25.04.2007. Использование результатов диссертации на ОАО ЧМЗ.203.

ПРИЛОЖЕНИЕ 7. Акт внедрения результатов диссертации в МИСиС.204.

СПИСОК ТЕРМИНОВ И СОКРАЩЕНИЙ.

Аллель — значение гена, вариант свойства.

Генетический алгоритм (классический), ГА — алгоритм поиска оптимальной битовой строки, который случайным образом выбирает начальную популяцию таких строк и затем подвергает их процессу искусственных мутаций, скрещивания и отбора по аналогии с естественным отбором (Goldberg, 1989) Ген — атомарный элемент генотипа, в частности, хромосомы Генотип — набор хромосом данной особи (часто генотип особи состоит из одной хромосомы).

Кроссинговер (кроссовер) — оператор ГА, который позволяет получать сходный генотип по отношению к нескольким заданным Локус — позиция размещения гена в хромосоме.

Мутация — оператор ГА, который позволяет случайным образом изменять генотип.

Особь — вариант решения поставленной задачи (точка в пространстве поиска), в контексте ГА представляется хромосомой (хромосомами) с закодированным множеством параметров задачи.

Отбор — оператор ГА, который выделяет наиболее приспособленных особей из популяции для выполнения операторов скрещивания и мутации, а наименее приспособленных — для удаления из популяции.

Поколение — стадия развития популяции, которая характеризуется степенью обновления ее членов.

Популяция — конечное множество особей.

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

Актуальность проблемы.

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

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

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

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

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

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

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

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

Постановка задачи.

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

В рамках поставленной цели решаются следующие задачи:

Анализ существующих модификаций ГА, идей и принципов лежащих в их реализации;

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

Разработка инструментария и методики проведения численных экспериментов по исследованию свойств ГА;

Выполнение численных экспериментов по исследованию свойств, влияния настраиваемых параметров и временной сложности ГА, анализ результатов;

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

Основные результаты.

В процессе исследований, выполненных в рамках диссертационной работы, получены следующие основные результаты: выполнена классификация генетических алгоритмов с подробным описанием существующих модификаций, что позволяет строить ГА на основе сочетаний различных стратегий из классификаторапроанализированы идеи и принципы операторов ГА на основе которых построена обобщающая модель генетического алгоритма позволяющая математически формализовать ГАна основе геометрических интерпретации действия операторов скрещивания и мутации, позволяющих более глубоко понять принципы функционирования генетического алгоритма, выявлена аналогия между генетическим алгоритмом и методом ветвей и границ, позволяющая прогнозировать основные характеристики ГАпредложен метод повышения эффективности ГА, связанный с нелинейным уменьшением максимального значения приращения оператора мутации и алгоритмом кластеризациипредложен подход к решению задач условной оптимизации с использованием штрафных функцийпредложен подход к решению задачи многокритериальной оптимизации на основе ГА и принципа справедливого компромиссаразработан пакет для решения оптимизационных научных и прикладных задач на основе ГАопределено влияние настраиваемых параметров метода, позволяющее выделить оптимальные сочетания для решения различных классов задач — проведено решение NP-полной задачи большой размерности (на примере задачи коммивояжера), подтвердившей возможность нахождения глобального оптимума и получена экспериментальная оценка вычислительной сложности генетического алгоритма, которая оказалась квадратичнойвыполнено технологическое (в зависимости от изменения многочисленных технологических факторов) прогнозирование эксплуатационных свойств труб из сплава Э110 произведенных на предприятии отечественной промышленности на основе сравнительного анализа аппроксимации на основе метода наименьших квадратов и ГА. Достоверность прогноза подтверждена улучшением и стабилизацией свойств (предела прочности, предела текучести, относительного удлинения, коэффициента ориентации гидридов, коэффициента анизотропии) циркониевых труб, выпущенных в течение 4 кв. 2006 — 1 кв. 2007 г. г.

Направления дальнейшей работы.

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

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

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

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