ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Solution for extended logistic problem using evolutionary algorithm

The article was published in issue no. № 1, 2011
Abstract:The article considers functional blocs of genetic algorithm. The author defines some arguments and solves TSP (traveling salesman problem), where new variables are added and function calculation is detailed using function of time optimization.
Аннотация:В работе рассмотрены функциональные блоки генетического алгоритма. Определены аргументы и решена задача коммивояжера. Добавлены новые переменные и детализированы вычисления функции через оптимизацию функции времени.
Author: (max_061@mail.ru) -
Keywords: function of time, logistics problem, generic algorithm
Comments: 1
Page views: 18107
Print version
Full issue in PDF (5.09Mb)
Download the cover in PDF (1.32Мб)

Font size:       Font:

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

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

Количество вариантов размещения 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 с.


Permanent link:
http://swsys.ru/index.php?page=article&id=2725&lang=en
Print version
Full issue in PDF (5.09Mb)
Download the cover in PDF (1.32Мб)
The article was published in issue no. № 1, 2011 Print version with comments

Perhaps, you might be interested in the following articles of similar topics: