Диссертация (792664), страница 12

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

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

Если значимым является разделение этого времени на98непродолжительные интервалы, то имеет смысл рассматривать квадратичныйкритерий: : (∑=1 ∑=0 { =2− : ) , если > : 0, если ≤ : (4.6)С∑=1 : + С − 1Введение нового критерия выбора рационального ГО ЭПС предполагаетмодификацию синтезированных ранее алгоритмов [53] [151].В статье [53] разработан рекурсивный алгоритм, который реализуетрешение задачи методом полного перебора. Выбор из полученного множестваназначений оптимального с точки зрения критерия (4.1) выполняется на базеаппарата дискретного варианта динамического программирования Беллмана[129]. В результате выполнения этого алгоритма получается ориентированныйграф вариантов ГО ЭПС.

Успешно построенному варианту ГО ЭПС в графесоответствует путь от истока до одного из стоков длиной ∑ .При использовании критериев (4.5) или (4.6) условие, накладываемое надлину пути от истока до одного из стоков для успешно построенного варианта ГОЭПС,перестаетбытьобязательным.Еслиреализованноеколичествообслуживаний внутри цепочки меньше необходимого:c i : N rr  c i : N r ,то в пути, соответствующем успешно построенному варианту ГО ЭПС, нанекоторых уровнях могут отсутствовать вершины и длина пути будет меньше∑ .Одновременно на каждом из уровней графа может увеличиться числовершин, так как использование критериев (4.5) или (4.6) предполагает, что длякаждого из задействованных в ГО ЭПС кандидатов и для каждого звенавыполняются ограничение на выбор места проведения ТО, однако требование на99периодичность проведения ТО (4.3) перестает быть обязательным, что расширяетмножество рассматриваемых вариантов назначений.Таким образом, задача построения прототипа ГО ЭПС формулируетсяследующим образом.

Найти способ организации ГО ЭПС, обеспечивающийминимум выбранного критерия оптимальности (выбор осуществляется извариантов, описанных формулами (4.1), (4.2), (4.5), (4.6) с учетом выполненияограничений (4.3) и (4.4)) для просмотренного множества вариантов организацииГО ЭПС, при условии, что весь ЭПС осуществляет движение по одной и той желинии метрополитена и имеет равные условия для проведения ТО.4.2 Построение прототипа ГО с использованием генетического алгоритма4.2.1Общая схема генетического алгоритмаНа Рисунке 4.5 представлена укрупненная схема ГА, решающего задачупостроения прототипа ГО.Блоком 1 – отмечено начало алгоритма.В блоке 2 – происходит инициализация исходных данных для работыалгоритма, которая включает в себя следующие действия [148]: загрузка описания хромосомы. Если необходимое условие наличиядостаточных ресурсов для построения ГО ЭПС (4.4) выполняется и фитнесфункция в виде (4.1) или (4.2) отражает равномерность размещения ТО, то вкачестве множества аллелей выступает множество кандидатов, доступных дляисполнения ТО.

Если необходимое условие наличия достаточных ресурсов дляпостроения ГО ЭПС (4.4) не выполняется и фитнес-функция (4.5) или (4.6)отражает превышение времени между ремонтами над допустимым интервалом1001Начало2Инициализация3Генерация первогопоколения4Вычисление фитнесфункции5Селекция6Кроссинговер7МутацияНет8Условие окончаниявыполняется?9ДаВизуализациярезультатов10КонецРисунок 4.5 – Схема ГА101времени между двумя обслуживаниями : , то в качестве множества аллелейвыступает расширенное множество кандидатов, мощность которого доведена дозначениясуммынеобходимыхколичествобслуживанийвнутривсехрассматриваемых цепочек ∑ путем включения в состав множества «мнимых»ремонтоввколичестве∑ − .ПрипостроениипрототипаПГДпредполагается, что составы находятся в движении с момента подачи напряженияна контактный рельс и до момента окончания движения по линии.

Припостроении ПГД превышение времени между ремонтами над допустимымзапрещено. Если в прототипе ГО, полученном для случая наличия ограниченныхресурсов, то есть при невыполнении необходимого условия построения ГО, естьтакое превышение, то при построении ПГД необходимо это учесть, то естьуменьшитьвремявдвижениимеждудвумяосмотрамипутемвводадополнительного отстоя, раннего ухода на ночную расстановку или болеепозднеговыходаизнее.Размещение«мнимого»осмотравлокусе,соответствующем некоторой цепочке, приводит к уменьшению на единицуреализованного количества обслуживаний внутри цепочки : , которое поумолчанию равно необходимому количеству обслуживаний внутри цепочки : ,и объединению звена, в котором размещен мнимый осмотр со следующим, то естьуменьшению количества звеньев в составе цепочки на единицу [153].

Этаинформация обобщена в Таблицах 4.1 и 4.2; загрузка данных для вычисления значения фитнес-функции; настройка параметров работы алгоритма (способа кроссинговера, размерапопуляции, максимального количества поколений без улучшений значенийфитнес-функции,точностиопределениязначенияфитнес-функции,максимального времени работы алгоритма и др.).В блоке 3 – случайным образом генерируется первое поколение популяции.В блоке 4 – производится вычисление значения фитнес-функции для каждойхромосомы.В блоках 5-7 – происходит формирование нового поколения, моделируется102процесс эволюции, который начался из популяции случайно сгенерированныхособей в блоке 3. Эволюция представляет собой итеративный процесс, на каждомшаге которого формируется новая популяция из следующих составляющих: особи с наилучшими значениями фитнес-функции, входящие в составтекущей популяции (блок 5); особи, полученные в результате кроссинговера особей, выбранных вкачестве родителей из состава текущей популяции (блок 6); особи, полученные в результате мутаций особей, выбранных в качестверодителей из состава текущей популяции (блок 7).Таблица 4.1 – Адаптация терминов ГА применительно к решаемой задачеТермин,заимствованныйиз генетикиПопуляция,поколениеОсобьХромосомаГенГенотипЛокусАллельФитнесфункцияМутацияКроссинговерЭволюцияАналогичный термин из решаемой задачимножество вариантов построения ГО, рассматриваемое наитерации эволюциисовпадает с хромосомой, так как особь описывается однойхромосомойвариант построения ГО, в котором каждому ремонту, которыйдолжен быть выполнен, поставлен в соответствие кандидат,который задает место и время его проведениякандидат, назначенный для выполнения ремонтахромосомапредставляетсобойупорядоченноеповыполняемымремонтаммножествокандидатов,используемых для реализации этих ремонтоводин из ремонтов, который должен быть выполнен и задаетодин элемент хромосомыодин из кандидатов, которые могут быть назначены длявыполнения ремонтацелевая функция, описываемая одним из выражений (4.1),(4.2), (4.5) или (4.6)изменение номера кандидата, который назначен длявыполнения ремонта, происходящее под влиянием внешнейили внутренней среды.изменение номера кандидата, который назначен длявыполнения ремонта, происходящее в результате обменагенетическим материалом между особями популяциипроцесс изменения множества рассматриваемых вариантовпостроения ГО103Таблица 4.2 – Определение множества аллелейНеобходимое Фитнесусловиефункцияналичиядостаточныхресурсов дляпостроенияГО ЭПСвыполняетсяневыполняетсяМножество аллелей Мощность Длинамножества хромосомаллелейыравномерностьпроведенияобслуживаниймножествокандидатов,доступныхисполненияобслуживанийпревышениевремени междуремонтами наддопустимыминтерваломвремени междудвумяобслуживаниямирасширенноемножествокандидатов,мощность которогодоведена до значениясуммы необходимыхколичествобслуживаний путемвключения в составмножества «мнимых»ремонтоввколичестве ∑ – .∑ ∑ ∑ дляВ блоке 5 – происходит упорядочивание популяции в порядке увеличениязначений фитнес-функции и формирование множества родителей, которыеучаствуют в процессе кроссинговера и мутаций и начинается формированиенового поколения путем включения в него особей с наилучшими значениямифитнес-функции.

Чем лучше значение фитнес-функции, тем у особи выше шансбыть выбранным в качестве родителя будущего поколения.В блоке 6 – дополняется новое поколение путем кроссинговера всоответствии с выбранным алгоритмом. Если ни один кроссинговер не былвыполнен, потомство является точной копией родителей.104В блоке 7 – дополняется новое поколение путем мутаций в соответствии свыбранным алгоритмом.В блоке 8 – проверяется условие окончания работы алгоритма. В случае,если условие окончания выполняется, происходит переход к блоку 9, а иномслучае – к блоку 4.В блоке 9 – выполняется визуализация результатов работы алгоритма.Блоком 10 – отмечено завершение алгоритма.4.2.2Определение размера первичной популяцииПроцесс настройки параметров работы ГА, описанного в п.

4.2.1, включаетв себя задание размера популяции, который определяет, сколько особейприсутствует в каждом поколении. Этот параметр, наряду с другими параметрамиалгоритма, как будет показано в п. 4.2, оказывает влияние на его работу. Прибольшом размере популяции ГА осуществляет поиск в пространстве решенийболее тщательно, уменьшая вероятность того, что будет найден лишь локальный,а не глобальный минимум. Вместе с тем, большой размер популяции приводит ктому, что алгоритм работать медленнее.Размер популяции может находиться в пределах [1, ( ! − )!], где –мощность множества аллелей, – длина хромосомы.Размер популяции !( − )!, определяемый формулой числа размещений аллелей по локусам – предельный случай, при котором ГА вырождается валгоритм полного перебора; а размер популяции 1 – вырожденный случай(случайный выбор любого значения и волюнтаристским образом объявление егооптимальным).Пусть размер популяции равен .

Наша цель – найти оптимальное значениеиз полного множества хромосом, поэтому набор хромосом должен содержать всезначения, необходимые для того, чтобы путем их рекомбинации можно было105получить любой из элементов полного множества. Для этого размер популяциидолжен быть таким, чтобы для каждого локуса во всей популяции былипредставлены все возможные значения аллелей.Рассчитаем вероятность того, что случайный набор хромосом будетсодержать все возможные значения аллелей в выбранном локусе. Вероятностьтого, что какой-либо один из локусов будет во всех хромосомах содержать одно ито же значение, равна1( ). В популяции полный набор аллелей в одном излокусов может присутствовать в случае, если ≥ . При этом в хромосомахзначения различаются, а в оставшихся принимают произвольные значения.

Числореализаций заполнения одноименного локуса в популяции, в которых хромосомыбудет содержать все возможные значения аллелей, в выбранном локусе,определяется следующим выражением:C NNa N a  C NNaNNa N a 1  C NN1N a N  1!N  1!,N  N a !N  1  N  N a ! N  N a !N a  1!−−где ̅ = +−– число сочетаний с повторениями N а аллелей в одном и −1том же локусе всех оставшихся после заполнения разными аллелями − хромосом, входящих в популяцию.Всего существует C NN  C NN  N 1 aaN a  N  1!вариантов заполнения одного иN !N a  1!того же локуса в популяции.

Тогда вероятность того, что случайный наборхромосом будет содержать все возможные значения аллелей в выбранном локусеравна:106N  1!Число благоприят ных событий  N  N a ! N a  1!p1 N a  N  1! Число всех событийN !N a  1!N  1! N !N a  1!N  1! N !N  N a !N a  1!N a  N  1! N  N a !N a  N  1!N a  N  1  N a ! N !АNNN   N  1     N  N a  1 NN  N a !N a  N  1! АN  N 1 N a  N  1  N a  N  2    NN  1    N  N a  1N a  N  1  N a  N  2    N  1aa(4.7)aгдеАNN a , АNNaa  N 1 – число размещений.Соответственно вероятность того, что все локусов будут содержатьполный набор аллелей каждый, равна:p N a   p1 Nс АN a   N aN  АN  N 1  aNс(4.8)Вероятность того, что какой-либо из локусов не будет содержать полныйнабор аллелей, равна:1  pN a АNN a 1  N АN a  N 1  aNc(4.9)4.2.3КроссинговерЭволюция начинается из популяции случайно сгенерированных особей ипредставляет собой итеративный процесс, на каждом шаге которого формируетсяновая популяция из следующих составляющих:107 особи с наилучшими значениями фитнес-функции, входящие в составтекущей популяции; особи, полученные в результате кроссинговера особей, выбранных вкачестве родителей из состава текущей популяции; особи, полученные в результате мутаций особей, выбранных в качестверодителей из состава текущей популяции.Действия кроссинговера и мутации могут выполняться в соответствии сразличными алгоритмами.Авторомисследованавозможностьпримененияразличныхтиповкроссинговера для решения задачи построения ГО.

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

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