Моделі та методи комбінаторної оптимізації та їх застосування

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Київський національний університет

імЕНІ Тараса Шевченка

01.05.04 - Системний аналіз і теорія оптимальних рішень

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

Моделі та методи комбінаторної оптимізації та їх застосування

Турчин Олександр Ярославович

Київ - 2011

Дисертацією є рукопис.

Робота виконана на кафедрі обчислювальної математики Київського національного університету імені Тараса Шевченка.

Науковий керівник:доктор фізико-математичних наук, професор,

член-кореспондент НАНУ

ЛЯШКО Сергій Іванович

Київський національний університет

імені Тараса Шевченка

Завідувач кафедри обчислювальної математики

Офіційні опоненти:доктор фізико-математичних наук

старший науковий співробітник

ШАРІФОВ Фірдовсі Ахун-огли

Інститут кібернетики імені В.М.Глушкова

старший науковий співробітник відділу методів негладкої оптимізації м. Київ

кандидат технічних наук, доцент

КУЛЯН Віктор Романович

Київський національний університет імені Тараса Шевченка

доцент кафедри моделювання складних систем м. Київ

Захист відбудеться «19» травня 2011р. о 1400 годині на засіданні спеціалізованої вченої ради Д 26.001.35 при Київському національному університеті імені Тараса Шевченка за адресою: Україна, 03680, м. Київ, просп. Академіка Глушкова 4Д, факультет кібернетики, ауд. 40.

З дисертацією можна ознайомитися у науковій бібліотеці Київського національного університету імені Тараса Шевченка (м. Київ,

вул. Володимирська, 58).

Автореферат розіслано «18» квітня 2011 р.

Вчений секретар

спеціалізованої вченої ради Д 26.001.35П.М.Зінько

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. При розв'язанні багатьох важливих прикладних проблем управління виробництвом, розробки біо- та нанотехнологій, проектування та розміщення об'єктів, планування експерименту, керування процесом обробки даних тощо важливу роль відіграють оптимізаційні задачі комбінаторного типу. Інтерес до таких задач виник ще у 50-ті роки минулого століття і постійно зростає завдяки розширенню сфери їх застосування.

За останні роки було розроблено ряд алгоритмів комбінаторної оптимізації (АКО), орієнтованих на розв'язання оптимізаційних задач, що виникають в різних прикладних областях. Але з часом виникають потреби в розв'язанні все нових і нових задач комбінаторної оптимізації (ЗКО) підвищеної розмірності та складності (зокрема, задач з неаналітичними цільовими функціями, тобто заданими або таблично, або такими, значення яких визначаються шляхом розв'язання ряду підзадач моделювання). Окремо слід зазначити недостатність теоретичних результатів, які стосуються оцінок ефективності відомих АКО і можуть бути корисними на практиці.

Останнім часом досягнуто значних успіхів у напрямку як побудови та дослідження моделей різноманітних класів ЗКО, так і розробки нових прикладних методів комбінаторної оптимізації. Значний внесок в розробку АКО зробили зарубіжні дослідники - М.Доріго, Ф.Гловер, Х.Пападімітріу, П.Пардалос, К.Стайгліц, Е.Талбі, Х.Гоос, Т.Штютцль, та ін. В Україні важливі результати були отримані рядом вітчизняних вчених, серед яких Гуляницький Л.Ф., Донець Г.О., Ємець О.О., Каспшицька М.Ф., Ляшко С.І., Михалевич В.С., Перепелиця В.О., Сергієнко І.В., Стоян Ю.Г., Трубін В.О., Шор Н.З., Яковлєв С.В. та інші.

В дисертаційній роботі розглянуто ряд класів прикладних методів комбінаторної оптимізації та запропоновано власний підхід до побудови ефективних наближених алгоритмів розв'язання ЗКО.

Сутність проблеми, що досліджується в роботі, полягає в тому, що розробка алгоритмів розв'язання ЗКО повинна враховувати як здатність алгоритму знаходити розв'язки задачі з підвищеною точністю, так і можливість знаходження цих розв'язків за умов помірних витрат машинного часу та пам'яті.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана на кафедрі обчислювальної математики Київського університету ім. Тараса Шевченка та пов'язана з виконанням тем № 01БФ015-06 «Моделювання та оптимізація інформаційних систем» (державний реєстраційний номер 0101U002178), № 06БФ015-04 «Теорія сингулярного оптимального керування системами з розподіленими параметрами» (державний реєстраційний номер 0106U005857), № 06БП015_07 «Нові підходи до комп'ютерного моделювання складних середовищ і систем, розробка на їх основі високоефективних методів і алгоритмів для інформаційно-аналітичних систем» (державний реєстраційний номер 0106U005861).

Мета і завдання дослідження. Метою роботи є розробка прикладних моделей і методів розв'язування ЗКО та їх застосування. Відповідно до сформульованої мети, в дисертації ставляться такі завдання:

проаналізувати класи АКО та запропонувати нові підходи до побудови ефективних алгоритмів розв'язання ЗКО;

провести детальний аналіз запропонованих алгоритмів шляхом теоретичного дослідження збіжності та проведенням ряду числових експериментів з розв'язування практичних задач;

визначити значущі виробничі процеси та технологічні обмеження, необхідні для побудови математичної моделі оптимізації прийняття рішень при плануванні технологічних процесів на прикладі великого металургійного комбінату (МК); комбінаторний оптимізація алгоритм

запропонувати, реалізувати програмно і застосувати алгоритм знаходження розв'язку відповідної оптимізаційної задачі.

Об'єкт досліджень - прикладні оптимізаційні задачі комбінаторного типу та технологічні процеси, що виникають на металургійному підприємстві.

Предмет досліджень - математичні моделі та алгоритми комбінаторної оптимізації, що використовують процедури стохастичного локального пошуку та прикладні оптимізаційні задачі комбінаторного типу, що виникають у оптимізації виробничих процесів на прикладі типового МК.

Методи дослідження полягають у побудові оригінальних алгоритмів, що використовують різні техніки пошуку в просторі розв'язків; проведенні оцінювання ефективності застосування розроблених алгоритмів та розробці математичної моделі для розв'язання практичної оптимізаційної проблеми, що виникає на великому металургійному виробництві.

Наукова новизна одержаних результатів полягає у тому, що в дисертації вперше:

наведена класифікація методів розв'язання ЗКО на основі понять метаевристик першого та другого роду. Розроблений підхід дозволяє класифікувати не лише існуючі, але й розроблювані АКО;

розроблені нові наближені алгоритми стохастичного локального пошуку, які належать до метаевристик першого роду;

запропоновано і досліджено підхід до побудови гібридних алгоритмів на базі генетичних алгоритмів і GS-алгоритмів, які відносяться до метаевристик другого роду;

проведено теоретичний аналіз ефективності і досліджена практична застосовність розроблених алгоритмів;

розроблена математична модель оптимізації прийняття рішень при плануванні технологічних процесів на великому МК, яка враховує найбільш суттєві обмеження та технологічні норми на типовому МК;

для розв'язання формалізованої задачі розроблено, реалізовано і застосовано наближений алгоритм розв'язання, який базується на схемі GS-алгоритмів.

Практичне значення одержаних результатів. Розроблені алгоритми та програмні засоби були застосовані на одному із підприємств металургійного комплексу - металургійному комбінаті «ISD Huta Czestochowa Sp. z o.o.» (Ченстохова, Польша). Результати дисертаційної роботи можуть бути використані як для розробки нових АКО, так і для їх практичного застосування у сферах управління виробництвом, проектування та розміщення об'єктів, планування експерименту, керування процесом обробки даних тощо. Отримані результати можуть бути узагальнені та застосовані для розв'язання інших класів ЗКО.

Особистий внесок здобувача. Основні результати, викладені у дисертації, отримані автором самостійно. В публікаціях, виконаних у співавторстві, розглянуто підходи до формалізації ЗКО, висвітлено результати щодо отримання оцінок швидкості збіжності побудованих алгоритмів. Особистий внесок здобувача полягав у виконанні всіх основних досліджень, доведень, побудові програмного комплексу. У роботах, опублікованих у співавторстві, автору дисертації належать: у [1] - формулювання та доведення лем, теореми; в [2] - обчислювальна схема та результати експерименту; в [5] - загальна схема алгоритму, варіанти генетичних операторів, результати розв'язування тестових задач; у [7] - реалізація підходу до комбінування алгоритмів, постановка ЗКО, результати обчислювального експерименту; в [10], [13], [14] - схема алгоритму, побудова функціоналу, постановка та доведення леми, теореми; в [12] - постановка задачі, схема алгоритму.

Апробація результатів дисертації. Основні результати роботи доповідалися та обговорювалися на міжнародних конференціях «The Experience of Designing and Application of CAD Systems in Microelectronics» «CADSM-2001», «CADSM-2003», «CADSM-2007» (м.Славсько, Україна, 2001, 2003, 2007 рр.), міжнародних семінарах «International Conference on Prediction and Decision Making under Uncertainties» «PDMU-2001», «PDMU-2003», «PDMU-2008», «PDMU-2010» (м.Київ, 2001, 2003, 2008, 2010 рр.), міжнародній конференції з індуктивного моделювання «ICIM-2002» (м.Львів, 2002 р.), міжнародних школах-семінарах «Теорія прийняття рішень» (м.Ужгород, 2004, 2010 рр.), 5-й Московской международной конференции по исследованию операций (м.Москва, 2005 р.), міжнародних конференціях «Knowledge-Dialog-Solution» «KDS 2007», «KDS 2008», «KDS 2009» (м.Варна-м.Київ, 2007, 2008, 2009 рр.), міжнародних симпозіумах «Питання оптимізації обчислень ПОО-ХХХІII», «Питання оптимізації обчислень ПОО-ХХХV» (м.Кацивелі, 2007, 2009 рр.), наукових семінарах кафедри обчислювальної математики, кафедри системного аналізу та теорії прийняття рішень КНУ ім. Т.Шевченка, та на науковому семінарі в Інституті кібернетики імені В.М.Глушкова.

Публікації. Результати дисертаційної роботи опубліковані в 16 наукових працях, з них 4 статті у фахових виданнях, затверджених ВАК України, 12 матеріалів і тез конференцій.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел із 92 найменувань на 9 сторінках, та 2 додатків на 4 сторінках. Загальний обсяг роботи - 120 сторінок (11 таблиць, 29 рисунків).

ОСНОВНИЙ ЗМІСТ ДИСЕРАТЦІЇ

У вступі обґрунтовується актуальність обраної теми, формулюється мета роботи, відзначається наукова новизна отриманих результатів та висвітлюється їх теоретична і практична значимість.

Перший розділ присвячено формалізації постановки ЗКО, розв'язання якої розглядається у дисертаційній роботі. Нехай - деякий простір, на якому визначена цільова функція , - множина припустимих розв'язків задачі. Часто розглядається як метричний простір, тобто вважається заданою певна метрика . В загальному випадку задача оптимізації полягає у тому, щоб знайти

. (1)

Нехай задані Y={1, … , m}, Z - дискретний, зокрема, скінченний простір (назвемо його твірним), - гомоморфізм, , що задовольняє деякій системі обмежень .

Означення 1. Будемо розуміти під комбінаторним об'єктом трійку , де - базовий простір.

Означення 2. Комбінаторними об'єктами 1-го порядку назвемо такі комбінаторні об'єкти, у яких базовий простір співпадає з твірним:

, де .

Означення 3. Комбінаторними об'єктами k-го порядку (k > 1) назвемо комбінаторні об'єкти

,

де

Означення 4. Простір називається локально скінченним, якщо будь-який має скінчений окіл такий, що .

На основі цих понять сформулюємо

Означення 5. Задача (1) називається ЗКО, якщо простір її розв'язків - це локально скінченний простір, елементами якого є комбінаторні об'єкти.

Нехай А1 - певний АКО, а А2 - інший алгоритм розв'язання ЗКО чи певна процедура генерування точок із простору розв'язків ЗКО, яка розглядається. Під метаевристикою МЕ розв'язування ЗКО будемо розуміти обчислювальну схему, яка об'єднує наявні процедури, що подамо так:

, (2)

де А1 називають провідним алгоритмом, а А2 - вбудованим алгоритмом (процедурою).

Означення 6. Метаевристику МЕ, подану у вигляді (2), назвемо метаевристикою першого роду, якщо вбудований алгоритм А2 не являє собою окремого алгоритму оптимізації.

Означення 7. Метаевристика МЕ, подана у вигляді (2), буде метаевристикою другого роду, якщо і провідний алгоритм А1, і вбудований алгоритм А2 являють собою певні окремі алгоритми оптимізації.

У першому розділі проведено огляд існуючих алгоритмів, запропонованих для розв'язання ЗКО, в якому розглядаються як точні, так і наближені алгоритми.

У другому розділі розроблено нові траєкторні та популяційні метаевристики на основі алгоритмів локального пошуку.

Запропоновано алгоритми стохастичного локального пошуку, які названо GS-алгоритмами. Вони належить до класу траєкторних метаевристик першого роду. Для побудови обчислювального процесу в GS-алгоритмі формується строго монотонно зростаюча послідовність дійсних чисел із відрізку [0,1]. Якщо xh - це знайдений поточний варіант на кроці h, і побудовано певний (метричний) окіл цієї точки , то досліджуваний варіант з цього околу, для якого f(y) > f(xh), може бути прийнято у якості xh+1 з імовірністю переходу p(xh,y), що залежить від різниці значень цільової функції і поточних значень . Загальна схема GS-алгоритму наведена на

procedure GS_Search(x)

x0 := деякий початковий припустимий варіант розв'язку з Х;

: = 0; h := 0; t : = 0; xrec:= x0; frec := f( x0 );

while окіл поточного розв'язку не проглянуто повністю do

while не виконана умова рівноваги do

у := ГенеруванняНаступноїТочкиОколу ;

Обчислення ;

if f(y) f(x) then p := (1- ) else p := 1;

о := random[0,1];

if p ? о then h:=h+1; xh := y ;

if frec > f(xh) then xrec := xh; frec := f ( xh ) end if

end if;

Визначаємо - ліву точку «золотого перерізу» ; t := t + 1;

return x= xrec;

Значення запропоновано визначити на основі підходу, що використовує принцип «золотого перерізу». Величина мt визначається як менша (ліва) з двох точок, які реалізують «золотий переріз» відрізку [мt ,1] (за умови, що м0=0). Таким чином, правило «золотого перерізу» задає швидкість наближення лівої межі цього відрізку до 1.

У схемі, представленій на Рис. 1, (x,y), 0 (x,y) 1, - деякий функціонал, що залежить від значень цільової функції ЗКО, яку будемо вважати невід'ємною. Визначимо імовірність переходу від точки x до точки y:

Показано, що при конкретному виборі функціонала (x,y) для поточного варіанту xh імовірність переходу p(xh,y) у точку подається кусково-лінійним функціоналом, що складається з трьох фрагментів: при f(y) < f(xh) його значення дорівнює 1, при f(xh) ? f(y) ?

(1+ ) f(xh) він спадає від 1 до 0, а при f(y) > (1+ ) f(xh) - приймає нульове значення (Рис. 2), де - параметр алгоритму, що задається .

0

1

0 f (xh) (1+г) f (xh) f(y)

г f (xh)

Рис. 2. Імовірність переходу у нову точку околу

Розглянемо один із найвідоміших класів ЗКО - задачі, що виникають на просторі перестановок. Для отримання оцінок швидкості збіжності траєкторію пошуку подамо у вигляді графа. Побудуємо повний зважений граф , де є множиною вершин, а - множиною ребер графа. Шляху між двома точками простору розв'язків оптимізаційної задачі (1) буде відповідати послідовність ребер цього графа: кожна з вершин графа, що відповідає , буде інцидентна тим вершинам, які відповідають точкам метричного околу (розглядається для конкретності транспозиційна метрика). Поставимо у відповідність околу множину наступним чином: якщо точка , то вершина, що відповідає у графі , буде зв'язана ребром з вершиною-образом точки . Іншими словами, якщо точки в просторі відрізнялись однією транспозицією, то на графі їх вершини-образи будуть з'єднані ребром.

У цьому разі випадковому процесу пошуку розв'язку задачі відповідає процес переходів від однієї вершини графа до другої з використанням запропонованих імовірнісних механізмів. У випадку нашого метричного простору перестановок ступінь графа дорівнює , а діаметр .

Будемо вважати, що варіант розв'язку ЗКО - це стан деякої системи. Тоді процес пошуку розв'язку ЗКО GS-алгоритмом моделюється ланцюгом Маркова, оскільки визначення стану, до якого відбудеться перехід, залежить лише від поточного стану системи. Скажемо, що

GS-алгоритм збігається, якщо відповідний ланцюг Маркова як мінімум один раз буде включати стан, що відповідає глобальному оптимуму. Імовірність переходу у наступний стан за умови знаходження наближення розв'язку з не меншим значенням цільової функції обмежена знизу величиною . Позначимо , .

Лема 1. Нехай - вершина, що відповідає деякому стану . Тоді очікувана кількість кроків,за яку буде досягнута вершина, що відповідає глобальному оптимуму, не перевищує .

Теорема 1. GS-алгоритм досягає глобального оптимуму цільової функції з імовірністю більшою, ніж , за кількість кроків, що не перевищую , і ця оцінка не залежить від початкового наближення розв'язку ().

Отримані результати теоретичного дослідження збіжності

GS-алгоритму можуть бути використані і при дослідженні інших алгоритмів прискореного імовірнісного моделювання та близьких до них технік пошуку.

Для побудови популяційної метаевристики першого роду було розроблено модифікацію генетичного алгоритму (ГА). Нехай задано - розмір популяції, а цільова функція задачі (1) є вираженням пристосованості особини. Пропонується популяційна метаевристика першого роду, побудована на базі ГА, яка отримала назву канонічний генетичний алгоритм (КГА). Схема роботи КГА приведена на Рис. 3.

Утворити початкову популяцію. Застосувати оператор відсіву, обрати пар особин для схрещення. Застосувати оператор схрещення UPMX для пар особин. Застосувати оператор мутації для нащадків. Утворити нову популяцію. Якщо критерій виходу не виконано, то перейти до п.2; інакше вихід.

Рис. 3. Обчислювальна схема КГА.

Наявний в схемі КГА оператор відбору використовує принцип «рулетки»: для -ї особини, , імовірність участі у схрещенні обчислюється пропорційно до рівня пристосованості цієї особини. Вибір оператора схрещення КГА було зупинено на UPMX (Uniform Partially-Mapped Crossover), який являє собою модифікацію двох найпоширеніших операторів кросоверу - PMX (Partially-mapped Crossover) та OX (Order Crossover). Від PMX запропонований оператор схрещення успадкував схильність до збереження у нащадків значної кількості фрагментів послідовності генів їх батьків, а від ОХ - формування генотипу за допомогою принципу черги. Певну кількість генів нащадок успадковує від домінуючого батька, решта генів у генотипу з певною ймовірністю буде нести в собі фрагменти послідовності генів іншого батька. Оператор схрещення UPMX є класичним прикладом одноточкового кросовера. У якості оператору мутації КГА використаємо циклічну транспозицію виділеного числа генів у генотипі представника популяції.

У третьому розділі розглянуто підхід до побудови нової гібридної метаевристики другого роду, в обчислювальній схемі якої у якості провідного алгоритму використано алгоритм КГА, а GS-алгоритм застосовано як вбудований алгоритм. Позначимо такий гібридний алгоритм як КГА+GS та наведемо його обчислювальну схему на Рис. 4.

Покласти . Утворити початкову популяцію . Для до виконати оператор селекції : Обчислити імовірність участі пари особин з покоління : . Обрати найкращих пар особин для схрещення згідно п.3.1 Для до виконати оператор схрещення : Обрати -ту пару для схрещення . Обчислити рівні пристосованості кожної особи з батьківської пари . Обчислити кількість генів , що перейде до нащадка від домінуючого батька. Для від 1 до виконувати (якщо домінує ). Для від до виконувати (якщо ген відсутній). Якщо генотип містить порожні місця, то заповнити їх рештою невикористаних генів випадковим чином. Застосувати GS-алгоритм() для нащадків, використовуючи їх генотипи у якості початкових наближень розв'язку. Утворити нову популяцію з популяції батьків та нащадків, використовуючи стратегією елітизму. Якщо критерій виходу не виконано, то покласти , оновити та перейти до п.2. Завершення роботи алгоритму.

Рис. 4. Обчислювальна схема алгоритму КГА+GS.

Дослідження збіжності запропонованої гібридної метаевристики КГА+GS також було проведено з використанням аналогії між ітераційним процесом побудови нового покоління та ланцюгом Маркова.

Генетичні оператори незалежні між собою та застосовуються послідовно. Більш того, популяція в наступному поколінні будується лише з урахуванням особин поточної популяції. Таким чином, можемо стверджувати, що відповідний ланцюг є ланцюгом Маркова з простором станів , де М - розмір популяції.

Отже, розглянемо ланцюг Маркова з матрицею переходів

.

Кажуть, що для ланцюга Маркова виконується міноризуюча умова на підмножині , якщо існують міра та такі, що

(3)

для всіх . Якщо , то міноризуюча умова (3) називається умовою Дьобліна (Doeblin's condition).

Д.Розенталем доведено наступну теорему щодо оцінки збіжності до стаціонарного розподілу.

Теорема 2. Нехай ланцюг Маркова задовольняє умові Дьобліна (), - стаціонарний розподіл . Тоді для довільного початкового розподілу

.

На основі цього результату отримано оцінки швидкості збіжності алгоритму КГА+GS.

Теорема 3. Нехай - ланцюг Маркова, що породжений КГА+GS; - розподіл на поколінні , - стаціонарний розподіл. Тоді

.

Окрему частину третього розділу присвячено апробації та дослідженню ефективності розроблених алгоритмів. Для цього була проведена серія обчислювальних експериментів, в яких розв'язувались ЗКО із відомих бібліотек практичних та тестових задач. Зазвичай, дослідники використовують для дослідження АКО бібліотеку TSPLIB95, що включає різноманітні прикладні задачі комівояжера, та бібліотеку QAPLIB, яка містить серію квадратичних задач про призначення. Для кожної окремої задачі бібліотеки містять дані, необхідні для обчислення цільової функції, та відомості стосовно найкращого відомого розв'язку.

Більшість задач із цих бібліотек мають значну прикладну цінність, тому вони використовуються для оцінки практичної ефективності АКО.

Результати розв'язання практичних і тестових задач продемонстрували здатність розроблених алгоритмів знаходити розв'язки з підвищеною точністю за умови помірного використання машинних ресурсів.

У четвертому розділі розглядається задача оптимізації виробничого розкладу металургійного підприємства та питання розробки відповідних систем моделювання. Проаналізовано основні виробничі процеси сталеплавильного та листопрокатного виробництва, наведено найважливіші технологічні та логістичні обмеження, які повинні враховуватися при проектуванні системи планування виробничих процесів. Сформульовані основні вимоги до системи автоматичного формування оптимального виробничого розкладу.

Також у цьому розділі сформульовані вимоги до функціональності систем формування виробничого розкладу, проаналізовано особливості їх діяльності, перераховано інформаційні потоки в таких системах та визначено формати даних. Приведена агрегована схема та короткий опис виробничих процесів, що здійснюються на великих МК замкнутого типу.

На основі проведеного аналізу запропоновано математичну модель оптимізації виробничого процесу та розроблені АКО, які апробовані при розв'язанні задач, що виникли на виробництві.

Для типового МК характерною є ситуація, коли формується місячний портфель замовлень. Основними параметрами портфеля є такі:

вага готової продукції;

число окремих замовлень;

загальна кількість листів прокату.

Кожний лист прокату може бути охарактеризовано наступним набором параметрів:

загальні ідентифікатори - номер замовлення, ідентифікатор замовника та ін.;

марка сталі;

технологічний регламент прокату;

метричні параметри (вага, геометричні розміри);

вимоги до відправлення.

Таким чином, кожному листу може бути приписано унікальний набір параметрів, який дозволяє однозначно ідентифікувати його на кожному етапі виробництва.

Була поставлена задача розробити алгоритми оптимізації, які б могли стати основою для відповідних блоків систем автоматичного формування виробничого розкладу та які забезпечували б виконання наявних замовлень найбільш оптимальним способом. Під виробничим розкладом розуміється сукупність графіків відправлення продукції виробничими підрозділами, в т.ч.:

графік лиття слябів (заготовок, з яких виготовлюються листи металу);

графік розігріву слябів;

графік прокату слябів;

графік відправлення замовлень.

Основним критерієм оцінки ефективності створюваних програмно-алгоритмічних засобів планування є можливість виконання генерованого ними виробничого розкладу, що означає відповідність сформованих планів технологічним нормам та задовольняння існуючим обмеженням.

Формування послідовності листів однозначно визначає послідовність всіх інших технологічних процесів - лиття слябів, розігріву слябів та відвантаження сформованих замовлень. При цьому реалізація вказаних процесів є більш простою, тому що перестановок яких-небудь елементів вже не передбачається.

На Рис. 5 наведена схема дій і факторів, які повинна охоплювати система оперативного виробничого планування.



Рис.5. Типова схема процесів на великому МК.

В цілому, вимоги до функціональності типової системи планування виробництва на МК сформульовані наступним чином:

Система повинна дозволяти складання виробничого розкладу з урахуванням пріоритетів виконання окремих замовлень до певного, наперед визначеного терміну.

Система повинна забезпечувати оптимальну відповідність компоновки листів з портфелю в сляби. Оптимальність у даному випадку передбачає поєднання максимальної кількості листів у слябі.

Система повинна забезпечувати оптимальне формування секвенцій. Секвенції повинні бути максимально довгими.

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

Система повинна забезпечувати оптимальне відправлення готової продукції, що дозволяє мінімізувати обсяг складу готової продукції.

Принцип дії системи полягає у здійсненні послідовного перебору варіантів виробничого розкладу з їх наступною оцінкою та вибором найкращого. При розробці алгоритмів перебору будемо виходити з пріоритетності своєчасного виконання замовлення - при цьому послідовність прокату буде «керуючим» процесом по відношенню до всіх інших - лиття, розігріву та висилки. Такий підхід до планування «від прокату» суттєво відрізняється від типового процесу планування на багатьох виробництвах, де послідовність прокату та висилки визначається роботою ливарного виробництва.

Як ілюструє Рис. 5, процес побудови потрібної послідовності листів є основним по відношенню до всіх інших процесів. Впорядкування послідовності листів з портфеля замовлень є складною проблемою з огляду на розмірність виникаючих оптимізаційних задач на перестановках, а розробка наближеного алгоритму розв'язання і стала предметом подальших досліджень.

Для розв'язання поставленої задачі запропоновано наступну математичну модель. Нехай:

N = {i : i = 1, …, n} - множина номерів (ідентифікаторів) листів в портфелі замовлень;

n - число всіх листів;

Vi - вага i-го листа;

Nk - листи, що входять до k-го замовлення , k = 1, …, K;

K - число замовлень.

Зрозуміло, що замовлення утворюють розбиття портфеля:

і ? j, i,j = 1, …, K.

Введемо позначення:

S - число сформованих слябів, які поступають на прокатне виробництво і до кожного з яких приписані певні листи замовлення з урахуванням класу сталі;

Dk - директивний термін виконання k-го замовлення (якщо для деякого замовлення l,

l {1, …, K}, він відсутній, то покладемо D l = Т );

В - пропускна спроможність прокатного стану за добу;

wk - вага (значимість) k-го замовлення;

ms - клас (код) сталі s-го сляба, s = 1, …, S;

Т - плановий період (для місячного планування Т {28, 29, 30, 31}).

Множину наявних слябів можна описати матрицею Y=(ysi)sn , де

yis =

Для подання варіанта розв'язку введемо матрицю = (хst)S Т розмірності S Т, де

На підставі наявної інформації запишемо матрицю Z = (zit)пТ , де

Для кожного замовлення k, k{1, …, K}, введемо множину, яка містить всі ті дні планового періоду, в які виконується замовлення k:

Зрозуміло, що склад цих множин залежить від варіанта розподілу слябів (листів) по днях, що і відображено в позначенні. Нехай тепер

Цілі планування виробничих процесів на МК були відображені шляхом формалізації наступних критеріїв.

,

де припускається, що числа такі, для яких

,

тут , а в > 0 - штраф за перевантаження прокатного стану на одиницю маси продукції.

де

тут - добова вага слябів.

Інтегральну цільову функцію задачі подамо у вигляді згортки пронормованих значень зазначених частинних критеріїв:

(4)

де - вагові коефіцієнти; при цьому , - нормовані значення критеріїв:

Обмежуючі умови задачі:

(5)

(6)

(7)

(8)

(9)

(10)

(11)

Тоді сформульована оптимізаційна задача полягає в пошуку такої матриці , яка мінімізує функцію (4)

де область П визначається умовами (5)-(11).

Для розв`язання задачі планування було застосовано GS-алгоритм, описаний в другому розділі дисертаційної роботи. Результати застосування моделі та розробленого алгоритму на одному із МК, подані у роботі [15], засвідчили ефективність запропонованого підходу. Практичний ефект від застосування полягав у наступних досягнутих результатах:

скорочено середній щоденний об'єм слябів на складі перед вальцюванням;

зменшено середній час виконання окремого замовлення;

підвищено відсоток завантаження технологічного обладнання;

збільшена середня довжина секвенцій.

ВИСНОВКИ

У дисертаційній роботі отримані нові науково обґрунтовані результати в галузі розробки прикладних моделей і методів розв'язування ЗКО та їх застосування. Проведено аналіз сучасного стану досліджень в прикладній комбінаторній оптимізації, на основі якого запропоновано оригінальні математичні моделі та наближені методи розв'язання ЗКО. Дисертація є новим комплексним дослідженням, що розв'язує важливі актуальні наукові проблеми, пов'язані з розробкою нових ефективних алгоритмів розв'язання оптимізаційних задач комбінаторного типу, оцінкою ефективності запропонованих алгоритмів з теоретичної та практичної точок зору, побудовою математичних моделей для практично значимих оптимізаційних задач.

Основні результати дисертаційної роботи полягають у наступному:

Запропоновано нові метаевристики першого роду. Траєкторні метаевристики представлено новими класами алгоритмів розв'язання ЗКО, названих GS-алгоритм та GS-табу [12]. Клас популяційних метаевристик першого роду представлено розробленою модифікацією генетичного алгоритму.

Запропоновано і досліджено підхід до побудови гібридних алгоритмів на базі генетичних алгоритмів (провідний алгоритм), де

GS-алгоритм є вбудованою процедурою. Цей підхід ліг у основу розробки нової метаевристики другого роду. Важливо зазначити, що більшість розроблених алгоритмів побудовано з урахуванням подолання такої типової вади складних метаевристик, як велика кількість параметрів.

Проведено аналіз ефективності розроблених алгоритмів як з теоретичної, так і з практичної точок зору. Отримано оцінки швидкості збіжності алгоритмів, проведено серії обчислювальних експериментів із розв'язання ряду практичних та тестових задач з відомих бібліотек, на основі яких проілюстровано практичну ефективність запропонованих АКО.

Розроблена математична модель оптимізації прийняття рішень при плануванні технологічних процесів на великому МК, яка враховує найбільш важливі обмеження та технологічні норми на типовому МК. Особлива цінність запропонованої моделі полягає у виділенні найбільш критичної ланки у технологічному процесі на МК і описанні їх у вигляді достатньо компактної математичної моделі, відповідної ЗКО без втрати адекватності.

Запропоновано і реалізовано алгоритм, що належить до класу

GS-алгоритмів, який здатний для виникаючої оптимізаційної задачі великої розмірності знаходити розв'язки з високою точністю за прийнятний час.

Розроблені алгоритми та програмні засоби були застосовані на одному із підприємств металургійного комплексу - металургійному комбінаті «ISD Huta Czestochowa Sp. z o.o.» (Ченстохова, Польша). Запропоновані алгоритми та побудовані моделі можуть бути застосовані для розв'язання ЗКО із інших класів. Крім того, ефективність застосування розроблених траєкторних метаевристик першого роду свідчить про те, що вони та близькі до них техніки пошуку можуть бути ефективно застосовані для розв'язання важливих практичних задач підвищеної розмірності та складності.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Ляшко С.І. До умов збіжності одного класу методів ймовірносного моделювання. / С.І. Ляшко, О.Я. Турчин // Журнал обчислювальної та прикладної математики. - 2001. - №1 (86). - С.8-12.

Hulyanitsky L. «Golden section» rule in probabilistic modeling algorithms. / Hulyanitsky L., Turchin O. // Вісник Нац. ун-ту "Львівська політехніка". - 2001. - №415. - С. 50-53.

Турчин О.Я. Дослідження збіжності алгоритму прискореного ймовірносного моделювання, що розв'язує певний клас задач комбінаторної оптимізації. / О.Я. Турчин // Вісник Київського університету. Серія: фізико-математичні науки. - 2003. - №1. - С.216-221.

Турчин О.Я. Використання траєкторних метаевристик для побудови методу табу-пошуку. / О.Я. Турчин // Вісник Київського університету. Серія: фізико-математичні науки. - 2008. - №4. - С.187-190.

Гуляницький Л.Ф. Про один підхід до використання імовірнісного моделювання в схемі генетичного алгоритму для розв'язання задач оптимізації на перестановках. / Л.Ф. Гуляницький, О.Я. Турчин // Міжнародна конференція з індуктивного моделювання (ICIM-2002) 20-25 травня 2002: праці. - Львів. - 2002. - С. 275-281.

Турчин О. Один підхід до дослідження збіжності класичного генетичного алгоритму. / О.Я. Турчин // Проблеми прийняття рішень в умовах невизначеності (PDMU-2003):міжнар. школа-семінар 8-12 вересня 2003: праці. - Київ. - 2003. - С. 166-168.

Hulianitsky L. On approach to combining genetic algorithms and accelerated probabilistic modeling algorithms. / L.Hulianitsky, A.Turchin // The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM-2003): міжнар. конференція 18-22 лютого 2003: праці. -Львів. - 2003. - С. 218-219.

Гуляницький Л.Ф. Про дослідження збіжності одного комбінованого алгоритму розв'язання задач комбінаторної оптимізації /

Л.Ф. Гуляницький, О.Я. Турчин // II-а міжнародна школа-семінар «Теорія прийняття рішень»: 27 вересня-2 жовтня 2004: праці. - Ужгород. - 2004. - С.30.

Турчин О.Я. On the convergence rates of hybrid algorithm solving combinatorial optimization problem. / О.Я. Турчин // V Московская международная конференция по исследованию операций: 21-23 апреля 2007: труды. - Москва. - 2007. - С. 178-180.

Л.Ф. Гуляницький Один класс алгоритмов стохастического локального поиска. / Л.Ф. Гуляницький, О.Я. Турчин // «Knowledge-Dialogue-Solution (KDS-2007)»: міжнар. конференція 17-25 червня 2007: праці. -Варна. - 2007. - С. 102-111.

О. Turchin Comparative analysis of metaheuristics solving combinatorial optimization problems. / О.Turchin // The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM-2007): міжнар. конференція 20-24 лютого 2007: праці. - Львів. - 2007. - С. 276-277.

Л.Гуляницкий Использование алгоритма ускоренного вероятносного моделирования в схеме табу-поиска / Л. Гуляницкий, А.Турчин // Supplement to International Journal «Information Technologies and Knowledge». - 2008. - Vol.2. - P. 137-142. - (International Book Series «Information Science and Computing»; №7).

L.Hulianytskyi One class of stochastic local search algorithms / L.Hulianytskyi, A.Turchin // «Information Theories and Applications». - 2008. - Vol.15. - P. 245-252.

Гуляницький Л.Ф. Узагальнені алгоритми прискореного ймовірнісного моделювання. / Л.Ф. Гуляницький, О.Я. Турчин // Питання оптимізації обчислень (ПОО-XXXIII): міжнар. симпозіум 24-29 вересня 2009: праці. - Київ. - 2009.- С. 184-189.

Турчин О.Я. Построение математической модели оптимизации производственного расписания металлургического производства / О.Я. Турчин // Supplement to International Journal «Information Technologies and Knowledge». - 2009. - Vol.3. - P. 134-138. - (International Book Series «Information Science and Computing»; №15).

Turchin О. Algorithms for solving combinatorial optimization problems: on approach of classification. / О. Turchin // V-а міжнародна школа-семінар «Теорія прийняття рішень»: 27 вересня-1 жовтня 2010: праці. - Ужгород. - 2010. - С.245.

АНОТАЦІЯ

Турчин О.Я. Моделі та методи комбінаторної оптимізації та їх застосування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.04 - системний аналіз і теорія оптимальних рішень. - Київський національний університет імені Тараса Шевченка, Київ, 2011.

Метою дисертаційної роботи є розробка прикладних моделей і методів розв'язування ЗКО та їх застосування. Формалізовано постановку задачі комбінаторної оптимізації. На основі введеного поняття метаевристик першого та другого роду запропоновано підхід до класифікації алгоритмів розв'язання оптимізаційних задач комбінаторного типу. Запропоновано нові траєкторні та популяційні метаевристики першого роду. Запропоновано і досліджено підхід до побудови гібридних алгоритмів на базі генетичних алгоритмів, на основі якого здійснена розробка нової метаевристики другого роду. Проведено аналіз ефективності розроблених алгоритмів шляхом отримання оцінок швидкості збіжності алгоритмів, проведено серії обчислювальних експериментів із розв'язання ряду практичних та тестових задач із відомих бібліотек, на основі яких проілюстровано практичну ефективність запропонованих алгоритмів комбінаторної оптимізації.

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

Ключові слова: комбінаторна оптимізація, задача комівояжера, квадратична задача про призначення, ланцюги Маркова, генетичні алгоритми, алгоритми прискореного імовірнісного моделювання.

АНОТАЦИЯ

Турчин А.Я. Модели и методы комбинаторной оптимизации и их применение. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук по специальности 01.05.04 - системный анализ и теория оптимальных решений. - Киевский национальный университет имени Тараса Шевченко, Киев, 2011.

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

(GS-алгоритм), представляющая класс G-алгоритмов; исследована сходимость предложенного алгоритма с помощью цепей Маркова. Популяционные метаевристики первого рода представлены модификацией генетического алгоритма.

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

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

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

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

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

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

ANNOTATION

Turchyn O.Y. Models and methods of combinatorial optimization and its application. - Manuscript.

Dissertation for a candidate's degree of technical sciences by specialty 01.05.04 - system analysis and optimal solutions theory. - Taras Shevchenko national university of Kyiv, Kyiv, 2011.

The goal of dissertation is about research in combinatorial optimization models and methods, and its application. General formalization of combinatorial optimization problem is given. New definitions of 1st-order metaheuristic and 2nd-order metaheuristic are introduced, alongside with new approach of algorithms classification based on these definitions. New trajectory and population 1st-order metaheuristics are built. New approach of hybrid algorithm construction, based on genetic algorithm usage, is developed and used for 2nd-order metaheuristic construction. Effectiveness of developed algorithms is proved with theoretical studies of convergence rates, and number of experiments solving test problems from well-known libraries.

Mathematic model of decision making on big metallurgical plant, using its technological processes specification, is presented. Constructed algorithms and models can be effectively applied for solving combinatorial optimization problems in different areas.

Keywords: combinatorial optimization, travelling salesman problem, quadratic assignment problem, Markov chain, genetic algorithms, accelerated probabilistic modeling algorithms.

Размещено на Allbest.ru

...