📄Работа №212580
Тема: Разработка алгоритма глобальной оптимизации на основе метода мультистарта
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Математика
Объем:
48 листов
Год:
2021
Просмотров:
36
4600
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Аннотация
ВВЕДЕНИЕ 7
1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ПОИСКА ГЛОБАЛЬНОГО
МИНИМУМА 9
1.1 Постановка задачи глобальной оптимизации 9
1.2 Описание групп оптимизационных задач 9
1.2.1 Метод мультистарта 12
1.2.2 Туннельные алгоритмы 13
1.2.3 Методы перехода из одного локального минимума в другой 14
1.2.4 Методы сеток 15
1.2.5 Методы покрытий 16
1.2.6 Редукция размерности 17
1.3 Методы локальной минимизации 18
1.4 Описание класса тестовых функций GKLS 22
1.5 Постановка задачи реализации метода оптимизации 24
1.6 Выводы по разделу 25
2 РАЗРАБОТКА И ТЕСТИРОВАНИЕ АЛГОРИТМА ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ 26
2.1 Общее описание алгоритма глобальной оптимизации 26
2.1.1 Алгоритм поиска точек методом мультистарта 26
2.1.2 Алгоритм поиска локальных минимумов методом Ньютона 27
2.2 Реализация алгоритма 29
2.3 Анализ сходимости алгоритма 35
2.4 Оценка трудоемкости алгоритма 35
2.5 Выводы по разделу 41
3 ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА 42
3.1 Описание критериев оценки 42
3.2 Выводы по разделу 46
ЗАКЛЮЧЕНИЕ 47
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 49
ПРИЛОЖЕНИЕ 1 Ошибка! Закладка не определена.
Ошибка! Закладка не определена.
ВВЕДЕНИЕ 7
1 ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ПОИСКА ГЛОБАЛЬНОГО
МИНИМУМА 9
1.1 Постановка задачи глобальной оптимизации 9
1.2 Описание групп оптимизационных задач 9
1.2.1 Метод мультистарта 12
1.2.2 Туннельные алгоритмы 13
1.2.3 Методы перехода из одного локального минимума в другой 14
1.2.4 Методы сеток 15
1.2.5 Методы покрытий 16
1.2.6 Редукция размерности 17
1.3 Методы локальной минимизации 18
1.4 Описание класса тестовых функций GKLS 22
1.5 Постановка задачи реализации метода оптимизации 24
1.6 Выводы по разделу 25
2 РАЗРАБОТКА И ТЕСТИРОВАНИЕ АЛГОРИТМА ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ 26
2.1 Общее описание алгоритма глобальной оптимизации 26
2.1.1 Алгоритм поиска точек методом мультистарта 26
2.1.2 Алгоритм поиска локальных минимумов методом Ньютона 27
2.2 Реализация алгоритма 29
2.3 Анализ сходимости алгоритма 35
2.4 Оценка трудоемкости алгоритма 35
2.5 Выводы по разделу 41
3 ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА 42
3.1 Описание критериев оценки 42
3.2 Выводы по разделу 46
ЗАКЛЮЧЕНИЕ 47
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 49
ПРИЛОЖЕНИЕ 1 Ошибка! Закладка не определена.
Ошибка! Закладка не определена.
📖 Аннотация
В данной работе представлена разработка и исследование алгоритма глобальной оптимизации, основанного на методе мультистарта. Актуальность исследования обусловлена широким спектром прикладных задач, требующих нахождения наилучшего решения в условиях наличия множества локальных экстремумов, где традиционные локальные методы оказываются неэффективными. Основным результатом является создание комбинированного алгоритма, который на первом этапе стратегически выбирает начальные точки для запуска, максимизируя расстояние до уже исследованных областей, а на втором этапе осуществляет локальный поиск с использованием метода Ньютона. Тестирование на функциях класса GKLS показало, что эффективность алгоритма зависит от характеристик задачи, таких как радиус области притяжения глобального минимума и его удаленность от центра параболоида. Научная значимость работы заключается в систематизации подходов к глобальной оптимизации и адаптации метода мультистарта, а практическая – в возможности применения алгоритма в экономическом моделировании, машинном обучении и инженерном проектировании. Теоретической основой послужили труды таких авторов, как А. Жиглявский, исследующий стохастические методы, Я.Д. Сергеев и Д.Е. Квасов, разрабатывающие диагональные алгоритмы, а также М. Gaviano и соавторы, предложившие генератор тестовых функций GKLS для объективной оценки алгоритмов.
📖 Введение
В любой сфере деятельности, будь то развитие экономики или эффективное обучение нейронной сети в программировании, прежде всего стремятся к достижению наилучшего, то есть оптимального результата. До повсеместного распространения ЭВМ методы оптимизации применялись очень редко, так как их практическое применение требовало трудоемких вычислений, которые человеку было не под силу сделать вручную. В настоящее время решение оптимизационных задач все еще является актуальной проблемой и поиск наилучших алгоритмов для их решения продолжается и по сей день, а применение компьютерных технологий дало толчок к развитию теории оптимизации.
Важным разделом данной теории является теория глобальной оптимизации, относящейся к области математического программирования, а ее задачи относятся к числу наиболее сложных, так как отыскание глобального экстремума требует вычисления значения функции во всей допустимой области. Развитие вычислительной техники и увеличение числа прикладных проблем способствовали развитию данной теории. Так, стандартные локальные методы часто неспособны найти глобальное (лучшее) решение, они не могут выйти из зоны локальных оптимумов и за счет этого не достигают глобального оптимума. Нахождение же глобального решения может быть более эффективным по сравнению с локальными.
Результаты исследований при решении задач глобальной оптимизации показали, что в зависимости от классов задач, эффективны различные методы глобального поиска. Поэтому было необходимо провести анализ методов глобальной оптимизации и выбрать наиболее подходящий для решения задач из класса функций GKLS, так как данные задачи являются многомерными и многоэкстремальными. В дальнейшем проводится разработка алгоритма на основе выбранного метода, строится его оценка, а также проводится реализация и тестирование на функциях из класса GKLS. Помимо этого, необходимо также сравнить полученный алгоритм с уже существующими алгоритмами глобальной многоэкстремальной оптимизации и оценить его эффективность. Таким образом, главной задачей данной работы является изучение существующих методов решения задач глобальной оптимизации и разработка алгоритма на основе всей информации.
Важным разделом данной теории является теория глобальной оптимизации, относящейся к области математического программирования, а ее задачи относятся к числу наиболее сложных, так как отыскание глобального экстремума требует вычисления значения функции во всей допустимой области. Развитие вычислительной техники и увеличение числа прикладных проблем способствовали развитию данной теории. Так, стандартные локальные методы часто неспособны найти глобальное (лучшее) решение, они не могут выйти из зоны локальных оптимумов и за счет этого не достигают глобального оптимума. Нахождение же глобального решения может быть более эффективным по сравнению с локальными.
Результаты исследований при решении задач глобальной оптимизации показали, что в зависимости от классов задач, эффективны различные методы глобального поиска. Поэтому было необходимо провести анализ методов глобальной оптимизации и выбрать наиболее подходящий для решения задач из класса функций GKLS, так как данные задачи являются многомерными и многоэкстремальными. В дальнейшем проводится разработка алгоритма на основе выбранного метода, строится его оценка, а также проводится реализация и тестирование на функциях из класса GKLS. Помимо этого, необходимо также сравнить полученный алгоритм с уже существующими алгоритмами глобальной многоэкстремальной оптимизации и оценить его эффективность. Таким образом, главной задачей данной работы является изучение существующих методов решения задач глобальной оптимизации и разработка алгоритма на основе всей информации.
✅ Заключение
Целью данной работы являлось изучение существующих методов глобальной оптимизации с дальнейшей разработкой алгоритма на основе метода мультистарта. Для этого был проведен анализ литературы, определены достоинства и недостатки различных методов, выделены преимущества выбранного метода. Так как метод мультистарта включает в себя фазу локального поиска отдельным алгоритмом, также было проведено исследование методов локального поиска с целью определения алгоритма для этой фазы. На основе выбранных методов был разработан алгоритм программы, включающий в себя фазу выбора начальных точек - мультистарт, и фазу локального поиска из выбранной точки методом Ньютона. Алгоритм мультистарта заключается в вычислении по сетке расстояния от уже найденных локальных минимумов и предыдущих точек старта до новой точки запуска, при этом берется точка, наиболее удаленная от уже существующих.
Далее было проведено тестирование разработанного алгоритма на функциях из генератора тестовых функций класса GKLS. Были выделены несколько классов с различными параметрами для оценки трудоемкости алгоритма по времени выполнения, количеству вызовов тестовых функций и количеству затраченных точек на поиск глобального минимума. По результатам тестирования алгоритм хуже справился с теми классами задач, у которых радиус области притяжения глобального минимума меньше, также на количество вычислений влияет расстояние от глобального минимума до центра параболоида, чем больше это расстояние, тем дольше алгоритм ищет глобальный минимум, хорошо заметны эти моменты на классе 2, где оба параметра в «невыгодных» для алгоритма значениях.
Также была проведена оценка эффективности алгоритма по критериям К 2 — максимальное количество испытаний, затраченное при поиске глобальных минимумов во всех функциях тестового класса, и К 4 — среднее количество испытаний, затраченное при поиске глобальных минимумов во всех функциях тестового класса. Сравнение проводилось с алгоритмами НМ-Ц и НМ-ЦЛ на двух классах функций GKLS с размерностью задач N = 2 и по результатам разработанный алгоритм оказался не так эффективен по обоим критериям, это связанно с реализацией локальной фазы поиска и, несмотря на особенности работы алгоритмов НМ-Ц и НМ-ЦЛ, такие как избыточное разбиение гиперинтервалов, из-за чего сходимость алгоритмов замедлена, разработанный алгоритм не смог достичь таких же результатов. Таким образом, в дальнейшем предполагается улучшение алгоритма для оптимизации фазы локального поиска и улучшения результатов работы.
Далее было проведено тестирование разработанного алгоритма на функциях из генератора тестовых функций класса GKLS. Были выделены несколько классов с различными параметрами для оценки трудоемкости алгоритма по времени выполнения, количеству вызовов тестовых функций и количеству затраченных точек на поиск глобального минимума. По результатам тестирования алгоритм хуже справился с теми классами задач, у которых радиус области притяжения глобального минимума меньше, также на количество вычислений влияет расстояние от глобального минимума до центра параболоида, чем больше это расстояние, тем дольше алгоритм ищет глобальный минимум, хорошо заметны эти моменты на классе 2, где оба параметра в «невыгодных» для алгоритма значениях.
Также была проведена оценка эффективности алгоритма по критериям К 2 — максимальное количество испытаний, затраченное при поиске глобальных минимумов во всех функциях тестового класса, и К 4 — среднее количество испытаний, затраченное при поиске глобальных минимумов во всех функциях тестового класса. Сравнение проводилось с алгоритмами НМ-Ц и НМ-ЦЛ на двух классах функций GKLS с размерностью задач N = 2 и по результатам разработанный алгоритм оказался не так эффективен по обоим критериям, это связанно с реализацией локальной фазы поиска и, несмотря на особенности работы алгоритмов НМ-Ц и НМ-ЦЛ, такие как избыточное разбиение гиперинтервалов, из-за чего сходимость алгоритмов замедлена, разработанный алгоритм не смог достичь таких же результатов. Таким образом, в дальнейшем предполагается улучшение алгоритма для оптимизации фазы локального поиска и улучшения результатов работы.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.