Коляда Александр Владимирович. Исследование ландшафтов целевых функций при эволюционной оптимизации

brief description

Коляда Александр Владимирович. Исследование ландшафтов целевых функций при эволюционной оптимизации : Дис. ... канд. техн. наук : 05.13.01 Таганрог, 2005 214 с. РГБ ОД, 61:05-5/3083

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ
На правах рукописи
КОЛЯДА Александр Владимирович
ИССЛЕДОВАНИЕ ЛАНДШАФТОВ ЦЕЛЕВЫХ
ФУНКЦИЙ ПРИ ЭВОЛЮЦИОННОЙ ОПТИМИЗАЦИИ
Специальность: 05.13.01 - системный анализ, управление и обработка
информации
Диссертация на соискание учёной степени
кандидата технических наук
Научный руководитель: Заслуженный деятель науки РФ, д.т.н., профессор Курейчик В.М.
Таганрог - 2005 
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 4
1. ПРИМЕНЕНИЕ АНАЛИЗА ЛАНДШАФТОВ ДЛЯ ВЫБОРА
ЭФФЕКТИВНОЙ ЦЕЛЕВОЙ ФУНКЦИИ 16
1.1. Анализ методов решения оптимизационных задач 16
1.2. Анализ целевых функций 20
1.3. Постановка задачи диссертационной работы 25
1.4. Использование ландшафта целевой функции для оценки её
эффективности 27
1.5. Использование ландшафтов для оценки эффективности непрерывных
целевых функций 28
1.6. Использование ландшафтов для оценки эффективности дискретных
целевых функций 36
1.7. Выводы и предложения 41
2. РАЗРАБОТКА МЕТОДОВ, ПОЗВОЛЯЮЩИХ СРАВНИВАТЬ
ЭФФЕКТИВНОСТЬ РАЗЛИЧНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ 43
2.1. Применение метода барьерных деревьев для анализа ландшафтов
целевых функций 43
2.2. Пример расчёта глубины и сложности ландшафта 52
2.3. Выводы и рекомендации по методу барьерных деревьев 59
2.4. Применение метода, основанного на спектральной теории для анализа
ландшафтов целевых функций 59
2.5. Пример расчёта спектра 74
2.6. Выводы и рекомендации по спектральному методу 91
2.7. Аппроксимация ландшафта целевой функции при помощи нейронной
сети 92
2.8. Пример аппроксимации ландшафта 96
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЕ
ЭКСПЕРИМЕНТЫ 103
3.1. Программа анализа ландшафтов целевых функций по методу барьерных
деревьев (LANDS) 103
3.2. Программа анализа ландшафтов целевых функций по методу,
основанному на спектральной теории (SPECTR) 109
3.3. Комплексная программа позволяющая сравнивать эффективность
различных алгоритмов (OCENKA) 111
3.4. Исследования по выявлению зависимости спектра от характера
поверхности 117
3.5. Исследования по выявлению связи спектра поверхности с её
сложностью 126
3.6. Новые методы сравнения спектров и анализ функций ДеИонга 134
3.7. Выводы и рекомендации 138
3.8. Практическое использование разработанного метода на примере задачи
о рюкзаке 139
3.9. Практическое использование разработанного метода на примере выбора
оптимальных параметров вибраторной антенны 141
3.10. Программа аппроксимации ландшафтов многомерных поверхностей
при помощи нейронной сети 147
ЗАКЛЮЧЕНИЕ 154
СПИСОК ЛИТЕРАТУРЫ 156
ПРИЛОЖЕНИЕ 1 165
ПРИЛОЖЕНИЕ 2 171
ПРИЛОЖЕНИЕ 3 173
ПРИЛОЖЕНИЕ 4 188
ПРИЛОЖЕНИЕ 5 191
ПРИЛОЖЕНИЕ 6 201
ПРИЛОЖЕНИЕ 7 210

bibliography

ЗАКЛЮЧЕНИЕ
1. Проанализированы существующие методы анализа ландшафтов целевых функций. Выделены их достоинства и недостатки. Определены области их применения.
2. Разработан алгоритм, позволяющий анализировать ландшафты целевых функций по методу барьерных деревьев. Разработан алгоритм поиска локальных оптимумов и путей из одного локального оптимума в другой, основанный на волновом алгоритме. Разработан алгоритм построения барьерного дерева. Осуществлена программная реализация разработанных алгоритмов, которая позволяет автоматизировать процесс анализа целевой функции по методу барьерных деревьев.
3. Разработан алгоритм, позволяющий анализировать ландшафты целевых функций по спектральному методу. Для этого выбран метод расчёта собственных чисел и собственных векторов. Осуществлена программная реализация разработанного алгоритма, которая позволяет автоматизировать процесс анализа целевой функции по спектральному методу.
4. Установлена зависимость между видом и параметрами амплитудного спектра ландшафта целевой функции и её сложностью с точки зрения эволюционных вычислений.
5. Предложен метод сравнения спектров на основе новых интегральных параметров, позволяющий точнее определять эффективность целевой функции, а также автоматизировать этот процесс.
6. Предложена идея расширяемого комплексного программного обеспечения позволяющего автоматизировать процесс выбора эффективной целевой функции, в основе которого лежат алгоритмы разработанные ранее. Осуществлена программная реализация предложенного программного обеспечения, которое включает реализацию нескольких методов анализа целевых функций, позволяющих
их сравнивать. Кроме того, функциональность разработанного программного обеспечения может расширяться за счёт других программ.
7. Проведены вычислительные эксперименты, которые позволили сделать выводы и рекомендации о том, каким образом использовать полученные интегральные параметры ландшафтов для анализа и сравнения их целевых функций. Показано, каким образом можно сравнивать целевые функции по методу барьерных деревьев, используя для этого рассчитанные глубину и сложность их ландшафтов. Установлена взаимосвязь спектра ландшафта целевой функции с характером ландшафта целевой функции - количеством локальных оптимумов, их величиной, размером их бассейнов и т.д. Определено, каким образом можно, используя спектр ландшафта среднее собственное число, и несколько новых интегральных параметров сравнивать эффективности целевых функций.
8. Проведены вычислительные эксперименты, в которых на примере задачи о рюкзаке и задачи выбора оптимальных параметров вибраторных антенн, было показано, как можно использовать разработанный комплекс алгоритмов и программ для выбора эффективной целевой функции. В ходе данного комплекса экспериментов была также доказана возможность практического применения разработанных методов и алгоритмов.