Software & Systems

При современном развитии экономики все более расширяют свои позиции глобальные торговые сети, которые располагают огромным количеством товаров различных наименований, причем в разных странах и на разных континентах. В этих условиях при проектировании бизнес-процессов нельзя не принимать во внимание проблему доставки определенных объемов товара в срок. Иными словами, при формировании запасов приходится решать логистическую задачу, оптимизированную по функции времени с добавлением таких параметров, как расстояние между городами, объем перевозимого товара, скорость выгрузки и загрузки. При этом затраты времени и ресурсов должны быть минимальными. Решая эту задачу, в каждом конкретном случае нужно учитывать множество параметров, оказывающих непосредственное вли­яние на рассматриваемую систему. 

Многочисленные исследования показали, что одним из наиболее перспективных способов решения логистических задач являются генетические алгоритмы (ГА) и основанные на них методы. Точные методы решения можно использовать только для небольшого круга сравнительно простых задач, поэтому на практике применяются приближенные методы. Таким образом, ГА применяются для решения оптимизационных задач с помощью метода эволюции, то есть путем отбора из множества решений наиболее подходящего. Примером могут служить комбинированные задачи, а также задачи, математическое описание которых не является гладкой непрерывной функцией. Здесь минимизируется целая функция, зависящая от порядка конечного числа объектов.

Количество вариантов размещения N-объектов и, следовательно, усилий для нахождения минимума целевой функции увеличивается экспоненциально с ростом N. К таким задачам относятся и задачи о коммивояжере. При решении задач оптимизации определяется некоторое множество {X}, называемое хромосомой, которое состоит из набора управляемых параметров {x1, x2, …, xn}. Каждый параметр xn – это ген, а значения генов – аллели. Рассмотрим  задачу о коммивояжере, сформулировав ее следующим образом: коммивояжеру необходимо посетить N городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальными затратами. Задача о коммивояжере является классической NP-полной задачей. Она заключается в нахождении кратчайшего гамильтонова цикла в графе. Кроме того, имеет теоретическую ценность, являясь асимптотической оценкой при исследовании различных эвристических алгоритмов, которые затем применимы для решения более сложных задач комбинаторной оптимизации, например, квадратичной задачи о назначениях, частным случаем которой является задача о коммивояжере. Любой ГА можно разбить на два связанных между собой функциональных блока. Первый – абстрактный, содержащий функциональность, не зависящую от решаемой задачи. Второй – прикладной, который необходимо обеспечивать требуемой информацией для решения новой задачи оптимизации.

На первом этапе рассмотрим следующее: дан граф G=(X, U), где ½X½=n – множество вершин (города); ½U½=m – множество ребер (возможные пути между городами). Дана матрица R(i, j), где i, jÎ1, 2, …., n, представляющая собой стоимость переезда из вершины xi в xj. Требуется найти перестановку j из элементов множества Х, чтобы значение целевой функции было равно

Fitness(φ)R(φ(1),φ(n))+Si{R(φ(i),φ(i+1))}→min.

Применение для решения задач коммивояжера стандартного оператора кроссинговера приводит к большому числу нереальных решений. Например, возьмем из популяции P={P1, P2, P3, P4, P5} хромосомы P4 – 1324765 и P5 – 6243517. Применим стандартный оператор кроссинговера. Точка разрыва между четвертым и пятым генами будет находиться в хромосоме. Получаются два потомка: P6 – 1324517 и P7 – 6243765.

Очевидно, что P6 и P7 являются нереальными решениями, поэтому выгодно применять матричное кодирование задачи о коммивояжере. При- менение модифицированных операторов кроссинговера (циклического, универсального, частично соответствующего и жадного) позволит найти реальные решения. Например, для хромосомы P4 матрица задачи о коммивояжере запишется так:

.

Как видно из матрицы, единицами кодируются переходы между генами в хромосоме.

Такое кодирование ввиду большого числа нулей является избыточным, хотя наглядно и удобно для преобразования. Пример стандартных генетических операторов для данной кодировки задачи о коммивояжере неэффективен из-за большого количества получаемых нереальных решений. Использование вместо матриц списков связности позволит получить набор строительных блоков, на котором на основе оператора сегрегации и оператора инверсии можно получить набор реальных потомков.

Представление задачи в виде матрицы смежности дает возможность анализировать шаблоны, применимые для n-размерной оптимизации ГА. Для данной задачи существует модифицированный оператор кроссинговера, позволяющий гарантированно получать реальные решения. Алгоритм построения оператора кроссинговера для задачи коммивояжера на основе «жадной» стратегии заключается в следующем.

1. Для каждой пары хромосом случайно выбирается точка разрыва, в качестве номера стартовой вершины берется номер отмеченного гена в хромосоме.

2. Сравнивается частичная стоимость путей, ведущих из текущих вершин в хромосомах-роди­телях, и выбирается кратчайший из них.

3. Если выбранная таким образом вершина графа уже была включена в частичный путь, берется случайная вершина из числа непросмотренных. Полученной вершине присваивается значение текущей.

4. При преждевременном образовании циклов выбирается другой кратчайший путь.

5. Повторяются пункты 2 и 3, пока не будет построен гамильтонов цикл с квазиминимальной суммарной стоимостью ребер.

6. Конец работы алгоритма.

Решение-потомок в алгоритме формируется как последовательность вершин графа в том порядке, в котором они становились текущими [1].

На втором этапе, определив аргументы и решения задачи коммивояжера, добавим новые переменные и детализируем вычисления данной функции только через оптимизацию функции времени. Тогда , где FS – функция, представляющая общую длину пути в графе G=(X, U); S – расстояние между городами; T – объем перевозимого товара; Vвыгр – скорость выгрузки, загрузки.

В итоге оптимизируемой функцией становится FS, по которой с помощью матрицы расстояний R(i, j), где i, jÎ1, 2, …, n, можно определить стоимость переезда из вершины xi в xj.

Метод генетической оптимизации позволяет отбирать из огромного числа возможных потомков более или менее перспективных, что приводит к значительному сокращению вычислительных операций. Генетический оператор эффективно работает, когда однообразие достигает высокого уровня, совместная эволюция управляет процессом ге-

нетического поиска. Отличительными особенностями именно этого алгоритма являются возможность решения стандартной задачи о коммивояжере, а также наложение на нее дополнительных параметров. Наиболее эффективна указанная методика при работе в режиме виртуального предприятия. Разновидность ГА является методом комбинированных эвристик по средствам декомпозиции основной задачи на ряд частных.

Таким образом, полученные результаты поз- воляют сделать вывод о перспективности применения генетических методов для решения ло- гистических задач, возникающих как на этапе планирования, так и на этапе реализации производственных процессов. Основным преимуществом генетических методов можно назвать относительную простоту (по сравнению с традиционными методами решения) адаптации алгоритма к различным вариантам постановки задачи. С помощью одного и того же варианта алгоритма можно решить целый ряд схожих задач. Кроме того, этот способ может быть дополнен подходом, суть которого заключается в постепенной корректировке исходных данных в процессе его реализации в зависимости от степени отличия реальных параметров задачи от ранее прогнозируемых. 

Литература

1. Норенков И.П., Кузьмин П.К. Информационная поддержка наукоемких изделий. CALS-технологии. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. 320 с.

2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы; [под ред. В.М. Курейчика]. М.: Физматлит, 2006. 320 с.