Применение методов эволюцинной оптимизации для решения задач производственного планирования

УДК 519.7

А.Н. ГВОЗДИНСКИЙ, В.А. МАЛЫШКИН, С.В. ТКАЧЁВ

ПРИМЕНЕНИЕ МЕТОДОВ ЭВОЛЮЦИННОЙ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ

Рассматривается многокритериальная задача принятия решений с использованием методов эволюционной оптимизации в системах производственного планирования.

1. Введение

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

В настоящее время наиболее известным представителем эволюционных алгоритмов является генетический алгоритм (ГА), который содержит все основные генетические операции. Он получен в процессе обобщения и имитации в искусственных системах свойств живой природы:

- приспособляемость к изменениям среды;

- естественный отбор;

- наследование потомками наиболее « ценных» свойств родителей и т.д.

С его помощью можно улучшить работу поисковых систем, которые требуют обработки больших массивов информации.

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

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

Используя генетическую информацию хромосомных наборов родителей в качестве генетических операторов получения новых генотипов «потомков», мы применяли два типа кроссоверов - одно и двухточечный. Вычислительные эксперименты показали, что даже для простых функций нельзя говорить о преимуществе того или иного оператора. Более того, было показано, что использование механизма случайного выбора одно- или двухточечного крассовера для каждой конкретной брачной пары иногда оказывается более эффективным, чем детерминированный подход к выбору кроссоверов , поскольку достаточно трудно априорно определить, который из двух операторов более подходит для каждого конкретного ландшафта приспособленности. Использование же случайного выбора преследовало цель, прежде всего, сгладить различия этих двух подходов и улучшить показатели среднего ожидаемого результата. Для всех представленных тестовых функций так и произошло. Метод случайного выбора оказался эффективнее худшего. Кроме того, в ряде случаев (функции Griewanka'a , 10-мерная функция Растригина) применение случайного механизма в выборе кроссовера дала лучшие результаты по сравнению с детерминированными подходами.

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

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

Задачи исследования. В рамках данной статьи рассмотреть 4 метода эволюционной оптимизации производственного планирования

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

1. Величина прибыли, получаемой предприятием, определяется с помощью соотношения:

Fi

j=i

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

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

S

2 Pi *Xi ^ max .

1=1

Для конкретных значений функция цели примет вид:

F2

3. Минимизация себестоимости

S

2 C1 * X1 ^ min .

i=i

4. Минимизация производственного времени:

2 Ti*Xi ^ min.

1=1

Тогда задача исследования может быть сформулирована таким образом.

Определить оптимальный план X(0) е Q производства продукции, удовлетворяющий указанным критериям (1) - (4).

Ограничениями на выпуск продукции различных видов служат производственные ресурсы bbb2,....,bm. С учетом норм затрат ресурсов на единицу каждого типа продукции указанные ограничения можно записать в виде:

AX < BT;

X > 0,

где BT = {b!,b2,..,bmb

А={ау}, 1=1, т , .¡=1,и - матрица норм затрат ресурсов на единицу каждого типа продукции.

Выражение (4) описывает условия, которые необходимо учесть в годовой производственной программе. Строкам матрицы А соответствуют все виды ресурсов (группы машин, запасы материалов), рассматриваемые в задачах. Соответствующие строкам матрицы А компоненты вектора В указывают ограничения видов ресурсов или объёмов производства, которые установлены для годовой производственной программы предприятия. Неравенство (5) представляет собой обычные условия неотрицательности, вытекающие из смысла задачи.

Общая постановка задачи состоит в следующем. Нам нужно определить вектор Х(0), обеспечивающий компромисс между величиной прибыли (1), валовым объемом (2) и минимальной себестоимостью (3), который удовлетворяет ограничениям минимизации производственного времени (5).

Один из возможных методов решения состоит в том , что вначале находятся три

оптимальных вектора производства x(i) ,i= 1,4, каждый из которых соответствует одному из

локальных критериев (1) - (4) . Затем определяется выпуклая линейная комбинация X(0) , представляющая собой оптимальную (компромиссную) программу относительно указанных критериев :

X

3

2v1 =1 v>0. (10) i=1

2. Расчёт показателей производства

2.1. Максимизация прибыли.

Расчет показателей качества продукции относится к задачам линейной оптимизации. В общем виде её можно записать так:

S

2

i=1

Эту задачу обычно решают симплекс-методом.

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

2.2. Определение валового объема выпускаемой продукции.

Для решения этой задачи с использованием ГА в качестве общей математической модели использовали формулу:

S

2 pi*Xi ^ max (12) i=1

Для конкретных значений функция цели примет вид:

F2

2.3. Третьей функцией цели представим минимизацию себестоимости, которая имеет общий вид:

S

2 Ci*Xi ^ min

i=1

Запишем эту функцию с конкретными значениями:

F3

2.4. И, наконец, в роли четвертой функции цели будет выступать минимизация производственного времени:

S

2 Ti*Xi ^ max (16) i=1

F4

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

Остановимся на применении генетических алгоритмов следующих видов.

Для решения задачи ,представленной моделями (1) - (2), используем генетический алгоритм типа метода муравьиных колоний [1].

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

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

Fi

j=i

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

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

S

2 P; * X; ^ max .

1=1

Для конкретных значений функция цели примет вид:

F2

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

3. Для решения задач, представленных моделями (3) - (4), воспользуемся генетическими алгоритмами [2]. Оптимизировать работу нефтяных трубопроводов; распределять инструменты в металлообрабатывающих цехах; осуществлять оптимизации является одной из основных областей применения ГА. Генетические алгоритмы имитируют процесс естественного отбора в природе. Для решения задачи, более оптимального с точки зрения некоторого критерия, все решения описываются набором чисел или величин нечисловой природы. Поиск оптимального решения похож на эволюцию популяции индивидов, которые представлены наборами их хромосом. В этой эволюции действуют три механизма, представленных на рисунке. Можно выделить следующие механизмы.

- отбор сильнейших наборов хромосом, которым соответствуют наиболее оптимальные решения;

- скрещивание - получение новых индивидов при помощи смешивания хромосомных наборов отобранных индивидов;

- мутации - преобразование хромосомы, случайное изменение одного или нескольких генов (чаще = одного).

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

Для рассмотрения данной задачи используем минимизацию себестоимости:

2 Ci*Xi ^ m1n.

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

Схема генетического алгоритма

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

S

Z Ti*Xi ^ min

i=1

Общую схему генетического алгоритма можно записать следующим образом.

1. Выбрать начальную популяцию Sk(0){Sk1,Sk2,...Skn}, где N - длина цепочки. Считать это f* = max {f(Sk) | Ske Sk(t)},t:=0.

2. Пока не выполнен критерий остановки , делать следующее :

- выбрать родителей Sk1,Sk2 из популяции Sk(t) (отбор);

- построить новое решение Sk по Sk1,Sk2 (скрещивание);

- модифицировать Sk (мутация);

- если f * < f (Sk), то f* :=f(Sk);

- обновить популяцию и считать t:= t+1.

3. Поиск оптимального компромиссного решения

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

Скалярная характеристика выбирается по формуле:

a*= J f^) ,

где Fj (xj)- значение локальной функции цели J-й задачи, вычисленной в результате подстановки решения 1-й задачи. Значение aij характеризует «качество» оптимальной производственной программы Хi относительно показателя Fj(x) ^ extr и представляет собой модуль потерь относительно этого показателя , если выполняется программа Xi вместо XJ.

Строкам матрицы A=||-aij|| соответствуют 3 оптимальных вектора производства

xn,(n=1,3 ), столбцам 3 - целевые функции Fj(x) ^ extr,(J = 1,3 ).

Матрица А может условно рассматриваться как матрица платежей матричной игры двух лиц Х и F с нулевой суммой, которая определена множеством чистых стратегий {x1,x2,x3} первого игрока и множеством чистых стратегий второго игрока.

4. Выводы

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

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

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

Научная новизна: результатом проведенного исследования является решение многокритериальной задачи с использованием генетических алгоритмов.

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

Список литературы: 1. Гвоздинский А.Н., Клименко Е.Г. Методы аналитической обработки информации // Радиоэлектроника и информатика. 2000. №4. С. 111-112. 2. Гвоздинский А.Н. , Клименко Е.Г. Приминение генетических алгоритмов для решения оптимизационых задач. 7-я Международная кон-фиренция «Теория и техника передачи , приёма и обработки информации»; Сб. научных трудов. Харьков: ХНУРЭ. 2001. С.390-391. 3. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. 2003.№4. С.58- 134.

Поступила в редколлегию 17.02.2011 Гвоздинский Анатолий Николаевич, канд. тех. наук, профессор кафедры искусственного интеллекта ХНУРЭ. Научные интересы: оптимизация процедур принятия решений в сложных системах управления. Адрес: Украина , 6166, Харьков, ул. Академика Ляпунова, 7,кв.9. тел. 702-38-23.

Малышкин Владимир Александрович, студент, бакалавр специальности интеллектуальные системы принятия решений, факультет КН ХНУРЭ. Адрес: Украина , 6166, Харьков, ул. Академика Ляпунова, 7, кв. 164, тел. 0956605746 e-mail: royall1feua@gmail.com. Ткачёв Сергей Владимирович, студент, бакалавр специальности интеллектуальные системы принятия решений, факультет КН ХНУРЭ. Адрес: Украина , 61202,Харьков, ул. Целиноградская, 36, к.306, тел. 0633006304 e-mail: serejjjke-2h@yandex.ru.