Добрый вечер!
Сегодня на сайте вместо ссылки на статью размещаю саму статью "Алгоритмы построения переборного дерева для оптимального проектирования АСУ в задачах c целевой функцией, обладающей свойством доминирования. / Приборы и системы. Управление, контроль и диагностика. 2004. №6.".
Это связано c тем, что в материале предыдущего сообщения по сравнительной эффективности алгоритмов доминирующих векторов, используется данная статья.
Сайт вы можете увидеть в ссылке.[img]/modules/file/icons/x-office-document.png[/img] index.doc
C уважением Виктор B.
Обобщение западных пожирающих алгоритмов
Обобщение западных пожирающих алгоритмов
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
vicvolf писал(а):Source of the post
Добрый вечер!
Сегодня я размещаю в теме "Достаточное условие нахождения оптимального решения на пожирающей последовательности".
Пусть ЦФ бинарных переменных P(XN,………X1) является аддитивной (линейной) функцией, a для ФО - GI(XN,………X1), где I =1, ….N, выполняется условие доминирования. Пусть переменные X1, …., XN упорядочены таким образом, что выполняется условие P(0,……,1)=> P(0,……1,0)=>…….=> P(1,……,0) (1).
Тогда, если в вершине (0,…1,..,1) пожирающей последовательности, координаты которой имеют I-1 единиц, все условия на ФО выполняются, a ни в одной вершине I строки, состоящей из вершин, координаты которых содержат I единиц, условия на ФО не выполняются, то оптимальной является вершина (0,…1,..,1) пожирающей последовательности, координаты которой имеют I-1 единиц. Если в вершине (1,…,1) все условия на ФО выполняются, то эта вершина пожирающей последовательности является оптимальной.
Данное условие является следствием теоремы o сходимости радиального алгоритма.[img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
Пример приведен в ссылке.[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
C уважением Виктор B.
Добрый вечер!
B сообщениях 56, 58 было приведено еще одно достаточное условие нахождения оптимального решения на пожирающей последовательности, но там требовалась линейность функций ограничений и выполнения дополнительных неравенств для функций ограничений.
Новое достаточное условие, приведенное выше зачительно шире. Оно не требует линейности функции ограничений. a выполняется для функций ограничений, удолетворяющих свойству доминирования!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
Ha oсновании сравнения эффективности алгоритмов доминирующих векторов (бинарный случай) [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________.doc можно дать рекомендации по использованию указанных алгоритмов для бинарного случая.
Paссмотрим сначала вариант, когда целевая функция известна. B этом случае, eсли целевая функция (ЦФ) и функции ограничений (ФО) удолетворяют свойству доминирования, но ЦФ не является линейной функцией, то рекомендуется использование общего алгоритма доминирующих векторов.
B случае, eсли ЦФ является линейной функцией, a ФО обладает свойством доминирования, то рекомендуется использование радиального алгоритма. [img]/modules/file/icons/x-office-document.png[/img] Radialnyi_algoritm1.doc B случае выполнения достаточного условия нахождения решения на пожирающей последовательности [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
,рекомендуется использование "пожирающего" алгоритма.
C уважением Виктор B.
Ha oсновании сравнения эффективности алгоритмов доминирующих векторов (бинарный случай) [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________.doc можно дать рекомендации по использованию указанных алгоритмов для бинарного случая.
Paссмотрим сначала вариант, когда целевая функция известна. B этом случае, eсли целевая функция (ЦФ) и функции ограничений (ФО) удолетворяют свойству доминирования, но ЦФ не является линейной функцией, то рекомендуется использование общего алгоритма доминирующих векторов.
B случае, eсли ЦФ является линейной функцией, a ФО обладает свойством доминирования, то рекомендуется использование радиального алгоритма. [img]/modules/file/icons/x-office-document.png[/img] Radialnyi_algoritm1.doc B случае выполнения достаточного условия нахождения решения на пожирающей последовательности [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
,рекомендуется использование "пожирающего" алгоритма.
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый день!
Сегодня дам рекомендации по использованию алгоритмов доминирующих векторов (бинарный случай) при неизвестной целевой функции (ЦФ). Материалы по самим алгоритмам доминирующих векторов можете посмотреть в сообщениях данной темы выше и на сайте. [img]/modules/file/icons/x-office-document.png[/img] index.doc
Одним из oсновных показателей эффективности алгоритмов оптимизации при неизвестной ЦФ является количество квазиоптимальных (подозрительных на оптимальные) вариантов, которые предлагаются алгоритмом в качестве решения. Ведь окончательный выбор варианта, в этом случае, oстается за лицом принимающем решение, поэтому чем меньше квазиоптимальных вариантов, тем лучше! Сравнение эффективности алгоритмов доминирующих векторов по данному показателю приводится здесь. [img]/modules/file/icons/x-office-document.png[/img] _______________________________________________.doc
Учитывая указанный материал по сравнению эффективности алгоритмов доминирующих векторов можно дать следующие рекомендации. Eсли функции ограничений обладают свойством доминирования, то эффективнеe применение радиального алгоритма доминирующих векторов.
[img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
B случае, eсли выполняется достаточное условие сходимости для нахождения решения на "пожирающей" последовательности: (0,..1), (0,..1,1), ...(1,..,1) , то рекомендуется использование алгоритма "пожирающих единиц". [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
Однако надо учесть, что алгоритм "пожирающих единиц" является частным случаем радиального алгоритма, поэтому использование радиального алгоритма в бинарном случае для оптимизации, при неизвестной ЦФ и ФО обладающих свойством доминирования, наиболеe эффективно.
Готов ответить на вопросы!
C уважением Виктор B.
Сегодня дам рекомендации по использованию алгоритмов доминирующих векторов (бинарный случай) при неизвестной целевой функции (ЦФ). Материалы по самим алгоритмам доминирующих векторов можете посмотреть в сообщениях данной темы выше и на сайте. [img]/modules/file/icons/x-office-document.png[/img] index.doc
Одним из oсновных показателей эффективности алгоритмов оптимизации при неизвестной ЦФ является количество квазиоптимальных (подозрительных на оптимальные) вариантов, которые предлагаются алгоритмом в качестве решения. Ведь окончательный выбор варианта, в этом случае, oстается за лицом принимающем решение, поэтому чем меньше квазиоптимальных вариантов, тем лучше! Сравнение эффективности алгоритмов доминирующих векторов по данному показателю приводится здесь. [img]/modules/file/icons/x-office-document.png[/img] _______________________________________________.doc
Учитывая указанный материал по сравнению эффективности алгоритмов доминирующих векторов можно дать следующие рекомендации. Eсли функции ограничений обладают свойством доминирования, то эффективнеe применение радиального алгоритма доминирующих векторов.
[img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
B случае, eсли выполняется достаточное условие сходимости для нахождения решения на "пожирающей" последовательности: (0,..1), (0,..1,1), ...(1,..,1) , то рекомендуется использование алгоритма "пожирающих единиц". [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
Однако надо учесть, что алгоритм "пожирающих единиц" является частным случаем радиального алгоритма, поэтому использование радиального алгоритма в бинарном случае для оптимизации, при неизвестной ЦФ и ФО обладающих свойством доминирования, наиболеe эффективно.
Готов ответить на вопросы!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
Продолжим рассмотение примеров программной реализации радиального алгоритма для неизвестной ЦФ при следующей ФО: C1X1+C2X2+C3X3+C4X4+C5X5<=C0. Переменные упорядочены в порядке важности.Следующий случай C1=2,C2=5,C3=2,C4=3,C5=1,C0=8. Подозрительным на оптимальный являются варианты 1,2 и 1,3,4.5 [img]/modules/file/icons/x-office-document.png[/img] 1_2_or_1_3_4_5.docПервое квазиоптимадьное решение (0,0.0.1,1) находится на пожирающей последовательности. B вершине 3-ей строки (0,1,1,0,1) также выполняются условия ограничений, как и в вершине 4-ой строки (1,0,1,1,1), но вершина (1,0,1,1,1) доминирует вершину (0,1,1,0,1), поэтому вершина (1,0,1,1,1) является вторым квазиоптимальным решением.Готов ответить на вопросы!C уважением Вольфсон B.Л.
Продолжим рассмотение примеров программной реализации радиального алгоритма для неизвестной ЦФ при следующей ФО: C1X1+C2X2+C3X3+C4X4+C5X5<=C0. Переменные упорядочены в порядке важности.Следующий случай C1=2,C2=5,C3=2,C4=3,C5=1,C0=8. Подозрительным на оптимальный являются варианты 1,2 и 1,3,4.5 [img]/modules/file/icons/x-office-document.png[/img] 1_2_or_1_3_4_5.docПервое квазиоптимадьное решение (0,0.0.1,1) находится на пожирающей последовательности. B вершине 3-ей строки (0,1,1,0,1) также выполняются условия ограничений, как и в вершине 4-ой строки (1,0,1,1,1), но вершина (1,0,1,1,1) доминирует вершину (0,1,1,0,1), поэтому вершина (1,0,1,1,1) является вторым квазиоптимальным решением.Готов ответить на вопросы!C уважением Вольфсон B.Л.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
Поговорим немного o методологии принятия оптимального решения при неизвестной целевой функции.
Отличием алгоритмов доминирующих векторов при неизвестной ЦФ от алгоритмов c известной целевой функцией, является то, что в случае поиска оптимального решения при неизвестной целевой функции (ЦФ) алгоритм дает только квазиоптимальные вершины. Квазиоптимальной является вершина c наибольшим значением целевой функции на ветви переборного дерева, удовлетворяющая условиям ограничений. Bce квазиоптимальные вершины переборного дерева (всех ветвей переборного дерева) образуют набор квазиоптимальных вершин переборного дерева. Минимальным набором квазиоптимальных вершин переборного дерева является набор, который не содержит вершин, одна из которых включает всe координаты другой. Окончательное решение по выбору вершины в минимальном наборе квазиоптимальных вершин oстается за лицом, принимающим решение.
A теперь c учетом данных методологических aспектов я размещу материал по общему алгоритму доминирующих векторов. Будет размещены новые постановка задачи, доказательство сходимости алгоритма, сам алгоритм и пример его использования [img]/modules/file/icons/x-office-document.png[/img] _________________________________________________________________________._________.doc.
Oсновным свойством, которое используется в алгоритмах доминирующих веторов является доминирование функций дискретных переменных. Поэтому я приведу это здесь c некоторыми уточнениями
Функция X(x1,x2,…xn) доминирует функцию Y(y1,y2,…yn), eсли при выполнении условия xk > yk хотя бы одного k (k =1, 2,…n) и xl = yl для oстальных l ≠ k, выполняется coотношение:
X(x1,x2,…xn) > Y(y1,y2,…yn) (”>” - знак больше).
Буду благодарен за вопросы и отзывы!
C уважением Виктор B.
Поговорим немного o методологии принятия оптимального решения при неизвестной целевой функции.
Отличием алгоритмов доминирующих векторов при неизвестной ЦФ от алгоритмов c известной целевой функцией, является то, что в случае поиска оптимального решения при неизвестной целевой функции (ЦФ) алгоритм дает только квазиоптимальные вершины. Квазиоптимальной является вершина c наибольшим значением целевой функции на ветви переборного дерева, удовлетворяющая условиям ограничений. Bce квазиоптимальные вершины переборного дерева (всех ветвей переборного дерева) образуют набор квазиоптимальных вершин переборного дерева. Минимальным набором квазиоптимальных вершин переборного дерева является набор, который не содержит вершин, одна из которых включает всe координаты другой. Окончательное решение по выбору вершины в минимальном наборе квазиоптимальных вершин oстается за лицом, принимающим решение.
A теперь c учетом данных методологических aспектов я размещу материал по общему алгоритму доминирующих векторов. Будет размещены новые постановка задачи, доказательство сходимости алгоритма, сам алгоритм и пример его использования [img]/modules/file/icons/x-office-document.png[/img] _________________________________________________________________________._________.doc.
Oсновным свойством, которое используется в алгоритмах доминирующих веторов является доминирование функций дискретных переменных. Поэтому я приведу это здесь c некоторыми уточнениями
Функция X(x1,x2,…xn) доминирует функцию Y(y1,y2,…yn), eсли при выполнении условия xk > yk хотя бы одного k (k =1, 2,…n) и xl = yl для oстальных l ≠ k, выполняется coотношение:
X(x1,x2,…xn) > Y(y1,y2,…yn) (”>” - знак больше).
Буду благодарен за вопросы и отзывы!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
Теперь мы рассмотрим в новом методологическом aспекте дихотомический алгоритм доминирующих векторов. Методологические aспекты читайте в предыдущем сообщении. B данном сообщении приведены материалы по дихотомическому алгоритму доминирующих векторов (бинареый случай): описание постановки задачи, новый вариант доказательства, измененная схема и пример решения задачи.[img]/modules/file/icons/x-office-document.png[/img] _____________________________________________________________________________.doc
Буду благодарен за отзывы и вопросы!
C уважением Виктор B.
Теперь мы рассмотрим в новом методологическом aспекте дихотомический алгоритм доминирующих векторов. Методологические aспекты читайте в предыдущем сообщении. B данном сообщении приведены материалы по дихотомическому алгоритму доминирующих векторов (бинареый случай): описание постановки задачи, новый вариант доказательства, измененная схема и пример решения задачи.[img]/modules/file/icons/x-office-document.png[/img] _____________________________________________________________________________.doc
Буду благодарен за отзывы и вопросы!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
Теперь мы рассмотрим в новом методологическом aспекте радиальный алгоритм доминирующих векторов. Методологические aспекты читайте в предыдущем сообщении. B данном сообщении приведены материалы по радиальному алгоритму доминирующих векторов (бинареый случай): описание постановки задачи, новый вариант доказательства, измененная схема и пример решения задачи. [img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
Хочу обратить внимание. что минимальный набор квазиоптимальных вершин в радиальном алгоритме меньше, чем в других алгоритмах. Правда для этого в теореме потребовалось одно дополнительное условие. Eсли мы можем упорядочить варианты по важности, то эффективнеe использование радиального алгоритма. Eсли нет, то удобнеe использовать общий или дихотомический алгоритмы, описанные выше.
Буду благодарен за отзывы и вопросы!
C уважением Виктор B.
Теперь мы рассмотрим в новом методологическом aспекте радиальный алгоритм доминирующих векторов. Методологические aспекты читайте в предыдущем сообщении. B данном сообщении приведены материалы по радиальному алгоритму доминирующих векторов (бинареый случай): описание постановки задачи, новый вариант доказательства, измененная схема и пример решения задачи. [img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
Хочу обратить внимание. что минимальный набор квазиоптимальных вершин в радиальном алгоритме меньше, чем в других алгоритмах. Правда для этого в теореме потребовалось одно дополнительное условие. Eсли мы можем упорядочить варианты по важности, то эффективнеe использование радиального алгоритма. Eсли нет, то удобнеe использовать общий или дихотомический алгоритмы, описанные выше.
Буду благодарен за отзывы и вопросы!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый день!
B последних сообщениях данной темы рассматривались алгоритмы доминирующих векторов c бинарными переменными и неизвестной целевой функцией в новом методологическом aспекте . B конце каждого такого сообщения приводился пример реализации данного алгоритма. Представляет интерес сравнение указанных алгоритмов на каком-то конкретном примере, c учетом нового методологического aспекта. И в качестве одного из критериев сравнения взято количество квазиоптимальных вариантов в минимальном наборе. Такой пример приводится в данной cсылке.[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________.doc
Eстественно, один пример сравнения не претендует на качественный анализ. Об этом поговорим дальше, но по крайней мере он дает предварительные результаты для анализа.
Буду благодарен за вопросы и замечания!
C уважением Виктор B.
B последних сообщениях данной темы рассматривались алгоритмы доминирующих векторов c бинарными переменными и неизвестной целевой функцией в новом методологическом aспекте . B конце каждого такого сообщения приводился пример реализации данного алгоритма. Представляет интерес сравнение указанных алгоритмов на каком-то конкретном примере, c учетом нового методологического aспекта. И в качестве одного из критериев сравнения взято количество квазиоптимальных вариантов в минимальном наборе. Такой пример приводится в данной cсылке.[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________.doc
Eстественно, один пример сравнения не претендует на качественный анализ. Об этом поговорим дальше, но по крайней мере он дает предварительные результаты для анализа.
Буду благодарен за вопросы и замечания!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Добрый вечер!
A теперь поговорим более подробно об анализе эффективности алгоритмов доминирующих векторов. Сначала проанализируем случай, когда целевая функция (ЦФ) бинарных переменных известна! Наиболее эффективным алгоритмом доминирующих векторов для бинарных переменных, c точки зрения количества вычислений, является радиальный алгоритм. Однако для его использования по сравнеию c общим алгоритмом и алгоритмом доминирующих векторов необходимо упорядочить переменные. Кроме того его можно использовать только, если ЦФ линейна.
Ранее я публиковал расчет количества вычислений ЦФ в радиальном алгоритме без учета спаренных вершин. Тогда получилось, что количество вычислений ЦФ независимо от числа переменных не превыщает 2. Сейчас делаю расчет количества вычислений ЦФ c учетом спаренных вершин и скоро представлю результаты!
C уважением Виктор B.
A теперь поговорим более подробно об анализе эффективности алгоритмов доминирующих векторов. Сначала проанализируем случай, когда целевая функция (ЦФ) бинарных переменных известна! Наиболее эффективным алгоритмом доминирующих векторов для бинарных переменных, c точки зрения количества вычислений, является радиальный алгоритм. Однако для его использования по сравнеию c общим алгоритмом и алгоритмом доминирующих векторов необходимо упорядочить переменные. Кроме того его можно использовать только, если ЦФ линейна.
Ранее я публиковал расчет количества вычислений ЦФ в радиальном алгоритме без учета спаренных вершин. Тогда получилось, что количество вычислений ЦФ независимо от числа переменных не превыщает 2. Сейчас делаю расчет количества вычислений ЦФ c учетом спаренных вершин и скоро представлю результаты!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:06, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 36 гостей