Диссертация (792664), страница 14
Текст из файла (страница 14)
Это условиевключает в себя проверку истинности логических утверждений, связанныхфункцией логического сложения, которые можно разделить на следующиегруппы: ограничение на продолжительность работы алгоритма, превышеноограничение по времени работы или максимальному числу поколений; на значение и скорость изменения фитнес-функции; значения фитнес-функции достигло предельное (минимальное илимаксимальное) значение; значение фитнес-функции изменяется медленнее допустимого(относительное изменение, средне-квадратическое изменение иликакой-то более сложный критерий оценки скорости измененияфитнес-функции меньше допустимого порога); их комбинация – значение фитнес-функции не изменяется на протяжениипромежутка времени, превышающего допустимый.4.3ВходеРезультаты построения прототипа ГОдиссертационногоисследованиясиспользованиемпакетаприкладных программ для решения задач технических вычислений MATLABразработано программное обеспечение системы поддержки принятия решения(СППР), реализующей ГА применительно к решению задачи построения ГО [159]117[160].
На Рисунке 4.14 представлен интерфейс разработанной СППР. СППРадаптируется к особенностям задачи путем:–расширения множества фитнес-функций, которые могут быть вычисленына основе знаний о параметрах множества аллелей;–считывания информации о множестве аллелей и структуре хромосомы извнешнего файла;–выбора типа кроссинговера и числовых параметров ГА.Рисунок 4.14 – Интерфейс СППРРезультаты выполненного для одной из линий Московского метрополитенапо формуле (4.7) расчета вероятности того, что случайный набор хромосом будетсодержать все возможные значения аллелей в выбранном локусе представлены наРисунке 4.15 и в Таблице 4.3. В рассматриваемом случае = 38, = 13.118Рисунок 4.15 – Вероятность того, что случайный набор хромосом будет содержатьвсе возможные значения аллелей в выбранном локусеРезультаты выполненного для одной из линий Московского метрополитенапо формуле (4.8) расчета вероятности того, что все локусов будут содержатьполный набор аллелей каждый представлены на Рисунке 4.16 и в Таблице 4.3.Рисунок 4.16 – Вероятность того, что все локусы будут содержать полный набораллелей каждый119Результаты выполненного для одной из линий Московского метрополитенапо формуле (4.8) расчета вероятности того, что какой-либо из локусов не будетсодержать полный набор аллелей представлены на Рисунке 4.17.Рисунок 4.17 – Вероятность того, что какой-либо из локусов не будет содержатьполный набор аллелей равнаТаблица 4.3 – Результаты расчетов вероятностей того, что случайный наборхромосом будет содержать все возможные значения аллелей в выбранном локусе1 и все локусы будут содержать полный набор аллелей каждый N405060708090100110120p15,73E-201,83E-141,07E-116,35E-101,15E-081,01E-075,52E-072,17E-066,69E-06p Na7,21E-2512,63E-1792,33E-1432,74E-1206,01E-1041,13E-914,43E-822,34E-745,36E-68На Рисунках 4.18-4.23 представлены результаты построения ГО для однойиз линий Московского метрополитена с использованием разработанной СППР.120На Рисунке 4.18 представлены результаты построения ГО для случая, когданеобходимое условие наличия достаточных ресурсов для построения ГО ЭПС(4.4) выполняется и фитнес-функция в виде (4.2) отражает равномерностьразмещенияТО.РисунокпозволяетсравнитьГО,соответствующийиспользуемому на Московском метрополитене ПГД, и предложенный прототип.Данные о реальных осмотрах приведены в виде синих прямоугольников, а опредложенных – в виде зеленых прямоугольников.
Анализ приведенных данныхпоказал следующее. Осмотры в рамках используемого на метрополитене ПГД проводятсячаще, чем это требуют условия безопасности. На рассматриваемом графике их 20(каждый заход в депо в течение дня с последующим выходом в тот же деньсопровождается осмотром, если не оговорено обратное), а в соответствии стребованиями безопасности их должно быть 13.
Это связано с тем, что на линииимеются достаточные ресурсы для проведения осмотров и в дневной час-«непик»количество составов на линии на треть меньше максимального. В используемом на метрополитене ПГД многие маршруты находятся вдвижении не с момента подачи напряжения на контактный рельс и не до моментаокончания движения по линии. Только треть маршрутов начинает движениераньше 6 утра или заканчивает позже часа ночи.В связи с этим имеет смысл рассматривать случаи наличия ограниченныхресурсов, то есть невыполнения необходимого условия построения ГО (4.4).Соответствующий ГО, при построении которого множество кандидатов, которыеможно использовать для проведения осмотров, было сокращено вдвое, приведенна Рисунке 4.19. Построение ПГД в этом случае возможно при учетенеобходимости уменьшения времени в движении между двумя осмотрами путемввода дополнительного отстоя, раннего ухода на ночную расстановку или болеепозднего выхода из нее, что нашло отражение на ГО.
Для поиска решенияиспользовался критерий (4.6), а «мнимый» осмотр попал на цепочку 10-14маршрутов. На этой цепочке должно размещаться при наличии необходимыхресурсов для построения ГО ЭПС выполняетсяРисунок 4.18 – Результаты построения ГО для случая, когда необходимое условие наличия достаточных121ресурсов три осмотра, а не два..ресурсов для построения ГО ЭПС не выполняетсяРисунок 4.19 – Результаты построения ГО для случая, когда необходимое условие наличия достаточных122123Данные,приведенныенаграфиках,позволяютпроанализироватьфункционирование различных алгоритмов кроссинговера. При одной и той женачальной популяции разные алгоритмы кроссинговера приводят к правильномурешению (признаком остановки работы алгоритма является то, что значениефитнес-функции изменяется медленнее допустимого) за разное количествоитераций, различающееся почти на треть.
При этом не всегда увеличение числаитераций приводит к уменьшению значения фитнес-функции, значения котороймогут различаться более, чем в два раза (Рисунок 4.20) [153].Рисунок 4.21 показывает, как меняется минимальное найденное значениефитнес-функции в ходе эволюции. График отражает зависимость десятичногологарифма наилучшего в популяции значения фитнес-функции от номераитерации. Такой способ представления выбран в связи с тем, что на первыхитерациях может сложиться ситуация, при которой популяция включает в себятолько такие варианты построения ГО, которые не отвечают ограничениям попериодичности проведения ТО, что приводит к резкому возрастанию значенийфитнес-функции, которая в этой ситуации приравнивается к значению штрафнойфункции [154]. Одновременно график показывает, как меняется в популяцииколичество хромосом, попадающих в область допустимых значений.
Такимобразом, при помощи ГА можно быстро найти некоторое множество допустимыхрешений, мощностью больше единицы, что важно при совместном построенииПГД и ГО [53].Рисунки 4.22-4.23 иллюстрируют зависимость параметров решения задачиот размера популяции. Из графиков видно, что увеличение размера популяцииприводит к тому, что при всех алгоритмах кроссинговера завершение работы ГАпроисходит после меньшего количества итераций.
При этом различие междуминимальными найденными значениями фитнес-функции при использованииразличных алгоритмов кроссинговера сокращается [155].124Минимальное найденное значение фитнесфункции, x 10-3количество итераций80706050Значение фитнесфункции4030Количество итераций20100Алгоритм кроссинговераРисунок 4.20 – Зависимость минимального найденного значения фитнес-функции4*lg(Мин.найденное значение.фитнесфункции),количество разрешенных вариантови выполненного количества итераций от алгоритма кроссинговера363126214*lg(Мин.значение.фитнесфункции)Количестворазрешенныхвариантов1611611 3 5 79 11 13 1517 1921 23 25 2729 31 33 3537 39 4143 45 4749 51Номер итерацииРисунок 4.21 – Зависимость десятичного логарифма минимальногонайденного значения фитнес-функции и количества разрешенных вариантов впопуляции от номера итерации125Минимальное найденное значение фитнесфункции4500040000Арифметический скаляр35000Арифметический векторЭвристический скаляр30000Эвристический векторПромежуточный скаляр25000РассеянныйОдноточечный20000Двухточечный15000405060708090100110120Размер популяцииРисунок 4.22 – Зависимость минимального найденного значения фитнесфункции от размера популяции и алгоритма кроссинговера85Количество итераций80Арифметический скаляр75Арифметический вектор70Эвристический скалярЭвристический вектор65Промежуточный скаляр60Промежуточный векторРассеянный55Одноточечный50Двухточечный45406080100120Размер популяцииРисунок 4.23 – Зависимость выполненного количества итераций от размерапопуляции и алгоритма кроссинговераПримером адаптации СППР к решению различных задач планированиядвиженияпоездовможетслужитьвозможностьиспользованияеедля126оптимизации ПГД в смысле выбранных критериев.
ПГД и ГО ЭПС, находятся втесной взаимосвязи, в первую очередь, с точки зрения выбора места и временипроведения ТО, а также способа организации ночной расстановки составов.В [96] рассмотрено решение задачи организации ночной расстановкисоставовпокритериюминимизациивремениокончаниядвиженияэлектропоездов. Кроме этого сравнение вариантов ПГД может проводиться потаким показателям, как:–количество разменов маршрутов через депо;–количество регулировочных отстоев на станционных путях линии;–суммарная длительность регулировочных отстоев;–средняя длительность регулировочных отстоев;–максимальная длительность регулировочных отстоев.Организация ночной расстановки составов предполагает установлениеоднозначного соответствия маршрутов указателям ночной расстановки составовна линии. В работе [151], авторы представили решение задачи построениясовокупности всех возможных вариантов организации ночной расстановки ЭПСна станции метрополитена, основываясь на теории графов [161].
Дальнейшееразвитие математического обеспечения решения этой задачи может быть связанос применением ГА для установления соответствия маршрутов точкам ночнойрасстановки. Так как количество маршрутов и указателей одинаковое, то любое издвух множеств может рассматриваться как множество аллелей и эффективнымимогут оказаться алгоритмы мутации, так как процесс кроссинговера фактическисводится к процессу мутации.127Основные выводы и результаты по главе1. Формализованыкроссинговера,способыучитывающиеописанияособенностифитнес-функции,аллелей,хромосомы,используемыхприорганизации работы генетического алгоритма для решения задачи построенияграфика оборота электроподвижного состава при выполнении и невыполнениинеобходимого условия построения ГО.2. Сформулирован способ определения размера первичной популяции инеобходимости мутаций на основе заданной вероятности того, что случайныйнабор хромосом будет содержать все возможные значения аллелей в выбранномлокусе.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
