Автореферат (792663), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Выбор данного примераобусловлен ограниченным объемом автореферата. Разработанные алгоритмымогут быть использованы для различных схем станции. В диссертацииприведены стадии преобразования информации для двух-трёх-четырёх-шести–стрелочных станций, существующих на Московском метрополитене.Мощность множества вершин «уплотненного» графа совпадает смощностью множества вершин исходного графа. Мощность множества ребер«уплотненного» графа превышает мощность множества ребер исходного графав 3-5 раз.Каждая третья или четвертая вершина дерева является стоком дерева.Число стоков равно числу возможных последовательностей заполнения илиосвобождения указателей ночной расстановки составов. Мощность множествавершин дерева растёт с увеличением числа стрелочных переводов на станции иможет превышать числа вершин исходного графа в 1000 раз.

При переходе отдвух стрелочных переводов к трем или четырем мощности множеств,описывающих деревья, увеличиваются на порядок, а при переходе к шестистрелочным переводам – еще в 30 раз.Информация, представленная в форме графов, может быть такжепредставлена в форме таблиц. Разработан алгоритм, позволяющий преобразоватьматрицу смежностей графа, полученного после удаления вершин,соответствующих стрелочным переводам, в матрицу смежностей «уплотненного»графа, что иллюстрирует Рисунок 4.

Исходный граф является подграфомуплотненного. Ребра, добавленные в граф в ходе перехода от исходного графа куплотненному, выделены пунктиром. Схема алгоритма представлена на Рисунке 5.Разработанные алгоритмы включены в состав программного обеспеченияавтоматизированной системы «АРМ Графиста – 2.0». Показано соответствиерезультатов работы созданных алгоритмов данным реальных ПГД, частныйпример которого представлен на Рисунке 6.В четвертой главе представлена процедура построения прототипа ГО ирезультаты ее исполнения.В процессе автоматизированного построения ПГД и ГО первымподпроцессом, реализующим преобразование данных, является подпроцесспостроения прототипа ГО.Рисунок 3 –Стадии преобразования информации для двухстрелочной станции1112а)N6N7N8Станция AN5б)N4N3в)00000000г)00000000N1N21000000001000000001000000001000000100000000001000000001010000000010000000010011100010111001110000001110000011010Рисунок 4 – Организация ночной расстановки составов.

а – схема организацииночной расстановки составов на станции; б – «уплотненный» графпоследовательностей заполнения или освобождения указателей ночнойрасстановки составов; в – матрица смежностей графа, полученного после удалениявершин, соответствующих стрелочным переводам; г – матрица смежностей«уплотненного» графа131.Начало процедуры «Просмотр строк»2.Выбор строки матрицы, котораясоответствует истоку графа3.Формирование множества номеровнепройденных строк4.5.НетВ строке только одна единица ?ДаУдаление из множества номеровнепройденных строк номера текущейстроки6.Переход к строке, номер которой равенномеру столбца, содержащему единицув текущей строке7.Cоставление множества номеровстолбцов, содержащих единицы8.Составление всех возможныхразмещений по 2 элемента этогомножества9.Запись единиц в ячейки, положениекоторых определяется полученныминаборами индексов10.Цикл по всем строкам, номера которыхравны номерам столбцов, содержащихединицы в текущей строкеРекурсивный вызов длястроки, являющейсяпараметром цикла11.Просмотр строк12.Цикл по всем строкам, номера которыхравны номерам столбцов, содержащихединицы в текущей строке13.14.Множество номеровнепройденных строк пустоеНетДаКонец процедуры «Просмотр строк»Рисунок 5 – Алгоритм преобразования матрицы смежностей графа14Рисунок 6 – Последовательность заполнения указателей ночной расстановки врамках ПГД для конечной шестистрелочной станции и «уплотненный» граф,полученный на основе информации для шестистрелочной станции.

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

Оценка сверху мощности множества9полученных вариантов построения ГО имеет порядок 10 . Их перебор требуетзначительных затрат времени. Поэтому актуальной является задача сокращениявремени, затрачиваемого на построение прототипа ГО. Эта задача приобретаетособую актуальность в связи с тем, что в процессе согласования ПГД и ГО можетвозникнуть задача неоднократной модификации прототипа ГО с учетом измененияисходных данных. В связи с этим в ходе выполненных автором исследований длярешения задачи был применен ГА.Ключевыми моментами использования ГА являются: описание хромосомы (вариант построения ГО, в котором каждомуремонту, который должен быть выполнен, поставлен в соответствие кандидат,который задает место и время его проведения); определение фитнес-функции (критерия выбора рационального решения)для каждой хромосомы в популяции (множество вариантов построения ГО,рассматриваемое на итерации эволюции); создание способов кроссинговера (основной генетический оператор, засчет которого производится обмен генетическим материалом между особями; внашем случае – изменение номера кандидата, который назначен длявыполнения ремонта), учитывающих особенности поставленной задачи.Выбор фитнес-функции определяет множество аллелей (состояния генов(ген – кандидат, назначенный для выполнения ремонта), занимающих одни и теже локусы (локус – один из ремонтов, который должен быть выполнен и задаетодин элемент хромосомы) в хромосомах; в нашем случае – один из кандидатов,которые могут быть назначены для выполнения ремонта).Если необходимое условие достаточности ресурсов при построения ГОвыполняется, и фитнес-функция отражает равномерность проведения осмотров, тов качестве множества аллелей выступает множество кандидатов, доступных дляисполнения осмотров.В этом случае в качестве критерия рационального планирования графикаоборота RR может быть выбран минимум среднего значения квадратаотклонения времен начала осмотра для кандидата, используемого дляпроведения осмотра, от желаемых времен начала проведения осмотра:  cN C ci :N rRR i 1: l j : t des  c i : l j : k : t b 2ij 1N r  1 min ,(1)где c – это кортеж, называемый «цепочка» и описывающий поведение состава смомента его выхода из депо до момента захода состава в депо;c : N r – необходимого числа осмотров внутри цепочки;N C – количество цепочек;16l– это кортеж, называемый «звено» и описывающий поведение состава смомента его выхода из депо до момента захода на осмотр, с момента выхода изосмотра до момента захода в депо или между двумя осмотрами;c i : l j : t des – желаемое время начала проведения осмотра, которое следует зазвеном c i : l j (время начала осмотра, при выполнении которого все осмотрывнутри цепочки отстоят один от другого на одинаковые промежутки времени);c i : l j : k – это кортеж, называемый «кандидат» и описывающий ресурсы,используемые для проведения осмотра, соответствующего звену c i : l j ;c i : l j : k : t b – время начала осмотра для кандидата c i : l j : k ;N r– сумма необходимого числа осмотров внутри всех рассматриваемыхцепочек.Использование этого критерия предполагает, что для каждого иззадействованных в плане кандидатов и для каждого звена выполняютсяограничения на выбор места проведения осмотра и периодичность проведенияосмотров.

В противном случае устанавливается «штрафное» значение критерияRR , многократно превышающее значение r : P  N r , где r : P – допустимыйинтервалвременимеждудвумяосмотрами;NCN r   c i : N r –суммаi 1необходимого числа осмотров внутри всех рассматриваемых цепочек.Необходимым условием наличия достаточных ресурсов для построенияГО ЭПС для ситуации, когда составы находятся в движении с момента подачинапряжения на контактный рельс и до момента окончания движения по линии,является превышение числа кандидатов N k над суммой необходимого числаосмотров внутри всех рассматриваемых цепочек N r или равенство этихвеличин:N k  N r(2)Если это условие не выполняется, то в качестве фитнес-функциииспользуется сумма квадратов превышений времени между ремонтами наддопустимым интервалом времени между двумя осмотрами.При построении прототипа ПГД предполагается, что составы находятся вдвижении с момента подачи напряжения на контактный рельс и до моментаокончания движения по линии.

Характеристики

Список файлов диссертации