Эволюционные вычисления: Информация
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 18 студентам
Уровень:
Для всех
Длительность:
22:10:00
Студентов:
869
Выпускников:
193
Рассмотрены основы нового направления в теории искусственного интеллекта, включающего эволюционные вычисления и роевые алгоритмы.
В курсе изложены основные теоретические и методологические материалы по эволюционным вычислениям, которые являются самостоятельным направлением в теории интеллектуальных систем. Последовательно вводятся базисные понятия классических генетических алгоритмов (ГА), теория схем и решения задач численной и комбинаторной оптимизации с помощью генетических алгоритмов. Рассмотрены многочисленные обобщения и модификации ГА. К ним относятся параллельные ГА, реализованные по модели «рабочий-хозяин» и «модель островов». Представлены различные варианты многокритериальных ГА на основе концепции Парето. Описаны вероятностные ГА, где популяция представляется вектором вероятностей. Изложены основы генетического программирования на основе различных форм кодирования потенциальных решений: древовидных, линейных и графоподобных структур. Представлены основы машинного обучения на базе Мичиганского и Питсбургского подходов. Описаны эволюционные стратегии, где основным генетическим оператором является мутация, и эволюционное программирование, которое в качестве потенциального решения использует модель конечного автомата.. Изложены также роевые и муравьиные алгоритмы.
Специальности: Программист, Архитектор программного обеспечения
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 59 минут
Введение.Основы генетических алгоритмов
В этой лекции описывается концепция простого генетического алгоритма (ГА), ориентированного на решение различных оптимизационных задач. Вводятся и содержательно описываются понятия, используемые в теории и приложениях ГА. Приводится фундаментальная теорема ГА и излагается теория схем, составляющие теоретическую базу ГА. Обсуждаются концептуальные вопросы, касающиеся преимуществ и недостатков ГА.
Оглавление
-
Лекция 2
2 часа 5 минут
Генетические алгоритмы для задач комбинаторной оптимизации
До сих пор рассматривалось применение ГА, в основном, при решении задачи численной оптимизации при поиске экстремумов функции. Но в настоящее время ГА используются больше для решения задач комбинаторной оптимизации, которым посвящена подавляющая часть публикаций. Базовой задачей комбинаторной оптимизации является задача коммивояжера, для которой отрабатываются новые методы решения задач данного типа. Поэтому большая часть лекции посвящена решению задачи коммивояжера с помощью ГА на основе различных способов кодирования потенциальных решений и проблемно-ориентированных генетических операторов кроссинговера. Однако сначала рассматриваются задачи об укладке рюкзака и покрытии множества, которые допускают использование простого (классического) ГА.
Оглавление
-
Лекция 3
2 часа 6 минут
Модификации генетических алгоритмов
В предыдущих лекциях, в основном, рассмотрена классическая реализация простого ГА. В настоящей лекции описаны модификации ГА. Прежде всего это различные модификации и обобщения для каждого функционального блока основной схемы ГА без изменения последовательности этих блоков. Описаны различные методы генерации начальной популяции, отбора родителей, разные формы представления потенциальных решений и генетические операторы кроссинговера и мутации, определенные для соответствующего кодирования. Кроме этого, изложены нестационарные ГА с изменяемой мощностью популяции, ниши и адаптивные ГА, где параметры подстраиваются в процессе поиска решения.
Оглавление
-
Лекция 4
57 минут
Параллельные генетические алгоритмы
Присущие ГА"внутренний" параллелизм и заложенная в них возможность распределенных вычислений способствовали развитию параллельных ГА (ПГА). В данной лекции изложены основы параллельных ГА, где используются следующие основные модели: 1)"рабочий-хозяин", "модель островов", клеточные ГА, коэволюционные ГА. Далее описаны эти виды ГА, их структура и основные параметры.
Оглавление
-
Лекция 5
48 минут
Генетические алгоритмы многокритериальной оптимизации
В большинстве реальных практических задач, как правило, необходимо выполнить оптимизацию по нескольким критериям. Многокритериальная оптимизация основана на поиске решения, которое одновременно оптимизирует не одну, а несколько функций. В этой лекции изложены основы многокритериальных ГА на основе концепции Парето. Описана общая структура многокритериального ГА и различные обобщения ГА для многокритериальной оптимизациии, включая: векторную оценку, ранжирование по Парето, метод взвешенной функции со случайными и адаптивными весами. Рассмотрены методы оценки качества решений в случае многокритериальной оптимизации.
Оглавление
-
Лекция 6
1 час 52 минуты
Генетическое программирование
Эта лекция посвящена генетическому программированию (ГП), средства которого ориентированы на автоматическое создание либо изменение программ. С применением используемой в ГП методологии происходит "выращивание" программ для решения поставленной вычислительной задачи. Такое "выращивание" осуществляется также, как и в ГА, путем формирования поколения за поколением новых программ, которые все "лучше" и "лучше" решают поставленную задачу. Методы ГА и ГП имеют много общего, но вместе с тем имеют и существенные отличия. Одно из важных отличий заключается в том, что в ГА оперируют с равными по размеру и одинаковыми по структуре особями, тогда как в ГП особи могут иметь совершенно отличные друг от друга структуры. Следствием этого является, например, возникновение проблем с оператором кроссинговера, поскольку его механизм сильно зависит от выбранного представления программы.
Оглавление
-
Лекция 7
1 час 40 минут
Машинное обучение
Эта лекция посвящена методам построения моделей, способных обучаться, а также разработке алгоритмов для их построения и обучения. Различают два типа обучения: 1) обучение по прецедентам (индуктивное обучение); 2) дедуктивное обучение, предполагающее формализацию знаний экспертов и создание на этой основе баз знаний. Второй тип обучения относится к экспертным системам, поэтому машинное обучение принято считать синонимом индуктивного. Именно о нем и пойдет речь в этой лекции.
Оглавление
-
Лекция 8
23 минуты
Вероятностные и компактные генетические алгоритмы
В настоящее время кроме детерминированных ГА разработаны и достаточно широко применяются вероятностные ГА (ВГА), в которых популяция представляется вектором вероятности. В данной лекции представлены основные ВГА, к которым относятся: базовый ВГА, пошаговое обучение на основе виртуальной популяции, компактный генетический алгоритм, генетический алгоритм SELFISH. Все они, в отличие от классического ГА, где популяция состоит из множества двоичных стрингов, основаны на вероятностном представлении популяции вектором вероятностей. Для разных ВГА применяются различные генетические операторы, которые здесь детально описаны.
Оглавление
-
Лекция 9
1 час 12 минут
Эволюционные стратегии
Эта лекция посвящена основам эволюционных стратегий (ЭС), которые являются самостоятельным разделом эволюционных вычислений и изначально ориентированы на оптимизацию в многомерном пространстве. Вводится представление потенциального решения с помощью векторов вещественных чисел и соответствующие генетические операторы мутации и рекомбинации. Представлены двукратная и многократные ЭС. Изложен основной алгоритм и параметры ЭС. Рассмотрены вопросы самоадаптации ЭС на основе коррекции значений параметров в процессе эволюции.
Оглавление
-
Лекция 10
1 час 24 минуты
Эволюционное программирование
Эволюционное программирование (ЭП), как и ЭС, использует эволюцию на уровне фенотипа. В данной лекции изложены основы ЭП, где потенциальное решение представляется в виде конечного автомата и применяется, в основном, оператор мутации. Описаны различные генетические операторы мутации и основной эволюционный алгоритм ЭП. Рассмотрены вопросы применения ЭП к задачам прогнозирования и управления. Представлено также современное направление ЭП, где потенциальное решение может кодироваться вещественными векторами.
Оглавление
-
Лекция 11
1 час 11 минут
Роевые и муравьиные алгоритмы
В последнее десятилетие при решении задач оптимизации все шире используются новые методы, которые фактически примыкают к эволюционным вычислениям по своей идеологии и основаны на моделировании социального поведения живых организмов. К ним относятся, прежде всего, роевые алгоритмы (PSO–particle swarm optimization), которые, в основном, используются в численной оптимизации, и муравьиные алгоритмы (ACO – ant colony optimization), применяемые, как правило, при решении задач комбинаторной оптимизации (прежде всего на графах). Далее кратко рассмотрим основные концепции и функциональные операции для этих двух новых направлений.
Оглавление
-
Лекция 12
1 час 45 минут
Муравьиные алгоритмы
Данная лекция посвящена методам оптимизации, основанным на поведении муравьиных колоний (Ant Colony Optimization - ACO), которые в последнее время получили широкое распространение. Рассматривается биологический прототип и непрямая форма общения особей колонии – стигметрия, которая основана на том, что муравьи по пути движения откладывают специальный фермент – феромон. Моделирование этого способа обмена информацией лежит в основе данного подхода. Вводится базовый муравьиный алгоритм с основными формулами определения откладываемой концентрации феромона и вероятности выбора пути в зависимости от этой концентрации. Муравьиный алгоритм иллюстрируется на примере задач выбора оптимальных путей на графах (например, задачи коммивояжера). Описаны многочисленные модификации и обобщения базового муравьиного алгоритма. Рассмотрены его параметры и их влияние на эффективность метода. Обсуждается применение этого метода в изменяющейся среде. Выполнено сравнение муравьиных и генетических алгоритмов.
Оглавление
-