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

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

11 2 Ю.О. Чернышев , Н.Н.Венцов , И.С. Пшеничный

1 Донской государственный технический университет, Ростов-на-Дону 2Краснодарское высшее военное училище Аннотация: Показано, что в настоящее время актуальной остается проблема одновременной обработки динамических информационных массивов разной степени структурированности и нечеткости. Одним из прообразов математических моделей, содержащих подобные информационные структуры, являются задачи практического распределения ресурсов в условиях возможных, трудно формализуемых воздействий. Высокая степень неопределенности, свойственная рассматриваемому процессу, снижает целесообразность использования ресурсоемких алгоритмов распределения. В тоже время необходимо получение множества альтернативных решений, обладающих разнообразием, с точки зрения устойчивости к возможным воздействиям. Так как, если все маршруты будут проходить через один транзитный узел, то все они в равной степени будут подвержены угрозам воздействия, свойственным данному узлу, и при выходе его из строя будут отсутствовать альтернативные маршруты, что потребует повторного поиска маршрутов передачи ресурсов. Быстрые эвристики, основанные, например, на жадных подходах, не могут обеспечить должного разнообразия, поэтому, даже при четких формулировках оптимизационных задач, попадают в локальные оптимумы. По этой причине процедуру формирования начального решения целесообразно дополнить заимствованными решениями из ранее рассмотренных задач. В целях улучшения решений, полученных на этапе формирования стартовой популяции, и обеспечения разнообразия потомков этих решений, описывающих маршруты передачи ресурсов, разработан эволюционный алгоритм нахождения множества подкратчайших по времени маршрутов передачи ресурсов. Особенностью процесса решения рассматриваемой задачи предложенным алгоритмом является поддержание разнообразия популяции решений с учетом возможных угроз.

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

Введение

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

условиях обстановки, когда существуют угрозы деструктивных воздействий, отношения предпочтения, в соответствии с которыми выбирают рациональные маршруты передачи ресурсов по транспортной сети, не всегда можно описать или задать функцией полезности. Это особенно имеет место, когда информация об относительной важности отношений доминирования угроз имеет нечеткий, противоречивый характер[3-5]. Если объект или процесс изменяется непредвиденным образом, то в момент принятия решения может отсутствовать адекватная математическая модель. В такой ситуации применяют процедуру идентификации - синтез адекватной объекту (процессу) модели [6]. Также проблематично построить математическую модель, адекватно отражающую особенности процесса распределения ресурсов в нестандартных ситуациях, по причине отсутствия объективной информации о предметной области. Поэтому, может оказаться целесообразным адаптивное заимствование нечеткой информации о моделируемой предметной области из решенных ранее задач, для построения актуальной на данный момент времени, модели распределения ресурсов [79].

Формализация проблемной области

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

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

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

В подобных ситуациях оптимизация распределительного процесса может быть выполнена с учетом функции [10]:

Г\Х,и,М, /'А, 21, 22)-^тт,

где Т - расчетное время передачи потока ресурсов Гк,Х - множество узлов сети передачи ресурсов, и - множество ребер,М - множество маршрутов передачи ресурса при наличии угроз, 21- кортеж, описывающий

нечеткое отношение предпочтения маршрутов, с точки зрения имеющихся угроз, ¿2-кортеж, описывающий нечеткое отношение предпочтения

важности угроз.

Целесообразность использования кортежа 21 обуславливается тем, что

на основе статистических и экспертных оценок можно сравнительно быстро определить отношения предпочтения ф^т^т]) маршрутов mi и т] с точки зрения устойчивости передачи ресурсов при возможном воздействии р^^и©), где ¥ - воздействия внутреннего, по отношению к системе распределения, характера, а © - внешнего. Кортеж II содержит

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

относительные оценки опасности воздействий р(; и рч, заданные матрицей м(Рв,Рд), РеР е(¥иЭ).

В приведенной формуле X, и, М, ^ - четкие параметры математической модели, а , - нечеткие. На основе четких параметров

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

В таком случае, расчетное время доставки можно оценить по формуле:

Т&Т\Х, и, М, ^)+Тн(М, , ),

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

Предлагаемый подход

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

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

Известным является определение контекста, предложенное в работе [11]: «Контекст - любая информация, которая может использоваться, чтобы характеризовать ситуацию объекта. Составляющими контекста являются [1113]: информация, поведение, вариация.

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

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

Рис. 1 Контекстные связи задач

задачи. Поэтому, целесообразным является процесс заимствования потенциально пригодных решений и формирования на их основе стартовой популяции решенийМ1, с последующим применением интеллектуальных методов для улучшения начальной популяции. Для улучшения начальных решений на практике эффективно используются генетические алгоритмы (ГА) [14-17].

Современные ГА манипулируют популяцией хромосом на основе механизма натуральной эволюции. Полное формальное определение ГА приведено в [18,19], рассмотрим его основные элементы:

,

гдеР - исходная популяция решений; N - мощность популяции, т.е. число

tp tp

входящих в нее решений; Р; й £ Pi - к-ое решение, принадлежащее /-ой

популяции, находящейся в T поколении эволюции; T = 0,1,2,... - номер поколения, проходящего популяцией во время эволюции; A - произвольный абстрактный алфавит, в котором кодируются хромосомы; (ЦФ,ОГР,ГУ) -целевая функция, ограничения и граничные условия, которые определяются на основе заданной модели исходной решаемой задачи; ГО - генетические операторы; k - критерий окончания работы ГА.

В рассматриваемом случае исходная популяция Р формируется на

основе множества М1.

В настоящее время разработано большое количество интеллектуальных алгоритмов, в том числе и для решения транспортных задач [20-22]. Большая часть подобных алгоритмов решает классические экстремальные задачи, многие из которых сводятся к нахождению наикратчайших или критических маршрутов. Особенностью решаемой задачи является то, что полученный результат будет в дальнейшем использован для получения итогового

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

- число элементов множества не должно быть избыточным, чтобы не затягивался процесс оценки относительных предпочтений;

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

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

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

и

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

КОНЕЦ

Рисунок 2 - Структура алгоритма нахождения множества подкратчайших по

времени маршрутов передачи ресурсов

При работе алгоритма (рис.2) полученное в стартовой популяции множество решений (блок 1), по рациональному направлению маршрутов передачи ресурсов, разбивается (копируется) на п подпопуляций (блок 2). К каждой из подпопуляций применяются генетические операторы со специфическими вероятностными характеристиками, также различной стратегией формирования новых особей на основе существующих: способы селекции решений внутри каждой из подпопуляций, вероятность выбора точек кроссинговера, вероятность применения оператора мутации (блоки 3-

5). Блок 6 проверяет выполнение критерия остановки для каждой подпуляции.

Блоки 7 и 9, по аналогии с [20], осуществляют контроль разнообразия внутри каждой подпопуляции, а также внутри всей популяции, с использованием показателя разнообразия в подпопуляции и его сравнение с показателем разнообразия среди всех подпопуляций. Для этого применяется нечеткое понятие «степень разнообразия популяции», представляемое нечетким множеством Я = {очень низкая степень, низкая степень, средняя степень, высокая степень, очень высокая степень}. Если популяция стремится к вырождению (очень низкая степень разнообразия), то для предотвращения вырождения используется оператор миграции. Для каждой популяции составляется таблица, описывающая подверженность маршрута угрозам.

Таблица. Подверженность маршрутов угрозам

№ п/п Маршрут Воздействия

1 mi Уу,^и, ФфФа

2 УхЖ, Фg

В приведенной таблице для каждого маршрута т^ анализируемого ГА, определены наиболее критические угрозы. Для представленных в таблице угроз справедливы условия:у№, Фч,Фа, Ф^ Ф^.

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

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

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

Заключение

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

Благодарности

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

Литература

1. McNulty Eileen. Understanding Big Data: The Seven V's, Dataconomy (22 May 2014) URL: dataconomy.com/2014/05/seven-vs-big-data/ (date of access: 17/12/18).

2. Laney Doug. 3D Data Management: Controlling Data Volume, Velocity, and Variety. MetaGroup(6February 2001), 2001. - 4 p.

3. Подиновский В. В. Потенциальная недоминируемость в задачах выбора нескольких лучших вариантов // Вестник Московского университета им. С.Ю. Витте. Серия 3: Образовательные ресурсы и технологии. 2013. №2. С. 57-63.

4. Жуковин В. Е. Нечеткие многокритериальные модели принятия решений. Тбилиси: Мецниереба, 1988. 71 с.

5. Берштейн Л.С., Карелин В.П., Целых А.Н. Методы и алгоритмы принятия решений при четких и нечетких исходных данных. Таганрог: ТРТУ, 2000.92 с.

6. Лебедев Б.К. Адаптация в САПР. Таганрог: ТРТУ, 1999. - 160 с.

7. Shell J, Coupland S. Fuzzy Transfer Learning: Methodology and Application// Preprint submitted to Information Sciences May 23, 2014. 27 p.

8. Чернышев Ю.О., Венцов Н.Н., Долматов А.А. Способ переноса данных между контекстно связанными задачами на основе PSO-метода // Известия ЮФУ. Технические науки. 2017. №7.С. 154-162.

9. Чернышев Ю.О., Венцов Н.Н., Долматов А.А. Реконфигурируемый агент в нечетком гетерогенном пространстве решений // Инженерный вестник Дона, 2017, № 2. URL: ivdon.ru/ru/magazine/archive/N2y2017/4163

10. Чернышев Ю.О., Венцов Н.Н., Пшеничный И.С. Возможный способ распределения ресурсов в условиях деструктивных воздействий // Кибернетика и программирование. 2018. №5.С. 1-7.

11. Dey A. Understanding and Using Context // Personal and ubiquitous computing. - 2001. - No. 5. - pp. 4-7.

12. Dourish P. What we talk about when we talk about context // Personal Ubiquitous Comput. - 2004. - No. 8. - pp. 19-30.

13. 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. - pp. 161-180.

14. Holland John H. Adaptation and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975. - 183 p.

15. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989. - 432 p.

16. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991. - 385 p.

17. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.3, Washington, USA, CRC Press, 1999. - 592 p.

18. Курейчик В.М. Гибридные генетические алгоритмы // Известия ЮФУ. Технические науки Тематический выпуск "Интеллектуальные САПР". 2007. №2. С. 5-12.

19. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. 2 изд. Ростов-на-Дону: Ростиздат, 2004. 320 с.

20. Кшын Д.С., Курейчик В.М. Параллельный генетический алгоритм с нечетким оператором миграции // Искусственный интеллект. 2010. №3. С. 73-80.

21. Чернышев Ю.О., Басова А.В., Полуян А.Ю. Решение задач транспортного типа генетическими алгоритмами. Ростов-на-Дону: ЮФУ, 2008.87 с.

22. Ляшов М.В., Береза А.Н., Коцюбинска С. А. Аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов // Инженерный вестник Дона, 2018, №4 URL: ivdon.ru/ru/magazine/archive/n4y2018/5259

References

1. McNulty Eileen. Understanding Big Data: The Seven V's, Dataconomy (22 May 2014). URL: dataconomy.com/2014/05/seven-vs-big-data/ (accessed 17/12/18).

2. Laney Doug. 3D Data Management: Controlling Data Volume, Velocity, and Variety. Meta Group (6 February 2001), 2001. 4 p.

3. Podinovskiy V. V. Vestnik Moskovskogo universiteta im. S.Yu. Vitte. Seriya 3: Obrazovatel'nye resursy I tekhnologii. 2013. №2. PP. 57-63.

4. Zhukovin V. E. Nechetkie mnogokriterial'nye modeli prinyatiya resheniy [Fuzzy multi-criteria decision-making models]. Tbilisi: Metsniereba, 1988. 71 p.

5. Bershteyn L.S., Karelin V.P., Tselykh A.N. Metody I algoritmy prinyatiya resheniy pri chetkikh I nechetkikh iskhodnykh dannykh [Methods and algorithms of decision making in crisp and fuzzy input data]. Taganrog: TRTU, 2000. 92 p.

6. Lebedev B.K. Adaptatsiya v SAPR [Adaptation in CAD]. Taganrog: TRTU, 1999. 160 p.

7. Shell J, Coupland S. Preprint submitted to Information Sciences May 23, 2014. 27 p.

8. Chernyshev Yu.O., Ventsov N.N., Dolmatov A.A. Izvestiya YuFU. Tekhnicheskie nauki. 2017. №7. p. 154-162.

9. Chernyshev Ju.O., Vencov N.N., Dolmatov A.A. Inzenernyj vestnik Dona (Rus), 2017, №2 URL: ivdon.ru/ru/magazine/archive/N2y2017/4163

10. Chernyshev Ju.O., Vencov N.N., Pshenichnyj I.S. Kibernetika I programmirovanie. 2018. №5. pp. 1-7.

11. Dey A. Personal and ubiquitous computing. 2001. No. 5. pp. 4-7.

12. Dourish P. Personal Ubiquitous Comput. 2004. No. 8. pp. 19-30.

13. Bettini C., Brdiczka O., Henricksen K., Indulska J., Nicklas D., Ranganathan A., Riboni D. Pervasive and Mobile Computing. 2010. No. 6. pp. 161-180.

14. Holland John H. Adaptation and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975. 183 p.

15. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989. 432 p.

16. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991. 385 p.

17. Practical Handbook of Genetic Algorithms. Editor I. Chambers. V.3, Washington/USA, CRC Press, 1999. 592 p.

18. Kurejchik V.M. Izvestija JuFU. Tehnicheskie nauki Tematicheskij vypusk "Intellektual'nye SAPR". 2007. №2. pp. 5-12.

19. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithm]. 2izd. Rostov-na-Donu: Rostizdat, 2004. 320 p.

20. Kshyn D.S., Kurejchik V.M. Iskusstvennyj intellekt. 2010. №3. pp. 73-80.

21. Chernyshev Ju.O., Basova A.V., Polujan A.Ju. Reshenie zadach transportnogo tipa geneticheskimi algoritmami [The solution of problems of the transportation type genetic algorithms]. Rostov-na-Donu: JuFU, 2008. 87p.

22. Ljashov M.V., Bereza A.N., Kocjubinska S.A. Inzenernyj vestnik Dona (Rus), 2018, № 4 URL: ivdon.ru/ru/magazine/archive/n4y2018/5259