The 8 reference contexts in paper E. Monakhova A., G. Toktoshov Y., O. Monahov G., Г. Токтошов Ы., О. Монахов Г., Э. Монахова А. (2016) “Алгоритм дифференциальной эволюции в задачах оптимизации маршрутов прокладки инженерных сетей // Differential Evolution Algorithm for Route Optimization Problems of Engineering Networks” / spz:neicon:technomag:y:2015:i:9:p:135-144

  1. Start
    1802
    Prefix
    эволюции, минимальная стоимость инженерных сетей Введение и постановка задачи Эффективность функционирования будущей сети (газо-, водо-, и теплоснабжения, сети связи и линии электропередач, автомобильные или железные дороги и т.д.) зависит от многих факторов, среди которых значимыми являются: рельеф, инженерногеологические условия, ценность занимаемых земель и т.д.
    Exact
    [1, 2]
    Suffix
    . Эти параметры должны учитываться еще при выборе направления трассы для прокладки физических линий, а значит и до начала строительно-монтажных работ. Другими словами, заданная территория предопределяет структуру любой инженерной сети, от которой в значительной степени зависит экономическая целесообразность и техническая возможность построения сети на соответствующем месте или, наоборот, от в
    (check this in PDF content)

  2. Start
    5173
    Prefix
    В нашем случае, процесс построения инженерных сетей рассматривается как двухуровневая иерархическая система, состоящая из следующих подсистем:  выбор трассы для данного вида инженерной сети;  реализация (размещения) инженерной сети по соответствующим трассам. 1. Математическая модель Пусть пространственное взаиморасположение этих подсистем моделируется гиперсетью
    Exact
    [3]
    Suffix
    Определение 1. Гиперсеть ),,;,,(WFPRVXSвключает следующие объекты: X(,,...,)21nxxx − множество узлов; V(,,...,)21gvvv − множество трасс; R(,,...,)21mrrr− множество физических линий (труб, кабелей и т.п.
    (check this in PDF content)

  3. Start
    6286
    Prefix
    PS, назовем вложением графа WS в PS. rRW:2(())rFPr − отображение, сопоставляющее каждому элементу rR подмножество ))(()(rFPrW, где YrFP))(( − множество вершин в PS, инцидентных трассам VrF)(. Отображение Wопределяет граф вторичной сети );,(WRYWS. Здесь в качестве первичной сети );,(PVXPS рассматривается дискретный аналог области , полученной на основе сеточной технологии
    Exact
    [4]
    Suffix
    . Граф PS можно интерпретировать как сеть возможных (допустимых) трасс, у которого вершины X соответствуют узлам сетки, а ребра V– ветвям. Вторичная сеть );,(WRXYWS соответствует структуре проектируемой сети, у которого множества вершин Y разбито на два непересекающихся подмножества, т.е.
    (check this in PDF content)

  4. Start
    7573
    Prefix
    Таким образом, в задаче ищутся трассы )(rF, прокладка физических линий через которых обеспечивает минимальности суммарных затрат (1). Данную задачу можно рассматривать как частный случай задачи Штейнера, относящуюся к классу NP-трудных задач
    Exact
    [5]
    Suffix
    . Для решения таких задач применяются различные приближенные и эвристические методы. Для поиска оптимальной инженерной сети на заданной области в данной работе используется модифицированный алгоритм дифференциальной эволюции [6, 7, 8], адаптированный к прикладной задаче трассировки инженерных коммуникаций.
    (check this in PDF content)

  5. Start
    7798
    Prefix
    Для решения таких задач применяются различные приближенные и эвристические методы. Для поиска оптимальной инженерной сети на заданной области в данной работе используется модифицированный алгоритм дифференциальной эволюции
    Exact
    [6, 7, 8]
    Suffix
    , адаптированный к прикладной задаче трассировки инженерных коммуникаций. Пусть область размещения инженерной сети (территория) представлена цифровой моделью местности (ЦММ), в нашем случае, это будет взвешенная решетка (граф первичной сети) с выделенными вершинами-потребителями и вершиной-источником для данной инженерной коммуникации.
    (check this in PDF content)

  6. Start
    8816
    Prefix
    минимальное покрывающее дерево, полученное на взвешенном полном графе, вершины которого представляют собой заданные вершины-потребители и вершина-источник для данной инженерной коммуникации, а веса ребер - расстояния между заданными вершинами на взвешенном графе первичной сети. Для нахождения минимального покрывающего дерева на полном графе используется алгоритм Крускала или Прима
    Exact
    [9]
    Suffix
    , а для определения матрицы кратчайших путей на графе первичной сети - алгоритм Флойда - Уоршелла [9]. Найденное минимальное покрывающее дерево отображаем на граф первичной сети, при этом каждое ребро дерева отображается в кратчайший путь между соответствующими вершинами графа, и получаем, таким образом, дерево на графе первичной сети как начальное решение задачи минимизации
    (check this in PDF content)

  7. Start
    8912
    Prefix
    Для нахождения минимального покрывающего дерева на полном графе используется алгоритм Крускала или Прима [9], а для определения матрицы кратчайших путей на графе первичной сети - алгоритм Флойда - Уоршелла
    Exact
    [9]
    Suffix
    . Найденное минимальное покрывающее дерево отображаем на граф первичной сети, при этом каждое ребро дерева отображается в кратчайший путь между соответствующими вершинами графа, и получаем, таким образом, дерево на графе первичной сети как начальное решение задачи минимизации суммарных затрат для данной инженерной коммуникации.
    (check this in PDF content)

  8. Start
    9654
    Prefix
    Для поиска координат ДТ с целью оптимизации затрат для инженерной сети на заданной области используется следующий алгоритм дифференциальной эволюции. 2. Алгоритм дифференциальной эволюции Алгоритм дифференциальной эволюции
    Exact
    [6, 7, 8]
    Suffix
    основан на моделировании процесса естественного отбора в популяции особей, каждая из которых представлена точкой в пространстве решений задачи оптимизации. Особи представлены структурами данных Gen - векторами (точками в k-мерном пространстве, в котором определена целевая функция), включающими свободные (неопределенные) параметры kp дерева TS: Gen{}{,,...,},021kpppPk.
    (check this in PDF content)