Browsing by Author "Kiselova, Olena"

Now showing 1 - 8 of 8
  • No Thumbnail Available
    Item
    Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств
    (Інститут кібернетики ім. В. М. Глушкова НАН України, 2020) Киселева, Елена Михайловна; Kiselova, Olena; Кісельова, Олена Михайлівна; Гарт, Людмила Лаврентьевна; Hart, Liudmyla; Гарт, Людмила Лаврентіївна; Притоманова, Ольга Михайловна; Prytomanova, Olha; Притоманова, Ольга Михайлівна
    An algorithm is proposed for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space. The algorithm is based on the formulation of the corresponding continuous problem of optimal set partitioning with a partition quality criterion providing the corresponding form of the Voronoi diagram, and on the application of the apparatus of the optimal partitioning theory to solve this problem. Herewith, the effective method of non-differentiable optimization is used for the numerical solution of an auxiliary finite-dimensional optimization problem arising in the development of the method for solving the mentioned infinite-dimensional optimal partitioning problem. Namely, that is one of the variants of the generalized gradient descent method with space expansion in the direction of the difference of two successive generalized antigradients (Shor’s r-algorithm). The proposed algorithm for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space has some advantages compared to those known in the scientific literature. It does not depend on the dimension of Euclidean space containing the original bounded set; it is applicable for large-scale problems (over 300 generator points); it works not only for Euclidean metrics, but also for Chebyshev, Manhattan and other ones; the complexity of the algorithm implementation for constructing a Voronoi diagram based on the proposed approach does not increase with an increase in the number of generator points. The results of software implementation of the developed algorithm are presented for constructing a standard Voronoi diagram with optimal placement of generator points, as well as some of its generalizations, such as additive, multiplicative and additive-multiplicative Voronoi diagrams with optimal placement of generator points. Запропоновано алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-вимірного евклідового простору. Алгоритм заснований на формулюванні відповідної неперервної задачі оптимального розбиття множин з критерієм якості розбиття, що забезпечує відповідний вид діаграми Вороного, і застосуванні для її розв’язання апарату теорії оптимального розбиття. При цьому для чисельного розв’язання допоміжної задачі скінченновимірної оптимізації, що виникає при розробці методу розв'язання згаданої нескінченновимірної задачі оптимального розбиття множин, використаний ефективний метод недиференційовної оптимізації — один з варіантів методу узагальненого градієнтного спуску з розтягуванням простору в напрямку різниці двох послідовних узагальнених антиградієнтів (r-алгоритм Шора). Запропонований у роботі алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-мірного евклідового простору має ряд переваг порівняно з відомими: він не залежить від розмірності евклідового простору, що містить вихідну обмежену множину; застосовний для задач великих розмірностей (понад 300 точок-генераторів); зберігає силу не тільки для евклідових метрик, але і для метрик Чебишева, манхеттенської та інших; складність реалізації алгоритму побудови діаграми Вороного на основі запропонованого підходу не збільшується при збільшенні кількості точок–генераторів. Представлено результати програмної реалізації розробленого алгоритму для побудови стандартної діаграми Вороного з оптимальним розміщенням точок-генераторів, а також деяких її узагальнень, таких як адитивна, мультиплікативна та адитивно-мультиплікативна діаграми Вороного з оптимальним розміщенням точок-генераторів.
  • No Thumbnail Available
    Item
    Алгоритм решения непрерывной задачи оптимального разбиения с нейролингвистической идентификацией функций, входящих в целевой функционал
    (Інститут кібернетики ім. В. М. Глушкова НАН України, 2018) Киселева, Елена Михайловна; Kiselova, Olena; Кісельова, Олена Михайлівна; Притоманова, Ольга Михайловна; Prytomanova, Olha; Притоманова, Ольга Михайлівна; Журавель, С. В.; Zhuravel, S.
    Предложен алгоритм решения одной непрерывной задачи оптимального разбиения множеств с n-мерного евклидова пространства на их подмножества с нейролингвистической идентификацией функций, входящих в целевой функционал, явный аналитический вид которых заранее неизвестен. Разрабоьано программное обеспечение, реализующее предложенный в статье подход на основе нейронечетких технологий с использованием r-алгоритма Шора. Изложены результаты программной реализации разработанного алгоритма для модельной тестовой задачи. Algorithm for solving a continuous optimal partitioning problem of sets from n-dimen-sional Euclidean space into subsets with a neurolinguistic identification of functions that included into target functional with undefined explicit analytical form is proposed. The software that implements the approach proposed in the article based on neuron-fuzzy technologies using Shor’s r-algorithm is developed. The results of program implementation of the developed algorithm for modeled test problem are described. Запропоновано алгоритм розв’язання однієї неперервної задачі оптимального розбиття множин з n-мірного евклідового простору на їх підмножини з нейролінгвістичною ідентифікацією функцій, що входять до цільового функціонала, явний аналітичний вид яких заздалегідь невідомий. Розроблено програмне забезпечення, що реалізує запропонований в статті підхід на основі нейронечітких технологій з використанням r-алгоритму Шора. Викладено результати програмної реалізації розробленого алгоритму для модельної тестової задачі.
  • No Thumbnail Available
    Item
    Алгоритм розвязання нечіткoї задачі оптимального розбиття множин із розміщенням центрів підмножин
    (Ljubljana, Slovenia, 2020) Кісельова, Олена Михайлівна; Kiselova, Olena; Киселева, Елена Михайловна; Притоманова, Ольга Михайлівна; Prytomanova, Olha; Притоманова, Ольга Михайловна
    Розроблено алгоритм розв’язання нечіткої неперервної задачі оптимального розбиття множин з n-вимірного евклідового простору n E із розміщенням центрів підмножин, яка є задачею нескінченносвимірного математичного програмування з булевими змінними. Алгоритм базується на синтезі методів теорії оптимального розбиття множин та теорії нечітких множин. Нечітка задача оптимального розбиття чіткої множини на її нечіткі підмножини формалізується за рахунок введення до цільового функціоналу задачі функцій належності нечітких підмножин. An algorithm for solving fuzzy continuous optimal partitioning of set problem from n-dimensional Euclidean space Еn into a subset with centers of the subset’s location, which can be defined as infinity-dimensional mathematics programming problem with Boolean variables is developed. The algorithm is based on the synthesis of optimal partitioning of set theory and fuzzy set theory. The fuzzy optimal partitioning of clear set for its fuzzy subsets is formalized by including the membership functions of a fuzzy subsets to the target function of the problem.
  • No Thumbnail Available
    Item
    Алгоритм розв’язання однієї задачі оптимального розбиття з нечіткими параметрами в цільовому функціоналі
    (Дніпровський Національний університет імені Олеся Гончара, 2018) Кісельова, Олена Михайлівна; Kiselova, Olena; Киселева, Елена Михайловна; Притоманова, Ольга Михайлівна; Prytoman; Журавель, С. В.; Zhuravel, S.; Шаравара, В. В.; Sharavara, V.
    Запропоновано алгоритм розв’язання неперервної лінійної однопродуктової задачі оптимального розбиття множини з n-вимірного евклідового простору Еn на підмножини з відшукуванням координат центрів цих підмножин при обмеженнях у формі рівностей та нерівностей, цільовий функціонал якої має нечіткі параметри. Алгоритм заснований на застосуванні нейронечітких технологій та r-алгоритму Н. З. Шора. The mathematical theory of optimal set partitioning (OSP) of the n-dimensional Eu-clidean space, which has been formed for todays, is the field of the modern theory of opti-mization, namely, the new section of non-classical infinite-dimensional mathematical pro-gramming. The theory is built based on a single, theoretically defined approach that sum up initial infinitedimensional optimization problems in a certain way (with the function of Lagrange) to nonsmooth, usually, finite-dimensional optimization problems, where lat-est numerical nondifferentiated optimization methods may be used - various variants r-algorithm of N.Shor, that was developed in V. Glushkov Institute of Cybernetics of the Na-tional Academy of Sciences of Ukraine. For now, the number of directions have been formed in the theory of continuous tasks of OSP, which are defined with different types of mathematical statements of partitioning problems, as well as various spheres of its application. For example, linear and nonlinear, single-product and multiproduct, deterministic and stochastic, in the conditions of com-plete and incomplete information about the initial data, static and dynamic tasks of the OSP without limitations and with limitations, both with the given position of the centers of subsets, and with definition the optimal variant of their location. Optimal set partitioning problems in uncertainty are the least developed for today is the direction of this theory, in particular, tasks where a number of parameters are fuzzy, inaccurate, or there are insuffi-cient mathematical description of some dependencies in the model. Such models refer to the fuzzy OSP problems, and special solutions and methods are needed to solve them. In this paper, we propose an algorithm for solving a continuous linear single-product problem of optimal set partitioning of n-dimensional Euclidean spaces Еn into a subset with searching of coordinates of the centers of these subsets with restrictions in the form of equalities and inequalities where target function has fuzzy parameters. The algorithm is built based on the application of neuro-fuzzy technologies and N. Shor r-algorithm.
  • No Thumbnail Available
    Item
    Застосування теорії оптимального розбиття множин до розв’язання задач штучного інтелекту та розпізнавання образів
    (Інститут прикладного системного аналізу Національного технічного університету України "Київський політехнічний інститут" Національної академії наук України і Міністерства освіти і науки України (ІПСА), 2021) Кісельова, Олена Михайлівна; Kiselova, Olena; Киселева, Елена Михайловна; Притоманова, Ольга Михайлівна; Prytomanova, Olha; Притоманова, Ольга Михайловна; Гарт, Людмила Лаврентіївна; Hart, Liudmyla; Гарт, Людмила Лаврентьевна
    Обґрунтовано можливість застосування математичної теорії неперервних задач оптимального розбиття множин n-вимірного евклідового простору, які належать до некласичних задач нескінченновимірного математичного програмування, до розв’язання задач штучного інтелекту та розпізнавання образів. Наведено постановки задач розпізнавання образів як в умовах визначеності, так і в умовах невизначеності, підходи до їх розв’язання із застосуванням теорії оптимального розбиття множин. Особливу увагу приділено застосуванню методів теорії оптимального розбиття для побудови нечітких діаграм Вороного. Наведено приклади побудови нечітких діаграм Вороного з оптимальним розміщенням точок-генераторів. The paper substantiates the possibility of applying the mathematical theory of continuous problems of optimal partitioning of sets of n-dimensional Euclidean space, which belong to the non-classical problems of infinite-dimensional mathematical programming, to the solution of problems of artificial intelligence and pattern recognition. The problems of pattern recognition both in conditions of certainty and in conditions of uncertainty are formulated. A particular attention is paid to the application of methods of the theory of optimal partitioning for the construction of fuzzy Voronoi diagrams. Examples of constructing fuzzy Voronoi diagrams with the optimal placement of generating points are given. Обоснована возможность применения математической теории непрерывных задач оптимального разбиения множеств n-мерного эвклидова пространства, которые относятся к неклассическим задачам бесконечномерного математического программирования, к решению задач искусственного интеллекта и распознавания образов. Приведены постановки задач распознавания образов как в условия определенности, так и в условиях неопределенности. Особое внимание уделено применению методов теории оптимального разбиения для построения нечетких диаграмм Вороного. Приведены примеры построения нечетких диаграмм Вороного с оптимальным размещением точек-генераторов.
  • No Thumbnail Available
    Item
    Объектно-ориентированный подход к программной реализации алгоритма решения нелинейных задач оптимального разбиения множеств
    (Дніпровський Національний університет імені Олеся Гончара, 2017) Киселева, Елена Михайловна; Kiselova, Olena; Кісельова, Олена Михайлівна; Притоманова, Ольга Михайловна; Prytoma; Притоманова, Ольга Михайлівна; Шаравара, В. В.; Sharavara, V.; Журавель, С. В.; Zhuravel, S.
    Рассматривается применение парадигмы объектно-ориентированного программирования при программной реализации алгоритма решения нелинейных многопродуктовых задач оптимального разбиения множеств в случае выпуклой либо вогнутой нелинейной части целевого функционала с отысканием оптимальных координат центров подмножеств и ограничениями в форме равенств и неравенств, а также их частных случаев . Use of object-oriented paradigm for implementing the algorithm of solving nonlinear multigrocery problems of optimal partitioning of sets in case of convex or concave nonlinear component of target functional with optimal placing of the centers at restrictions in the form of equalities and inequalities and their particular cases is considered. Розглядається застосування парадигми об'єктно-орієнтованого програмування при програмній реалізації алгоритму розв'язання нелінійних багатопродуктових задач оптимального розбиття множин у випадку опуклої або увігнутої нелінійної частини цільового функціоналу з відшуканням оптимальних координат центрів підмножин та обмеженнями у формі рівностей і нерівностей, а також їх частинних випадків.
  • No Thumbnail Available
    Item
    Решение двухэтапной непрерывно-дискретной задачи оптимального разбиения-распределения с заданным положением центров подмножеств
    (2020) Киселева, Елена Михайловна; Kiselova, Olena; Кісельова, Олена Михайлівна; Притоманова, Ольга Михайловна; Prytomanova, Olha; Притоманова, Ольга Михайлівна; Ус, Светлана Альбертовна; Us, Svitlana; Ус, Світлана Альбертівна
    Предложены метод и алгоритм решения двухэтапной непрерывно-дискретной задачи оптимального разбиения-распределения, являющейся обобщением, с одной стороны, классической транспортной задачи на случай, когда объемы производства (хранения, переработки) в заданных пунктах не известны заранее, а отыскиваются как решение соответствующей непрерывной задачи оптимального разбиения множества непрерывно распределенных потребителей (поставщиков) на сферы обслуживания их этими пунктами, с другой стороны, дискретных двухэтапных производственно-транспортных задач на случай непрерывно распределенного потребителя. Работа предложенного алгоритма проиллюстрирована на решении модельной задачи. A method and algorithm of solving a two-stage continuous-discrete optimal partitioning-allocation problem are proposed. On the one hand, this problem is a generalization of the classical transportation problem to the case where production (storage, recycling) volumes at specified points are unknown in advance, and are sought as a solution of the corresponding continuous problem of optimal partitioning of a set of continuously distributed consumers (suppliers) into their service areas by these points. On the other hand, this problem generalizes discrete two-stage production-transportation problems in the case of a continuously distributed consumer. The operation of the proposed algorithm is demonstrated by solving a model problem. Запропоновано метод і алгоритм розв’язання двоетапної неперервно-дискретної задачі оптимального розбиття–розподілу, яка є узагальненням, з одного боку, класичної транспортної задачі на випадок, коли обсяги виробництва (зберігання, переробки) в заданих пунктах не відомі заздалегідь, а відшукуються як розв’язок відповідної неперервної задачі оптимального розбиття множини неперервно розподілених споживачів (постачальник ів) на сфери їхнього обслуговування в цих пунктах, з іншого боку, дискретних двоетапних виробничо-транспортних задач на випадок неперервно розподіленого споживача. Роботу запропонованого алгоритму проілюстровано розв’язуванням модельної задачі.
  • No Thumbnail Available
    Item
    Розв'язання однієї нескінченновимірної задачі location-allocation із нечіткими параметрами
    (Дніпровський Національний університет імені Олеся Гончара, 2018) Кісельова, Олена Михайлівна; Kiselova, Olena; Киселева, Елена Михайловна; Притоманова, Ольга Михайлівна; Prytomanova, Olha; Притоманова, Ольга Михайловна; Журавель, С. В.; Zhuravel, S.; Шаравара, В. В.; Sharavara, V.
    Сформульовано нескінченновимірну задачу location-allocation з нечіткими параметрами. Розроблено програмне забезпечення, що реалізує алгоритм її розв’язання на основі нейронечітких технологій з використанням r-алгоритму Шора. Викладено результати розрахунків для модельної задачі location-allocation з нечіткими параметрами, які отримано за допомогою розробленого програмного забезпечення. The problem of enterprises location with the simultaneous allocation of this region, coninuously filled by consumers, into consumer areas, where each of them is served by one enterprise, in order to minimize transportation and production costs, in the mathematical definition, are illustrated as infinite-dimensional optimal set partitioning problems (OSP) in non-intersecting subsets with the placement of centers of these subsets. A wide range of methods and algorithms have been developed to solve practical tasks of location-allocation, both finite-dimensional and infinite-dimensional. However, infinite-dimensional location-allocation problems are significantly complicated in uncertainty, in particular case when a number of their parameters are fuzzy, inaccurate, or an unreliable mathematical description of some dependencies in the model is false. Such models refer to the fuzzy OSP tasks, and special solutions and methods are needed to solve them. This pa-per is devoted to the solution of an infinite-dimensional problem of location-allocation with fuzzy parameters, which in mathematical formulation are defined as continuous line-ar single-product problem of n-dimensional Euclidean space Еn optimal set partitioning into a subset with the search for the coordinates of the centers of these subsets with con-straints in the form of equalities and inequalities whose target functionality has fuzzy pa-rameters. The software to solve the illustrated problem was developed. It works on the ba-sis of neuron-fuzzy technologies with r-algorithm of Shore application. The object-oriented programming language C# and the Microsoft Visual Studio development envi-ronment were used. The results for a model-based problem of location-allocation with fuzzy parameters obtained in developed software are presented. The results comparison for the solution to solve the infinite-dimensional problem of location-allocation with de-fined parameters and for the case where some parameters of the problem are inaccurate, fuzzy or their mathematical description is false.