36209

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

Доклад

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

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

Русский

2013-09-21

126.5 KB

68 чел.

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


 

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

78800. Словникова робота на уроках української мови у 2 класі 35.5 KB
  Під час читання творів: виконуємо завдання: 1 прочитати слова 2 перекласти слова 3 зрозуміти значення слів робота з тлумачним словником. Подивились значення слів у тлумачному словнику: верболіз лози молоді гнучкі вербові пагони осока багаторічна болотна трава з довгим гострим листям.
78801. Повторение. Имя существительное и имя прилагательное 83 KB
  Приглашаем отправиться с нами в весёлую страну Грамматику, не забудьте взять с собой быстроту мысли, находчивость, смекалку, сообразительность. Наши команды уже прибыли в эту страну. Знакомьтесь, справа команда «Слово», слева - «Предложение».
78802. Світло згаслих зірок 55 KB
  Мета: Сприяти формуванню звичок здорового способу життя. Ознайомити учнів з видатними особистостями, які в розквіті сил та творчої наснаги пішли з життя завдяки страшній хворобі – СНІД. Форма проведення: Вечір-реквієм
78803. Пословицы и поговорки о соли 3.9 MB
  Практическая – расширить знания учащихся о химических веществах, хорошо известных, но малознакомых на примере кухонной соли. Совершенствовать навыки практической работы с лабораторным оборудованием.
78804. Сценарій виховного заходу «Солдатські будні» 36.5 KB
  6 грудня у календарі позначено як День Збройних сил України. І вже стало традицією вітати у цей день усіх чоловіків, хлопців. Напевне, цим жінки, дівчата хочуть зайвий раз підкреслити у чоловіках такі риси, як мужність, сміливість, щиросердя, шляхетність.
78805. Година спілкування. Знайомство з собою 91.5 KB
  Мета: познайомитись з учнями надати їм можливість поринути у власний внутрішній світ вчити бачити в оточуючих людях позитив формувати соціальну компетентність засобами ігрового спілкування. З чим ви згодні а з чим ні Чи цікаво вам побачити себе з іншого боку Що сподобалось вам сьогодні на нашій годині...
78806. Фізичні наслідки раннього статевого життя 74.5 KB
  Вступне слово вихователя. Про це говорити вголос начебто неприйнято… хоча в усіх на вустах… Перш за все тому, що багато хто з нас ніколи не чув, щоб дані аспекти статевих зв’язків коли-небудь обговорювалися. Наші батьки не бесідували з нами про це.
78807. Поспішай творити добро 71 KB
  Обладнання: записи висловів видатних людей про добро приказок та приповідок учнівські твори та вірші картки із запитаннями для підсумкової розповіді. Тренінг Риси хорошої людини; технологія Мікрофон Народний золотослів про добро вислови видатних людей про добро і доброту...
78808. Копійка податку – мільйони достатку. Задекларуй свої доходи 273.5 KB
  Ліцеїсти нашого закладу мають змогу зрозуміти переконатись і відчути вагомість податків у особистому житті та житті суспільства. Тут вони мають змогу закріпити отримані на уроках з економіки знання ознайомитися на практиці з роботою податківців пізнати особливості різних...