Решение задач оптимизации роевыми и эволюционными алгоритмами
|
Введение 3
Глава 1. Обзор роевых и эволюционных алгоритмов, описание их модификаций и способов адаптации к задачам оптимизации 5
1.1. Особенности класса стохастических алгоритмов поиска 5
1.2. Эволюционные алгоритмы: идея, формализация, основные генетические операторы 8
1.3. Алгоритм роя частиц: история. идея и математическая формализация 11
1.4. Способы адаптации алгоритма роя частиц к задачам оптимизации 17
Глава 2. Применение роевого и эволюционного алгоритма для решения двухуровневой задачи оптимизации 27
2.1. Математическая постановка задачи двухуровневой оптимизации 27
2.2. Описание алгоритмов BLEAQ и BPSOQ для решения задачи двухуровневой оптимизации 33
2.3. Реализация алгоритмов BLEAQ и BPSOQ и их сравнительный анализ 38
Глава 3. Решение двухуровневой задачи оптимизации топологии транспортной сети алгоритмом PSODP - leBlanc с динамическим коэффициентом инерции 50
3.1. Математическая постановка двухуровневой задачи оптимизации топологии транспортной сети 50
3.2. Исследование способов адаптации алгоритма роя частиц для эффективного решения задач оптимизации 56
3.3. Описание алгоритма PSODP - LeBlanc с динамическим коэффициентом инерции 63
3.4. Реализация алгоритма PSO PSODP - leBlanc с динамическим коэффициентом инерции и его применении на сети Sioux-Falls 65
Заключение 69
Список использованных источников 71
Приложение А. Общая схема работы алгоритма PSODP-LeBlanc с динамическим коэффициентом инерции 74
Приложение Б. Исходные данные для обратной задачи алгоритма 75
Приложение В. Полученное равновесное распределение максимальной пропускной способности дуг 80
Приложение Г. Равновесное распределение загрузки узлов сети 81
Приложение Д. Информация об изменении лучшего решения, найденного каждой частицей 82
Глава 1. Обзор роевых и эволюционных алгоритмов, описание их модификаций и способов адаптации к задачам оптимизации 5
1.1. Особенности класса стохастических алгоритмов поиска 5
1.2. Эволюционные алгоритмы: идея, формализация, основные генетические операторы 8
1.3. Алгоритм роя частиц: история. идея и математическая формализация 11
1.4. Способы адаптации алгоритма роя частиц к задачам оптимизации 17
Глава 2. Применение роевого и эволюционного алгоритма для решения двухуровневой задачи оптимизации 27
2.1. Математическая постановка задачи двухуровневой оптимизации 27
2.2. Описание алгоритмов BLEAQ и BPSOQ для решения задачи двухуровневой оптимизации 33
2.3. Реализация алгоритмов BLEAQ и BPSOQ и их сравнительный анализ 38
Глава 3. Решение двухуровневой задачи оптимизации топологии транспортной сети алгоритмом PSODP - leBlanc с динамическим коэффициентом инерции 50
3.1. Математическая постановка двухуровневой задачи оптимизации топологии транспортной сети 50
3.2. Исследование способов адаптации алгоритма роя частиц для эффективного решения задач оптимизации 56
3.3. Описание алгоритма PSODP - LeBlanc с динамическим коэффициентом инерции 63
3.4. Реализация алгоритма PSO PSODP - leBlanc с динамическим коэффициентом инерции и его применении на сети Sioux-Falls 65
Заключение 69
Список использованных источников 71
Приложение А. Общая схема работы алгоритма PSODP-LeBlanc с динамическим коэффициентом инерции 74
Приложение Б. Исходные данные для обратной задачи алгоритма 75
Приложение В. Полученное равновесное распределение максимальной пропускной способности дуг 80
Приложение Г. Равновесное распределение загрузки узлов сети 81
Приложение Д. Информация об изменении лучшего решения, найденного каждой частицей 82
В современной науке наблюдается увеличение количества исследований, посвященных методам роевой оптимизации, одним из которых является алгоритм роя частиц (PSO). Это объясняется развитием окружающих человека систем, где для принятия оптимальных управленческих решений использование классических методов становится невозможным. У целевой функции могут отсутствовать свойства выпуклости, дифференцируемости, унимодальности. Также многие задачи являются NP-трудными и нахождение точного решения на больших размерностях становится невозможным.
Актуальность работы обусловлена усложнением задач оптимизации и как следствие невозможностью их решения точными методами.
Целью работы является сравнительный анализ эффективности роевых и эволюционных алгоритмов в решении прикладных задач двухуровневой оптимизации.
Для осуществления поставленной цели необходимо реализовать следующие задачи:
1. Провести обзор существующих методов оптимизации с применением роевого интеллекта и эволюционных подходов.
2. Осуществить апробацию инструментов роевого интеллекта для решения двухуровневых задач оптимизации на тестовых примерах.
3. Сравнить полученные результаты с эволюционными процедурами решения двухуровневых задач оптимизации на тестовых примерах.
4. Адаптировать наиболее эффективный алгоритм к решению задач двухуровневой оптимизации на транспортных сетях.
5. Реализовать эффективные процедуры решения задачи оптимизации топологии транспортной сети с применением построенных эвристик.
Теоретическая значимость работы заключается в консолидации и систематизации сведений об алгоритме роя частиц, которые в малом объеме представлены в русскоязычной научной литературе. Исследовании новых подходов его адаптации, которые с одной стороны повышают вероятность и скорость его сходимости, а с другой расширяют круг к различным оптимизационным задачам.
Практическая значимость работы заключается в применении данного алгоритма для получения приближенного решения двухуровневой оптимизационной задачи равновесного распределения транспортных потоков.
Методами исследования настоящей работы являются описание, формализация, классификация, практическое моделирование, эксперимент, сравнение, измерение, итерационные методы, численные методы, обобщение и анализ результатов.
Актуальность работы обусловлена усложнением задач оптимизации и как следствие невозможностью их решения точными методами.
Целью работы является сравнительный анализ эффективности роевых и эволюционных алгоритмов в решении прикладных задач двухуровневой оптимизации.
Для осуществления поставленной цели необходимо реализовать следующие задачи:
1. Провести обзор существующих методов оптимизации с применением роевого интеллекта и эволюционных подходов.
2. Осуществить апробацию инструментов роевого интеллекта для решения двухуровневых задач оптимизации на тестовых примерах.
3. Сравнить полученные результаты с эволюционными процедурами решения двухуровневых задач оптимизации на тестовых примерах.
4. Адаптировать наиболее эффективный алгоритм к решению задач двухуровневой оптимизации на транспортных сетях.
5. Реализовать эффективные процедуры решения задачи оптимизации топологии транспортной сети с применением построенных эвристик.
Теоретическая значимость работы заключается в консолидации и систематизации сведений об алгоритме роя частиц, которые в малом объеме представлены в русскоязычной научной литературе. Исследовании новых подходов его адаптации, которые с одной стороны повышают вероятность и скорость его сходимости, а с другой расширяют круг к различным оптимизационным задачам.
Практическая значимость работы заключается в применении данного алгоритма для получения приближенного решения двухуровневой оптимизационной задачи равновесного распределения транспортных потоков.
Методами исследования настоящей работы являются описание, формализация, классификация, практическое моделирование, эксперимент, сравнение, измерение, итерационные методы, численные методы, обобщение и анализ результатов.
Таким образом, цель работы можно считать достигнутой, а задачи выполненными. В ходе выполнения работы была изучена общая постановка задач двухуровневой оптимизации, а также двухуровневая задача оптимизации топологии сети. Были реализованы алгоритмы BLEAQ и BPSOQ, проведен их сравнительный анализ. Также был реализован алгоритм PSODP-LeBlanc с динамическим коэффициентом инерции, были подобраны адаптации, эффективно решающие исследуемую задачу. Код всех реализованных алгоритмов доступен по ссылке [28].
В первой главе был проведен обзор особенностей эволюционного отбора и роевого интеллекта из которого видно, что концепции этих подходов отличаются как на уровне природных механизмов, так и математически.
Алгоритмы роевого интеллекта принципиально отличаются от эволюционных, так как не требуют создания новой популяции на каждой итерации через эволюционные механизмы. Они используют коллективные децентрализованные перемещения членов популяции. Был предложен способ отнесения алгоритмов к роевым: в формулах, которые описывают миграцию агентов роя, необходимо наличие объекта, который дает возможность косвенного обмена информацией между ними.
Область применения алгоритмов роевого интеллекта помимо задач оптимизации дополняется управлением группами роботов. Данное направление носит название роевой робототехники и активно развивается в последние годы. Управление роботами на основе эволюционных процессов невозможно, так как для этого необходимо было бы организовать создание новых роботов на основе старых непосредственно во время управления.
Во второй главе были описаны результаты реализации алгоритмов, основанных на роевых и эволюционных подходам и проанализирована эффективность их работы на примере решения задачи двухуровневой оптимизации. В результате проведения сравнительного анализа алгоритмов BLEAQ и BPSOQ для решения двухуровневых задач оптимизации на тестовых примерах более эффективно показали себя роевые эвристики.
В первую очередь это объясняется что в эволюционном алгоритме потомками, участвующими в соревновании на место в популяции являются две ее случайные особи. В какой-то момент потомки оказываются хуже своих родителей в результате чего обновление популяции прекращается. Кроме того, алгоритм роя частиц реализован на идее коллективного поведения и общение всех участников популяции между собой позволяет более тщательно исследовать пространство поиска, захватывая большие расстояния в начале работы алгоритма и более глубоко исследуя локальные минимумы в конце. Для двухуровневой задачи оптимизации топологии транспортной сети было решено использовать именно роевой интеллект, подобрав перед этим наиболее эффективную адаптацию.
В третьей главе была дана математическая математическая постановка двухуровневой задачи оптимизации топологии сети с задачей равновесного распределения транспортных потоков на нижнем уровне. Были подобраны нужные адаптации для проведения эффективной оптимизации.
В результате проведения исследования адаптаций алгоритма было решено:
• использовать динамический линейный коэффициент инерции вида (1.4);
• численность роя принять равной 20;
• использовать полносвязную структуру топологию соседства частиц на этапе исследования пространства решения и кольцевую на этапе эксплуатации.
Был реализован алгоритм PSODP - LeBlanc для задачи оптимизации топологии сети. Количества особей в рое было достаточно для эффективного исследования пространства поиска. Динамика изменения и непосредственно лучшее решение, найденное каждой отдельной частицей, вынесены в приложение Д. Минусом алгоритма является большая скорость вычисления равновесного распределения транспортных потоков на нижнем уровне. Однако это дает возможность получить более точное решение оптимизируемой функции, что оправдывает затраченные вычислительные мощности.
В первой главе был проведен обзор особенностей эволюционного отбора и роевого интеллекта из которого видно, что концепции этих подходов отличаются как на уровне природных механизмов, так и математически.
Алгоритмы роевого интеллекта принципиально отличаются от эволюционных, так как не требуют создания новой популяции на каждой итерации через эволюционные механизмы. Они используют коллективные децентрализованные перемещения членов популяции. Был предложен способ отнесения алгоритмов к роевым: в формулах, которые описывают миграцию агентов роя, необходимо наличие объекта, который дает возможность косвенного обмена информацией между ними.
Область применения алгоритмов роевого интеллекта помимо задач оптимизации дополняется управлением группами роботов. Данное направление носит название роевой робототехники и активно развивается в последние годы. Управление роботами на основе эволюционных процессов невозможно, так как для этого необходимо было бы организовать создание новых роботов на основе старых непосредственно во время управления.
Во второй главе были описаны результаты реализации алгоритмов, основанных на роевых и эволюционных подходам и проанализирована эффективность их работы на примере решения задачи двухуровневой оптимизации. В результате проведения сравнительного анализа алгоритмов BLEAQ и BPSOQ для решения двухуровневых задач оптимизации на тестовых примерах более эффективно показали себя роевые эвристики.
В первую очередь это объясняется что в эволюционном алгоритме потомками, участвующими в соревновании на место в популяции являются две ее случайные особи. В какой-то момент потомки оказываются хуже своих родителей в результате чего обновление популяции прекращается. Кроме того, алгоритм роя частиц реализован на идее коллективного поведения и общение всех участников популяции между собой позволяет более тщательно исследовать пространство поиска, захватывая большие расстояния в начале работы алгоритма и более глубоко исследуя локальные минимумы в конце. Для двухуровневой задачи оптимизации топологии транспортной сети было решено использовать именно роевой интеллект, подобрав перед этим наиболее эффективную адаптацию.
В третьей главе была дана математическая математическая постановка двухуровневой задачи оптимизации топологии сети с задачей равновесного распределения транспортных потоков на нижнем уровне. Были подобраны нужные адаптации для проведения эффективной оптимизации.
В результате проведения исследования адаптаций алгоритма было решено:
• использовать динамический линейный коэффициент инерции вида (1.4);
• численность роя принять равной 20;
• использовать полносвязную структуру топологию соседства частиц на этапе исследования пространства решения и кольцевую на этапе эксплуатации.
Был реализован алгоритм PSODP - LeBlanc для задачи оптимизации топологии сети. Количества особей в рое было достаточно для эффективного исследования пространства поиска. Динамика изменения и непосредственно лучшее решение, найденное каждой отдельной частицей, вынесены в приложение Д. Минусом алгоритма является большая скорость вычисления равновесного распределения транспортных потоков на нижнем уровне. Однако это дает возможность получить более точное решение оптимизируемой функции, что оправдывает затраченные вычислительные мощности.
Подобные работы
- Решение задач оптимизации роевыми и эволюционными алгоритмами
Магистерская диссертация, математика и информатика. Язык работы: Русский. Цена: 4600 р. Год сдачи: 2022 - ИНТЕЛЛЕКТУАЛЬНЫЙ АЛГОРИТМ УПРАВЛЕНИЯ ГРУППОЙ БЕСПИЛОТНЫХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ
Бакалаврская работа, информатика. Язык работы: Русский. Цена: 4315 р. Год сдачи: 2020 - РАЗРАБОТКА КОМПОНЕНТА РЕАЛИЗАЦИИ МЕТОДА ОТЖИГА ДЛЯ ПЛАТФОРМЫ .NET
Магистерская диссертация, математика. Язык работы: Русский. Цена: 4900 р. Год сдачи: 2017 - Методы случайного поиска и машинного
обучения для получения оптимальной по
стоимости траектории дороги на рельефе
местности
Дипломные работы, ВКР, математика. Язык работы: Русский. Цена: 4750 р. Год сдачи: 2024 - Методы случайного поиска и машинного
обучения для получения оптимальной по
стоимости траектории дороги на рельефе
местности
Дипломные работы, ВКР, математика. Язык работы: Русский. Цена: 4800 р. Год сдачи: 2024