Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

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

# 09, сентябрь 2015
DOI: 10.7463/0915.0800020
Файл статьи: SE-BMSTU...o144.pdf (1002.12Кб)
авторы: Монахов О. Г.1,*, Монахова Э. А.1, Токтошов Г. Ы.1

УДК 519.87+519.6+681.324

1 Россия,  Институт вычислительной математики и математической геофизики СО РАН

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

Список литературы
  1. Ловягин В.Ф. Геоинформационные технологии в инженерных изысканиях трасс линейных сооружений. Новосибирск: СГГА, 2010. 153 с.
  2. Райфельд В.Ф. Инженерно-геодезические работы при изысканиях линейных сооружений. М.: Недра, 1983. 143 с.
  3. Попков В.К. Математические модели связности / отв. ред. А. С. Алексеев. 2-е изд. Новосибирск: ИВМиМГ СО РАН, 2006. 490 с.
  4. Попков В.К., Токтошов Г.Ы., Юргенсон А.Н. Об одном подходе к оптимизации инфраструктуры инженерных сетей // Вестник СибГУТИ. 2012. № 3. С. 11-28.
  5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: пер. с англ. М .: Мир , 1982. 416 с . [Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Co., 1979.].
  6. Storn R., Price K. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces // Journal of Global Optimization. 1997. Vol . 11, no . 4. P . 341-359. DOI: 10.1023/A:1008202821328
  7. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с .
  8. Zaheer H., Pant M., Kumar S., Monakhov O., Monakhova E., Deep K. A new guiding force strategy for differential evolution // International Journal of System Assurance Engineering and Management. 2015. Vol. 6. P . 1-14. DOI: 10.1007/s13198-014-0322-6
  9. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ: пер. с англ . 2- е изд .  М .: Вильямс , 2006. 1296 с . [ Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms . 2nd ed. MIT Press and McGraw-Hill, 2001.].
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2018 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)