36209

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

Доклад

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

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

Русский

2013-09-21

126.5 KB

70 чел.

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


 

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

2539. Распределение электронной плотности атома водорода 46.53 KB
  Цель работы: рассчитать распределение радиальной электронной плотности вероятности в различных состояниях для атома водорода.
2540. Нелинейные и дискретные системы автоматического управления 2.68 MB
  Система автоматического управления (САУ) является нелинейной, если хотя бы один ее конструктивный элемент (или одно ее алгоритмическое звено) описывается нелинейным уравнением. Практически все реальные САУ содержат один или несколько нелинейных элементов (или так называемых нелинейностей).
2541. Проектирование магистральных и внутризоновых ВОЛП 440.84 KB
  Необходимо спроектировать трассу ВОК на участке Смоленск – Москва. Определить необходимое количество каналов и определить параметры оптического кабеля. При выборе оптимального варианта трассы прокладки волоконно-оптического кабеля (ВОК) исходят из того, что линейные сооружения являются наиболее дорогой и сложной частью сети связи.
2542. Материаловедение и технология конструкционных материалов для строительства 1.82 MB
  Строительное материаловедение является наукой о строительных материалах и изделиях. Без достаточных знаний о многочисленных разновидностях строительных материалов, способах их производства и качественных показателях, методах их правильного хранения и использования невозможно проектировать и строить здания и сооружения.
2543. Культура користування мобільним зв’язком 1.58 MB
  Мета уроку: перевірити рівень мобільної культури серед молоді, обговорити зі школярами правила дотримання мобільного етикету як в школах, так і в громадських місцях, сформувати культуру спілкування та застерегти учнів від помилок у користуванні мобільним зв'язком.
2544. Умеешь ли ты дружить 50 KB
  Цель: Раскрыть сущность понятия дружба, показать какими качествами должен обладать настоящий друг, какую роль играют друзья в нашей жизни; развить стремление дружить с окружающими. Формирование у учащихся нравственных качеств, присущих дружеским и товарищеским взаимоотношениям.
2545. Проект комплексной механизации животноводческой фермы 496.5 KB
  Количество скотомест для предприятий крупного рогатого скота по производству молока рассчитывается с учетом коэффициентов, приведенных в таблице № 1 в зависимости от количества коров на ферме.
2546. Проект внеклассного мероприятия, посвящённого 200-летию Отечественной войны 1812 года 705.27 KB
  У школьников велика потребность в игре, она необходима им для развития воображения, инициативы, творчества. Кроме этого игровая форма способствует развитию познавательного интереса, интеллектуальных способностей, позволяет лучше усвоить предлагаемый материал, расширить и углубить знания по той или иной теме.
2547. Инновационный маркетинг 417.52 KB
  Инновационный маркетинг — понятие, возникшее относительно недавно. Предпосылкой появления данной экономической категории явилось общее возрастание роли инноваций в деятельности компаний. В силу ограниченности научно-технических ресурсов, являющихся базой для появления первичных инноваций.