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

• Автор: Штуца, Илья Михайлович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 204 с. : ил.

ОГЛАВЛЕНИЕ

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

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

1.2.2. Описание генетического алгоритма
1.2.3. Классификация ГА
1.2.4. Символьная модель ГА
1.2.5. Работа классического ГА.
1.2.6. Теорема схем шим
1.3. Применимость ГА
1.4. Анализ идеи и принципов операторов ГА
1.5. Выводы.
ГЛАВА 2. Теоретическое исследование ГА
2.1. Обобщенная модель ГА.
2.2. Модели операторов ГА.
2.2.1. Операторы отбора и замещения.
2.2.2. Оператор скрещивания
2.2.3. Оператор мутации
2.3. Предложение по модификации оператора мутации.
2.4. Условная оптимизация на основе ГА
2.5. Многокритериальная оптимизация на основе ГА
2.6. Выводы
ГЛАВА 3. Разработка инструментария для исследования свойств ГА.
3.1. Разработка функциональной схемы.
3.2. Выбор программного средства.
3.3. Разработка структур данных и оценка емкостной сложности алгоритма.
3.4. Разработка методов задания целевой функции
3.5. Разработка алгоритма оптимизации, оценка вычислгггельной сложности
3.6. Разработка алгоритма кластеризации
3.7. Оценка быстродействия.
3.8. Системы поддержки принятия решений и ГА.
3.9. Выводы
ГЛАВА 4. Проведение численною эксперимента.
4.1. Технология постановки численною эксперимента
4.2. Планирование эксперимента.
4.3. Исследование направлений отимизации.
4.3.1. Оценка поиска на максимум ЦФ.
4.3.2. Оценка поиска на минимум ЦФ
4.3.3. Оценка приведения ЦФ к заданному значению
4.4. Оценка целочисленной оптимизации
4.5. Исследование условной оптимизации.
4.6. Исследование настраиваемых параметров ГА
4.6.1. Исследование различных стратегий отбора
4.6.2. Оценка влияния вероятности скрещивания
4.6.3. Оценка влияния вероятности мутации
4.7. Исследование эволюционирования при смене ЦФ
4.8. Исследование оптимизации разрывных функций.
4.9. Исследование работы ГА с модифицированным оператором мутации.
4 Многокритериальная оптимизация
4 Решение задачи коммивояжера.
41. Постановка задачи
42. Кодирование хромосом.
43. Разработка генетичсских операторов.
44. Результаты решения задач большой размерности.
45. Экспериментальная оценка вычислительной сложности алгоритма
4 Выводы.
ГЛАВА 5. Технологическое прогнозирование производства труб из сплава Э0 .
5.1. Актуальность задачи.
5.2. Пассивный эксперимент.
5.3. Сравнительный анализ регрессионного анализа на основе метода наименьших квадратов и ГА
5.4. Производство труб из сплава Э0 в России.
5.5. Исходные данные и прогнозные модели.
5.6. Анализ результатов
5.7. Выводы
ВЫВОДЫ.
Выводы по диссертации
Основные результаты
Направления дальнейшей работы
СПИСОК ИСТОЧНИКОВ


Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут бьпъ классифицированы как Искусственная Жизнь (Artificial Life). В настоящее время формируется ente одно направление решения оптимизационных задач гг моделирования процессов на основе биологических принципов - «Искусственные иммунные системы» [J. Конечно, эво. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а нс биологических процессах. Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Основные принципы ГА были сформулированы Голландом (Holland, ) [J, и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, ГА только моделируют тс процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос, какие биологические процессы существенны для развитая, и какие нет - все еще открыт для исследователей. В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за привлечение брачного партера. Слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространяться в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению "суперприспособленного" потомка, чья приспособленность больше, чем приспособленность . Таким образом, вил развивается, лучше и лучше приспосабливаясь к среде обитания. ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезачъ из популяции в процессе эволюции. Так и воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это повое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. В конечном итоге, популяция будет сходтъся к оптимальному решению задачи. Имеются много способов реализации идеи биологической эволюции в рамках ГА []. Традиционным считается ГА, представленный на схеме. Рисунок 1.