Канд техн наук. В. Л. Вольфсон icon

Канд техн наук. В. Л. Вольфсон



НазваниеКанд техн наук. В. Л. Вольфсон
Дата конвертации25.06.2012
Размер105.05 Kb.
ТипЗадача


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

Канд.техн.наук. В.Л. Вольфсон


1. Введение

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

В работах [1, 2] рассмотрены алгоритмы поиска оптимального решения соответственно для известной и неизвестной целевой функции, обладающей свойством доминирования.

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

X > Y, если при выполнении условия xk>yk : X(x1,…xn) > Y(y1,…yn).

Таким образом, свойство доминирования аналогично свойству возрастания функции непрерывных переменных.

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

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

Qз = П (1-i )/( 1-i xi) , где

xi = 0,1.

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

Qз(x1,…1,…1,… xn) = П (1-i )/( 1-i xi)

i =k, i = l

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

Qз(x1,…1,…0,… xn) = (1-l) П (1-i )/( 1-i xi) = (1-l) Qз(x1,…1,…1,… xn).

i =k, i = l

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

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

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

Пусть требуется максимизировать (минимизировать) ЦФ f(x1,...xn) (критерий оптимальности проектирования), при условиях g1(x1,...xn)<0, . . .gN(x1,...xn)<0 (затраты на проектирование не превышали заданные). При этом ЦФ обладает свойством доминирования.

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


  1. Проблема построения переборного дерева для алгоритмов доминирующих векторов.

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

Пример переборного дерева с булевыми переменными приведен на рис. 1


(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

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

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

Алгоритм заключается в следующем. Сначала строится крайнее слева поддерево. Его построение начинается с изменения первой координаты от наибольшего до нулевого значения, затем изменяется аналогично вторая координата, третья, четвертая пока значения всех координат станут нулевыми. Затем проводится обратный ход. Возвращаемся на одну координату по поддереву вверх и пытаемся построить ветвь вниз из точки (0,0,0,1). Однако точка (0,0,0,0) уже есть, и мы поднимаемся еще на одну точку вверх (0,0,1,1). Пытаемся снова построить ветвь доминирующих векторов (0,0,1,0). Возвращаемся еще на одну координату вверх и строим ветвь из доминирующих векторов (0,1,0,1); (0,1,0,0). Далее возвращаемся в точку (0,1,1,1) и строим вектор (0,1,1,0). Поднимаемся вверх в корень дерева (1,1,1,1) и строим новое поддерево, изменяя вторую координату (1,0,1,1): (1,0,1,0): (1,0,0,0). Делаем обратный ход. Из точки (1,0,1,1) строится вектор (1,0,0,1). Возвращаемся в корень дерева и строим следующее поддерево, изменяя 3 координату: (1,1,0,1): (1,1,0,0). Снова возвращаемся в корень и строим последнее поддерево, изменяя 4 координату: (1,1,1,0). Построение переборного дерева приведено на рис.2.

(1,1,1,1)

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

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

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

(0,0,0,0)

рис.2

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

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

С другой стороны в работе [3] показано, что чем длиннее ветви переборного дерева, тем эффективнее работают алгоритмы доминирующих векторов. Поэтому имеет интерес построение переборных деревьев с максимальным значением средней длины ветвей переборного дерева.


  1. Построение переборной последовательности с бинарными переменными.

Одним из эффективных способов аналитического представления переборного дерева является переборная последовательность. Для случая с одной бинарной переменной переборная последовательность состоит из одного поддерева из двух векторов (значений) – {0,1}. Поэтому средняя длина ветви поддерева с одной бинарной переменной Lср(1) =2 (как частное от деления количества значений в поддеревьях на число поддеревьев).

В случае с двумя бинарными переменными возможны две последовательности по два поддерева в каждой {00,01,11|10} и {00,01|10,11}, где значок | означает переход на другое поддерево. В каждой последовательности находится по 4 значения и два поддерева, поэтому для обеих последовательностей Lср(2) =2.

Существует простой алгоритм построения бинарной последовательности, который не требует большого количества операций и запоминания членов переборной последовательности. Предположим, что уже построена бинарная последовательность для n бинарных переменных. Тогда бинарная последовательность для n + 1 бинарной переменной получается добавлением сначала 0, а затем 1 перед каждым членом бинарной последовательности. Например, для n + 1= 3 получаем следующие бинарные последовательности {000,001,011|010|100,101,111|110} и {000,001|010,011|100,101|110,111}.

Назовем этот метод построением производной последовательности. Последовательность, от которой строится производная, назовем образующей. При построении производной последовательности количество ее членов удваивается, возрастает в два раза и число поддеревьев, поэтому средняя длина поддерева при построении производной последовательности не меняется. Это свойство производных последовательностей в дальнейшем будет использовано. Легко проверить, что для полученной последовательности Lср(3) =2.

Однако это не значит, что для любой бинарной переборной последовательности Lср(n)=2. Для подтверждения этого рассмотрим одну из бинарных переборных последовательностей для n = 3 – {000,001,011,111|010,110|100,101}. В данном случае количество поддеревьев равно 3, а количество членов последовательности – 8, поэтому для этой последовательности Lср(3) =2,66(6). В случае, если для данной последовательность построить производную - для n = 4, то для нее, на основании сказанного выше, мы получим Lср(4) =2,66(6) и.т.д.

Какова же максимальная средняя длина поддерева для последовательности из n бинарных переменных?

Всего количество членов последовательности – 2n.

Минимальное количество поддеревьев:

C n [n/2],

где [ ] – целая часть числа, поэтому


Lср(n) = 2n / C n [n/2] (1).

Посмотрим, как изменяется максимальная средняя длина поддерева при переходе от n к n+1.

Lср(n+1)/ Lср(n) = 2*C n+1[(n+1)/2] / C n[n/2] , если n=2k(четное число), то Lср(n+1)/ Lср(n) = 2*С n+1 n/2 / С n n/2 = 2/(1+ (к/к+1)) > 1. Следовательно, максимальная средняя длина поддерева в этом случае возрастает.

В случае если n = 2k+1(нечетное число): Lср(n+1)/ Lср(n) = 2/(2k+2/k+1) = 1 и максимальная средняя длина поддерева не возрастает.

Ниже приведена таблица максимальных значений средней длины поддерева для n бинарных переменных:

n

1

2

3

4

5

6

7

8

Lср(n)

2

2

2,6(6)

2,6(6)

3,2

3,2

3,66

3,66


Теперь посмотрим, как меняется минимальное значение средней длины поддерева. Для n = 1 и n = 2 - Lсрmin(n) = 2, как мы уже видели. Для n = 3 по построению не получается более 4 поддеревьев, а поэтому Lсрmin(3) = 23 /4 = 2. Однако уже для n = 4 существует последовательность {0000, 0001, 0011, 1011| 1001 |0101 |0111 |0010, 0110| 0100| 1000, 1010 |1100, 1110, 1111| 1101}, которая содержит 9 поддеревьев и имеет Lсрmin(4) = 24 /9 = 1,7(7).

На основании свойства метода производной последовательности можно утверждать, что для n > 4 также существуют последовательности с Lср(n) = 1,7(7); 2; 2,6(6). Для n > 5 - Lср(n) = 1,7(7); 2; 2,6(6); 3,2. Для n > 7 - Lср(n) = 1,7(7); 2; 2,6(6); 3,2; 3,66.


  1. Построение переборной последовательности с дискретными переменными.

Рассмотрим сначала переборную последовательность с одной координатой (n = 1). Например, пусть первая последовательность принимает значение {0, 1, 5, 10}. Следовательно, последовательность содержит 4 члена и 1 поддерево, поэтому Lср1(1) = 4. Вторая последовательность {0, 5, 10}содержит 3 члена и 1 поддерево, поэтому Lср2(1) = 3. Таким образом, уже у последовательности с одной дискретной координатой Lср(1) имеет разное значение и равно числу членов последовательности.

Для построения переборной последовательности с n = 2, из указанных выше последовательностей, воспользуемся методом производной последовательности. Сначала образуем поддерево с первой координатой 0, затем второе - с первой координатой 5 и третье с первой координатой 10: {0,0; 0,1; 0,5; 0,10|5,0; 5,1; 5,5; 5,10|10,0; 10,1; 10,5; 10,10}. В этом случае последовательность содержит 4 * 3 = 12 членов и 3 поддерева, поэтому Lср1(2) = 12 / 3 = 4. Действительно мы строили производную последовательность от первой, поэтому, на основании свойства метода производной последовательности Lср1(1) = Lср1(2) = 4.

Если бы мы строили производную последовательность от второй последовательности, в которой только 3 члена, то получили бы, на основании свойства метода производной последовательности, Lср2(1) = Lср2(2) = 3. Действительно последовательность содержит тоже число членов 3 * 4 = 12 и 4 поддерева, т.е. Lср2(2) = 12/ 4 = 3.

Таким образом, на основании свойства метода производной последовательности, Lср(n) равно количеству членов в первой (образующей) последовательности. Докажем это другим способом.

Общее число членов последовательности M = n1 * n2 * …* nk , где nk – количество членов в k координате последовательности. Общее число поддеревьев N = 1 * n2 * …* nk.

Следовательно, Lср(k) = n1 * n2 * …* nk/ 1 * n2 * …* nk = n1.

Следствие. Для того, чтобы получить переборную дискретную последовательность с наибольшим значением Lср(n), надо в качестве первой (образующей) координаты использовать координату с наибольшим числом членов. В рассмотренном выше примере это первый случай с Lср1(2) = 4.


6. Выводы

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

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

3. В работе разработан простой алгоритм построения переборного дерева (последовательности) – метод производной последовательности.

4. Доказано свойство метода производной последовательности.

5. Определена максимальная средняя длина поддерева для последовательности из n бинарных переменных.

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

7. Показано следствие из свойства метода производной бинарной последовательности – при построении переборных деревьев (последовательностей) данным методом. Переборные деревья с большим числом бинарных переменных включают все значения Lср(n) переборных деревьев с меньшим числом переменных.

8. Для переборного дерева (последовательности) n дискретных переменных Lср(n) равно количеству членов в первой (образующей) координате последовательности.

9. Показано следствие - чтобы получить переборную дискретную последовательность с наибольшим значением Lср(n), надо в качестве первой (образующей) координаты использовать координату с наибольшим числом членов.

Литература





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

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

  3. Вольфсон В.Л Эффективность алгоритмов оптимального проектирования АСУ в задачах с целевой функцией, обладающей свойством доминирования. /Приборы и системы. Управление, контроль и диагностика. 2003. №2.










Похожие:

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


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

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