Генетические методы решения задачи оптимального планирования грузовых морских перевозок

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

Постановка задачи оптимального планирования грузопотоков. Такого рода задачу свести к одному критерию достаточно трудно, так как целей может быть много. В этом случае оптимизацию проводят по нескольким частным критериям Q ( x )( i = 1,2,..., s ) , а полученные задачи называют задачами многокритериальной или векторной оптимизации . Многокритериальная оптимизация представляет собой попытку получить наилучшее значение для некоторого множества характеристик рассматриваемого объекта, т.е. найти некоторый компромисс между теми частными критериями Q^x)(i = 1,2,..., s ) , по которым требуется оптимизировать решение.

Будем решать двухкритериальную задачу о назначениях, минимизируя стоимость и общее время выполнения работ:

n n

ЕЕ cjxj ^ min, i=1 j=i nn

“ EE^ min, ij ij i=1 j=1

n                       ____ n                      ____

Е ^x j = ¹ j = ^(1, n ), Е ^x j = ^{1 1}= ^(1, n ), ^x j ^e {°,¹},

. i = 1                                      j = 1

где c j - стоимость назначения i - го судна на j -й рейс; t ij - время выполнения i - м судном j -го рейса. При этом решение будем представлять в виде матрицы из нулей и единиц.

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

Воспользовавшись формулой F = w 1 -]Т '£_Cyx:_y + w ₂ -jr j^ tjxj для оценки годности каждо- i = 1 j = 1                        i = 1 j = 1

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

Применение операторов кроссинговера и мутации сопровождается дилеммой: использовать фиксированное число особей для обработки генетическими операторами или применить более мягкую «вероятностную» стратегию? Получив в результате действия генетических операторов определенное количество потомков, перейдем к отбору особей при формировании нового поколения. Затем процесс повторяется до тех пор, пока не будет достигнут критерий останова.

Алгоритм создания начальной популяции. Пусть множество Е состоит из элементов {1,2,., n }, а множество F - из элементов {1,2,., m }. Генерируем случайное число I от 1 до n (т.е. ieE¹ ) и случайное число j от 1 до m (т.е. jeF ).

Вычислим допустимое число рейсов i -го судна на j- м рейсе:

k_a = a_i l_ij .

Вычислим необходимое число рейсов i -го судна для перевозки грузов j -го рейса: b _j kb = — +¹ .

p ij

(*) Если k a =k b , то Х у =к а =к ь, a . =0 , b j =0.

Если k a b , то X ij =k a , a . = 0 , b^b j - px .

Если k a >k b , то х=к ь, a . = a , - l j x j , b j =0 .

Если a i =0 (все рабочее время исчерпано, столбец насыщен), то E =E 1 i.

Если b j =0 (объем поставок выполнен, строка насыщена), то F =F 1 j.

Если Е ^0 и F *0 , то переход в начало алгоритма, иначе - переход к (*).

Конец работы.

Операторы кроссинговера и мутации. Особи для кроссинговера выбираются с использованием различных стратегий. На селектированные индивидуальности действуют операторы кроссинговера и мутации с вероятностью р _к и р _м соответственно. Если Х 1 , X 2 , .„, X_p - допустимые решения, тогда потомки Х 1 ’ X 2 ‘ .„, X/ с помощью оператора кроссинговера будут создаваться по правилу:

X/=с 1 *X ₁ +c 2 *X 2 +_+cp*X p ,

X , '=c 1 *X 2 +c 2 *X _; +...+cp*X 1 ,

X_p‘ = c 1 *X_p+c 2 *X i + ...+cp*X_P . 1 , где с 1 +с 2 + ...+cp= 1 .

Пусть для мутации селектирована особь Х. Вычислим произведения cj = cj (xj). Найдем g наибольших значений сц (i= 1,2,..., n, j= 1,2,...,m) и соответствующие им элементы матрицы Х: xi ,,х, j,...,xi , . Определим множества: I= {i 1, i2..... ig} и J= {j' 1, j2..... jg}. Установим субматрицу W i 1 j 1 i 2 j 2           igjg из элементов матрицы Х следующим образом: элемент xij∈X переходит в W тогда и только тогда, когда ieI и jeJ. Зададим новые значения a(w) и b(wj):

Подключим алгоритм создания начальной популяции. Этот алгоритм работает так, что все ограничивающие условия для a ( Wi ) и b ( w j ) будут удовлетворены и получены новые значения для матрицы W . Заменяем выбранные элементы матрицы Х на новые элементы из матрицы W .

Затем вновь полученные решения оцениваются, сортируются и строится новая популяция. Размер популяции в нашем алгоритме поддерживается постоянным. То есть, если после действия генетических операторов получим популяцию размерности р+р 1, то на следующем шаге после оценки и сортировки последниер 1 индивидуальностей выбрасывают из популяции.

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

Материал поступил в редакцию 28.04.2011.

GENETIC SOLUTION METHODS FOR PROBLEMOF STORES SHIPMENT OPTIMAL PLANNING

(Don State Technical University),

(LLC ‘Spetsmorstroi’)

A genetic algorithm for solving the optimization problem of stores shipment is developed. The algorithm permits to find a good approximate solution, and it has acceptable computational complexity.