Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ответы к вопросам к экзамену ММО.docx
Скачиваний:
12
Добавлен:
01.05.2025
Размер:
5 Мб
Скачать
☆
  1. Алгоритм культурного обмена (Леша)

Является одним из направлений искусственного интеллекта, который основан на моделировании и использовании эволюционных процессов общественных структур. Оп представляет собой совокупность двух пространств, взаимодействие между которыми определяется соответствующим протоколом или набором правил. ( см ниже)

Компонента «общество « состоит из индивидуумов, каждый из которых обладает собственным видением решения проблемы в исследуемой сфере. Лучшие из таких суждений за период существования поколения формируют «общественное мнение». Протокол ( передача-влияние) , в свою очередь, определяет меняющуюся с течением времени зависимость одного компонента от другого: обновление мнений, при появлении нового поколения, и влияние полученных решений на генерацию новых. Описание алгоритма см ниже:

Рассмотрим применение данного алгоритма для решения задачи топологической оптимизации компьютерной сети. Согласно концепции алгоритма ключевым элементом моделируемой системы являются представители популяции. Множество представителей формируют «общество». У каждого из них есть собственное представление об исследуемой области (суждение). Для задачи топологической оптимизации оно может быть представлено следующим выражением {2,0,3,1} ( Т.Е. насколько я понял, в данном случае узел представляется индивидуумом, а совокупность узлов – обществом). Данная запись задает предполагаемую последовательность соединения объектов сети в оптимальную топологию. После выбора первого объекта в сети, обновляется общественное мнение, путем исключения выбранного узла и обновляется общество, путем исключения уже выбранных узлов.

  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 раза подряд выбирает один и тот же вектор для перехода, длина этого вектора удваивается. Длины векторов, однако, ограничены как снизу, так и сверху — либо структурой пространства решений, либо явно заданными значениями.

Описанный алгоритм является внутренним циклом. Он напоминает метод циклического покоординатного спуска, однако может применяться и для задач с дискретным пространством поиска. Цикл повторяется до тех пор, пока алго­ритм не приходит к точке локального оптимума. Такое решение алгоритм не может улучшить. Это происходит тогда, когда длины всех векторов набора яв­ляются минимально возможными. Этот признак можно использовать в качестве критерия останова внутреннего цикла.

Задача внешнего цикла - перезапускать описанную процедуру локально­го поиска с целью максимально тщательного исследования пространства ре­шений. Наиболее эффективным способом выбора точки перезапуска является её расположение максимально удалённо от всех ранее пройденных алгорит­мом точек. Поскольку базис ортогонален, каждая из пройденных точек вместе с базисными векторами делит пространство поиска на области — и-мерные прямоугольные параллелепипеды. Для перезапуска следует выбирать область наибольшего объёма.

Такой подход гарантирует максимально подробное исследование про­странства поиска, однако становится слишком сложным для пространств с большим числом измерений: число параллелепипедов растет экспоненциаль­но при увеличении размерности пространства. В таких случаях наиболее простым решением будет случайный выбор точки перезапуска.

Метод дождевой капли. Ещё одной модификацией метода подъёма яв­ляется метод дождевой капли. Он был разработан Pete Bettinger и Jianping Zhu в 2006 г. для задачи планирования лесов . В оригинальном варианте ал­горитма пространство решений и пространство значений целевой функции совпадают. Алгоритм используется в условиях поиска при жестких ограни­чениях для допустимых решений. На рис. 3.1 представлена укрупненная блок-схема алгоритма дождевой капли.

В качестве критерия останова алгоритм использует ограничение на число итераций без улучшения решения (рис. 3.1). Он изменяет один из компонентов решения и следит за соблюдением ограничений. Если ни одно из них не было нарушено, алгоритм переходит к следующей итерации, вновь изменяя решение. Если же новое решение не соответствует ограничениям, алгоритм пытается из­менить другой компонент решения, наиболее близкий к уже изменённому, что­бы вернуть решение в рамки ограничений. Если более далёкие компоненты вы­ходят за рамки ограничений, то процедура повторяется. В итоге каждая подоб­ная итерация приводит к тому, что в обе стороны от измененного изначального состояния компоненты возвращаются в рамки ограничений.