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

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

С. М. Білан, Н. Р. Кондратенко, А. А. Данченко

Вінницький державний технічний університет

Хмельницьке шосе, 95, 21021 Вінниця, Україна

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

Ключові слова: календарний план, мережевий графік, генетичний алгоритм.

Вступ

Відомо, що задачі оптимального календарного планування є досить складними і супроводжуються громіздкими обчислювальними процедурами. Багаточисельні дослідження вказують на необхідність удосконалення існуючих способів розв'язку таких задач та на створення нових моделей для успішного їх вирішення 1. У цьому напрямку доцільно було б розглянути так звані еволюційні або генетичні алгоритми, які на даний час з успіхом використовуються для розв'язання певного кола достатньо складних задач оптимізації. Загальну схему генетичного алгоритму можна зобразити як процес, що складається з кількох етапів 2.

1. Генерація початкової популяції.

2. Створення нащадків:

1) вибір батьківської пари й здійснення схрещування;

2) внесення мутаційних змін у популяцію.

3. Відбір і формування нового покоління.

4. Якщо не виконується умова зупинки, то перехід до п. 2.

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

Постановка задачі

Розглянемо наступну постановку задачі. Є N = {1, 2, …, n} вимог, які задовольняються приладами з множини M = {1, 2, …, m} у заданій, специфічній для них послідовності. Цей процес виконання може включати в себе повторне звернення до одних і тих самих приладів, кожен з яких одночасно обслуговує не більше однієї вимоги, і відомо час обслуговування кожної вимоги кожним приладом. Переривання в процесі виконання кожної окремої вимоги відповідним приладом не припускаються. Необхідно побудувати оптимальний за швидкодією розклад процесу обслуговування усіх вимог.

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

Методика досліджень

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

Таблиця 1. Вхідні дані тестової задачі 1.

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

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

генетичний алгоритм календарний план

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

Рис. 1. Загальний вигляд хромосоми.

Тобто, хромосома є послідовністю чисел від одиниці до k, де k -- максимальний номер вимоги, n -- остання операція змішаного графа, а уся популяція буде мати певну кількість таких хромосом -- числових послідовностей, згенерованих випадково. Опишемо як відбувається перетворення хромосоми в орієнтований граф. На першому кроці виконуємо вимогу, номер якої вказаний у хромосомі. На рис. 1 перший ген дорівнює одиниці; це означає, що вибирається операція першої вимоги. Всі ребра, які виходять з даної вершини перетворюємо на дуги, які з неї виходять. Після цього виключаємо цю вершину з графу разом з усіма інцидентними їй дугами. Наступний ген дорівнює 4. Обираємо операцію цієї вимоги та виконуємо аналогічні дії, і так до кінця хромосоми. Процес виключення вимог з хромосоми є послідовним, але коли операції однієї з вимог виконані, то всі інші вимоги перенумеруються. У граничних випадках хромосома може складатися з однакових чисел, що не впливає на загальний алгоритм перетворень, але буде збільшуватись час на перенумерацію, особливо для дуже довгих хромосом. Таким чином у результаті таких перетворень кожній хромосомі буде відповідати тільки один орієнтований граф, який не буде мати контурів, тому що вершина, в якій ребра замінюються на дуги, виключається з розгляду.

2-й етап -- створення нащадків. Після першого етапу маємо згенеровану випадково початкову популяцію, яка складається з числових послідовностей (орієнтованих графів -- розв'язків). Візьмемо розмір популяції (кількість хромосом) рівним 50. За схемою генетичного алгоритму над цією популяцією повинні виконуватися два генетичні оператори: схрещування та мутація. Схрещування проведемо за схемою схрещування з однією точкою. Сутність цієї схеми полягає у наступному. Випадково вибирається точка на хромосомі, що називається точкою схрещування. Після цього створюємо хромосому-нащадка шляхом комбінування сегменту першого з батьків, що стоїть зліва від обраної точки схрещування, з сегментом другого з батьків, що стоїть справа від точки схрещування.

На рис. 2 представлена операція схрещування з однією точкою, яка у даному випадку буде мати наступний вигляд.

Рис. 2. Операція схрещування.

1. Вибрати 2 хромосоми батьків шляхом генерування двох випадкових чисел.

2. Отримати хромосому-нащадка.

3. Якщо не всі хромосоми перебрані, то перейти до п. 1.

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

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

1. Згенерувати випадкові числа (номер хромосоми та номер гена у хромосомі).

2. Випадковим чином змінити ген. Запам'ятати змінену хромосому.

3. Якщо не виконується умова зупинки, то на п. 1.

У даному випадку коефіцієнт мутації (відношення кількості хромосом, що мутують, до загальної кількості хромосом) дорівнював 0,12. Тобто мутація здійснювалася над 9 хромосомами. У результаті розмір популяції став 84.

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

Для розв'язання даної задачі було проведено 500 ітерацій. Результати обчислювальних експериментів наведені на рис. 3, де по осі абсцис відкладені номери дослідів (запусків програми), по осі ординат -- мінімальний час виконання розкладу, лінія 1 та лінія 2 -- результати роботи класичних алгоритмів 1, лінія 3 --генетичного алгоритму.

Рис. 3. Графічні результати вирішення задачі 1.

Подальші дослідження можливості використання генетичних алгоритмів для вирішення задач календарного планування проведено шляхом зміни вхідних даних (див. табл. 2) та удосконаленням операторів генетичного алгоритму.

Таблиця 2. Вхідні дані тестової задачі 2.

Початкову процедуру отримання хромосом залишаємо без змін. Розмір популяції візьмемо рівним 50. Оператор схрещування буде працювати в такій послідовності.

1. Встановлюємо лічильник хромосом у 0.

2. Генеруємо 2 випадкових числа та запам'ятовуємо їх.

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

4. Виконуємо п. 3, перебираючи всі запам'ятовані випадкові числа.

5. Інкрементуємо лічильник хромосом. Якщо він дорівнює 25, то вихід, інакше на п. 2.

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

Операція мутації буде мати наступний вигляд.

1. Генеруємо випадкові числа (номер хромосоми, кількість генів, які мутують).

2. Змінюємо ген. Якщо не виконується умова виходу, то на п. 1.

Коефіцієнт мутації для даного випадку дорівнює 0,1. Звідси розмір популяції після мутації буде дорівнювати 110. Відбір був реалізований як елітний. Але у наступну популяцію проходить не більше однієї хромосоми, що мають абсолютно ідентичний генний набір. Якщо таких хромосом більше ніж одна, то всі наступні замінюються на інші хромосоми. Це зроблено з метою запобігання виродження популяції, так як простір можливих рішень має дуже велику кількість локальних екстремумів.

Графічні результати вирішення задачі 2 наведені на рис. 4.

Рис. 4. Графічні результати вирішення задачі 2.

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

Висновок

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

Література

1. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. -- М.: Наука, 1975. -- 256 с.

2. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. -- М.: Горячая линия -- Телеком, 2001. -- 377 с.

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