FORMALIZING AND SOLVING WITH GENETIC ALGORITHMS THE VEHICLE ROOTING PROBLEM FOR INDUSTRIAL TRANSPORT

Abstract

Vehicle rooting problem for industrial transport is formalized as a mixed-integer zero-one problem. Specially de- signed genetic algorithms are used for solving the problem.

Full Text

Задача распределения транспортных ресурсов на предприятии состоит в установлении очередности обслуживания некоторых производственных объектов имеющимися транспортными средствами. комплектующих, доставляемых транспортными сред- ствами. В общем случае, условие выполнимости мар- шрута можно записать в виде некоторого ограничения image на элементы ( j ) 0, 1, Рассмотрим систему с n объектами x1, x2, …, xn и m k j l ³ j j = m . Введем в рассмотретранспортными средствами. Под маршрутом j-го транспортного средства k l j , j ние множество L всех выполнимых маршрутов системы. Тогда распределение транспортных средств сис- темы можно представить в виде задачи оптимизации: j = 1, 2, …, m будем понимать последовательность kj m элементов (производственных объектов) j x1 , x2 , ..., xk å k j ® max, j =1 в том порядке, в котором транспортное средство их обходит. Под выполнимым маршрутом понимается k j(l j ) ³ 0, j j = 1, 2, ..., m, k l j Î L, j j = 1, 2, ..., m. маршрут, обеспечивающий непрерывную работу включенных в него объектов, т. е. ситуация, в которой нет простоя оборудования объектов из-за отсутствия Каждый объект xi, i = 1, 2, …, n в некоторый момент времени характеризуется двумя числами (ti, йi), где ti - время достижения транспортным средством объекта xi; йi - допустимое время ожидания. Для про- изводства это время, в течение которого работа обо- рудования не прерывается благодаря имеющемуся запасу сырья и комплектующих. Точки x1, x2, …, xk (k ≤ n) образуют выполнимый маршрут lk длины k, если для всех i, i = 2, 3, …, k, име- Пусть максимальная длина выполнимого маршру- та установлена и равна p. Тогда составляем всевоз- можные сочетания из n элементов по p и формулиру- ем задачу минимизации среднего времени достижения объекта транспортным средством (при фиксированной длине маршрута): ет место условие i ti ³ åts , 1 n image å z j y j ® min, p j =1 (3) s =1 т. е. в выполнимом маршруте время возможного ожигде æ ö z j y j = ç ådij zi ti + t j ÷ z j время достижения j-го дания i-го элемента должно превосходить суммарное время посещения всех предшествующих элементов (выполнимый маршрут длины k обеспечивает беспе- ребойную работу всем k объектам). Задача распределения транспортных средств по è i ¹ j ø объекта транспортным средством. Если объект j не обслуживается (zj = 0), соответствующее время не на- ходим. Ограничения следующие: n выполнимым маршрутам сводится к следующей постановке. Найти такую систему маршрутов {l j }, å z j j =1 = p, j = 1, 2, ..., m , чтобы m k j z j (dij + d ji ) = z j , æ ö zitj ³ ç ådij zi ti + t j ÷ z j . åk j ® max, è i ¹ j ø j =1 i i å s j В зависимости от постановки практической задачи можно штрафовать за опоздание транспортного сред- ства - считать убыток от простоя оборудования или, t j ³ s =1 t j , i = 1, 2, ..., k , j = 1, 2, ..., m. Рассмотрим простой случай, когда имеется только одно транспортное средство. Тогда задача сводится к поиску максимального выполнимого маршрута lk, что приводит к решению следующей задачи: k ® max, наоборот, штрафовать за досрочный приход транспортного средства. Если ожидание объектом транс- портного средства возможно, но экономически невы- годно, т. е. приносит убытки, учитываем их, а мар- шруты с опозданием считаем при этом выполнимыми, т. е. допустимыми. i t i ³ åts , s=1 i = 1, 2, ..., k. (1) Пусть за единицу времени простоя j-го объекта берется штраф gj. Тогда Для нахождения максимальной длины выполнимо- го маршрута предлагается формулировка задачи (1) в виде задачи целочисленного математического проn å g j z j ( y j - t j ) j =1 sign ( y j - t j ) +1 image 2 ® min. (4) граммирования. Введем булевы переменные: Выражение sign ( y j - t j ) +1 image 2 = 1 , если y j > t j ; иначе dij = 1 , если объект i обслуживается ранее объекта j, sign ( y j - t j ) +1 = 0. dij = 0 , в противном случае, i = 1, n , image j = 1, n , i ¹ j; 2 z j = 1 , если объект j будет обслужен, тивном случае. z j = 0 в про- Ограничения следующие: z j (dij + d ji ) = z j , Тогда задача (1) может быть записана в виде n æ ö z j t j ³ ç ådij zi ti + t j ÷ z j , max å Z j (2) è i ¹ j ø при ограничениях: j =1 z j (dij + d ji ) = z j , æ ö æ ö z j y j = ç ådij zi ti + t j ÷ z j . è i ¹ j ø Это - задача смешанного целочисленного математи- ческого программирования (СЦП) так как yj - вещестz j t j ³ ç ådij zi ti + t j ÷ z j . è i ¹ j ø Если zj = 0, ограничения нет, т. е. соответствующий объект не обслуживается транспортным средством; в правой части каждого ограничения суммируется вре- мя достижения объектов, уже обслуженных до j-го. Задача включает n(n - 1) + n целочисленных булевых переменных. Число ограничений-неравенств не пре- восходит (n - 1) и зависит от численных значений па- раметров tijtj. венные переменные. При фиксировании булевых переменных получаем задачу линейного программиро- вания. Таким образом, получены формулировки практи- ческих задач в виде задач смешанного или полностью целочисленного программирования. Доказано, что задачи СЦП даже в линейном случае относятся к классу NP-полных задач [1]. Это означает, что для отыскания оптимального решения требуется экспо- ненциальное время, такие задачи по существу трудно решаемы с вычислительной точки зрения. Из этого, в частности, следует, что построение точных алгорит- мов является нецелесообразным, что, в свою очередь, приводит к необходимости разработки приближенных эвристических методов. Одним из перспективных подходов к решению задач СЦП является применение методов эволюционного поиска. В генетическом алгоритме используются механиз- мы, аналогичные тем, что существуют в природе - кодирование информации в линейные структуры и перераспределение этой информации при помощи специальных «генетических» операций. Алгоритм состоит из следующих шагов: инициализация популя- ции, оценка пригодности каждого индивида, селекция, скрещивание, мутация, проверка условия останова [2]. Далее шаги повторяются, начиная с оценки пригодно- сти. Опишем конкретную реализацию генетического алгоритма, использованного для решения описанной задачи. Выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако фор- мирование «хорошей» начальной популяции (напри- мер, из множества локальных оптимумов) может за- метно сократить время достижения глобального оп- тимума. В отсутствие априорной информации началь- ная популяция выбирается случайным образом; при этом генерируем не самого индивида, а его хромосому (бинарное представление), придавая каждому биту значение 0 или 1 с вероятностью Ѕ. Количество сгене- рированных хромосом соответствует заданной раз- мерности популяции. Затем осуществляется декоди- рование: каждой хромосоме ставится в соответствие индивид - возможное решение задачи. В нашем слу- чае все целочисленные переменные булевы, поэтому их представление используется впрямую: под каждую бинарную переменную отводится одна позиция. Под индивидом понимаем строку значений цело- численных переменных в решении задачи. Если два индивида допустимы (не нарушена система ограниче- ний), то в случае полностью целочисленной задачи они сравниваются по значению целевой функции (лучшему индивиду соответствует большее значение функции), при этом недопустимые индивиды могут быть сравнимы между собой по степени нарушений ограничений (любой допустимый индивид считается лучше любого недопустимого). В задаче СЦЛП стра- тегия решения основана на разделении переменных на множество целочисленных и вещественных. Целочис- ленные переменые фиксируются через эволюционную систему, в то время как вещественные определяются как функция от них через решение полученной задачи линейного программирования симплексным методом [3]. Если решение соответствующей задачи линейного программирования допустимо, то ее решение - оценка пригодности соответствующего индивида; иначе со- ответствующий индивид недопустим. Допустимые индивиды сравниваются по значению функции при- годности. В случае недопустимости индивида форму- лируем задачу линейного програмирования для мини- мизации этой недопустимости (т. е. суммы нарушений ограничений) и решаем полученную задачу симплекс- ным методом [4]. Посредством оператора селекции индивиды (хро- мосомы) выбираются для порождения потомков. Для имитации естественной селекции индивиды с более высокой пригодностью выбираются с большей веро- ятностью. Существует большое число различных мо- делей селекции, некоторые из которых не имеют био- логических аналогов. Большинство схем селекций, используемых в генетических алгоритмах, создают промежуточную популяцию и затем выбирают из нее случайным образом пары индивидов для скрещива- ния. В данном алгоритме реализован метод ранговой селекции. Все индивиды популяции ранжируются по пригодности. Каждому индивиду назначается вероят- ность быть отобранным для скрещивания, взятая из некоторого распределения. Созданное программное обеспечение позволяет использовать либо линейное распределение, либо отрицательное экспоненциаль- ное. Оператор селекции работает до создания проме- жуточной популяции заданной размерности. При этом существует возможность копирования и перехода в следующее поколение лучшего индивида (элитарная селекция). Основным порождающим оператором генетиче- ских алгоритмов считается оператор скрещивания (кроссовер, кроссинговер). Кроссовер заключается в перемешивании бит, содержащихся в исходных хро- мосомах. Для скрещивания случайным образом отби- раются пары индивидов из промежуточной популяции (кандидаты в родители). Скрещивание происходит с заданной вероятностью скрещивания p. Если скрещи- вание произошло, в следующее поколение переходит один из потомков (с вероятностью 0,5). Если скрещи- вание не произошло, то клонируем лучшего родителя. Родители возвращаются в популяцию и вновь прини- мают участие в селекции. Наш генетический алгоритм равновесный; скрещивание продолжается, пока не будет создано новое поколение. Реализуемые виды скрещивания: одноточечное - разрезание родитель- ских хромосом в одной точке и обмен правыми частя- ми; двухточечное - хромосома рассматривается как кольцо со связанными первым и последним генами, которое рассекается на две части, и полученные фраг- менты обмениваются; равномерное - каждый ген по- томка выбираем случайным образом из соответст- вующих генов родителей. Отличительная особенность всех разновидностей данного оператора состоит в том, что, будучи применен к паре совпадающих хромосом, он не меняет их. Мутация состоит из выполнения (обычно неболь- ших) изменений одного или нескольких генов в хро- мосоме. В случае бинарного представления исходного пространства поиска примером мутации может слу- жить инвертирование (применение операции логиче- ского отрицания) одного или нескольких случайно выбранных бит генотипа. Вектора, представленные исходной и мутировавшей цепочками, могут сильно отличаться друг от друга, что позволяет алгоритму преодолевать окрестности локальных экстремумов. В целом мутация рассматривается как метод восста- новления потерянного генетического материала, а не поиск лучшего решения. В генетических алгоритмах мутация применяется к генам с очень низкой вероят- ностью. Условия останова - по числу поколений. Генетиче- ский алгоритм эволюционирует в соответствии с при- веденными операторами, пока число поколений не достигнет заданного значения. В качестве ответа по- лучаем оценку пригодности лучшего индивида (по всем поколениям). Подход состоит в том, что мы решаем генетиче- ским алгоритмом задачу (2); при этом индивиды, со- ответствующие максимальной длине выполнимого маршрута, копируются в одно из последних поколе- ний генетического алгоритма решения задачи (3). Во время работы генетического алгоритма проис- ходят два взаимно противоположных процесса. С од- ной стороны, отбор пытается исключить из популяции индивидов с худшими значениями функции пригод- ности и увеличить число индивидов с лучшими оцен- ками. С другой стороны, репродукция приводит к по- явлению новых индивидов, предотвращая преждевре- менную остановку алгоритма в точке локального ми- нимума. Необходимое равновесие между этими двумя процессами осуществляется при помощи набора па- раметров. Для простейшего генетического алгоритма такими параметрами являются следующие: размер популяции, число поколений, длина хромосомы в би- тах, вероятность скрещивания, вероятность мутации. Эти параметры должны быть идентифицированы в ходе численных экспериментов. В результате проведенных расчетов можно сфор- мулировать несколько утверждений относительно влияния параметров алгоритма на его работу: интенсивная мутация снижает скорость алгорит- ма и может серьезно повлиять на сходимость, т. е. алгоритм работает дольше и может не найти опти- мального решения; слишком малая вероятность мутации затрудняет выход алгоритма из локальных минимумов, т. е. алго- ритм сходится достаточно быстро, но не к глобально- му решению; большие популяции сходятся дольше (требуют большего времени до остановки); при малом размере популяции возрастает веро- ятность остановки в локальном минимуме. Для каждой решаемой задачи выбор параметров должен осуществляться отдельно в ходе численного эксперимента.