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

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



НазваниеВ. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования
Дата конвертации25.06.2012
Размер281.77 Kb.
ТипЗадача


В.Л. ВОЛЬФСОН, канд. техн. наук

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

В статье представлены комбинаторные алгоритмы поиска оптимального решения для задач проектирования различных, в т. ч. программных, компонентов АСУ. Рассмотренные алгоритмы применимы к задачам с целевой функцией (ЦФ) булевых и целочисленных переменных, обладающей свойством доминирования. Исследованы алгоритмы для известной ЦФ и функций ограничений (ФО). Приведены примеры использования указанных алгоритмов при проектировании различных компонентов АСУ.

There are put forward combinatorial algorithms for searching the optimal solutions in problems of design of different control systems parts including software. The mentioned algorithms can be applied to the problems having the goal functions of Boolean and integer parameters. The goal function has the property of domination. There are investigated the algorithms for the known goal function and functions of restrictions. Several examples are given to illustrate the application of these algorithms at designing different parts of control systems.
Введение

При решении задач оптимального проектирования различных компонентов АСУ, в т. ч. программных, в качестве ЦФ или ФО часто используются стоимостные, трудовые или какие-то другие затраты на проектирование, которые удовлетворяют свойству доминирования. Использование данного свойства может значительно повысить эффективность алгоритмов комбинаторных методов.

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

Однако метод ветвей и границ имеет недостатки, которые проявились в машинных экспериментах:

  • тенденция к экспоненциальному возрастанию трудоемкости вычислений при росте числа переменных;

  • большая трудность в доказательстве оптимальности полученного решения [1].

Метод динамического программирования применим в сравнительно узких рамках, например, при выполнении свойства мультипликативности ЦФ. Кроме того, большое количество операций при проведении каждого шага и объем необходимой памяти позволяют сделать вывод о нецелесообразности его применения для задач большой размерности [2].


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

Работа [3] явилась шагом в этом направлении. В ней были разработаны алгоритмы, основанные на выполнении свойства доминирования для ЦФ  алгоритм доминирующих векторов, и выполнении свойства доминирования также для ФО  дихотомический алгоритм. Интерес представляет разработка новых, более эффективных алгоритмов доминирующих векторов при известной ЦФ и ФО.

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

f(X) = (1)

при условии

< B, (2)

где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.

Не умаляя общности можно предположить, что переменные занумерованы так, что C1  C2  … Cn или C1/A1C2/A2 …Cn/An. Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2). Подобные методы в западной литературе называются “пожирающими” алгоритмами. В приведенном выше примере, с одним ограничением, данный алгоритм всегда приводит к оптимальному решению. В связи со сказанным возникает проблема  выделение класса задач, для которых алгоритм пожирающего типа приводит к оптимальному решению [1].

^
Свойство доминирования

Введем свойство доминирования () и строгого доминирования (>) над функциями X(x1,…xn) и Y(y1,…yn):

а) XY, если k: xk > yk и i = k(i = 1, n) xiyi.

б) X > Y, если xi > yi (i = 1, n);


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

Функция с булевыми переменными обладает свойством аддитивности, если

F (x1,…1,…1,…xn) = F(x1,…1,…0,… xn) + F(x1,…0,…1,… xn).

Так как F(x1,…0,…1,… xn)  0 , то F (x1,…1,…1,… xn)  F(x1,…1,…0,… xn).

Следовательно функция с булевыми переменными обладает свойством доминирования.

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

Допустим количество вариантов проектирования ^ N, тогда можно выбрать такое n, что 2n > N. Таким образом, любое количество вариантов проектирования N можно описать n булевыми переменными. Следовательно, доказанное выше свойство, имеет более общий характер.

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

Производится ввод записи данных, состоящей из n полей. При вводе каждого поля возможно появление ошибки с вероятностью i (i = 1, n). При контроле поля ошибка обнаруживается с вероятностью 1; если поле не контролируется, то вероятность отсутствия ошибки в i-ом поле  (1i). Таким образом, достоверность ввода записи (отсутствия ошибки) определяется по формуле:

Qз =

где xi = 0,1.

Функция Qз не обладает свойством аддитивности, но обладает свойством доминирования. Проверим это. Для доказательства рассмотрим значение Qз в точке (x1,…1,…1,… xn):

Qз(x1,…1,…1,… xn) =

где ik; il (xk = 1, xl = 1).

Теперь рассмотрим значение Qз в точке (x1,…1,…0,… xn):

Qз(x1,…1,…0,… xn) = (1l) = (1l) Qз(x1,…1,…1,… xn),

где i  k; il.

Следовательно, Qз(x1,…1,…1,… xn) > Qз(x1,…1,…0,… xn) и функция Qз обладает свойством доминирования.

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

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

Таким образом, получим упорядоченные последовательности:

для 1-го поля



для 2-го поля



для n-го поля



Составим следующие вектора



Покажем, что для функции достоверности ввода записи выполняется свойство доминирования, т.е. Q(Xk+1)  Q(Xk).

Так как pk+1ipki , то 1 – i /1  i pk+1i  1 – i /1  i pki . Следовательно,


^
Алгоритмы доминирующих векторов при известных ЦФ и ФО
Общий случай

На рассмотренных свойствах доминирования основываются алгоритмы доминирующих векторов. Рассмотрим случай, когда ЦФ и ФО либо вычисляются, либо заранее известны.

Сначала проводится построение переборного дерева, вершинами которого являются варианты векторов с дискретными координатами. Корнем дерева является доминирующий вектор, при котором значение ЦФ максимально или минимально. Далее переборное дерево строится таким образом, что векторы вершин более высокого уровня доминируют над группой вершин более низких уровней. Рядом стоящие вектора в поддереве отличаются по одной координате на минимальную величину. Листьями поддеревьев являются вектора с хотя бы одной нулевой координатой.

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

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

Пример 1.

Пусть требуется максимизировать достоверность ввода данных ^ Q при условии ограничений трудовых – Т0 и стоимостных С0 затрат. Предположим, что трудовые и стоимостные затраты на проектирование контроля i-го поля соответственно Тi, Сi. Тогда задачу оптимизации можно записать в виде:

найти максимум ЦФ при условиях

где Xi = 0,1.

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

Предположим для определенности, что число полей в записи n = 3, вероятности появления ошибок при вводе полей соответственно: 1 = 0,05; 2 = 0,1; 3 = 0,15. Значения трудоемкости и стоимости проектирования программного контроля полей соответственно:

T1 = 2; T2 = 4;T3 = 7; C1 =1; C2= 5; C3 = 3. Ограничения: Т0 = 8; С0 = 6.

Построим переборное дерево вариантов:

(1,1,1)

(0,1,1) (1,0,1) (1,1,0)

(0,0,1) (1,0,0) (0,1,0)

(0,0,0)

Начинаем движение по первому поддереву. Вычисляем значение в корне Т(1,1,1) = 13 > Т0 = 8. Условия не выполняются, поэтому переходим к следующей точке и вычисляем Т(0,1,1) = 11 > Т0. Условие опять не выполняется, переходим к следующей точке поддерева: Т(0,0,1) = 7 < Т0 = 8; С(0,0,1) = 3 < С0 = 6. Оба условия выполнены, поэтому определяем значение ЦФ в данной точке Q(0,0,1) = (1 – 1) (1 – 2) = 0,95  0,9 = 0,855. Переходим к следующему поддереву Т(1,0,1) = 9 > Т0 = 8. Условия не выполняются. Переходим к следующей точке Т(1,0,0) = 2 < Т0 = 8; С(1,0,0) = 1 < С0 = 6. Определяем Q(1,0,0) = (1 – 2) (1 – 3) = 0,9  0,85 = 0,765. Переходим к последнему поддереву Т(1,1,0) = 6 < Т0 = 8; С(1,1,0) = 6 = С0. Условия выполняются. Определим Q(1,1,0) = 1 – 3 = 0,85. Максимальное значение ЦФ достигается в точке Q(0,0,1) = 0,855, которое является оптимальным. Число вариантов неполного перебора N = 6. При полном числе вариантов перебора – 8.

Пример 2.

Теперь рассмотрим случай с дискретными переменными.

Предположим у нас имеется два варианта контроля первого поля с вероятностями обнаружения ошибок соответственно: p11 = 0,3; p12 = 0,1. Имеется один вариант контроля второго поля с вероятностью обнаружения ошибки p21 = 0,2 и три варианта контроля третьего поля соответственно с вероятностями обнаружения ошибок p31 = 0,8; p32 = 0,6; p33 = 0,4. Пусть затраты на контроль информации составляют соответственно: C11 = 1; C12 = 2; C21 = 5; C31 = 2; C32 = 3; C33 = 4; T11 = 2; T12 = 4; T21 = 4; T31 = 6; T32 = 7; T33 = 8. Переборное дерево для алгоритма доминирующих векторов в этом случае выглядит следующим образом:


(0,3;0,2;0,8)

(0,1;0,2;0,8) (0,3;0;0,8) (0,3;0,2;0,6)

(0,1;0,2;0,6) (0;0,2;0,8) ( 0,1;0;0,8) (0,3;0;0,6) (0,3;0,2;0,4)

(0,1;0,2;0,4) (0;0;0,8) (0;0,2;0,6) (0,1;0;0,6) (0,3;0;0,4) (0,3;0,2;0)

(0,1;0,2;0) (0;0;0) (0;0,2;0,4) (0,1;0;0,4) (0,3;0;0)

(0;0,2;0) (0,1;0;0)


Вычисляем значение в корне Т(p11,p21,p31) = T11 + T21 +T31 =12> Т0. Условие не выполняется, переходим к следующей точке поддерева. Вычисляем Т(p12,p21,p31) = T12 + T21 +T31 = 14 > Т0. Переходим к точке Т(0,p21,p31) = 0+ T21 +T31 =10> Т0. Переходим к точке Т(0,0,p31) =6 < Т0, проверим С(0,0, p31) =2 < С0. Определим значение ЦФ Q(0,0, p31) = (1 – 1) (1 – 2)(1 – 3)/(1 – 3p31) = 0,826. Переходим к следующему поддереву Т(p11,0,p31) = T11 + 0 +T31 = 8 = Т0, С(p11,0, p31) =3 < С0. Определим значение ЦФ Q(p11,0, p31) = (1 – 1) (1 – 2)(1 – 3)/ (1 – 1p11) (1 – 3p31)= 0,747. Переходим к следующему поддереву Т(p12, p21, p32) =15> Т0. Переходим к следующей точке поддерева Т(p12, p21, p33)=12 > Т0. Переходим к следующей точке поддерева Т(p12, p21, 0) = 8= Т0. Проверим С(p12, p21, 0) =7 > С0. Переходим к следующему поддереву Т(p12, 0, p31) =10 > Т0. Переходим к следующей точке поддерева Т(p12, 0, p32)= 11> Т0. Переходим к следующей точке поддерева Т(p12, 0, p33)= 12> Т0. Переходим к следующей точке поддерева Т(p12, 0, 0) = 4 < Т0, проверим С(p12, 0, 0) = 2 < С0.

Определим значение ЦФ Q(p12, 0, 0) = (1 – 1) (1 – 2)(1 – 3)/(1 – p12) = 0,73. Переходим к следующему поддереву Т(0, p21, p31) = 11> Т0. Переходим к следующей точке поддерева Т(0, p21, p33) = 12 > Т0. Переходим к следующей точке поддерева Т(0, p21, 0) = 8 = Т0. Проверим С(0, p21, 0) = 5 < С0. Определим значение ЦФ Q(0, p21, 0) =(1 – 1) (1 – 2)(1 – 3)/(1 – 2p21) = 0,742.

Переходим к следующему поддереву Т(p11, p21, p32) = T11 + T21 + T32 = 13> Т0. Переходим к следующей точке поддерева Т(p11, p21, p33)= T11 + T21 + T33 = 14> Т0. Переходим к следующей точке поддерева Т(p11, p21, 0) = T11 + T21 + 0 = 6 < Т0, проверим С(p11, p21, 0) = 6 = С0. Определим значение ЦФ Q(p11, p21, 0) = (1 – 1) (1 – 2)(1 – 3)/(1 – p11)(1 – 2p21) = 0,753. Это наибольшее значение, поэтому данная точка является оптимальной.

Всего переборное дерево данного примера содержало 24 варианта. Чтобы найти оптимальный вариант нами было проанализировано 18. Количество вариантов неполного перебора в данном примере было довольно большим. Это связано с “жесткими” ограничениями (Т0 = 8; С0 = 6). В этом случае область допустимых значений мала. Если ограничения менее “жесткие”, то область допустимых значений расширяется и общий алгоритм в этом случае становится более эффективным, так как, двигаясь вниз по переборному дереву, мы быстрее попадаем в область допустимых значений. Покажем это на том же примере, но с менее “жесткими” ограничениями (Т0 = 12; С0 = 8). Переборное дерево тоже.

Начинаем движение по первому поддереву. Вычисляем Т(1,1,1) = 13 > Т0. Переходим к точке Т(0,1,1) = 11 < Т0 и С(0,1,1) = 8 = С0. Вычисляем значение Q = 1 – 1 =0,95. Переходим к следующему поддереву Т(1,0,1) =9 < Т0. Определяем С(1,0,1) = 4 < С0. Вычисляем значение Q = 1 – 2 = 0,9. Переходим к следующему поддереву Т(1,1,0) = 6 < Т0. Вычисляем значение Q = 1 – 3 = 0,85. Следовательно, оптимальным является значение Q(0,1,1) =0,95. В данном случае потребовался перебор всего четырех вариантов.

В случае более “жестких” ограничений, когда область допустимых значений мала и указанный алгоритм не эффективен, рекомендуется применение другого алгоритма. В этом случае, после построения переборного дерева как в первом алгоритме, движение по переборному дереву начинается от листьев к корню. Сначала двигаемся по крайнему слева поддереву до тех пор, пока ограничения не перестают выполняться. Тогда возвращаемся в предыдущего точку, где ограничения выполняются, и вычисляем значение ЦФ. Затем переходим на следующее поддерево правее, выполняем аналогичный алгоритм и так до тех пор, пока все деревья не будут исчерпаны. После чего выбирается вариант с минимальным значением ЦФ.

Покажем это на примере 1 со следующими ограничениями: Т0 = 8; С0 = 6. Определим Т(0,0,0) = 0 < Т0; C(0,0,0) = 0 < С0. Переходим к следующей точке левого поддерева Т(0,0,1) = 7 < Т0; C(0,0,1) = 3 < С0. Переходим к следующей точке левого поддерева Т(0,1,1) = 11 > Т0, так как условие не выполняется, то возвращаемся в предыдущую точку Q(0,0,1) = (1 – 1) (1 – 2) = 0,855. Переходим к следующему поддереву Т(0,1,0) = 9 > Т0 (условия не выполняются). Возвращаемся к предыдущей точке Q(1,0,0) = (1 – 2) (1 – 3) = 0,765. Переходим на следующее поддерево Т(0,1,0) = 4 < Т0; C(0,1,0) = 5 < С0. Переходим к следующей точке Т(1,1,1) =13 > Т0. Возвращаемся к предыдущей точке Q(1,1,0) = (1 – 3) = 0,85. Оптимальное значение достигается в точке Q(0,0,1) = 0,855.

В рассмотренных вариантах алгоритма доминирующих векторов (общий случай) свойство доминирования выполняется только для ЦФ, поэтому количество вариантов перебора может быть значительным. Если для ФО также выполняется свойство доминирования, то количество вариантов перебора может быть сокращено.

^
Дихотомический алгоритм

Рассмотрим следующую задачу с дискретными переменными. Пусть требуется максимизировать(минимизировать) ЦФ f(x1,...xn) при условиях g1(x1,...xn)  0,…gN(x1,...xn)  0. При этом функции f(x1,...xn), g1(x1,...xn),…gN(x1,...xn) обладают свойством доминирования.

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

В этом случае последовательность вершин каждого поддерева разбивается примерно пополам, вычисляются функции условий g1(x1,...xn),…gN(x1,...xn) для данной точки и проверяется выполнение условий. Если все условия выполняются, то отбрасывается нижняя часть поддерева (ближе к листьям), так как по свойству доминирования значение ЦФ f(x1,...xN) там меньше, чем в верхней части. Если хотя бы одно условие не выполняется, то отбрасывается верхняя часть поддерева, так как по свойству доминирования для ФО в верхней части поддерева данные условия ограничений также будут нарушены. Затем аналогично “разбивается” оставшаяся часть поддерева и.т.д. , пока в поддереве не останется один вектор. Сходная процедура выполняется с другими поддеревьями. Только у выбранных таким образом точек (подозрительных на оптимальную) вычисляется значение ЦФ и находится точка с ее наибольшим (наименьшим) значением.

Дихотомический алгоритм сокращает количество вычислений ФО с N до log2 N и, кроме того, значительно уменьшает объем вычислений ЦФ.

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

Разделим первую ветвь переборного дерева примерно пополам и определим функции условий Т(0,0,1) = 7 < Т0 и С(0,0,1) =3 < С0. Условия выполняются, поэтому отбрасываем нижнюю часть поддерева, так как значение ЦФ Q меньше. Разобьем оставшуюся часть поддерева пополам и проверим условие Т(0,0,1) > Т0. Так как это условие не выполняется, то отбрасываем оставшуюся верхнюю часть поддерева, где условия также не выполняются. В первом поддереве больше не осталось векторов, поэтому определяем ЦФ Q в выбранной точке поддерева, где выполнены условия: Q(0,0,1) = 0,855. Переходим к следующему поддереву . Проверим условие Т(1,0,1) = 9 > Т0. Так как оно не выполняется, то отбрасываем верхнюю часть поддерева, где условия такжее не выполняются. В последнем поддереве осталась одна точка. Проверим в ней выполнение условий Т(1,0,0) =2< Т0 и С(1,0,0) =1 < С0. Они выполняются. Так как отбрасывать в поддереве больше нечего, то определим Q(1,0,0) =0,765. Переходим к последнему поддереву. Разделим его пополам и проверим условия Т(1,1,0) =6< Т0 и С(1,1,0) =6 = С0. Так как они выполняются, то отбрасывается нижняя часть поддерева, где значение ЦФ Q меньше, чем в точке (1,1,0). Проверим условие в последней точке Т(1,1,1) = 13 > Т0. Оно не выполняется, поэтому определим значение Q(1,1,0) =0,85. Максимальное значение Q(0,0,1) =0,855. В этом случае N = 6. При увеличении числа переборных вариантов дихотомический алгоритм станет более эффективным, так как число вариантов перебора будет стремиться к log2M, где M – число вариантов полного перебора.

В примере 2 были рассмотрены функции условий с дискретными переменными:

которые хотя и являются аддитивными, но не удовлетворяют условиям доминирования. Если бы они были с булевыми переменными, то на основании доказанной теоремы они обладали бы свойством доминирования. Изменим условия, чтобы указанные функции удовлетворяли свойству доминирования: C11 =2; C12 =1; C21 =5; C31 =4; C32 =3; C33 =2; Т11 =4; Т12 =2; Т21 =8; Т31 =8; Т32 =7; Т33 =6; Т0 =8; C0 =6.

В этом случае в примере 2 можно использовать дихотомический алгоритм. Начнем с левого поддерева. Т(p12, p21, p32) = 9 > Т0. Следовательно, отбрасываем верхнюю часть поддерева, так как там условие тем более не выполняется. Определим Т(p12, p21, p33) = 8= Т0; C(p12, p21, p33)= 8 > C0. Поэтому отбрасываем верхнюю часть оставшегося поддерева и остается одна точка Т(p11, p21, 0) = 6 < Т0; C(p11, p21, 0) = 6 = C0. Данная точка удолетворяет условиям, поэтому определим Q(p11, p21, 0)= (1 – 1) (1 – 2)(1 – 3)/(1 –  p11)(1 – 2p21) = 0,745. Переходим на следующее поддерево правее. Определим Т(0, p21, p31)= 16 > Т0. Отбросим верхнюю часть поддерева. Определим Т(0, 0, p31)= 8= Т0; C(0, 0, p31) = 4 < C0. Находим Q(0, 0, p31)= (1 – 1) (1 – 2)(1 – 3)/(1 – 3p31)= 0,826. Нижнюю часть поддерева отбрасываем, так как там значение Q меньше. Переходим на поддерево правее. Определим Т(p12, 0, p32)= 9 > Т0. Отбрасываем верхнюю часть поддерева, так как условия тем более не выполняется. Определим Т(p12, 0, p33) = 8 = Т0; C(p12, 0, p33)= 3 < C0; Q(p12, 0, p33) = (1 – 1) (1 – 2)(1 – 3)/(1 – p12)(1 – 3 p33) = 0,774. Отбрасываем оставшуюся часть поддерева, так как значение Q там меньше. Переходим на последующее поддерево. Определим Т(0, p21, p33)= 14 > Т0. Отбросим верхнюю часть поддерева, так как там условия тем более не выполняются. Определим значение в последней оставшейся точке Т(0, p21, 0) = 8 = Т0; С(0, p21,0) = 5 < C0; Q(p12, 0, p33) = (1 – 1) (1 – 2)(1 – 3)/(1 – 2 p21) = 0,742. Перейдем на следующее поддерево правее. Определим Т(p11, 0, p33)= 10 > Т0. Отбрасываем верхнюю часть поддерева. Проверим Т(p11, 0, p32)= 11> Т0. Отбросим верхнюю часть. Проверим последнее оставшееся значение Т(p11, 0,0) = 4 > Т0; C(p11, 0, 0) = 2 < C0; Q(p11, 0, 0) = (1 – 1) (1 – 2)(1 – 3)/(1 –  p11) = 0,764. Рассмотрим последнее поддерево Т(p11, p21, p33) = 18 > Т0. Отбросим верхнее поддерево. Проверим последнюю оставшуюся точку Т(p11, p21, 0) = 12 > Т0. Таким образом оптимальное значение достигается в точке Q(0, 0, p11)= 0,826.

Обратим внимание, что число вариантов перебора в данном примере – 14 (из 24), т. е. значительно меньше, чем в примере 2 с общим алгоритмом.

Алгоритмы пожирающего типа, как частный случай алгоритмов доминирующих векторов

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

Пусть ЦФ обладает свойством доминирования f(x1, x2,…,xn) в частном случае является аддитивной функцией .

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

Например, производится улучшение качества изделия. Предположим, что после выбора какого-то варианта улучшения изделия мы его реализуем и приступаем к выбору следующего варианта улучшения. После этого мы снова его реализуем до тех пор, пока качество изделия нас станет удовлетворять. Если варианты выбора упорядочены в последовательности осуществления выбора, то областью допустимых значений данной задачи является крайнее слева поддерево. В этом случае реализации первого улучшения соответствует точка (0,…,1) , реализацией двух улучшений является точка (0,..1,1) и т.д. Таким образом, областью допустимых значений для указанного случая является крайнее слева поддерево, поэтому оптимальное значение достигается в одной из его точек. Однако это тривиальный случай.

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

Предположим, варианты упорядочены таким образом, что выполняется условие:

f(0,…0,1)  f(0,…1,0) …  f(1,…0,0).

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

Но с другой стороны возможен такой случай, что крайнее слева поддерево не входит в область допустимых значений и поэтому оптимальное решение достигается в другой точке. Чтобы этого не было, требуется выполнение дополнительных условий на ФО:

g1(0,. . ,1)  g1(0,. . 1,0)  . . . g1(1,. . 0,0);

. . . . . . . . . . . . . . .

gn(0,. . ,1)  gn(0,. . 1,0)  . . . gn(1,. . 0,0).

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

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

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

f(0,. . 0,1)  f(0,. . 1,0)  . . . f(1,. . 0,0);

g1(0,. . ,1)  g1(0,. . 1,0)  . . . g1(1,. . 0,0);

. . . . . . . . . . . . . . . . . . .

gn(0,. . ,1)  gn(0,. . 1,0)  . . . gn(1,. . 0,0).

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

Q(0,0,1) = 0,855 > Q(0,1,0) = 0,808 > Q(1,0,0) =0,765;

T(0,0,1) = 2 <T(0,1,0) = 4 <T(0,0,1) = 7;

C(0,0,1) = 1 < C(0,1,0) = 5 < C(1,0,0) = 7.

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

Разобьем крайнюю слева ветвь переборного дерева примерно пополам и определим T(0,0,1) =2 < T0 и С(0,0,1) =1 < C0. Условия выполняются, поэтому отбрасываем нижнюю часть поддерева, так как там значения ЦФ Q меньше. Разбиваем оставшуюся часть поддерева пополам и вычисляем условия T(0,1,1) = 6 < T0 . Одно из условий не выполняется, поэтому отбрасываем оставшуюся верхнюю часть поддерева, так как там условия тем более не выполняются. В крайнем слева поддереве больше не осталось векторов, поэтому найденная точка (0,0,1) является оптимальной и значение ЦФ в ней Q = 0,855.

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

При полном переборе ^ M = 8 , log2 8 = 3 > 2.Следовательно, число вариантов перебора сократилось более чем с M до log2M.

Указанный алгоритм пожирающего типа можно обобщить на ЦФ и ФО с дискретными переменными.

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

Пусть ЦФ f(x1,. . . xn) c дискретными переменными обладает свойством доминирования. Предположим, что варианты упорядочены таким образом, что выполняются условия:

f(0,. . . x11)  f(0,. . . x21,0)  . . .  f(xN1,. . . 0,0) .

С другой стороны выполняются также следующие условия на ФО:

g1(0,. . . x11)  g1(0,. . . x21,0)  . . .  g1(xN1,. . . 0,0);

. . .

gn(0,. . . x11)  gn(0,. . . x21,0)  . . .  gn(xN1,. . . 0,0).

Построим переборное дерево доминирующих векторов.

(хn1, . . ., x21,x11)

(хn1, . . ., x21,x12) (хn1, . . ., x22,x11) . . . (хn2, . . ., x21,x11)

. . . . . . . .

(хn1, . . ., x21,x1k1) (хn1, . . ., x2k2,x11) (хnk2, . . ., x21,x11)

(хn1, . . ., x21,0) (хn1, . . ., 0,x11) (0, . . ., x21,x11)

. . .

(0, . . ., 0,0)

Благодаря указанным предположениям для ЦФ выполняются условия:

f(хn1, . . ., x21,x12)  f(хn1, . . ., x22,x11)  …  f(хn2, . . ., x21,x11);

. . .

f(хn1, . . ., x21,x1k1)  f(хn1, . . ., x2k2,x11)  …  f(хnk2, . . ., x21,x11);

f(хn1, . . ., x21,0)  f(хn1, . . ., 0,x11)  …  f(0, . . ., x21,x11).

Таким образом, значения ЦФ в крайнем слева поддереве превосходят значения во всех поддеревьях справа. На основании выполнения условий на ФО точки крайнего слева поддерева входят в область допустимых значений, поэтому в этом случае достаточно использовать алгоритм доминирующих векторов только для крайнего слева поддерева.

Рассмотрим пример 2. Проверим выполнение условий:

Q(0,0,p31) = 0,826 > Q(0, p21,0) =0,742 > Q(p11, 0,0) =0,738;

T(0,0,p31) = 6 > T(0, p21,0) = 4 > T(p11, 0,0) =2;

C(0,0,p31) = 2 < C(0, p21,0) = 5 > C(p11, 0,0) =1.

Таким образом, условия на ФО не выполняются, и мы не можем применить алгоритм пожирающего типа.

Для его применения изменим условия задачи:

T31 = 2; T32 = 3; T33 = 4; T21 = 3; T11 = 5; T12 = 6; T0 = 8;

C31 = 1; C32 = 2; C33 = 3; C21 = 2; C11 = 4; C12 = 5; С0= 6.

Проверим выполнение условий:

T(0,0,p31) = 2 < T(0, p21,0) = 3 < T(p11, 0,0) = 5;

C(0,0,p31) = 1 < C(0, p21,0) = 2 > C(p11, 0,0) = 4.

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

Определим T(p11, p21, p31) = T11 + T21 + T31 = 5 + 3 + 2 = 10 > T0.

Условие не выполняется, поэтому переходим к следующей точке поддерева T(p11, p21, p33) = T11 + T21 + T33 =5 + 3 + 4 = 12 > T0. Переходим к следующей точке поддерева T(p11, p21,0) = T11 + T21 = 5 + 3 = 8 = T0, С(p11, p21,0) = С11 + С21 = 4+ 2 = 6 = С0. Определим значение в оптимальной точке Q(p11, p21,0) = 0,753. Для нахождения его нам потребовалось проверить всего 4 варианта вместо 18, как при решении примера 2 в общем случае.

Радиальный алгоритм доминирующих векторов Вольфсона
^

Рассмотрим случай ЦФ с булевыми переменными. Предположим, что варианты упорядочены таким образом, что выполняются условия:


f (0,. . . 1)  f(0,. . . 1,0)  . . .  f(1,. . . 0).

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

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

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

(0, . . . 0)




(0, . . .1) (0, . . .1,0) (0,. . . 1,0,0) . . . (1,. . .0)




(0,. . .1,1) (0,. . 1,1,0) (0,. .1,1,0,0)




. . . . . . (1,. . . 1,0,0)




(1,. .1,1,1,0)


(1,. . . 1,1)


Вариант 1 соответствует следующим соотношениям между ФО:

g1 (0,. . . 1)  g1(0,. . .,1,0)  . . . g1(1,. . .,0);

. . .

gn (0,. . . 1)  gn(0,. . .,1,0)  . . .  gn(1,. . .,0).

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

Вариант 2 соответствует следующим соотношениям между ФО:

g1 (0,. . . 1) > g1(0,. . .,1,0) > . . . > g1(1,. . .,0);

. . .

gn (0,. . . 1) > gn(0,. . .,1,0) > . . . > gn(1,. . .,0).

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

Чаше всего встречается вариант 3 (волна), которому соответствуют следующие соотношения между ФО (меняются знаки неравенств):

g1 (0,. . . 1)  g1(0,. . .,1,0)  . . .  g1(1,. . .,0);

. . .

gn (0,. . . 1)  gn(0,. . .,1,0)  . . .  gn(1,. . .,0).

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

Других вариантов расположения области допустимых значений быть не может. Дискретной области допустимых значений быть не может в силу условий построения последовательности доминирующих векторов. Так при движении вниз по поддеревьям возрастают значения ФО, и как только в какой-то точке хотя бы одно условие ограничений не выполняется, то оно тем более не будет выполняться в точках ниже.

Следовательно, при выполнении условий f(0,. . . 1)  f(0,. . . 1,0)  . . .  f(1,. . . 0) значения ЦФ в точках, равноотстоящих от корня дерева, возрастают от крайнего справа поддерева до крайнего слева поддерева, где оно достигает максимального значения.

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

Движение начинается от корня к листьям крайнего слева поддерева до тех пор, пока ограничения не нарушаются. После этого переходим на поддерево правее, но начинаем не с его корня, как в общем алгоритме доминирующих векторов, а перемещаемся по радиусу и берем следующую точку и т.д., пока условия ограничений нарушаются. Если ограничения выполняются, то берем точку ниже с большим числом “1”, но в которую не включается точка с нарушениями ограничений и т.д., пока точек, удовлетворяющих данным условиям, больше не останется.

Рассмотрим пример применения данного алгоритма для точек с четырьмя координатами. Упорядочим варианты таким образом, чтобы выполнялись следующие условия для ЦФ:

f(0,0,0,1)  f(0,0,1,0)  f(0,1,0,0)  f(1,0,0,0).

Теперь можно использовать радиальный алгоритм. Построим переборное дерево для данного случая. Предположим, что в точке (0,0,0,1) условия выполняются, тогда проверим выполнение условий в точке (0,0,1,1). Если условия не выполняются, то проверяется выполнение условий в точке (0,1,0,1). В случае невыполнения условий в данной точке, проверяется выполнение условий в точке (1,0,0,1). Если условия выполнены, то проверяется выполнение условий в точке (1,1,1,0), так как в точках (1,0,1,1) и (1,1,0,1) условия также не выполняются, потому что они были не выполнены в точках (0,0,1,1) и (0,1,0,1). Независимо от того выполняются условия в данной точке перебор вариантов заканчивается. Таким образом, мы проверили четыре точки.

Граф переборного дерева имеет вид:


(0,0,0,0)




да


(0,0,0,1) нет(0,0,1,0)нет(0,1,0,0)нет (1,0,0,0)




да


(0,0,1,1) нет(0,1,0,1)нет (1,0,0,1)нет(0,1,1,0)нет (1,0,1,0)нет(1,1,0,0)




да да


(0,1,1,1)нет (1,0,1,1)нет (1,1,0,1) нет (1,1,1,0)




да


(1,1,1,1)

Попробуем решить первую задачу с помощью радиального алгоритма. Пусть n = 3; 1 = 0,05; 2 = 0,05; 3 = 0,05; T1 = 14; T2 = 2; T3 = 7; C1 = 7; C2 = 1; C3 = 5; C0 = 6.

Проверим выполнение условий на ЦФ:

Q(0,0,1) = (1  1)(1  2) = 0,855  Q(0,1,0) = (1  1)(1  3) = 0,808  Q(1,0,0) = (1  2)(1  3) = 0,765.

Так как ЦФ обладает свойством доминирования, то можно построить переборную последовательность:


(0,0,0)


(0,0,1) (0,1,0) (1,0,0)


(0,1,1) (1,0,1) (1,1,0)


(1,1,1)


Двигаемся по левому поддереву Т(0,0,1) = Т1= 4 < T0, C(0,0,1) = 7 > C0. Переходим на поддерево правее в точку Т(0,1,0) = Т2 = 2 < T0; C(0,1,0) = C2 =1 < C0. Переходим на следующую точку Т(1,1,0) = Т3 + Т2 = 9 > Т0. Следовательно, оптимальным является значение Q(0,1,0) = 0,8075.
Выводы

  1. Рассмотрены алгоритмы оптимизации для комбинаторных задач с ЦФ, обладающей свойством доминирования.

  2. Исследованы алгоритмы с известной ЦФ и ФО. Рассмотрены общий случай алгоритма доминирующих векторов и дихотомический алгоритмы. Разработан новый радиальный алгоритм, который значительно сокращает количество вариантов перебора. Получены условия, при которых алгоритм пожирающего типа приводит к оптимальному решению.

Контактный телефон (095) 921-48-29.

E-mail: Volfson.Viktor@gci.cbr.ru

Список литературы


  1. Современное состояние теории исслелования операций / Под ред. Н.И. М о и с е е в а. М.:Наука, 1979.

  2. Вентцель Е.С. Исследование операций: задачи, принцип, методология. М.: Наука, 1980.

  3. Вольфсон В.Л. Математическое и программное обеспечение задачи анализа качества обработки данных в АСУ / Автореф. дисс. на соискание уч. степени канд. техн. наук. М.: МЛТИ, 1987.





Похожие:

В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconКанд техн наук. В. Л. Вольфсон
...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconВ. Л. Вольфсон, канд техн наук Алгоритм оптимального проектирования асу в задачах с неизвестной целевой функцией, обладающей свойством доминирования
Задач проектирования различных, в т ч программных, компонентов асу с целевой функцией (ЦФ), обладающей свойством доминирования. Исследованы...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconCНиП 01. 09-91
Усср (канд техн наук А. А. Петраков; канд техн наук Ю. Л. Бучинский), Киевзнииэп госкомархитектуры (канд техн наук В. Б. Шевелев),...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconСНиП 02. 03-84
Л. Гугель), Южгипрошахтом Минуглепрома СССР (Е. М. Дуров, А. М. Парецкий), вними минуглепрома СССР (кандидаты техн наук И. И. Добкин,...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconПроектирование систем оповещения и управления эвакуацией людей при пожарах в общественных зданиях пособие (к сниП 08. 02-89)
Пособие разработано авторским коллективом в составе: канд техн наук Мешалкин Е. А., канд техн наук Никонов С. А., Тадеуш С. В. (Вниипо...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconСтроительные нормы и правила защита горных выработок от подземных и поверхностных вод сниП 06. 14-85 издание официальное
Шахтспецстрой и треста Союзшахтоосушение Минмонтажспецстроя СССР (инженеры Я. И. Фэйгин, Э. В. Олизаревич, Л. Н. Московская). Всегингео...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconВедомственные строительные нормы проектирование среды жизнедеятельности
Н. Н. Щетинина, М. Н. Тюричева), цнииэп курортно туристских зданий и комплексов (кандидаты архитектуры Н. О. Шенгелия, Е. М. Либерман),...
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconА. О. Простейшая оценка риска инвестиционного проекта Простейшая оценка риска инвестиционного проекта Недосекин Алексей Олегович, консультант компании Сименс Бизнес Сервисез, канд техн наук Рассмотрим процесс бизнес-план
Недосекин Алексей Олегович, консультант компании Сименс Бизнес Сервисез, канд техн наук
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconВероятностные распределения с нечеткими параметрами
Недосекин Алексей Олегович, ст консультант компании Сименс Бизнес Сервисез, канд техн наук
В. Л. Вольфсон, канд техн наук Алгоритмы оптимального проектирования асу в задачах с известной целевой функцией, обладающей свойством доминирования iconОт вычислений со словами – к вычислениям с образцами
Недосекин Алексей Олегович, ст консультант компании Сименс Бизнес Сервисез, канд техн наук
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов