Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Чернышев Юрий Олегович

доктор технических наук

профессор, Донской государственный технический университет

344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1

Chernyshev Yurii Olegovich

Doctor of Technical Science

Professor, Department of Automation of Production Processes, Don State Technical University

344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1

myvnn@list.ru
Другие публикации этого автора
 

 
Венцов Николай Николаевич

кандидат технических наук

доцент, Донской государственный технический университет

344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1

Ventsov Nikolai Nikolaevich

PhD in Technical Science

Associate Professor, Department of Information Technology, Don State Technical University

344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1

vencov@list.ru
Другие публикации этого автора
 

 
Пшеничный Игорь Сергеевич

не работает временно

350063, Россия, г. Краснодар, ул. Красина, 4

Pshenichnyi Igor' Sergeevich

Adjunct, Krasnodar Higher Military School

350063, Russia, g. Krasnodar, ul. Krasina, 4

valleyigor@mail.ru

DOI:

10.25136/2644-5522.2018.5.27626

Дата направления статьи в редакцию:

09-10-2018


Дата публикации:

03-11-2018


Аннотация: Предметом исследования является подход к распределению ресурсов в условиях возможных деструктивных воздействий. Объектом исследования является модель процессов принятия решений распределительного характера в условиях возможных деструктивных воздействий. Авторы рассматривают вопросы моделирования процессов распределения потоков ресурсов в условиях возможных нежелательных воздействий. Показано, что применение относительных нечетких оценок предпочтения маршрутов передачи ресурсов целесообразнее моделирования всей области распределения ресурсов с точки зрения временной сложности процесса принятия решений, так как на основе статистических и экспертных оценок можно сравнительно быстро определить предпочтительности маршрутов с точки зрения гарантированности передачи ресурса при деструктивных воздействиях. Метод исследования базируется на использовании теории множеств, нечеткой логики, эволюционных и иммунных подходов. Использование нечетких отношений предпочтения позволяет сократить время построения модели, а применение эволюционных и иммунных методов – ускорить поиск решения. Основным выводом проведенного исследования является возможность использования относительных нечетких оценок предпочтения используемых маршрутов при организации распределения ресурсов. Предложен алгоритм распределения ресурсов в условиях деструктрвных воздействий, отличительной чертой которого является использование информации о реализованных ранее распределениях ресурсов при формировании множества начальных решений. Верификацию полученных решений предполагается производить при помощи метода отрицательного отбора – одного из способов моделирования иммунной системы. Модификацию имеющихся решений целесообразно производить, например, при помощи методов эволюционного моделирования.


Ключевые слова:

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

Работа выполнена при поддержке РФФИ, проекты №: 16-01-00390, 16-01-00391, 18-01-00314

Abstract: The subject of research is the approach to the allocation of resources in terms of possible destructive conditions.The object of the research is a model of decision-making processes of a distributional nature under the conditions of possible destructive influences. The authors consider the issues of modeling the processes of resource flow distribution under the conditions of possible undesirable effects. It is shown that the use of relative fuzzy estimates of resource transfer routes is more expedient than modeling the entire resource allocation area in terms of the time complexity of the decision-making process, since, based on statistical and expert assessments, route preferences can be quickly determined from the point of view of guaranteed resource transfer under destructive impacts. The research method is based on the use of set theory, fuzzy logic, evolutionary and immune approaches. The use of fuzzy preference relations reduces the time to build a model, and the use of evolutionary and immune methods to speed up the search for a solution. The main conclusion of the study is the possibility of using relative fuzzy estimates of the preferences of the used routes when organizing the allocation of resources. An algorithm for the allocation of resources in the context of destructive influences is proposed, a distinctive feature of which is the use of information about previously implemented resource allocations in the formation of a set of initial solutions. Verification of the solutions obtained is supposed to be carried out using the method of negative selection - one of the methods of modeling the immune system. Modification of existing solutions is advisable to produce, for example, using the methods of evolutionary modeling.


Keywords:

distribution, optimization, intellectual method, adaptation, modeling, decision making, fuzziness, evolution, immune approach, flows

Введение. Задачи оптимального распределения ресурсов особенно актуальны в условиях кризисных ситуаций, когда построение точных математических моделей затруднительно, а в ряде случаев – невозможно, например, по причине отсутствия достаточного количества объективной информации о предметной области. Проблематичным является построение моделей, учитывающих особенности районов бедствий или групп потребителей ресурсов, оказавшихся в специфических условиях [1]. Используемые для подобных целей цифровые карты местности, содержат информацию о рельефе и характере заполнения определенного региона (растительность, водное пространство, строения и т.д.). Чем выше разрешение карты, тем выше точность расчетов и больше размер файлов карты [2]. Таким образом, организуя распределение ресурсов в некоторой проблемной области, в условиях возможных нежелательных воздействий, необходимо говорить о построении многокритериальной и многопараметрической модели, содержащей информацию о рельефе местности, особенностях распределяемых ресурсов и потребителях данного ресурса, топологии распределительной сети, структуре и параметрах нежелательных воздействий и т.д.

Описание проблемной области. Характер распределяемых ресурсов и смысл оптимальности может быть различным в зависимости от рассматриваемой прикладной области и конкретной задачи. В силу того, что распределительные задачи принадлежат к классу NP-полных задач, создание эффективных методов их решения является актуальной проблемой [3-5].

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

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

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

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

Предлагаемый подход. По аналогии с [8] цель адаптации математической модели к реальной динамической ситуации можно описать как:

,

где L(Pmod,Pfact) - метрика близости оценок математического описания распределения Pmod и фактического распределения Pfact, ε – степень близости оценок, выше которой, располагается область эквивалентности данных оценок.

Таким образом, Pmod должна постоянно корректироваться на основе Pfact.

В соответствии с [9] величина потока, образованного передачей ресурса dk, определяется как:

,

где - Vk – среднее количество передаваемого ресурсаdk, Ik- интенсивность передачи ресурса dk.

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

где Tф – фактическое время передачи потока ресурсов Fk, X – множество узлов сети передачи ресурсов, U – множество ребер, M – множество маршрутов передачи ресурса при наличии воздействий, Ψ – воздействия внутреннего характера и Θ – воздействия внешнего характера.

Априорно определить точное влияние Ψ и Θ на процесс передачи ресурсов по предполагаемому маршруту mi из множества возможных маршрутов Mk в реальных динамических условиях проблематично.

По аналогии с [6,10,11] рассматривая множество маршрутов как некоторые конкурсные альтернативы, можно задать множество упорядоченных пар решений:

.

Тогда нечеткое отношение предпочтения маршрутов mi, mj можно задать кортежем .

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

На указанные отношения можно наложить ограничения следующего вида [11]:

- обратное ;

- равноценности ;

- строгое:

По указанной выше причине целесообразность передачи данных необходимо оценивать на основе функции:

где Tp – расчетное время передачи потока ресурсов Fk.

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

Структурная схема алгоритма распределения ресурсов в условиях возможных воздействий приведена на рисунке.

Рис. Структурная схема алгоритма распределения ресурсов в условиях воздействий

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

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

Предлагается использовать как успешные, так и неудачные результаты, полученные ранее при решении контекстно связанных задач, для повышения эффективности распределения ресурсов. Под контекстом принято понимать любую информация, которая может использоваться, чтобы характеризовать ситуацию объекта. Объект – человек, место, предмет, который относится к взаимодействию между объектами [12-14].

Заимствование решений подразумевает адаптивный перенос информации о реализованных ранее распределениях ресурсов. На основе заимствованных фрагментов, полученных ранее успешных решений контекстно связанных задач, предполагается формировать начальные решения текущей задачи. Известные эволюционные алгоритмы решения современных оптимизационных задач являются стохастическими (вероятностными) как с точки зрения времени поиска решений, так и с точки зрения получаемых результатов [15,16]. Подобные алгоритмы крайне зависимы от качества начальной популяции [15]. Вероятностный характер эволюционных алгоритмов поиска подразумевает получение как успешных (оптимальных или близких к оптимальным) результатов, так и наличие неудачных решений.

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

Модификацию имеющихся решений целесообразно проводить, например, при помощи методов эволюционного моделирования [15].

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

Библиография
1. Shell J, Coupland S. Fuzzy Transfer Learning: Methodology and Application// Preprint submitted to Information Sciences May 23, 2014.-27 p.
2. Панков С.Е., Петров В.Ф., Архипкин А.В., Гуреев А.В. Планирование радиопокрытия области применения РТК ВН как способ увеличения надежности и скрытности его функционирования Известия ЮФУ. Технические науки.-2018.-№ 1 (195).-С. 6-14.
3. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Распределение ресурсов на основе гибридных моделей роевого интеллекта // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 6. С. 1063–1073. doi: 10.17586/2226-1494-2017-17-6-1063-1073
4. Золотарев А.А. Методы оптимизации распределительных процессов. М.: Инфра-Инженерия, 2014. 160 с.
5. Brucker P. Scheduling Algorithms. 5th ed. Springer, 2007. 379 p.
6. Берштейн Л.С., Карелин В.П., Целых А.Н. Методы и алгоритмы принятия решений при четких и нечетких исходных данных: Учебное пособие. Таганрог: Изд-во ТРТУ, 2000. 92 с.
7. Серая О.В. Распределительная задача линейного программирования // Системы обработки информации. 2013. № 2 (109). С. 167–170.
8. Берштейн Л.С., Беляков С.Л., Боженюк А.В. Маршрутизация в условиях неопределенности с использованием нечётких темпоральных внешне устойчивых множеств// Известия ЮФУ. Технические науки. – 2013. – № 1 – С. 82-89.
9. Матвейкин И.В., Попов И.В. Определение основных параметров интегрированной модели обработки информации//IS-IT18: тр. Междунар. конгр. по интеллект. системам и информ. технологиям, п. Дивноморское, 2-9 сент. / ЮФУ. – Тананрог, 2018, Т.2, С.163-167.
10. Погонин В.А. Модели диспетчерского управления роботами// Информационные процессы и управление. – 2006. – № 1, С 45–55.
11. Жуковин В. Нечеткие многокритериальные модели принятия решений. Тбилиси: "Мецниереба", 1988.-71 с.
12. Dey A. Understanding and Using Context // Personal and ubiquitous computing. – 2001. – No. 5. – P. 4-7.
13. Dourish P. What we talk about when we talk about context // Personal Ubiquitous Comput. – 2004. – No. 8. – P. 19-30.
14. Bettini C., Brdiczka O., Henricksen K., Indulska J., Nicklas D., Ranganathan A., Riboni D. A survey of context modelling and reasoning techniques // Pervasive and Mobile Computing. – 2010. – No. 6. – P. 161-180.
15. Генетические алгоритмы/ Под ред. В.М. Курейчика.– 2-е изд., испр. и доп.-М.: ФИЗМАТЛИТ, 2006. – 320 с.
16. Агибалов О.И., Венцов Н.Н. Оценка зависимостей времени работы генетического алгоритма, выполняемого на CPU и GPU // Кибернетика и программирование. — 2017.-№ 6.-С.1-8. DOI: 10.25136/2306-4196.2017.6.24509. URL: http://e-notabene.ru/kp/article_24509.html
17. Искусственные иммунные системы и их применение /Под ред. Д. Дасгупты. Пер. с англ. под ред А.А. Романюхи. — М.: ФИЗМАТЛИТ, 2006. — 344 с.-ISBN 5-9221-0706-2
18. D. Dasgupta, S. Forrest. Novelty Detection in Time Series Data using Ideas from Immunology. Fifth International Conference on Intelligent Systems. Reno, Nevada: June, 1996
19. Чернышев Ю.О., Венцов Н.Н. Разработка декодеров искусственной иммунной системы, восприимчивых к нечетким командам // Кибернетика и программирование. — 2016.-№ 5.-С.213-221. DOI: 10.7256/2306-4196.2016.5.19885. URL: http://e-notabene.ru/kp/article_19885.html
References
1. Shell J, Coupland S. Fuzzy Transfer Learning: Methodology and Application// Preprint submitted to Information Sciences May 23, 2014.-27 p.
2. Pankov S.E., Petrov V.F., Arkhipkin A.V., Gureev A.V. Planirovanie radiopokrytiya oblasti primeneniya RTK VN kak sposob uvelicheniya nadezhnosti i skrytnosti ego funktsionirovaniya Izvestiya YuFU. Tekhnicheskie nauki.-2018.-№ 1 (195).-S. 6-14.
3. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Raspredelenie resursov na osnove gibridnykh modelei roevogo intellekta // Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki. 2017. T. 17. № 6. S. 1063–1073. doi: 10.17586/2226-1494-2017-17-6-1063-1073
4. Zolotarev A.A. Metody optimizatsii raspredelitel'nykh protsessov. M.: Infra-Inzheneriya, 2014. 160 s.
5. Brucker P. Scheduling Algorithms. 5th ed. Springer, 2007. 379 p.
6. Bershtein L.S., Karelin V.P., Tselykh A.N. Metody i algoritmy prinyatiya reshenii pri chetkikh i nechetkikh iskhodnykh dannykh: Uchebnoe posobie. Taganrog: Izd-vo TRTU, 2000. 92 s.
7. Seraya O.V. Raspredelitel'naya zadacha lineinogo programmirovaniya // Sistemy obrabotki informatsii. 2013. № 2 (109). S. 167–170.
8. Bershtein L.S., Belyakov S.L., Bozhenyuk A.V. Marshrutizatsiya v usloviyakh neopredelennosti s ispol'zovaniem nechetkikh temporal'nykh vneshne ustoichivykh mnozhestv// Izvestiya YuFU. Tekhnicheskie nauki. – 2013. – № 1 – S. 82-89.
9. Matveikin I.V., Popov I.V. Opredelenie osnovnykh parametrov integrirovannoi modeli obrabotki informatsii//IS-IT18: tr. Mezhdunar. kongr. po intellekt. sistemam i inform. tekhnologiyam, p. Divnomorskoe, 2-9 sent. / YuFU. – Tananrog, 2018, T.2, S.163-167.
10. Pogonin V.A. Modeli dispetcherskogo upravleniya robotami// Informatsionnye protsessy i upravlenie. – 2006. – № 1, S 45–55.
11. Zhukovin V. Nechetkie mnogokriterial'nye modeli prinyatiya reshenii. Tbilisi: "Metsniereba", 1988.-71 s.
12. Dey A. Understanding and Using Context // Personal and ubiquitous computing. – 2001. – No. 5. – P. 4-7.
13. Dourish P. What we talk about when we talk about context // Personal Ubiquitous Comput. – 2004. – No. 8. – P. 19-30.
14. Bettini C., Brdiczka O., Henricksen K., Indulska J., Nicklas D., Ranganathan A., Riboni D. A survey of context modelling and reasoning techniques // Pervasive and Mobile Computing. – 2010. – No. 6. – P. 161-180.
15. Geneticheskie algoritmy/ Pod red. V.M. Kureichika.– 2-e izd., ispr. i dop.-M.: FIZMATLIT, 2006. – 320 s.
16. Agibalov O.I., Ventsov N.N. Otsenka zavisimostei vremeni raboty geneticheskogo algoritma, vypolnyaemogo na CPU i GPU // Kibernetika i programmirovanie. — 2017.-№ 6.-S.1-8. DOI: 10.25136/2306-4196.2017.6.24509. URL: http://e-notabene.ru/kp/article_24509.html
17. Iskusstvennye immunnye sistemy i ikh primenenie /Pod red. D. Dasgupty. Per. s angl. pod red A.A. Romanyukhi. — M.: FIZMATLIT, 2006. — 344 s.-ISBN 5-9221-0706-2
18. D. Dasgupta, S. Forrest. Novelty Detection in Time Series Data using Ideas from Immunology. Fifth International Conference on Intelligent Systems. Reno, Nevada: June, 1996
19. Chernyshev Yu.O., Ventsov N.N. Razrabotka dekoderov iskusstvennoi immunnoi sistemy, vospriimchivykh k nechetkim komandam // Kibernetika i programmirovanie. — 2016.-№ 5.-S.213-221. DOI: 10.7256/2306-4196.2016.5.19885. URL: http://e-notabene.ru/kp/article_19885.html