- •Методологические основы моделирования (Миша)
- •Общая классификация основных видов моделирования (Миша)
- •Процедурно-технологическая схема построения и исследования моделей сложных систем (Аня)
- •Отличительные особенности моделей различных классов (Аня)
- •Области применения имитационного моделирования (Люба)
- •Сущность метода имитационного моделирования (Люба)
- •Статическое и динамическое представление моделируемой системы (Виля)
- •Управление модельным временем (Виля)
- •Проблемы стратегического и тактического планирования имитац.Эксп. (Гриша)
- •Общая технологическая схема имитационного моделирования (Гриша)
- •Базовые концепции структуризации и формализации имитационных систем (Леша)
- •Методологические подходы к построению дискретных имитационных моделей (Леша)
- •Язык моделирования gpss (Макс)
- •Сети Петри и их расширения (Макс)
- •Основы технологии имитационного моделирования (Киря)
- •Описание поведения системы (надо убрать воду и проверить формулы) (Киря)
- •Моделирование асинхронных процессов (Даша)
- •Обзор алгоритмов оптимизации (Даша)
- •Глобальная оптимизация (Дима)
- •Классификация алгоритмов оптимизации (Дима)
- •Скорость и точность оптимизации (Антон)
- •Метод Дельфи (Антон)
- •Метод Анализа Иерархий (маи) (Серега)
- •Анкетирование (Серега)
- •Экспертные оценки (Катя)
- •Обработка экспертных оценок (Катя)
- •Метод непосредственного оценивания (Вова)
- •Метод ранжирования (Саша)
- •Основные понятия га (Егор)
- •Стратегии отбора для га (Егор)
- •Модели га (Паша)
- •Применение алгоритмов, инспирированных природными явлениями, для решения задач оптимизации (Паша)
- •Алгоритм имитации отжига (Настя)
- •Алгоритм роя частиц (Настя)
- •Алгоритм муравьиной колонии (Миша)
- •Пчелиные алгоритмы (Люба)
- •Моделирование перемещения бактерий (Виля)
- •Алгоритм культурного обмена (Леша)
- •Алгоритм подъема (Киря)
- •Алгоритм поиска с запретами (Дима)
- •Меметический алгоритм (Антон)
- •Алгоритм поиска гармонии (Серега)
- •Отбор объектов в пространстве признаков. Метод Парето (Катя)
- •Применение интерактивного подхода к решению опт. Задач (Саша)
- •Типовые задачи многокритериальной оптимизации (Паша)
Алгоритм культурного обмена (Леша)
Является одним из направлений искусственного интеллекта, который основан на моделировании и использовании эволюционных процессов общественных структур. Оп представляет собой совокупность двух пространств, взаимодействие между которыми определяется соответствующим протоколом или набором правил. ( см ниже)
Компонента
«общество « состоит из индивидуумов,
каждый из которых обладает собственным
видением решения проблемы в исследуемой
сфере. Лучшие из таких суждений за период
существования поколения формируют
«общественное мнение». Протокол (
передача-влияние) , в свою очередь,
определяет меняющуюся с течением времени
зависимость одного компонента от
другого: обновление мнений, при появлении
нового поколения, и влияние полученных
решений на генерацию новых. Описание
алгоритма см ниже:
Рассмотрим применение данного алгоритма для решения задачи топологической оптимизации компьютерной сети. Согласно концепции алгоритма ключевым элементом моделируемой системы являются представители популяции. Множество представителей формируют «общество». У каждого из них есть собственное представление об исследуемой области (суждение). Для задачи топологической оптимизации оно может быть представлено следующим выражением {2,0,3,1} ( Т.Е. насколько я понял, в данном случае узел представляется индивидуумом, а совокупность узлов – обществом). Данная запись задает предполагаемую последовательность соединения объектов сети в оптимальную топологию. После выбора первого объекта в сети, обновляется общественное мнение, путем исключения выбранного узла и обновляется общество, путем исключения уже выбранных узлов.
Алгоритм подъема (Киря)
Алгоритм подъёма является одним из старейших алгоритмов оптимизации, относящихся к классу метаэвристических алгоритмов Монте-Карло. Алгоритм относительно прост в реализации, однако во многих случаях он показывает результаты, сопоставимые с результатами работы более сложных алгоритмов имитации отжига и поиска с запретами, выигрывая у них в вычислительной сложности и, следовательно, скорости.
На каждой итерации алгоритм создает единственное новое решение, базирующееся на лучшем из найденных ранее решений. Если новое решение лучше исходного (т. е. значение целевого критерия с использованием нового решения меньше предыдущего), то потомок заменяет родителя и алгоритм переходит к следующей итерации. В противном случае на следующей итерации используется старое решение. Таким образом, алгоритм является жадным - он всегда двигается к лучшему из найденных на данный момент решений.
В определённом смысле алгоритм подъёма можно назвать упрощённой разновидностью генетических алгоритмов со значением размера популяции, равным единице. Опишем работу алгоритма подъёма с помощью псевдокода:
solution <- initSolution while not terminationCriteria do
offspring <- mutate(solution) if cost(offspring) < cost(solution) then solution <- offspring return solution
В качестве критерия останова terminationCriteria могут применяться такие характеристики, как достижение определённого числа шагов алгоритма, ограничение по времени работы алгоритма, отсутствие значительного улучшения значения целевой функции. Могут также использоваться такие характеристики, как улучшение самого решения на шаге или на протяжении определённого числа шагов.
Один из главных недостатков алгоритма подъёма заключается в его преждевременной сходимости. Поскольку он всегда использует для получения нового решения лучшее из найденных ранее, он легко может застрять в локальном оптимуме. Из-за этого алгоритм подъёма в исходном виде представляет собой скорее алгоритм локального поиска, чем глобальной оптимизации. Существует несколько способов, позволяющих избежать данной проблемы. Они будут рассмотрены далее.
Вследствие своей вычислительной простоты алгоритм подъёма применяется особенно часто тогда, когда требуется оптимизация «на лету». Алгоритм широко применяется в задачах, связанных с сетевыми технологиями и связью, робототехникой, интеллектуальным анализом данных и поведением интеллектуальных агентов [3].
Алгоритм стохастического подъёма. Избежать проблемы преждевременной сходимости алгоритма подъёма можно, перезапуская его случайным образом при достижении определённого условия. Перезапуски помогают тщательнее исследовать пространство поиска и увеличивают вероятность нахождения глобального оптимума. Такой подход получил название алгоритма стохастического подъёма. Данный алгоритм требует хранения двух решений: лучшего из решений, полученных при текущем запуске алгоритма, и лучшего решения всех запусков. Кроме того, следует определить критерий перезапуска. Обычно перезапуск выполняют в случае, если на протяжении большого числа итераций результат существенно не улучшился.
Использование такого критерия останова локального поиска гарантирует тщательное исследование области вокруг точки перезапуска. С другой стороны, оно приводит к неопределённой длительности работы алгоритма. Если требуется гарантировать завершение работы алгоритма в заранее известное время, следует производить перезапуск после определённого числа итераций локального поиска. Можно добиться ещё лучших результатов, если при каждом перезапуске программы выбирать исходные точки не случайным образом, а по более сложному алгоритму.
Алгоритм динамического подъёма. В 1993 г. Michael de la Maza и Deniz Yuret предложили свою модификацию алгоритма подъёма, заимствующую идеи из генетических алгоритмов и методов сопряженных градиентов. Алгоритм динамического подъёма использует последние 2 посещённых решения для генерации единичных векторов в пространстве поиска. Направление поиска нового решения, таким образом, подстраивается под структуру пространства поиска. Для работы алгоритма требуется хранение набора ортогональных векторов-решений, образующих базис, а также набора противоположных по знаку первым векторов. Алгоритм включает в себя 2 цикла: внешний и внутренний. Как и в алгоритме стохастического подъёма, внутренний цикл выполняет задачу локального поиска, а внешний отвечает за исследование всей области поиска,
solution <- initSolution best <- solution
while not terminationCriterion do basis <- initBasis do
vector <- basis[vector w/ largest magnitude] if cost (solution + vector) < cost(solution)
then
solution <- solution + vector if vector = oldVector
then vector <- vector * 2 oldVector <- vector
else
vector <- vector / 2 while not basis = minBasis
if cost(solution) < cost(best) then best <- solution solution <- randomSolution
На каждой итерации из набора выбирается вектор с наибольшей длиной и вычисляется сумма исходного вектора-решения и выбранного вектора. Если значение целевой функции в этой точке больше, чем в исходной, происходит перемещение к новому решению и цикл повторяется. В противном случае длина выбранного вектора уменьшается вдвое. Кроме того, если алгоритм 2 раза подряд выбирает один и тот же вектор для перехода, длина этого вектора удваивается. Длины векторов, однако, ограничены как снизу, так и сверху — либо структурой пространства решений, либо явно заданными значениями.
Описанный алгоритм является внутренним циклом. Он напоминает метод циклического покоординатного спуска, однако может применяться и для задач с дискретным пространством поиска. Цикл повторяется до тех пор, пока алгоритм не приходит к точке локального оптимума. Такое решение алгоритм не может улучшить. Это происходит тогда, когда длины всех векторов набора являются минимально возможными. Этот признак можно использовать в качестве критерия останова внутреннего цикла.
Задача внешнего цикла - перезапускать описанную процедуру локального поиска с целью максимально тщательного исследования пространства решений. Наиболее эффективным способом выбора точки перезапуска является её расположение максимально удалённо от всех ранее пройденных алгоритмом точек. Поскольку базис ортогонален, каждая из пройденных точек вместе с базисными векторами делит пространство поиска на области — и-мерные прямоугольные параллелепипеды. Для перезапуска следует выбирать область наибольшего объёма.
Такой подход гарантирует максимально подробное исследование пространства поиска, однако становится слишком сложным для пространств с большим числом измерений: число параллелепипедов растет экспоненциально при увеличении размерности пространства. В таких случаях наиболее простым решением будет случайный выбор точки перезапуска.
В качестве критерия останова алгоритм использует ограничение на число итераций без улучшения решения (рис. 3.1). Он изменяет один из компонентов решения и следит за соблюдением ограничений. Если ни одно из них не было нарушено, алгоритм переходит к следующей итерации, вновь изменяя решение. Если же новое решение не соответствует ограничениям, алгоритм пытается изменить другой компонент решения, наиболее близкий к уже изменённому, чтобы вернуть решение в рамки ограничений. Если более далёкие компоненты выходят за рамки ограничений, то процедура повторяется. В итоге каждая подобная итерация приводит к тому, что в обе стороны от измененного изначального состояния компоненты возвращаются в рамки ограничений.
