В.А. АЙНУТДИНОВ, В.Н. ГОРБАЧЕВ

 

Московский государственный инженерно-физический

институт(технический университет)

ОПТИМИЗАЦИЯ СТРУКТУРЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

 ДЛЯ РЕШЕНИЯ ЗАДАЧ СИНТЕЗА РАСПИСАНИЙ

 

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

 

Задачи синтеза расписаний (Job shop scheduling problems - JSSP)  относятся к классу комбинаторных, NP-трудных задач дискретной оптимизации, что исключает возможность их решения точными методами. Эффективными методами решения подобных задач являются генетические алгоритмы (ГА).

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

Хромосома в многостадийных задачах синтеза расписаний  по методу НСМ представляет собой матрицу G, где элемент Gki есть ген, относящийся к i шагу синтеза на q стадии. Значением Gki является номер эвристики, применяемой на  i-м шаге синтеза расписания.

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

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

Для обеспечения равномерного просмотра поискового пространства применяются операторы эволюционного стохастического спуска (stochastic hillclimbing), работа которых заключается в выполнении не менее К попыток улучшения значения функции пригодности FF при помощи макромутаций. Макромутации  в НСМ заключается в присвоении избранным генам случайных значений из диапазона номеров эвристик c вероятностью  qi.

Предлагается следующая модификация эволюционно-генетического алгоритма.

На каждом шаге синтеза расписаний применяется оператор локального спуска, который осуществляет К попыток улучшения значения функции пригодности FF на основе последовательного выбора  i-й эвристики в соответствии со значением  qi.

Вероятность выбора эвристик  qi определяется  либо на основании значений, полученных после предварительного прогона задачи, либо заданием значения qik вручную.

По первому варианту вероятность выбора эвристик  qi определяется по формуле   qi = wik / g , где   wik - число генов  с номером  i-й эвристики с учетом стадии выполнения k в лучшей хромосоме после; g - общее число генов в хромосоме.

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

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

 

 

,

Список литературы

 

1.        Норенков И. П.. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации. Информационные технологии, 1999, №2.

2.        Kobayashi S.,Ono I., Yamamura M. An Efficient Genetic Algorithm for Job Scheduling Problem // Proc. of 6th Int. Conf. on GA, San Francisco, 1995.