36209

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

Доклад

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

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

Русский

2013-09-21

126.5 KB

66 чел.

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  и т.д.). Целочисленные точки куба с заданными размерами можно получить с помощью алгоритма генерации размещений с повторениями (или, что то же самое,  – генерации декартовой степени целочисленного множества).


 

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

42952. Організації передачі повідомлень на базі нових мережевих технологій 54.45 KB
  Завантаження однієї абонентської лінії телефонною розмовою складає в середньому 002 Ерланга в годину у годину пік – у 5 разів більше. Для спрощення розрахунків думаємо що динаміка росту кількості абонентів описується лінійним законом; завантаження однієї абонентської лінії телефонною розмовою складає в середньому 002 Ерланга в годину у годину пік – у 5 разів більше; середній трафик мови визначаємо по формулі: Тм сер = 002 Nб Тм сер = 002 13=026 Тм сер = 002 15=030 Тм сер = 002 16=032 Тм сер = 002 17=034 Тм сер = 002...
42953. Физические основы рентгеноспектрального и рентгенофлуоресцентного методов анализа 1.05 MB
  Свойства тонкоплёночных твёрдотельных объектов (электрические, магнитные, оптические и др.) зависят от их химического состава и толщины. Поэтому определение химического состава, толщины и других физико-химических характеристик твёрдотельных плёнок и покрытий для получения материалов с уникальными физическими свойствами является важной задачей
42954. Технологический процесс на изготовление детали – ступенчатый вал 252.63 KB
  Деталь изготавливается в условиях единичного производства из стали 45 ГОСТ 1050-88 твердостью НВ 280, термообработка - нормализация. Она представляет собой 5-ти ступенчатый вал длиной 360 мм. Относится к группе цилиндрических изделий. Внутри - сплошной. Основное предназначение вала – передавать крутящий момент в редукторе тихоходной ступени.
42956. КОМПЛЕКТУВАННЯ ОПТИМАЛЬНОГО СКЛАДУ МТП БРИГАДИ С ТОВ ім. КІРОВА З РОЗРОБКОЮ ОПЕРАЦІЙНО-ТЕХНІЧНОЇ КАРТИ ПОСІВУ ЦУКРОВОГО БУРЯКА 324.5 KB
  В процесі курсового проектування студенти повинні закріпити, поглибити і узагальнити знання з загально-технічних спеціальних предметів, розвити навички самостійної роботи, навчитися використовувати отримані знання при вирішенні питань виробничо-технічного характеру.
42957. Разработка устройства защиты коллиматора для твердотельного лазера на неодимовом стекле 87.78 KB
  Проверил преподаватель Москва 2012 Цель работы: разработка устройства защиты коллиматора для твердотельного лазера на неодимовом стекле. Схема лабораторной установки 3Dмодель устройства защиты коллиматора от попадания лазерных лучей при измерении.
42958. Расчет ролика резьбонакатного семизаходного 457.23 KB
  Основные требования предъявляемые к режущим инструментам определяется их служебным назначением, т.е. способностью выполнять требуемые функциональные действия, обеспечивая при этом образования соответствующих поверхностей на заготовке и необходимых экономических показателей в процессе обработки.