Модели и алгоритмы принятия решений на основе генетического поиска тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Штуца, Илья Михайлович

• Штуца, Илья Михайлович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Штуца, Илья Михайлович

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

ВВЕДЕНИЕ.

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы принятия решений на основе генетического поиска»

Постановка задачи.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]

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

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

Список литературы диссертационного исследования кандидат технических наук Штуца, Илья Михайлович, 2008 год

1. Базы данных. Интеллектуальная обработка информации/ В.В. Корнеев, А.Ф. Гареев, B.C. Васюткин, В.В. Райх. М.: Нолидж, 2001. - 496 с.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. — Воронеж: Воронеж, 1995. — 64 с.

3. Батищев ДИ. Методы оптимального проектирования.—М.: Радио и связь, 1984.-248 с.

4. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. — Воронеж: Воронеж, 1997. — 416 с.

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: БИНОМ, 2002. 632 с.

6. Брандт 3. Статистические методы анализа наблюдений — М.: Мир, 1975. — 312 с.

7. Букатова И.Л. Эволюционное моделирование и его приложения .- М.: Наука, 1979,- 231 с.

8. Васильев Ф.П. Методы оптимизации. — М.: Факториал Пресс, 2002. — 824с.

9. Гарнаев Ю.А. Самоучитель YBA. Технология создания приложений. — М.: BHV, 1999.-512 с.

10. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности/ Г.К. Вороновскин, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. — Харьков: Основа, 1997. — 112 с.

11. Гладков А.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. — М.: Физматлит, 2006. 320 с.

12. Грешплов А.А. Математические методы принятие решений. — М.:МГТУ им. Н.Э. Баумана, 2006. — 584 с.

13. Дасгупта В. Искусственные имунпые системы и их применение. — М.: Физматлит, 2006. 344 с.

14. Джопс Т. Программирование искусственного интеллекта в приложениях. М.: ДМК Пресс, 2004. - 312 с.15