Алгоритм стаи серых волков для решения задач оптимизации
|
Аннотация 2
1. Введение 3
2. Методы исследования 8
2.1 Метод градиентного спуска 8
2.1.1 Метод наискорейшего спуска с автоматическим выбором параметра 9
2.1.2 Результаты расчетов 11
2.2 Метод дифференциальной эволюции 13
2.2.1 Описание метода 13
2.2.2 Вычислительные эксперименты по настройке параметров метода (NP, CR, w)..18
2.3 Метод стаи серых волков 23
2.3.1 Описание метода 25
2.3.2 Результаты вычислительных экспериментов по настройке параметров метода(а,
NP) 28
2.4 Сравнительный анализ методов дифференциальной эволюции и стаи стаи серых
волков 35
2.4.1 Влияние выбора размера популяции 35
2.4.2 Сравнение эффективности работы алгоритмов для различных размеров задач. 37
2.4.3 Сравнение при n = 6 при NP = 50 для различных оптимизируемых функций.. .39
3 Применение методов стаи серых волков и дифференциальной эволюции для
нахождения решения плохо обусловленной системы уравнений 41
4 Заключение 45
5 Список использованной литературы 47
1. Введение 3
2. Методы исследования 8
2.1 Метод градиентного спуска 8
2.1.1 Метод наискорейшего спуска с автоматическим выбором параметра 9
2.1.2 Результаты расчетов 11
2.2 Метод дифференциальной эволюции 13
2.2.1 Описание метода 13
2.2.2 Вычислительные эксперименты по настройке параметров метода (NP, CR, w)..18
2.3 Метод стаи серых волков 23
2.3.1 Описание метода 25
2.3.2 Результаты вычислительных экспериментов по настройке параметров метода(а,
NP) 28
2.4 Сравнительный анализ методов дифференциальной эволюции и стаи стаи серых
волков 35
2.4.1 Влияние выбора размера популяции 35
2.4.2 Сравнение эффективности работы алгоритмов для различных размеров задач. 37
2.4.3 Сравнение при n = 6 при NP = 50 для различных оптимизируемых функций.. .39
3 Применение методов стаи серых волков и дифференциальной эволюции для
нахождения решения плохо обусловленной системы уравнений 41
4 Заключение 45
5 Список использованной литературы 47
Актуальность
Само понятие задач оптимизации подразумевает отыскание наилучшего решения среди совокупности всех возможных, что без каких-либо сомнений наталкивает на мысль об их повсеместном применении. Изо дня в день человек стремится найти самое эффективное для него решение проблемы с минимальными затратами. Однако, упоминая решение задачи оптимизации, нельзя говорить лишь о рутинных потребностях человека, ведь данная тема в действительности обладает большей глобальностью, чем может показаться на первый взгляд. Для детального погружения в актуальность обсуждаемой темы следует привести конкретные примеры областей, для успешной деятельности которых необходим процесс оптимизации:
1. Экономика, а в частности одно из ее направлений — логистика.
Целью логистических компаний всегда является выбор наиболее эффективного варианта обеспечения различных систем товарно-материальными ресурсами.
2. В таких разделах автоматики как робототехника и производственное управление также применяются задачи оптимизации.
3. Инженерное дело, конкретнее — задачи планировки и размещения объектов.
4. Решение множественных задач календарного планирования(теории расписаний) невозможно представить без использования оптимизационных задач.
Вышеперечисленные конкретные примеры лишь малая часть всевозможных областей применения оптимизации, что не дает усомниться в ее актуальности на сегодняшний день.
Классификация методов оптимизации
Методы, на основе которых построены алгоритмы нахождения оптимума функции называют методами оптимизации. Выделяют несколько основных критериев, определяющих их классификацию.
По способу отыскания решения:
1. аналитические(к ним относят методы дифференциального и вариационного исчисления, а также принцип максимума Понтрягина)
2. численные(методы, в которых как исходные данные, так и сами решения представимы в виде чисел).
По критерию размерности задачи:
1. задачи одномерной оптимизации
2. задачи многомерной оптимизации
По определению значений входных параметров:
1. детерминированные(значения переменных определяются
однозначно)
2. стохастические(используется понятие случайной величины)
3. комбинированные
По порядку метода:
1. Методы нулевого порядка(прямые)
2. Методы первого порядка(используется информация не только о
самой функции, но и значениях ее первых производных)
3. Методы второго порядка(при работе используется информация о функции, а также значениях первых и вторых производных)
Обоснование выбора методов
В данной работе будут рассмотрены следующие методы оптимизации: метод наискорейшего спуска, метод дифференциальной эволюции и метод стаи серых волков.
Метод наискорейшего спуска [3] является разновидностью градиентных методов, его особенность заключается в выборе длины шага из решения задачи одномерной минимизации. Алгоритм метода достаточно прост в реализации, использовании, а также широко распространен, что делает его первым кандидатом для изучения в данной работе.
Метод дифференциальной эволюции [4] относят к классу стохастических методов, использующих в своей работе генератор случайных чисел. Кроме того, изучаемый метод не требует использование производных, что позволяет применять его к недифференцируемым, нелинейным, а также многоэкстремальным целевым функциям. Дифференциальная эволюция относится к эволюционным алгоритмам, однако алгоритм метода не обусловлен биологически, что вызывает бурный интерес к изучению.
Метод стаи серых волков [9] — это метаэвристический алгоритм для поиска минимума функции, он основывается на типичном образе жизни стаи, их принципах охоты, а также иерархии волков в природе. Данный метод самый «молодой» среди вышеупомянутых, однако это вовсе не значит, что он уступит в эффективности двум предыдущим. Кроме того, согласно [5] алгоритм стаи серых волков имеет достаточно неплохие результаты при его сравнении с другими известными алгоритмами, такими как генетический алгоритм и алгоритм роя частиц.
Цель работы
Первостепенной задачей работы является изучение методов численной оптимизации функции многих переменных, а также практическое их применение к некоторым тестовым функциям. Кроме того, интерес представляет также выявление лучшего набора параметров каждого из методов, а в дальнейшем и обнаружение наиболее эффективного алгоритма среди описанных.
Заключительным пунктом поставленных целей будет применение двух лучших методов при решении прикладной задачи оптимизации, такой как нахождение решения плохо обусловленной системы уравнений.
Описание тестовых функций
В данном разделе дается краткое описание выбранным тестовым функциям, к которым в дальнейшем и будут применены алгоритмы. Чтобы иметь достаточно разнообразное видение методов численной оптимизации предлагается остановить свой выбор на функциях Растригина и Розенброка.
Функция Растригина — невыпуклая функция, задающаяся уравнением
n
f ( X ) = An +^(x2-Acos(2nxi)) , где А = 10 и X,.G[-5.12,5.12] . Глобальный
i=1
минимум в точке х=0 , где f (x)=0 . Данная функция имеет большое
количество локальных экстремумов(в чем не сложно убедиться, взглянув на ее график(рис.1)), а это в определенной мере усложняет процесс поиска
глобального минимума.Функция Розенброка — невыпуклая функция, задающаяся уравнением
n
fl -уЛ— А I 1 ПП I V2 V 12Ж I V 1 ^21 ТТттст TTRWV TTA'AAAJAtrtTKTY АТТ ТУ А ТТА ТТСГА'ТА СГ
j (x)— (100(x(2у—1) x2i) + (X(2i-1) 1) ) . для двух переменных определяется
i —1
следующим образом: f (x,y)—(1 — x)2+100(y — x2)2 . Она имеет глобальный минимум в точке (x,y)—(1,1) , где f (x,y)—0 . Считается, что поиск глобального минимума этой тестовой функции является нетривиальной задачей, ведь он находится внутри длинной, узкой, параболической полосы(рис.2).
Само понятие задач оптимизации подразумевает отыскание наилучшего решения среди совокупности всех возможных, что без каких-либо сомнений наталкивает на мысль об их повсеместном применении. Изо дня в день человек стремится найти самое эффективное для него решение проблемы с минимальными затратами. Однако, упоминая решение задачи оптимизации, нельзя говорить лишь о рутинных потребностях человека, ведь данная тема в действительности обладает большей глобальностью, чем может показаться на первый взгляд. Для детального погружения в актуальность обсуждаемой темы следует привести конкретные примеры областей, для успешной деятельности которых необходим процесс оптимизации:
1. Экономика, а в частности одно из ее направлений — логистика.
Целью логистических компаний всегда является выбор наиболее эффективного варианта обеспечения различных систем товарно-материальными ресурсами.
2. В таких разделах автоматики как робототехника и производственное управление также применяются задачи оптимизации.
3. Инженерное дело, конкретнее — задачи планировки и размещения объектов.
4. Решение множественных задач календарного планирования(теории расписаний) невозможно представить без использования оптимизационных задач.
Вышеперечисленные конкретные примеры лишь малая часть всевозможных областей применения оптимизации, что не дает усомниться в ее актуальности на сегодняшний день.
Классификация методов оптимизации
Методы, на основе которых построены алгоритмы нахождения оптимума функции называют методами оптимизации. Выделяют несколько основных критериев, определяющих их классификацию.
По способу отыскания решения:
1. аналитические(к ним относят методы дифференциального и вариационного исчисления, а также принцип максимума Понтрягина)
2. численные(методы, в которых как исходные данные, так и сами решения представимы в виде чисел).
По критерию размерности задачи:
1. задачи одномерной оптимизации
2. задачи многомерной оптимизации
По определению значений входных параметров:
1. детерминированные(значения переменных определяются
однозначно)
2. стохастические(используется понятие случайной величины)
3. комбинированные
По порядку метода:
1. Методы нулевого порядка(прямые)
2. Методы первого порядка(используется информация не только о
самой функции, но и значениях ее первых производных)
3. Методы второго порядка(при работе используется информация о функции, а также значениях первых и вторых производных)
Обоснование выбора методов
В данной работе будут рассмотрены следующие методы оптимизации: метод наискорейшего спуска, метод дифференциальной эволюции и метод стаи серых волков.
Метод наискорейшего спуска [3] является разновидностью градиентных методов, его особенность заключается в выборе длины шага из решения задачи одномерной минимизации. Алгоритм метода достаточно прост в реализации, использовании, а также широко распространен, что делает его первым кандидатом для изучения в данной работе.
Метод дифференциальной эволюции [4] относят к классу стохастических методов, использующих в своей работе генератор случайных чисел. Кроме того, изучаемый метод не требует использование производных, что позволяет применять его к недифференцируемым, нелинейным, а также многоэкстремальным целевым функциям. Дифференциальная эволюция относится к эволюционным алгоритмам, однако алгоритм метода не обусловлен биологически, что вызывает бурный интерес к изучению.
Метод стаи серых волков [9] — это метаэвристический алгоритм для поиска минимума функции, он основывается на типичном образе жизни стаи, их принципах охоты, а также иерархии волков в природе. Данный метод самый «молодой» среди вышеупомянутых, однако это вовсе не значит, что он уступит в эффективности двум предыдущим. Кроме того, согласно [5] алгоритм стаи серых волков имеет достаточно неплохие результаты при его сравнении с другими известными алгоритмами, такими как генетический алгоритм и алгоритм роя частиц.
Цель работы
Первостепенной задачей работы является изучение методов численной оптимизации функции многих переменных, а также практическое их применение к некоторым тестовым функциям. Кроме того, интерес представляет также выявление лучшего набора параметров каждого из методов, а в дальнейшем и обнаружение наиболее эффективного алгоритма среди описанных.
Заключительным пунктом поставленных целей будет применение двух лучших методов при решении прикладной задачи оптимизации, такой как нахождение решения плохо обусловленной системы уравнений.
Описание тестовых функций
В данном разделе дается краткое описание выбранным тестовым функциям, к которым в дальнейшем и будут применены алгоритмы. Чтобы иметь достаточно разнообразное видение методов численной оптимизации предлагается остановить свой выбор на функциях Растригина и Розенброка.
Функция Растригина — невыпуклая функция, задающаяся уравнением
n
f ( X ) = An +^(x2-Acos(2nxi)) , где А = 10 и X,.G[-5.12,5.12] . Глобальный
i=1
минимум в точке х=0 , где f (x)=0 . Данная функция имеет большое
количество локальных экстремумов(в чем не сложно убедиться, взглянув на ее график(рис.1)), а это в определенной мере усложняет процесс поиска
глобального минимума.Функция Розенброка — невыпуклая функция, задающаяся уравнением
n
fl -уЛ— А I 1 ПП I V2 V 12Ж I V 1 ^21 ТТттст TTRWV TTA'AAAJAtrtTKTY АТТ ТУ А ТТА ТТСГА'ТА СГ
j (x)— (100(x(2у—1) x2i) + (X(2i-1) 1) ) . для двух переменных определяется
i —1
следующим образом: f (x,y)—(1 — x)2+100(y — x2)2 . Она имеет глобальный минимум в точке (x,y)—(1,1) , где f (x,y)—0 . Считается, что поиск глобального минимума этой тестовой функции является нетривиальной задачей, ведь он находится внутри длинной, узкой, параболической полосы(рис.2).
В следствие проделанной работы можно сделать следующие выводы: были успешно изучены три метода оптимизации такие как метод наискорейшего спуска, дифференциальной эволюции и стаи серых волков. Экспериментальные исследования способствовали нахождению наиболее благоприятного определения параметров для каждого из методов, приложенных к двум тестовым функциям — Растригина и Розенброка. Для выявления самого эффективного среди них было произведено сравнение по нескольким параметрам.
Метод наискорейшего спуска оказался не таким эффективным в нахождении глобального минимума функции Растригина, имеющей множество точек экстремума. Ему удавалось лишь «проваливаться» в ближайший локальный минимум, чего нельзя сказать о методах дифференциальной эволюции и стаи серых волков, которые с легкостью справились с поставленной задачей. С функцией же Розенброка ни у одного из рассмотренных методов не возникло проблем в поисках оптимального решения.
Таким образом, сравнение трех методов сократилось до двух. Теперь же было необходимо провести исследования влияния таких параметров как размер популяции, размерность задачи, а также выбор функции на эффективность методов стаи серых волков и дифференциальной эволюции. В ходе подобных экспериментов безусловное лидерство одержал алгоритм метода стаи серых волков, превзошедший своего конкурента в большинстве сравнительных операций.
Заключительным этапом работы является практическое применение двух лидирующих алгоритмов для отыскания решения системы уравнений с плохо обусловленной матрицей. При равных условиях алгоритм метода дифференциальной эволюции уступил алгоритму стаи серых волков, справившись с задачей менее эффективно.
Все вышеупомянутые сравнительные операции приводят к выводу о том, что метод стаи серых волков является наиболее эффективным алгоритмом, чем метод дифференциальной эволюции и метод наискорейшего спуска, особенно в задачах оптимизации с большим числом локальных минимумов. Кроме того, он способен успешно справиться с такой непростой математической задачей как решение плохо обусловленной системы уравнений.
Метод наискорейшего спуска оказался не таким эффективным в нахождении глобального минимума функции Растригина, имеющей множество точек экстремума. Ему удавалось лишь «проваливаться» в ближайший локальный минимум, чего нельзя сказать о методах дифференциальной эволюции и стаи серых волков, которые с легкостью справились с поставленной задачей. С функцией же Розенброка ни у одного из рассмотренных методов не возникло проблем в поисках оптимального решения.
Таким образом, сравнение трех методов сократилось до двух. Теперь же было необходимо провести исследования влияния таких параметров как размер популяции, размерность задачи, а также выбор функции на эффективность методов стаи серых волков и дифференциальной эволюции. В ходе подобных экспериментов безусловное лидерство одержал алгоритм метода стаи серых волков, превзошедший своего конкурента в большинстве сравнительных операций.
Заключительным этапом работы является практическое применение двух лидирующих алгоритмов для отыскания решения системы уравнений с плохо обусловленной матрицей. При равных условиях алгоритм метода дифференциальной эволюции уступил алгоритму стаи серых волков, справившись с задачей менее эффективно.
Все вышеупомянутые сравнительные операции приводят к выводу о том, что метод стаи серых волков является наиболее эффективным алгоритмом, чем метод дифференциальной эволюции и метод наискорейшего спуска, особенно в задачах оптимизации с большим числом локальных минимумов. Кроме того, он способен успешно справиться с такой непростой математической задачей как решение плохо обусловленной системы уравнений.
Подобные работы
- Рейтинговый подход к оценке конкурентоспособности организации
Магистерская диссертация, экономика. Язык работы: Русский. Цена: 4900 р. Год сдачи: 2018 - ВЛИЯНИЕ ЛИЧНОСТНЫХ ОСОБЕННОСТЕЙ НА ФУНКЦИОНИРОВАНИЕ АВТОБИОГРАФИЧЕСКОЙ ПАМЯТИ ЛЮДЕЙ ЗРЕЛОГО ВОЗРАСТА
Магистерская диссертация, психология. Язык работы: Русский. Цена: 4960 р. Год сдачи: 2017 - Разработка бизнес-плана развития компании путем создания Telegram-ботов (Национальный Институт Бизнеса)
Дипломные работы, ВКР, бизнес планирование. Язык работы: Русский. Цена: 2000 р. Год сдачи: 2024