Ответы_на_вопросы_по_материалам_курса_МО

4.Определяется следующая точка xk+1 = xk + a·pk, где a – решение задачи одномерной минимизации функции

5.В точке xk+1 вычисляется градиент f'(xk+1)

6.Если ||f'(xk+1)|| ≤ , то поиск заканчивается и полагается, что x*=xk+1 и y*=f(x*), иначе переходим к пункту 3.

Вторая модификация Эта модификация связана с обновлением матрицы вторых производных через

определенное количество шагов. Формула вычисления очередной точки xk+1будет выглядеть следующим образом:

хjm+i+1 = xjm+i– ajm+i· (f''(xjm)) –1·f'(xjm+i)

Методы определения экстремума овражных функций.

Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f(x) сильно вытянуты. Этот факт известен в литературе как “эффект оврагов”. Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции – эта группа переменных характеризует “склон оврага”, а по остальным переменным, задающим направление “дна оврага”, функция меняется незначительно.

Траектория метода характеризуется довольно быстрым спуском на “дно оврага”, и затем медленным зигзагообразным движением в точку минимума.

Пусть хk и хk1 - две произвольные близкие точки. Из хk совершают обычный градиентный спуск с постоянным шагомα и после нескольких итераций с малым шагом α попадают в точку uk. Тоже самое делают для точки хk1, получая точку uk1. Две точки uk и uk1 лежат в окрестности «дна оврага». Соединяя их прямой, делают «большой овражный шаг» λ в направлении убывания функции, перемещаясь «вдоль дна оврага» (шаг λ называют овражным шагом). Точка хк+1 определяется следующим образом. По формуле

Вычисляют точку xk+1. Из неѐ осуществляют градиентный спуск и получают точку uk+1. Если f(uk+1)<f(uk), то полагают x*=xk+1и u*=uk+1. В противном случае уменьшают овражный шаг и повторяют определение xk+1.

Общая идея модификации овражного метода Пусть х0 и х1 – две произвольные близкие точки. Как и в предыдущем случае, из

каждой точки осуществим градиентные спуски с постоянным шагом α. Получим точки u0 и u1, лежащие в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг» λ в полученном направлении. В результате получим точку х2. Из этой точки осуществим градиентный спуск и получим точку u2. А вот направлении и определяем х3. Далее аналогичным образом вычисляются х4, х5 далее, для того чтобы осуществить «овражный шаг», используем точку u1. Соединяя прямой точки u2 и u1, делаем шаг λ в полученном направлении и определяем x3. Далее аналогичным образом вычисляются x4, x5,…

Методы штрафных функций.

Если ограничения представляют собой равенства и нестрогие неравенства, используют штрафные функции:

11

т.е. если эксперимент вышел за ОДЗ, штрафная функция резко возрастает (убывает) при поиске max (min) и возвращает исследование в ОДЗ.

Если ограничения представляют собой строгие неравенства, то используются барьерные функции, значения которых неограниченно возрастает (убывает) при поиске max (min) при приближении к границе ОДЗ. Барьерная функция должна быть непрерывной внутри ОДЗ, т.к. все исследуемые при этом точки лежат внутри ОДЗ. Данный метод называют методом внутренней точки. В качестве барьерной часто применяют функции вида

=1

Трудности возникают при определении начальной точки исследования, а также если экстремум достигается на границе ОДЗ, т.к. значение обобщенной функции у границ ОДР определяется величиной барьерной функции и экстремум не всегда может быть получен с заданной точностью.

Стохастическое программирование.

Детерминированные методы поиска экстремума предполагают, что вся исходная информация строго однозначна, и на каждом шаге однозначно определяют положение точки исследования (одномерный поиск: дихотомия, метод Фибоначчи, золотого сечения, градиентный метод и метод наискорейшего спуска).

Модели часто оказываются неадекватными реальным процессам, что объясняется неполнотой или неточностью данных, на основе которых строилась модель.

Водних случаях некоторые (а возможно и все) параметры носят вероятностный характер. В этих случаях говорят о ситуациях, связанных с риском.

Вдругих случаях имеющаяся информация не позволяет составить представление о характере изменения параметров, описывающих изучаемый процесс. Такие ситуации называют неопределенными.

Оптимизационные задачи, при постановке которых нет исчерпывающих данных об их условиях, называются стохастическими.

Стохастическое программированиеизучает теорию и методы решения условных экстремальных задач при неполной информации об условиях задачи.

Пассивное стохастическое программирование (ПСП) – это совокупность приемов, позволяющих находить наилучшее решения и экстремальное значение ЦФ в оптимизационных задачах со случайными исходными данными.

Активное стохастическое программирование (АСП ) – это совокупность приемов, позволяющих развивать методы выбора решений в условиях риска и неопределенности

Основным отличием стохастических методов от детерминированных является введение элемента случайности в процесс поиска экстремума.

Стандартный стохастический алгоритм состоит из 2-х шагов: сбор информации; принятие решения о движении

12

Алгоритмы случайного поиска различаются условиями выбора рабочего шага по направлению и возможностью изменения его размера в процессе поиска, а также возможностями алгоритма изменять вероятностные свойства случайности.

Под накоплением понимают сбор с помощью пробных шагов информации о поведении функции вблизи рассматриваемой точки для дальнейшей какой-либо оптимальной обработки этой информации и выборе эффективного направления рабочего шага.

Ненаправленный случайный поиск.

Задача поиска оптимальных решений: требуется найти минимума функции W(X) векторного аргумента X=(x1, x2, …, xn) в некоторой заданной области Dдопустимых значений X. Область Dопределяет пространство допустимых решений, каждой точке которого соответствует некоторое значение вектора X и целевой функции W(X), удовлетворяющие заданным ограничениям. Вектор X* принадлежит Dи соответствует минимуму оптимизируемой функции W(X), является целью поиска.

Ненаправленный случайный (слепой) поиск экстремума производят следующим образом: строят последовательность

независимых случайных векторов, концами которых являются точки, принадлежащие области D. Затем вычисляют соответствующие значения целевой функции

из которых выбирают наименьшую: W(X*)=min{W1, W2, …,WN}

Если задано Wmin, то поиск осуществляется до тех пор, пока не будет найден X* такой, что

|W(X*)-Wmin|≤

В основе метода лежит проведение испытаний модели с использованием выборки объема Nнезависимых случайных точек исследования {xi} для выявления области вероятного экстремума.

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

для любого вида целевой функции.

Необходимость продолжения вычислений определяется тем, насколько подробно была рассмотрена область D:

1.Область Dразбивается на lинтервалов, вычисляют эмпирические частоты

1 / , ( = 1, 2, … , ) попадания отдельных значений целевой функции Wв i-ый интервал. Поиск прекращается, если на некотором s-м шаге для любого интервала

выполняется условие

2.По результатам большого числа Ni испытаний (Ni>100)строят вариационный ряд (последовательность расположенных в возрастающем порядке значений целевой функции):

W1<W2<…<WNи эмпирическую интегральную функцию распределения. Если после проведения дополнительного числа испытаний интегральная функция несущественно отличается от предыдущей, то говорят о достаточности объема вычислений.

Эффективность ненаправленного случайного поиска

Пусть заданы вероятность р и точность нахождения экстремума функции W(X) в области D. Точность определяет множество оптимальных решений {X*}. Отношение объема области оптимальных решений к объему области D обозначим через z. Тогда

13

необходимое число шагов для однократного попадания в область {X*} с вероятностью pможно определить по формуле

≥

lg (1 − )

lg (1 − )

Направленный случайный поиск: поиск с возвратом при неудачном шаге, поиск с наказанием случайностью, поиск парными пробами, поиск по наилучшей пробе.

Для направленного случайного поиска характерно ограничение зоны поиска областью, центром которой является найденная в ходе поиска точка с наилучшим значением целевой функции. Если на новом шаге найдена точка с лучшим значением целевой функции, то эта точка становится новым центром зоны поиска. Этим достигается последовательное смещение ограниченной зоны поиска в район цели.

Поиск с возвратом при неудачном шаге В пространстве параметров произвольно выбирается точка Х0. Задается постоянный

шаг h. Из точки Х0 в случайном направлении, определенном случайным единичным вектором ζ = (ζ1,…, ζn), осуществляется шаг на величину h. Вычисляется значение целевой функции в новой точке X1. Если значение W(X1) <W(X0) (в случае поиска минимума), то шаг считается рабочим, и новый шаг осуществляется из точки X1 в случайном направлении. Если W(X1) > W(X0), то шаг считается неудачным, производится возвращение в точку X0, из которой в случайном направлении снова совершается пробный шаг.

Повторное определение W(X) при возвращении в исходный центр поиска следует применять в тех случаях, когда целевая функция по каким-либо причинам изменяется во времени, например при наличии помех.

Поиск с наказанием случайностью Предполагает движение в благоприятном направлении до первого неудачного шага.

После этого проводится случайный поиск нового благоприятного направления.

Движение из центра зоны поиска Xj-1 , найденного в процессе поиска, ведется в случайном направлении Xj=Xj-1+ah до тех пор, пока не обнаружится благоприятное направление такое,

благоприятном направлении с фиксированным шагом ∆ = и соответствующим смещением зоны поиска до тех пор, пока ∆ < 0.

Вначале поиска используют достаточно большой шаг, а затем его уменьшают. Недостаточная длина рабочего шага поиска приводит к возрастанию вероятности «застревания» в локальном экстремуме.

Врассматриваемом алгоритме случайность вводится как отрицательная реакция на неудачный шаг.

Алгоритмы поиска с «наказанием» случайностью предполагают смещение зоны поиска

вблагоприятном направлении сразу после удачного шага.

Поиск парными пробами Предполагается четкое разделение между пробным и рабочим шагами. Направление

рабочего шага выбирается после двух пробных шагов из исходной точки X0в точки X1и X2вдоль случайного направления:

14

Поиск по наилучшей пробе

Характеризуется проведением m случайных пробных шагов из исходной точки Xj-1 , в точки X1, X2,..., Xm так, что

Самообучение в методах случайного поиска. Поиск с обучением по одной попытке (жесткое и нежесткое обучение).

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

Предыдущие шаги рассматриваются при этом как результаты испытаний системы, дающие представление о благоприятном направлении оптимизации.

Вектор в этом случае перестает быть равновероятным и в результате самообучения приобретает некоторые преимущества в направлении наилучшего шага.

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

Поиск с обучением по одной попытке Случайность вводится после повторного неудачного шага. Смещение на каждом шаге

поиска производится следующим образом: Xj+1=Xj+ . При удачном шаге. После первого неудачного шага центр зоны поиска смещается в направлении, противоположном

15

неудачному, т.е. +1 = − , а при следующем неудачном шаге направление смещения выбирается случайным

Рассмотренный алгоритм напоминает поиск с «наказанием» случайностью и является

алгоритмом «жесткого» обучения по одной попытке

Нежесткое обучение по одной попытке Предусматриваем автоматическое изменение масштаба, т.е. при удачном шаге +1 =

1 , а при неудачном шаге +1 = −(1/ 2) , причем d1>d2>=1

Существуют также разновидности алгоритмов поиска с самообучением по нескольким шагам и непрерывного обучения.

Улучшенная сходимость методов направленного случайного поиска с элементами самообучения по сравнению с методом ненаправленного случайного поиска достигается за счет снижения универсальности метода.

Адаптация в методах случайного поиска.

Адаптациейназывается целенаправленный процесс изменения различных параметров поиска (например, шага) для повышения его эффективности. Процесс адаптации можно вводить и в детерминированные методы.

Адаптация величины рабочего шага От размера шага зависит сходимость метода: большой шаг дает быстрое приближение

к экстремуму, но появляется вероятность «блуждания» около него. Малый шаг не позволяет быстро достигнуть экстремума, но удобен для работы внутри его окрестности. Поэтому целесообразно вводить процедуру автоматического изменения шага. На значительном расстоянии от ext шаг должен увеличиваться, а по мере приближения к ext он должен уменьшаться. Изменение шага может осуществляться по результатам одной или нескольких попыток

Структурная адаптация Осуществляется за счет параметризации структуры алгоритма, т.е. введения

параметров, которые определяют структуру алгоритма поиска

Если {Fi} – конечное множество возможных алгоритмов поиска, тогда их линейная комбинация

Если же снять эти ограничения, то получим гибридную структуру алгоритма. Рассмотренные методы направленного случайного поиска носят локальный характер и

имеют малую эффективность в задачах с многоэкстремальной целевой функцией. Уменьшение риска потери глобального экстремума требует равномерного и

достаточно полного просмотра всей области определения целевой функции (т е. использования элементов ненаправленного случайного поиска).

16

Метод случайного поиска экстремума функции по статистическому градиенту, блуждающие методы случайного поиска.

В методе статистического градиента по mпробам составляется векторная сумма

являющаяся статистической оценкой градиента ЦФ. Рабочий шаг осуществляется в направлении градиента:

При → ∞направление статистического градиента стремится по вероятности к направлению градиента. При m=n, где n-число переменных ЦФ, а m-число случайных

ортогональных проб , рассматриваемый алгоритм вырождается в детерминированный метод градиента.

Различают независимые, блуждающие и комбинированные методы глобального поиска экстремума.

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

Принцип их таков: берется детерминированный метод, например градиентный, и на

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

Эволюционные вычисления.

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

(GeneticAlgorithms - GA), методы поведения «толпы» (ParticlesSwarmOptimization - PSO) и методы «колонии муравьев» (AntColonyOptimization - ACO).

Начало применению генетических алгоритмов для решения задач оптимизации положил Д.Холланд в 1975 г. Фундаментальный вклад в развитие GA внес Д.Гольдберг. В дальнейшем генетические алгоритмы успешно применялись для различных задач синтеза конструкций, составления расписаний, маршрутизации транспортных средств, компоновки оборудования, раскроя материалов и др.

Алгоритм поведения толпы первоначально был описан применительно к задачам математической биологии в 1987 г.

Впервые идея использования для решения оптимизационных задач аналогии с поведением колонии муравьев высказана в 1992 г. Применение методов ACO показано на примерах задачи коммивояжера, раскроя и упаковки и др.

17

Для применения эволюционных методов к решению конкретной задачи нужно, вопервых, сформулировать множество управляемых параметров X, во-вторых, разработать модель приложения в виде алгоритма вычисления целевой функции F(X), в-третьих, разработать алгоритмическую реализацию эволюционного метода. При этом, учитывая приближенность и статистическую природу этих методов, нужно стремиться к получению высокоэффективных алгоритмов с позиции как точности, так и трудоемкости вычислений.

Общая структурная схема эволюционных методов:

1.Формирование исходного поколения

2.Пока не выполнится условие останова делать следующее

2.1.Определение перспективности членов популяции

2.2.for k от 1 до n

2.2.1.Формирование новой хромосомы

2.2.2.Оценка целевой функции

2.2.3.Селекция

2.3.Смена поколения

Вычисления начинаются с формирования множества G информационных объектов Xj=(xj1, xj2,…,xjn), j=1,2,…,N, которые в соответствии с принятой в ГА терминологией, называются хромосомами. Хромосома состоит из генов xj1, значения генов называют аллелями, а позиции генов в хромосоме – локусами.Обычно в задачах оптимизации гены отождествляют с управляемыми параметрами. Множество G называют популяцией, а состав популяции в конкретный момент вычислений – поколением.

Эволюция представляет собой многошаговый процесс. На каждом шаге формируются новые хромосомы и Nхромосом отбирается (селекционируется) в новое поколение. Формирование хромосом нового поколения происходит с использованием генного материала текущего поколения и с учетом качества этого материала. Качество j-й хромосомы оценивается значением целевой функции F(Xj), а качество каждого поколения – наилучшим (минимальным) значением целевой функции, полученным на данный момент вычислений.

Решение задач оптимизации методами моделирования эволюции.

Эволюционное моделирование использует признаки теории Дарвина для построения интеллектуальных систем. Является частью более обширной области искусственного интеллекта – вычислительного интеллекта.

Эволюционное моделирование это уже достаточно сложившаяся область, в которой можно выделить:

1. Моделирование возникновения молекулярно – генетических информационных

систем

2.Моделирование общих закономерностей эволюции

3.Эволюционные модели

4.Прикладное эволюционное моделирование.

Алгоритм решения задач оптимизации методами моделирования эволюции:

1.Формирование исходного поколения

2.Пока не выполнится условие останова делать следующее

2.1.Определение перспективности членов популяции

2.2.for k от 1 до n

2.2.1.Формирование новой хромосомы

2.2.2.Оценка целевой функции

18

2.2.3. Селекция 2.3.Смена поколения

+ дополнительно смотреть из вопросов 19, 21

Генетические алгоритмы. Генетические операторы.

В задачах структурного синтеза любая структура представляется значениями структурных параметров xiмножества X. В генетических методах множеству Xсоответствует запись, называемая хромосомой, элементы хромосомы соответствуют параметрам xi, их называют генами, а значения генов – аллелями. Каждый ген размещается в хромосоме в некоторой позиции – локусе. В случае геометрической интерпретации каждому гену соответствует одна из осей координатного пространства, а хромосоме некоторая точка поискового пространства.

Очевидно, что в большинстве практически значимых задач структурного синтеза число возможных альтернатив столь велико, что явное представление множества альтернатив невозможно. Поэтому в каждый момент поиска генетический алгоритм (ГА) оперирует подмножеством альтернатив мощности N, представляющим некоторые N точек пространства структурных параметров. Это подмножество называют популяцией, а N - размером популяции. Хромосома, представленная конкретными значениями своих генов, есть проектная альтернатива или экземпляр хромосомы.

Основная идея ГА заключается в эволюции популяции, повторяющей некоторые черты эволюции организмов в живой природе. Если цель эволюции в живой природе - обеспечение наибольшей жизнеспособности популяции в условиях окружающей среды, то цель эволюции в ГА - получение экземпляров с наилучшими значениями определенных критериев, характеризующих качество экземпляра, т.е. синтезируемой структуры. Как и в других методах синтеза, в ГМ при наличии нескольких критериев задача должна быть сведена к однокритериальной путем свертки векторного критерия. Получающуюся целевую функцию часто называют функцией полезности. Любой конкретный экземпляр хромосомы называют генотипом, а множество значений характеризующих хромосому критериев - фенотипом.

Таким образом, цель генетического поиска - найти экземпляр хромосомы, имеющий значение функции полезности, максимально близкое к ее экстремальному значению. Направленный поиск малой окрестности экстремума осуществляется в ГА с помощью генетических операторов выбора родителей, кроссовера, мутации, селекции, переупорядочения, поясняемых ниже.

Генетические алгоритмы имитируют эволюционный процесс приближения к оптимальному результату, начиная с некоторого исходного поколения структур, представленных экземплярами хромосом. Этот процесс в базовом ГА является вложенным циклическим вычислительным процессом. Внешний цикл имитирует смену поколений. Во внутреннем цикле формируются члены очередного поколения.

Члены исходного поколения генерируются случайным образом. При этом для каждого гена задана область определения, например, в виде интервала [Xmini, Xmaxi], и значения генов выбираются с равной вероятностью в его пределах.

Результатом каждого очередного витка внешнего цикла является новое поколение, о качестве которого судят по экземпляру хромосомы с лучшим значением функции полезности

F.

Характер приближения к экстремуму обычно таков, что на начальных витках скорость улучшения целевой функции довольно значительная, но по мере приближения к экстремуму она замедляется и может наступить прекращение улучшения F на некотором удалении от экстремальной точки. Это явление называют стагнацией. Обычно оно происходит из-за

19

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

Во внутреннем цикле базового ГА выполняется следующая последовательность генетических операторов: выбор родителей, кроссовер (скрещивание), мутации, формирование нового поколения.

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

Оператор кроссинговера Заключается в разрыве двух выбранных родительских хромосом и рекомбинировании

образовавшихся хромосомных отрезков, что дает пару хромосом потомков.

На рисунке представлен пример кроссинговера (разрыв после третьего локуса) и рекомбинация отрезков.

Оператор мутации

Мутации, т.е. случайные изменения некоторых аллелей, предназначены для реализации поиска в пространстве всех возможных экземпляров хромосом. Без мутаций поиск не может выйти за пределы того подмножества экземпляров хромосом, в котором аллели совпадают с сгенерированными значениями генов в начальной популяции. Например, если в некотором гене, отображающем дни недели, в хромосомах начальной популяции оказались сгенерированными только значения "понедельник", "среда", "четверг" и "воскресенье", то при выполнении операторов кроссовера или селекции значения "вторник", "пятница" и "суббота" появиться не могут. Мутации устраняют этот недостаток. Они происходят в очередном гене с некоторой заданной вероятностью Рм, эта вероятность обычно выбирается достаточно малой (сотые-тысячные доли). При мутациях значение гена выбирается случайным образом среди множества возможных значений, т.е. в нашем примере произойдет равновероятный выбор среди всех семи возможных дней недели.

Постановка задачи ЛП. Формы записи ЗЛП. Геометрическая интерпретация ЗЛП, основная теорема линейного программирования.

Задача линейного программирования заключается в изучении способов отыскания наибольшего или наименьшего значения линейной функции при наличии линейных ограничений.

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

20