36209

Задачи дискретной оптимизации. Основные точные методы дискретной оптимизации: поиск с возвратом, динамическое программирование, метод ветвей и границ. Приближённые методы дискретной оптимизации: жадный алгоритм, метод локальных вариаций

Доклад

Математика и математический анализ

Тогда в терминах ЦЧЛП задача о рюкзаке может быть сформулирована так: найти максимум линейной функции при ограничениях хj  0 . Найти кратчайший маршрут коммивояжера бродячего торговца начинающийся и заканчивающийся в заданном городе и проходящий через все города. Воспользовавшись им при k = n – 1 1 можно найти Q х0 – оптимальное значение критерия эффективности. Зная х1 можно найти – оптимальное управление на 2й стадии и т.

Русский

2013-09-21

126.5 KB

67 чел.

6

7 Вопрос

Задачи дискретной оптимизации. Основные точные методы дискретной оптимизации: поиск с возвратом, динамическое программирование, метод ветвей и границ. Приближённые методы дискретной оптимизации: жадный алгоритм, метод локальных вариаций.

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

Рассмотрим несколько классических примеров задач дискретной оптимизации.

Задача о рюкзаке (о ранце). Имеются вещи одного из n типов, определенной ценности сj и веса wj, значения которых – натуральные числа. В рюкзак можно положить не более H кг груза. Выбрать вещи, суммарная ценность которых максимальна.

Данную задачу можно считать частным случаем следующей.

Задача целочисленного линейного программирования (ЦЧЛП), т.е. задача ЛП, в которой все переменные хj – целые числа.

В задаче о рюкзаке обозначим хj – количество вещей j-го вида. Тогда в терминах ЦЧЛП задача о рюкзаке может быть сформулирована так: найти максимум линейной функции  при ограничениях хj  0, .

Задача о коммивояжере. Имеется n городов. Для любой их пары (i, j) задано расстояние сij  0 между ними. Найти кратчайший маршрут коммивояжера (бродячего торговца), начинающийся и заканчивающийся в заданном городе и проходящий через все города.

Задачи на графах, известные из курса дискретной математики:

- поиск кратчайшего пути в ориентированном графе;

- поиск остова минимального веса;

- построение оптимальных вершинных подмножеств – минимального покрытия, максимального независимого множества и др.

9.1. Поиск с возвратом

Общая схема рекурсивного варианта алгоритма. Пусть дано n упорядоченных множеств В1, В2,… Вn. Решением задачи является вектор Х = (х1, х2,… хn), где xiВi, удовлетворяющий некоторым дополнительным условиям. Иными словами Х В1В2 Вn.

В алгоритме поиска с возвратом вектор Х строится покомпонентно слева направо. Предположим, что уже найдены первые k – 1 компонент х1, х2,… хk–1. Тогда их значения определяют некий набор условий, ограничивающих выбор  k-й компоненты некоторым множеством Sk  Вk. Если Sk не пусто, мы вправе выбрать в качестве хk первый по порядку элемент из Sk, присоединить его к уже выбранным компонентам, и перейти к выбору хk+1 и так далее. Однако, если набор условий таков, что Sk пусто, либо хk равен его последнему элементу, то мы возвращаемся к выбору k–1-й компоненты. При этом мы отбрасываем хk–1 и выбираем в качестве новой k–1-й составляющей вектора Х тот элемент из Sk–1, который непосредственно следует за только что отброшенным хk–1.

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

Этот процесс продолжается, пока не будут рассмотрены все возможные вектора решений.

Данная схема легко реализуется посредством рекурсивной процедуры.

procedure Solve ( k, Х ,  Sk );

           { k – номер подбираемой координаты (глубина рекурсии) }

           { Х – вектор текущего решения }

 { Sk – множество допустимых значений Хk }

begin if   Х – решение   then   

begin  Вычислить f(Х) ;   

if   f(Х) лучше текущего оптимума  then  запомнить Х

end

                else

begin         

                     for  у  Sk  do  

begin   Сузить  Sk+1 с учетом выбранного у ;

          Solve ( k+1,  (Х & у),  Sk+1 ) ;

                              { & – операция добавление к вектору компоненты }

end;

         end;

end;

{ Головная программа }

begin   Solve ( 1, ,  B1 );

end.

Если сравнивать алгоритмы поиска с возвратом и полного перебора вариантов, то первый имеет два преимущества.

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

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

9.2. Метод динамического программирования

Пусть имеем процесс, состоящий из n стадий. Состояние процесса на каждой  k-й стадии определяется значением некоторого параметра хk, k = 1,…n, в общем случае – векторного. k-я стадия процесса формально представима переходом из состояния хk–1 в хk под действием управляющего параметра uk, т.е. хk – является некоторой функцией от хk–1 и uk:

хk = ( хk–1, uk).

Пусть эффективность такого перехода оценивается значением критерия qk–1, uk), а эффективность всего процесса оценивается величиной

.

Рассмотренный выше алгоритм поиска с возвратом достаточно универсален, т.е. его можно использовать во многих приложениях, однако выигрыш от его применения обычно не столь велик. Метод же динамического программирования позволяет существенно сократить число перебираемых вариантов, однако оптимизируемый процесс должен обладать следующим специальным свойством: эффективность перехода хk–1 хk не зависит от значений параметров хj  для  j < k–1, т.е. не зависит от способа попадания в состояние хk–1 (аналог известного свойства отсутствия последействия). К таким процессам применим так называемый принцип оптимальности Беллмана (ПОБ).

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

Пусть для любого k хk  Vk, где Vk – множество допустимых значений параметра хk; uk Uk–1), где Uk–1) – множество допустимых управлений на k-й стадии (в общем случае оно зависит от значения  хk–1) и хk = ( хk–1, uk).

Замечание. Для сравнения – в поиске с возвратом множество Sk – аналог множества допустимых управлений Uk, зависит от всего сформированного набора х1 ,… xk–1, а не только от последней составляющей xk–1.

Предположим также, что начальное х0 и конечное хn состояния процесса заданы и необходимо оптимально перевести объект из х0 в хn.

Введем в рассмотрение так называемую функцию Беллмана Q( хk), определяющую значение эффективности процесса при оптимальном переходе из хk в хn. По определению положим Q( хn) = 0 (перехода из хn в хn нет, значит, эффективность равна 0). Тогда для n-й стадии эффективность перехода   хn–1  хn  для любого  хn–1  равна

Q( хn–1) = qn–1, un) + Q( хn),

т.е. эффективность оптимального перехода  хn–1  хn  плюс эффективность оптимального перехода хn  хn (второе слагаемое, равное 0, добавлено пока что  формально).

Рассмотрим n–1-ю стадию процесса: хn–2  хn–1. ПОБ требует, чтобы при любом возможном хn–2 параметр хn–1 выбирался так, чтобы общая эффективность переходов хn–2  хn–1  хn  была наилучшей. Следовательно,

Q( хn–2) = { qn–2, un–1) + Q( хn–1)},

т.е. управление un–1 должно быть таким, чтобы суммарная эффективность двух последних переходов была наилучшей. Так как хn–1 = ( хn–2, un–1), то окончательно получаем

Q( хn–2) = { qn–2, un–1) + Q[ ( хn–2, un–1) ]  }.

Аналогично, для любого k 

Q( хk–1) = { qk–1, uk) + Q [ ( хk–1, uk) ]  }.          (9.2)

Полученное выражение называется уравнением Беллмана. Оно представляет собой рекуррентное соотношение, определяющее значение Q( хk–1) для всех  хk–1 при начальном условии Q( хn) = 0. Воспользовавшись им при k = n – 1, … 1 можно найти Q( х0) – оптимальное значение критерия эффективности. Процесс рекуррентного вычисления Q( х0) по формуле (9.2) называется обратным ходом метода динамического программирования (название связано с тем, что расчет начинается с последней стадии). В составленной ранее таблице 9.1 вторая строка представляет собой значения функции Беллмана для задачи о рюкзаке.

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

Таким образом, при обратном ходе вычисляются и запоминаются все значения параметров, удовлетворяющих ПОБ, т.е. необходимым условиям оптимальности. Для выбора среди них оптимального решения организуем процесс прямого хода. Пусть  – оптимальное управление на 1-й стадии, найденное при обратном ходе. Так как состояние х0 фиксировано, то данное управление является единственно возможным, а значит – оптимальным на 1-й стадии. Тогда х1 =  ( х0, ) – оптимальное состояние процесса после 1-й стадии. Зная х1, можно найти  – оптимальное управление на 2-й стадии и т.д. В результате для поиска оптимальных управлений и состояний имеем рекуррентные соотношения при заданном х0:

  хk =  ( хk–1, ).

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

Здесь V[k] – массив значений x[k] – множество Vk.

begin   read(x[0], x[n]);    { Краевые условия }

Q [ x[n] ] :=0;                                          

for  k:= n  downto  1  do          { ЦИКЛ ОбратнОГО ходА }

for y V[k –1]  do  

begin  

Q[y]  :={ q ( y, uk )  + Q [ ( y, uk ) ]  };

                           { Вычислить значение функции Беллмана }

u_opt[k, y ] := arg_opt{….};

end;                     { Запомнить оптимальное управление}

for  k := 1 to  n  do                        { ЦИКЛ ПрямоГО ходА }                                

begin  write ( Q ( x[k–1]), u_opt[k, x[k–1] ] ) ;

х[k] := ( x[k–1]), u_opt[k, x[k–1] ] ) ;

                  { Определить следующее состояние }

end;

end.

Пример 9.2. В ориентированном бесконтурном графе найти путь минимального веса, соединяющий две фиксированные вершины s и t.

Решение. Для применения метода динамического программирования при решении этой задачи воспользуемся следующим свойством бесконтурных графов: в произвольном бесконтурном графе  G = (V, E) вершины можно перенумеровать так, чтобы для каждой дуги (u, v)  E выполнялось условие u < v. Положим s = 1, t = n.

Представим граф в виде списков следования, т.е. для любой вершины      v  V вводится список СЛЕД[v] вершин, смежных с v, и таких, чтобы  r  СЛЕД[v]   (v, r) E (см. тема 3, п. 3 определение Г(Si)). Тогда:

- состояниями хk процесса движения по графу являются текущие вершины vk;

- управляющим параметром uk(vk–1) – номер следующей вершины на маршруте из множества СЛЕД[vk–1];

- критерием q( хk–1, uk) – вес ребра (vk–1, vk), где vk = uk(vk–1).

9.3. Метод ветвей и границ

Методы этого типа широко используются для решения дискретных оптимизационных задач. Различные варианты метода  существенно используют специфику задачи и поэтому заметно отличаются друг от друга. Однако, все они основаны на последовательном разбиении множества допустимых решений на части (ветвление) и вычислении оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие оптимального решений. Благодаря этому число перебираемых вариантов может существенно сократиться. Недостаток алгоритма в том, придумать хорошие правила ветвления и “дальнего обнаружения” плохих ветвей – обычно весьма сложная творческая задача, не имеющая готовых рецептов на все случаи. Например, при решении задачи коммивояжера разбиение организуется по следующему принципу: в одно множество включаются маршруты, содержащие некоторое фиксированное ребро        (Сj, Сk), а в другое – маршруты, не содержащие этого ребра. В других задачах применяются, соответственно, другие правила ветвления.

Рассмотрим простейший вариант оценивания ветвей на примере задачи целочисленного линейного программирования, т.е. задачи ЛП, в которой все переменные хj – целые числа.

Общая схема алгоритма.

Пусть имеем задачу: найти максимум функции q(x) при условии х  D, где область D задается системой равенств и неравенств.

Обозначим a, b – векторы двойных неравенств для переменных x[i] :     a[i] <= x[i] <= b[i]. Первоначально a[i] = 0, b[i] = +, если исходная задача не содержит иных двойных ограничений.

begin   Найти x – решение исходной задачи | a[i] <= x[i] <= b[i]

          (x, q(х), a, b )  CTEK;

repeat (y, q, a0, b0 )  max_q (CTEK) ; {Элемент стека с максимальным q}

k:= 0;

for i:= 1 to n do

if  trunc(y[i]) <> y[i]  then k := i; { k – номер нецелочисленного х }

if  k <> 0   then  { Решение нецелочисленное }

begin  a[k] := trunc(y[k]) + 1 ;

  Найти x – решение задачи | a[i] <= x[i] <= b0[i]

 (x, q(х), a, b0 ) CTEK;  

 b[k] := trunc(y[k]) ;

  Найти x – решение задачи | a0[i] <= x[i] <= b[i]

 (x, q(х), a0, b ) CTEK;

end;

until (k = 0)  or (CTEK = );

write(y);

end.

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

9.4. Приближенные методы

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

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

Пример 9.4. Рассмотрим следующую задачу. Дана матрица

.

Необходимо выбрать по одному элементу из каждого столбца, так, чтобы их сумма была максимальна. С помощью жадного алгоритма выбираем числа 9, 5, 8, сумма которых равна 22. Это и будет оптимальное решение.

Пусть теперь необходимо выбрать по одному элементу из каждого столбца и каждой строки, так, чтобы их сумма была максимальна. Жадный алгоритм на каждом шаге будет выбирать максимальный из возможных элементов. В результате будут выбраны числа 9, 2, 1, которые в сумме составят 12. Оптимальное же решение составляет последовательность 8, 2, 8 с суммой 18, т.е. на 50% больше. Таким образом, для одних задач жадный алгоритм позволяет найти оптимальное решение, для других – нет.

Общая схема жадного алгоритма имеет следующий вид.

procedure greedy;   

begin  for i := 1  to   n   do

begin   Определить Si ;    хi  := arg_max_q (Si );   

end;

end;

Применительно к задаче о рюкзаке простейшим вариантом жадного алгоритма является выбор на каждом шаге номера i, доставляющего  максимум выражению , при этом , W_si+1 = W_s ix iw i. При исходных данных предыдущего раздела получим с помощью жадного алгоритма, что надо отобрать одну вещь массой 11 кг, ценностью 20 у.е., что хуже оптимального решения на 1 у.е.

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

Различные варианты метода отличаются способом построения окрестностей и стратегией их расширения. Пусть надо решить задачу целочисленного (не обязательно – линейного) программирования. В простейшем случае окрестность может иметь вид куба с центром в исходной точке и стороной 2, 4, 6 и т.д. единиц (т.е. вершины в точках x0 1, x0 2  и т.д.). Целочисленные точки куба с заданными размерами можно получить с помощью алгоритма генерации размещений с повторениями (или, что то же самое,  – генерации декартовой степени целочисленного множества).


 

А также другие работы, которые могут Вас заинтересовать

30853. Системные регуляторные реакции и процессы 24.5 KB
  Адаптация приспособление механизмы которые обеспечивают приспособление организма к действию раздражителей. Адаптация бывает двух видов: а срочная адаптация б долговременная адаптация Срочная адаптация очень энергозатратна. При умеренных раздражителях тоже возникает срочная адаптация но явных признаков стресса нет. Но если раздражитель действует повторно многократно то возникает долговременная адаптация.
30854. Функциональные системы 23 KB
  Функциональные системы Функциональная система это временная динамическая саморегулирующаяся организация все составные компоненты которой взаимодействуя обеспечивают достижение полезных приспособительных результатов. В функциональной системе есть периферические и центральные составляющие: Периферические составляющие: А Исполнительные соматические вегетативные и эндокринные компоненты в том числе и поведенческие включающие механизмы формирование результата. Б Полезный приспособительный результат. В Рецепторы...
30855. Рефлекторная регуляция 34.5 KB
  Передача возбуждения в синапсе . иррадиация возникшего возбужденияраспространение возбуждения на рядом лежащие нейроны. концентрация возбуждениястягивание возбуждения на один или несколько нейронов. Индукция бывает: положительная когда наводится процесс возбуждения отрицательная когда наводится процесс торможения.
30856. Рефлексы 31 KB
  Рефлексы Рефлексы делятся на безусловные и условные. Безусловные рефлексы Это врожденные рефлексы которые не требуют предварительной выработки при действии раздражителя реализуются однотипно без особых предварительных условий. Безусловные рефлексы являются видовыми т. Рефлексы направленные на сохранение вида.
30857. Вегетативная нервная система 35.5 KB
  Очаговое представительство нервных центров СНС и ПСНС в ЦНС и. СНС боковые рога тораколюмбального отдела спинного мозга. ПСНС три зоны где лежат её центры:а мезенцефальный отдел ветви в составе глазодвигательного нерва зрачок некоторые слюнные железы;б бульбарный отдел лицевой языкоглоточный нерв и n. ВНС представлена двумя отделами: а симпатическая нервная система СНС б парасимпатическая нервная система ПСНС.
30858. Гуморальная регуляция функций 39.5 KB
  Классификация биологически активных веществ БАВ: Неспецифические метаболиты. Специфические метаболиты: а тканевые гормоны парагормоны; б истинные гормоны. Неспецифические метаболиты продукты метаболизма вырабатываемые любой клеткой в процессе жизнедеятельности и обладающие биологической активностью СО2 молочная кислота. Специфические метаболиты продукты жизнедеятельности вырабатываемые определенными специализированными видами клеток обладающие биологической активностью и специфичностью действия: а тканевые...
30859. Гуморальная регуляция функций. Межсистемный уровень 29.5 KB
  Истинные гормоны. Парагормоны. Истинные гормоны БАВ вырабатывающиеся в специализированных железах внутренней секреции обладающие дистантным действием и высокой активностью. Делятся по принадлежности к железам внутренней секреции половые гормоны тиреоидные гормоны и т.
30860. Гипоталамо-гипофизарная система 24 KB
  Меланостатин Релизинг–факторы регулируют выделение гормонов передней доли гипофиза большая часть которых гландулярные регулируют деятельность других желез внутренней секреции выделение ими гормонов. Регуляция в системе гипоталамус гипофиз осуществляется по принципу отрицательной обратной связи избыток гормонов в крови торможение их выработки: 1. Короткая петля регуляции: Рецепторы ГФ реагируют на концентрацию тропныхсобственных гормонов изменяют их выделение и опосредовано уровень гормонов периферических желез вн. Длинная...
30861. Передняя, задняя и промежуточная доли гипофиза 35.5 KB
  Передняя доля гипофиза Все гормоны передней доли являются веществами белковой природы пептиды белки гликопротеиды. Гормоны передней доли гипофиза: 1. Соматотропный гормон СТГ гормон роста соматотропин. Этот гормон белковой природы 191 аминокислота 1стимулирует синтез белка в органах и тканях 2способствует утилизации аминокислот 3увеличивает дифференцировку и созревание клеток.