Главная » Просмотр файлов » Курс Алгоритмы оптимизации, основанные на методе проб и ошибок

Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 19

Файл №1121255 Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (Курс Алгоритмы оптимизации, основанные на методе проб и ошибок) 19 страницаКурс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255) страница 192019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

После того, как все муравьизавершили построение путей, обновляется количество феромона на ребрах:m ij t  1  1  p   ij t     ij , k t k 1 F Tk t , i, j   Tk t  ij , k t   0, i, j   Tk t Здесь Tk(t) – путь, построенный k-м муравьем, а F(T) – целевая функция,определяющая качество пути, m – количество муравьев, p[0,1] – коэффициент испаренияферомонов. Испарение феромонов вводится для избегания попадания алгоритма влокальный оптимум, когда первый найденный путь с относительно хорошим значениемцелевой функции становится единственно значимым.Основными задачами, которые необходимо решить для того, чтобы использоватьмуравьиный алгоритм для решения конкретной задачи условной оптимизации, являются:1.

Сведение задачи условной оптимизации к задаче нахождения на графемаршрута, обладающего определенными свойствами.2. Задание локальной эвристической функции на ребрах графа.3. Определениеалгоритмапостроениямаршрутамуравьем(например,определение правила формирования табу-списка вершин).955.3. Модификации муравьиных алгоритмовМодификации муравьиных алгоритмов были разработаны с целью устранитьследующие основные недостатки базового алгоритма:возможность потери наилучшего найденного решения;низкой скоростью сходимости к оптимуму из-за приблизительно равноговклада в обновление феромонов хороших решений из различных областейпространства решений;хранением в памяти алгоритма (количество феромона на ребрах) заведомоне перспективных решений.Решить эти проблемы путем выбора соответствующих значений коэффициентаиспарения феромонов (p) и параметров , , определяющих важность феромонного следаи локальной целевой функции удается не для всех задач.5.3.1.

Максиминный алгоритмМаксиминная схема алгоритма позволяет решить проблему быстрой сходимостимуравьиного алгоритма к локальному оптимуму. Для этого к базовой схеме добавляютсятри правила:1. На каждой итерации феромон добавляется только на лучшее из решений, срединайденных на данной итерации;2. Ограничивается минимальное и максимальное количество феромона на ребрах: ij  [ min ; max ] ;3. Изначально количество феромона на всех ребрах равно max.Изначально одинаковое количество феромона на всех ребрах уменьшает вероятностьвыбора одного и того же маршрута разными муравьями, а условие ij  [ min ; max ]непозволяет одному относительно хорошему решению доминировать над другими. Такимобразом, эти ограничения позволяют разнообразить находимые алгоритмом маршруты иизбежать попадания в локальный оптимум. Кроме того, для дополнительного расширенияобласти поиска в максиминном алгоритме применяется механизм «сглаживания следов»:количество откладываемого на ребрах феромона пропорционально величине  max   ij .965.3.2.

Модификация с поглощением феромонаМодификация с поглощением феромона – ещё один метод, применяющийся длярасширения области поиска решений. Проходя по ребру при построении пути, муравейпоглощает часть феромона на этом ребре: ij   ij  (1  d ) , где d – доля поглощаемого феромона.Таким образом, ребро, по которому уже прошел один из муравьев, сразу теряет своюпривлекательность для других муравьев, что заставляет их выбирать другие ребра.5.3.3.

Совместное использование с алгоритмами локального поискаСуть подхода заключается в том, что на каждой итерации муравьиного алгоритмаалгоритмы локального поиска пытаются улучшить найденные решения. Обычноприменяются локально-оптимальные алгоритмы.Для задачи коммивояжера, часто используются алгоритмы локального поиска,которые улучшают маршрут заменой заданного количества ребер.5.4. Муравьиные алгоритмы для решения задачи построения статикодинамических расписания (два способа представления задачи)Математическая постановка задачи приведена в разделе1.4.2.5.4.1. Первый способ сведения задачи построения статико-динамическогорасписания к задаче нахождения на графе маршрутаПостроим полносвязный граф G=<N,A>, где: N={ni|i[1..n]}{O} – множество вершин; A={(ni,nj)|i,j[1..n],ij}{(O,ni)|i[1..n]}> – множество ребер.Каждой вершине графа соответствует одна из размещаемых работ.

Кроме того,добавляется еще одна вершина О, соответствующая началу расписания.Муравьиный алгоритм строит маршруты, в которых все вершины включены ровноодин раз. Каждому такому маршруту соответствует последовательность работ, такая что,в нее включены все работы из исходно заданного набора и каждая работа включена вданную последовательность один раз.

Опишем алгоритм для построения расписания потакойпоследовательностиработ.ПустьданапоследовательностьработSL={aik|aikSW;i,k[1..n]}. Первый индекс означает номер работы, второй - номер местаработы в последовательности. Построим расписание SP по следующему алгоритму:4. Инициализация расписания: Time=0 – текущая длина расписания; k=1 – номерместа размещаемой работы в SL; SW0= – список работ в добавляемом окне;975. Установка начальных параметров окна: S=max(Time,sik), F=fik – границыдобавляемого окна; T=2 – минимальная необходимая длина окна с учетомдобавленных работ; R=rik – раздел для работ в окне;6. Обновление значений параметров окна с учетом новой добавляемой работы:S’=max(S,sik), F’=min(F,fik), T’=T+tik;7. Добавление работы в текущее окно: если rik=R , T’F’–S’ (условиякорректности не нарушаются), то:S=S’, F=F’, T=T’, SW0=SW0{aik}, k=k+1,если kn (список SL еще не пройден), переход к п.3;8.

Проверка возможности добавления работы в новое окно: если fik–F–<tik , тоk=k+1, если kn переход к п.3 – данная работа не может быть размещена ни втекущее окно, ни в новое окно (дальше в списке еще могут быть работы,которые можно разместить в текущее окно);9. Закрытие окна: F=S+T – устанавливаем время закрытия окна минимальновозможным;10. Добавление данного окна в расписание: SP=SP{<S,F,SW0>};11. Пересчет длины расписания: Time=F+, k=k+1;12. Если k  n (список еще не пройден), переход к п.2.Расписание, построенное при помощи данного алгоритма, будет удовлетворятьвсем условиям корректности:13. Условие корректности 1 выполняется, т.к. каждая вершина встречается впостроенном маршруте ровно один раз, и соответствующая ей работаразмещается лишь в одно окно;14. Условие 2 выполняется, т.к.

S’=max(S,sik)sik; F’=min(F,fik)fik (п.3);15. Выполнение условий 3 и 5 обеспечивается проверками в п.4 алгоритма – еслиограничения нарушаются, работа не размещается в данное окно;16. Условие 4 выполняется, т.к. Si+1Time (п.2), где Time=Fi+п.8Такимобразом,припомощиописанногоалгоритмапозаданнойпоследовательности работ однозначно строится корректное расписание. Фактически,данный алгоритм устанавливает соответствие между пространством расписаний ипространствомпоследовательностейработ,которое,всвоюочередь,являетсяпространством поиска для муравьиного алгоритма.Недостатком данного подхода является то, что множество корректных расписанийсодержит больше элементов, чем множество последовательностей работ, т.е.

существуютрасписания, для которых не существует соответствующих им цепочек работ. Причина98заключается в том, что последовательность работ не задает однозначно распределениеработ по окнам. Более того, можно привести пример задач, для которых оптимальноерасписание не будет принадлежать к пространству поиска муравьиного алгоритма.Пример исходных данных такой задачи: SW={a1=<0,11,4,1>,a2=<4,11,2,1>,a3=<4,11,2,1>},==1(рис.5.2.).Прямоугольникамипоказаныдирективныеинтервалы,заштрихованными областями – время выполнения работ. Раздел у всех работ одинаковый.Рисунок 5.2.

Исходные данные.На рис. 5.3. показаны все возможные расписания, которые могут быть построеныприведенным алгоритмом по различным маршрутам в графе. Все эти расписания неявляются оптимальными.Рисунок 5.3. Построенные расписания.При этом расписание, в котором все работы размещены, существует (рис.5.4.).Рисунок 5.4. Оптимальное расписание.Можновыдвинутьгипотезу,чтонесуществуетдетерминированногополиномиального алгоритма A построения расписания по маршруту в графе G такого, чтодля (SW,,):SL:A(SL)=SP0, где SP0 – оптимальное расписание. Т.е.

не существуетдетерминированного полиномиального алгоритма, который для любой частной задачи могбы построить оптимальное расписание по одному из возможных маршрутов. По крайне99мере, пока такой алгоритм найти не удалось, однако нет и доказательства, что такогоалгоритма не существует.В качестве локальной целевой функции на ребрах графа G используется следующая 1  1  , если   0функция:  ij   0 , если   0, где   f j t j si  ti  – разница во времени междуминимальным временем завершения i-й работы и максимальным временем начала j-йработы. Если θ < 0, то j-я работа не может идти в расписании после i-й.

В противномслучае, чем меньше значение θ, тем меньше максимальный возможный промежуток врасписании между работами, соответствующими вершинам i и j, и тем больше значениелокальной целевой функции.Целевая функция для оценки качества маршрута задается отношением количестваработ, размещенных в расписание без нарушения условий корректности, к количествуисходных заданных работ. Значение данной функции вычисляется алгоритмом, строящимрасписание по маршруту.5.4.2. Второй способ сведения задачи построения статико-динамическогорасписания к задаче нахождения на графе маршрутаЧтобы устранить недостаток первого подхода, предлагается использоватьизмененное представление задачи в виде поиска маршрута на графе, в котором каждойработе будет соответствовать не одна, а две вершины.

Появление в маршруте первой изэтих вершин будет означать размещение работы без закрытия текущего окна. Другаявершина будет соответствовать размещению работы с закрытием окна. Соответственно, вмаршруте может присутствовать только одна вершина из каждой такой пары.Построим граф G’=<N’,A’>, гдеN’={ni+,ni–|i[1..n]}{O} – множество вершин; вершина ni+ соответствуетразмещению работы без закрытия текущего окна, ni– – размещению работы с закрытиемокна.

Характеристики

Список файлов лекций

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6547
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее