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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

При этом в алгоритм добавлен параметр Nbest, определяющий количествоэкземпляров лучшей строки, гарантированно остающихся в популяции.Общая схема работы комбинированной операции селекции такова:'с1. На этапе вычисления функции выживаемости выбирается строка популяции X bestнаилучшимзначениемфункциивыживаемости'Fbest,значениефункциивыживаемости сравнивается со значением функции выживаемости лучшей строки'предыдущих итераций Fbest. Если Fbest Fbest или это первая итерация алгоритма, то''как лучшую строку X best  X best.запоминаем X best2.

В популяции вычисляется количество строк равных Xbest и запоминается какNbest_exist.3. По схеме пропорциональной селекции вычисляется количество потомков длякаждой строки. Если количество строк в новой популяции равно Npop, где Npop –размер популяции, то выбирается (Nbest - Nbest_exist) худших строк в популяции (таккак Nbest_exist имеющихся лучших строк всегда перейдут в новую популяцию по89определению схемы пропорциональной селекции) и заменяется на копии лучшейстроки Xbest и операция селекции завершается, в противном случае перейти к 4.4. По схеме рулетки распределить Npop - Nsel1 - (Nbest - Nbest_exists) потомков, где Nsel1 –количество строк, полученное по схеме пропорциональной селекции, затемдобавить в популяцию Nbest - Nbest_exists лучших строк Xbest, в случае если даннаявеличина отрицательна, то добавления не происходит.Операция мутации и скрещивания.Поскольку ограничения на изменения значений параметров предложенного вразделе 2.5.2.

способа представления расписаний задаются в видеa i  y i  bi , y i  Z ,то могут быть использованы любые известные операции мутации и скрещивания,используемые при целочисленном кодировании решений (см. Приложение 1).4.5.4. Функция выживаемости и критерий остановаФункция выживаемости может быть задана следующим образом:F(kt, ke)=C1kt+C2ke, С1+С2=1, Ci≤0 (i=1,2) T dir, при T dir  Tkt  T1,при T dir  Tke  1 M ( HP, HW 0KВ качестве критерия останова может быть использован любой из критериевприведенных в разделе 4.1.4.6. Алгоритмы дифференциальной эволюцииАлгоритмы дифференциальной эволюции являются модификацией эволюционныхалгоритмов, в которой предпринята попытка ослабить влияние способа кодированиярешения на принципиальную работоспособность алгоритма и повысить скоростьсходимости алгоритма к оптимуму.Как и генетические алгоритмы, алгоритмы дифференциальной эволюции [Storn R.,Price K.

Minimizing the real functions of the ICEC'96 contest by differential evolution // IEEE Conference onEvolutionary Computation, Nagoya, 1996, pp. 842-844.] используют набор решений (популяцию) и накаждом шаге преобразовывают ее последовательным применением операций селекции,мутации и скрещивания. Основной особенностью алгоритма является использование90"дифференциальной" операции мутации, которая целенаправленно изменяет решения втекущей популяции.Общую схему алгоритмов дифференциальной эволюции можно представитьследующим образом.1.

Сгенерировать случайным образом начальную популяцию P 0 , состоящую из N popдопустимых (удовлетворяющих всем ограничениям) решений.2. Вычислить целевую функцию для каждого элемента популяции P 0 .3. Положить популяцию P 0 текущей популяцией: P  P 0 .4. Изменить популяцию P посредством операции мутации: P m  mutate(P ) ;5.

Выполнить операцию скрещивания над элементами измененной популяции P m итекущей популяции P: P c  crossover ( P m , P ) .6. Вычислить целевую функцию и функции ограничений для каждого элемента популяцииPc .7. Выполнить операцию селекции: P new  select ( P c , P) .8. Положить популяцию P new текущей популяцией: P  P new9. Если критерий останова не достигнут, перейти к шагу 4, иначе завершить работу.ОперациямутацииP m  mutate(P )порождаетэлементыпопуляцииP m  { X 1m , X 2m ,..., X Nmpop } с помощью прибавления к элементам исходной популяцииP  { X 1 , X 2 ,..., X N pop } взвешенных разностей ("дифференциалов") других элементовпопуляции P. Элемент популяции P m с номером i может вычисляться по следующимправилам:стандартная схема: X im  X r1    ( X r2  X r3 )"жадная" схема: X im  X i    ( X b  X i )    ( X r2  X r3 )Здесь, r1 , r2 , r3  {1,2,..., N pop } - случайно выбираемые номера элементов популяции P(попарно различные), X b - наилучшее найденное на текущий момент решение,  ,   0 настраиваемые параметры операции.Отличие "жадной" схемы от стандартной заключается в целенаправленном смещениитекущего решения в направлении наилучшего найденного на текущий момент решения( X b ), что заметно повышает скорость сходимости алгоритма (за счет некоторогоослабления глобально-поисковых свойств алгоритма).91ОперацияскрещиванияP c  crossover ( P m , P )P c  { X 1c , X 2c ,..., X Nc pop } , i-й элемент которойформируетпопуляциюX ic  ( xic,1 xic, 2 ...xic, N ) представляет собойкомбинацию элементов популяций P m и P с тем же номером i (эти элементы обозначеныниже, соответственно, как X im  ( xim,1 xim, 2 ...xim, N ) и X i  ( xi ,1 xi , 2 ...xi , N ) ): xim, jx  xi , jдля j  Sici, jN, Si  1 N ,..., Si  Li  1NиначеЗдесь, Si - целое число, случайно и равновероятно выбранное из интервала [0, N  1] ; Li случайное целое число, выбранное из интервала [0, N  1] , при этом вероятность выборазначения k определяется формулой Pr( Li  k )  CR k .

Здесь CR  [0,1] - параметр операции;N- операция взятия числа по модулю N.Фактически, операция скрещивания в некоторой степени "нейтрализует" действиемутации, отменяя изменения определенных элементов вектора X i . При этом малыезначения Li более вероятны - это означает, что последовательное применение операциймутации и скрещивания обеспечивают высокую вероятность малых изменений в текущихрешениях, и меньшую (но не нулевую) вероятность больших изменений.ОперацияселекцииP new  select ( P c , P)обеспечиваетвыборкуизтекущейпопуляции P и модифицированной операциями мутации и скрещивания популяции P c ,новой текущей популяции P new .

Элемент модифицированной популяции P c выживает,только если он удовлетворяет всем ограничениям задачи и улучшает значение целевойфункции по сравнению с элементом текущей популяции с тем же номером:X c ,X inew   i Xi,если f ( X ic )  f ( X i ) и X ic  S  g j ( X ic )  0, j  1,2,.., kиначеКритерий останова.

Возможен один или некоторая комбинация следующихспособов останова: выполнение алгоритмом априорно заданного числа итераций; выполнение алгоритмом априорно заданного числа итераций без улучшения целевойфункции; достижение некоторого априорно заданного значения целевой функции.925. Муравьиные алгоритмы5.1. Концепция построения алгоритмов (биологическая модель)Интересным результатом кооперативного поведения биологических муравьевявляется нахождение кратчайшего маршрута от источника пищи к гнезду. Рассмотрим,как кооперативное поведение биологических муравьев позволяет найти кратчайшиймаршрут к источнику пищи.

Пусть гнездо соединено с источником пищи двумя ребрамиразной длины (рис.5.1.). Муравьи при прохождении маршрута откладывают феромоны ичем больше муравьев прошло по ребру, тем выше концентрация феромонов на этом ребре.Чем выше концентрация феромонов на ребре, тем выше вероятность, что муравей пойдетпо нему. Изначально вероятности выбора маршрутов равны. Муравьи, выбравшиекороткое ребро, возвращаются быстрее. Количество феромонов на коротком ребре растетбыстрей и следовательно повышается вероятность его выбора, т.е. через некоторое времяпо нему будет проходить большинство муравьев.

Со временем феромоны испаряются, чтопозволяет муравьям адаптировать поведение под изменение внешней среды.Рис. 5.1.93Таким образом, при решении задачи нахождения кратчайшего пути муравьиныеалгоритмы позволяют автоматически настраиваться на пример задачи (заданы конкретныезначения исходных данных) путем дополнительной разметки исходных данных, котораяиспользуется для построения решения на каждой итерации алгоритма и уточняется помере увеличения числа итераций.5.2. Общая схема работы муравьиных алгоритмовОбщую схему работы муравьиных алгоритмов можно представить в следующемвиде:1.

Задание начального количества феромона на ребрах графа, количества иначального положения муравьев.2. Построение муравьями пути (каждый муравей строит путь независимо отостальных).3. Вычисление целевой функции для каждого пути.4. Обновление количества феромона на ребрах.5. Если условие останова не выполнено, то переход к п.2.Муравьи строят маршруты, последовательно переходя от вершины к вершине,руководствуясь при этом определенным алгоритмом для определения списка вершин,доступных на данном этапе (например, при решении задачи коммивояжера используетсятабу-список недоступных вершин, в который добавляются пройденные муравьемвершины). Выбор очередной вершины зависит от количества феромонов и значениялокальной эвристической функции на ребрах, ведущих из текущей вершины в доступные.Эти значения определяют вероятность перехода в ту или иную вершину, после чегоочередная вершина определяется по правилу рулетки.В конце каждой итерации для каждого найденного маршрута вычисляетсязначение целевой функции.

Оно используется для вычисления количества феромона,добавляемого на ребра, входящие в данный маршрут.Операция построение муравьем пути. Муравей строит путь, переходя из однойвершины в другую. Пройденные муравьем вершины добавляются в табу-список (памятьмуравья), чтобы избежать повторного их посещения. Вероятность перехода муравья из i-йвершины в j-ю зависит от количества феромона на данном ребре, значения локальнойцелевой функции на ребре и состояния табу-списка. Вероятность перехода k-го муравья изi-й вершины в j-ю на t-й итерации алгоритма рассчитывается по следующей формуле:94   ij t    ij t  , j  Lk   t    t Pij , k t   ilill J k0, j  LkЗдесь ij(t) - количество феромона на ребре (i,j), ij (t ) - значение локальной целевойфункции на ребре (i,j),  и  - параметры алгоритма, определяющие важностьферомонного следа и локальной целевой функции, Lk – множество вершин, включенных втабу-список муравья k.Операция обновление количества феромона на ребрах.

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

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