Формирование замкнутых множеств параметров сложной формы и деревьев перспективных подмножеств

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 7
ФОРМИРОВАНИЕ ЗАМКНУТЫХ МНОЖЕСТВ ПАРАМЕТРОВ СЛОЖНОЙ ФОРМЫ И ДЕРЕВЬЕВ ПЕРСПЕКТИВНЫХ ПОДМНОЖЕСТВ
орнеев А.М.,бдуллах Л.С.,метанникова Т.А.
1 ФГБОУ ВПО «Липецкий Государственный технический университет» России, Липецк, (398 600, Липецк, ул.
Московская, 30), e-mail: d. 48@rambler. ru_
Представлен численный метод решения задач дискретной оптимизации сложных производств, отличающийся использованием сетки множества m-подпространств, образованных случайными величинами, и возможностью формирования m-деревьев перспективных подпространств и описания пространства параметров сложной формы. Данный подход позволяет решать оптимизационную задачу поиска глобального оптимума. Организация ветвления основывается на структуре пространства, и в качестве множеств ветвления берутся многомерные параллелепипеды. Исходной областью является параллелепипед, содержащий все имеющиеся наблюдения или базисное пространство. Область разбивается на подпространства, сформированные при различной значности алфавитов случайных величин. Степень детализации соответствует уровням формируемого m-дерева. Метод m-сеток — метод поиска глобального экстремума, состоящий в построении сетки, вычислении значений целевой функции в подпространствах и выборе лучшего. Число m-подпространств в процессе поиска может изменяться в зависимости от степени детализации используемых алфавитов исследуемых случайных величин.
Ключевые слова: численный метод, сложных производств системы, структуре множества, дискретной оптимизации.
FORMATION CLOSED SETPARAMETERS OF COMPLEX FORMS AND TREES PERSPECTIVE SUBSETS
1Korneev A.M., 1Abdullakh L.S., 1 Smetannikova T.A.
1"LipetskState Technical University", Lipetsk, ((39 600, Lipetsk, streetMoskovskaya, 30), e-mail: d. 48@rambler. ru Is the numerical method of discrete optimization complex production, using different sets m -subspaces grid random variables, and the possibility of forming m -trees promising subspaces description of the parameter space complex shape. This approach allows us to solve the optimization problem of finding global optimum. The organization is based on the branching structure of space and the sets are taken multidimensional branching box. The starting area is a box containing all the available observations or base space. Area is divided into subspaces formed at different alphabets-valued random variables. The level of detail corresponds to the levels generated m -tree. Method m — nets — method of finding the global extremes, which consists in the construction of the grid, the computation of the objective function in subspaces and choosing best. Number m -subspaces in the search may vary depending on the degree of detail used alphabets random variables
investigated. _
Keywords: numerical method, complex production system, structure of the set, discrete optimization.
В процессе дискретной оптимизации формируются замкнутые множества параметров сложной формы и деревья перспективных m-подмножеств на основе композиционности подмножеств, состоящие в исключении из базисного множества некоторых неблагоприятных подмножеств и присоединении благоприятных подмножеств, не лежащих в базовом множестве [2]. Организация ветвления основывается на структуре множества, и в качестве множеств ветвления берутся многомерные параллелепипеды. Исходная область разбивается на подмножества, сформированные при различной значности алфавитов случайных величин [1−3]. Разбиение на m-подмножества формирует m-деревья, входящие в
иерархическое дерево, узлами которых являются т-подмножества с различной степенью детализации случайных величин [6].
Степень детализации соответствует уровням формируемого т-дерева. На каждом шаге формирования т-дерева значность алфавитов возводится в степень 2. Таким же образом изменяется количество т-подмножеств.
к М
т=ПП А
к=1 тк =1
где п — уровень т-дерева (номер шага детализации).
Для удобства кодировки получаемых т-подмножеств и узлов т-дерева используется кодировка алфавитов случайных величин.
Если диапазон изменения входной величины разбивается на ряд составляющих
, ь
алфавитов: ^ь^^^^к & gt-->-Ьктк^
Ь
ктк]п
, то кодировать каждую составляющую
алфавита '-& quot-"-итк можно номером этой составляющей (& quot-/тк). Например, для узла т-дерева (3×2) кодировка т-подмножеств будет иметь вид (рис. 1):
8 узел дерева (3×2) / - Я / - & quot->- 8 узел дерева (3×2) Г -Я / -?
^к12'-^к22 (К22) (23,2а) (З3,2а)
(1зЛ) (23Д2) ОМ

J = 3 J = 2
Рис. 1. Кодировка т-подмножеств узла т-дерева (3×2) (к1 '- к2).
Пример разбиения множества случайных величин на т-подмножества представлен на рисунке 2.
Г)
111?-2


от
(з4д4)
(44,24)
(44Л4)
Д)
(ЦЛ) (24 40 (34,44) (4,. 4,)
(14,34) (24 з4) (34, 34) (44,34)
(14,2*) (24 20 (34. 20 (1,24)
(ЫО (24. 14) (34 ДО (44Л4)
Е)
(18,83) (28,8а): З8!88) (48,88) (34,44) (44. 44)
(18,7а) (2 В, 78) (48,78)
(14,34) 63) (5 3,63) (6з, 6з) (44,^4)
(ЗВ, 58) (4з, 53) (5з, 5з) (6З, 58)
(14Д4) (З3,4з) (4цА) (5з, 48) (6з-4в) 7з, 48) (8з, 43)
(з8: з8) (48,& amp-) (5З, 38) (68,38) |Мй)
(14Л4) (24Л4) (З4Л4) (44 Л 4)
Рис. 2. Пример разбиения множества случайных величин на т-подмножества. Исходный параллелепипед, содержащий все имеющиеся наблюдения, изображен на
рис. 2, А. Обозначим эту область (11,11) (рис. 2, Б). Ей соответствует корневой узел дерева. Пусть область множества, закрашенная серым цветом, является оптимальной с точки зрения
(т- / х*)
получения требуемых выходных свойств у '- [2, 4, 7].
Светлая область характеризуется возможностью получения некачественных свойств (т~ / х *)
^ г '- или отсутствием попадания в нее значений случайных величин (рис. 2, А). При формировании т-дерева (2×2)
J = 2 J = 2
(к1 '- к2) на первом шаге область разбивается на 4 т-подмножества (рис. 2, В), на втором шаге — 16 и т. д.
Задаваемое т — нами пороговое значение точек должно быть превышено в подмножестве. Если это условие не соблюдается, то дальнейшая детализация не может быть выполнена. Процесс прекращается при достижении требуемой точности разбиения. Далее производим возврат на предыдущий уровень для разбиения соседнего многомерного т-подмножества.
В пустотах, которые остались после отсева, необходимо выделить т-подмножества, которые обеспечивают получение требуемых свойств с максимальной частотой. Узлы т-дерева обозначены следующим образом:
о — соответствующее т-подмножество с детализацией на уровне-? — пустое т-подмножество без детализации не осуществляется- ¦ - т-подмножество, удовлетворяющее критерию отбора и точности разбиения. Пунктиром на рисунке 2 обозначено разбиение, с областью шага на 4 т-подмножества с кодировкой (12,12), (12,22), (22,22), (22,12). Каждому из этих т-подмножеств соответствуют узлы т-дерева, расположенные на первом иерархическом уровне (рис 3). Процесс разбиения продолжается для каждого из т-подмножеств. Подмножества, не удовлетворяющие критерию отбора, считаются пустыми и в дальнейшем рассмотрении не участвуют. Для остальных т-подмножеств производится такое же разбиение, что и для исходного прямоугольника. Процесс повторяется до тех пор, пока размер т-подмножества последнего уровня не будет превышать требуемой точности приближения. В частности, т-подмножество (22,12) разбивается на подмножества (34,14), (34,24), (44,24), (44,14) (рис. 2, Г). В результате формируется оптимальная область случайных величин сложной формы (Рис. 2, Е), т-дерево которой изображено на рисунке 3. Дерево имеет 3 уровня иерархии, соответствующие заданной степени детализации.
величин
Рассмотренный подход формирования иерархического т-дерева относится к алгоритму построения иерархии «сверху вниз» — от верхних уровней к нижним. Исходная область разбивается на конечное множество т-подмножеств, из которых формируется замкнутое оптимальное множество сложной формы.
Обратный подход состоит в формировании иерархии «снизу вверх» — от нижних уровней к верхним. В этом случае исходное множество случайных величин разбивается на максимальное число т подмножеств, которое определяется планируемой сложностью формируемого т-дерева и зависит от количества его уровней. т-подмножества нижнего уровня объединяются в более крупные. Критериями объединения служат композиционность подмножеств контакт т-подмножеств между собой по одной или нескольким осям изменения случайных величин и увеличение значения целевой функции при их объединении.
Заключение
Разработан метод формирования пространств параметров сложной формы и т деревьев перспективных подпространств на основе композиционности подпространств, состоящий в исключении из базисного пространства некоторых неблагоприятных подмножеств и присоединении благоприятных подмножеств, не лежащих в базовом пространстве. Метод отличается использованием сетки множества т-подпространств, образованных случайными величинами.
Список литературы
1. Блюмин С. Л. Дискретное моделирование систем автоматизации и управления [Текст]: Монография- Липецкий эколого-гуманитарный институт/ С. Л. Блюмин, A.M. Корнеев. -Липецк: ЛЭГИ, 2005. — С. 124.
2. Корнеев А. М. Методы идентификации сквозной технологии производства металлопродукции [Текст]: монография / А.М. Корнеев- Липецкий государственный педагогический университет. — Липецк: ЛГПУ, 2009. — С. 286.
3. Корнеев А. М. Использование итеративных цепей для описания многостадийных пространственно-распределенных производственных систем [Текст]/ А. М. Корнеев, В. Н. Малыш, Т. А. Сметанникова // Вестник Российского университета дружбы народов. Серия: Инженерные исследования. — 2012. — № 2. — С. 78−84.
4. Корнеев, А. М. Структурное клеточно-иерархическое моделирование сложных пространственно-распределенных систем [Текст] / А. М. Корнеев // Вести высших учебных заведений черноземья. — 2011. — № 1, С. 62−66.
5. Корнеев А. М., Блюмин С. Л., Сметанникова Т. А. Численные методы поисковой оптимизации дискретных клеточно-иерархических систем [Текст] / Корнеев А. М., Блюмин С. Л., Сметанникова Т. А. // Вести высших учебных заведений Черноземья. — 2013. — № 3. — С. 21−26.
6. Корнеев А. М., Мирошникова Т. В. Методика поиска оптимальных границ факторов сквозной технологии. Системы управления и информационные технологии. 2008, № 3(33), С. 93−96.
7. Korneev A.M., Abdullah L.S., Smetannikova T.A. Structural cell-hierarchical identification of complex spatially distributed production systems // Proceedings of the 3rd International Academic Conference. 2013, St. Louis, Missouri, USA. С. 75−79.
Рецензенты:
Володин И. М., д.т.н., профессор, проректор по научной работе, ФГБОУ ВПО «Липецкий государственный технический университет», г. Липецк-
Шмырин А. М., д.т.н., доцент, заведующий кафедрой высшей математики, ФГБОУ ВПО «Липецкий государственный технический университет», г. Липецк.

ПоказатьСвернуть
Заполнить форму текущей работой