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



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

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

проф. Самотий В.В.

$1.$ Завідувач кафедри автоматики та інформаційних технологій,

Краківська політехніка ім. ТадеушаКостюшки

$2.$ Завідувач кафедри управління інформаційною безпекою,

Львівський державний університет безпеки життєдіяльності,

доц. Павельчак А.Г.

Доцент кафедри комп’ютеризованих систем автоматики,

Національний університет “Львівська політехніка”

Польща, Краків; Україна, Львів

Peculiarities of algorithmic implementation of genetic algorithm to parametric optimization of control systems

Structure data and algorithmic implementation of genetic algorithm with expanded parameters set for parametric optimization of control systems was considered.

Key words: optimization, genetic algorithm, control system.

prof. Samotyy V.V.

$1.$ Head of Department of Automation and Information Technology,

Cracow University of Technology (Tadeusz Kościuszko)

$2.$ Head of Department of Information Security Management,

Lviv State University of Life Safety

doc. Pavelchak A.G.

Docent of The Department of Computerized Automatics Systems,

Lviv Polytechnic National University

Poland, Cracow; Ukraine, Lviv.

Вступ

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

Автоматизоване керування системами покладається на регулятор, який вибирають у залежності від моделі об’єкта керування. Наприклад, достатньо популярним і надалі залишається ПІД-регулятор, а найбільш складнішою частиною його реалізації є вибір коефіцієнтів ${{K}_{p}}$, ${{T}_{i}}$, ${{T}_{d}}$. Відомі прості методики для розрахунку параметрів ПІД-регуляторів, такі як Зіглера-Нікольса [1] чи метод CHR [2], не забезпечують достатньої точності налаштування регулятора.Синтез регулятора, тобто обчислення його параметрів на підставі моделі системи,також має певні обмеження, що пов’язані з апроксимацією динаміки об’єкта моделлю першого чи другого порядку із затримкою. У свою чергу це робить неможливим аналітичний розв’язок системи рівнянь, який є необхідний при розв’язуванні моделей більш вищого порядку, вже не кажучи про враховування нелінійностей об’єкта керування. Також часто використовують і ручний підбір параметрів регулятора. Це свого роду метод спроб та помилок. При цьому для покращення пошуку параметрів застосовують певні правила, що ґрунтуються на досвіді, теоретичному аналізі та числових експериментах.

Для врахування усіх особливостей, в тому числі і нелінійностей, об’єкта керування використовують числові методи оптимізації. Оптимізаційні методи дають можливість отримати точні значення параметрів регулятора та не потребують спрощення моделі керування. Хоча інколи процес пошуку мінімуму може бути достатньо тривалим. При оптимізації параметрів ПІД-регулятора існують локальні оптимуми, і тому застосування детерміністичних методів [3, 4] тут є недоцільним. Наприклад, метод градієнтного спуску дає можливість знайти глобальний оптимум лише для опуклої функції. Для таких задач використовують ймовірнісні методи оптимізації [5-8], зокрема, генетичні алгоритми.

Алгоритмічна реалізація генетичного алгоритму

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

На рисунку зображена розроблена нами структура даних для алгоритмічної реалізації генетичного алгоритму. Основним елементом генетичного алгоритму є хромосома, яка складається з n-кількості генів. Гени в свою чергу представляють параметри досліджуваної для оптимізації задачі. Тип даних для кодування хромосом в генетичному алгоритмі може бути подано у бінарному або дійсному вигляді. Кодування параметрів в бінарні гени здійснюється шляхом квантування (1) діапазону можливих змін значень параметрів.

\[ste{{p}_{i}}=\frac{valueMa{{x}_{i}}-valueMi{{n}_{i}}}{{{2}^{n}}-1}, gen{{e}_{i}}=\frac{para{{m}_{i}}-valueMi{{n}_{i}}}{ste{{p}_{i}}}\quad\quad\quad (1)\]

Зворотне декодування здійснюється за формулою (2).

\[para{{m}_{i}}=valueMi{{n}_{i}}+gen{{e}_{i}}\cdot ste{{p}_{i}}\quad\quad\quad (2)\]

В алгоритмічній реалізації хромосома в бінарному представлені є масивом генів беззнакового цілого типу даних. Для кодування параметрів ми можемо вибирати довільну кількість бітів, у нашому випадку від 8 до 32 бітів. Менша кількість бітів дає можливість швидше покривати простір досліджень, а більша кількість –точність дослідження. Розроблені алгоритми для операторів бінарного генетичного алгоритму працюють лише у межах вибраних бітів, решта старших бітів у масиві генів мають значення нуль та ігноруються.

При представленні генів дійсними числами вибрані параметри об’єкта для оптимізації повинні бути нормалізованими в межах [0, 1]. Для цього випадку кодування параметрів в гени та їхнє декодування здійснюється за формулами (3, 4), а хромосома представлена масивом генів з типом даних у вигляді чисел з плаваючою комою подвійної точності.

\[gen{{e}_{i}}=\frac{para{{m}_{i}}-valueMi{{n}_{i}}}{valueMa{{x}_{i}}-valueMi{{n}_{i}}}\quad\quad\quad(3)\]

\[para{{m}_{i}}=valueMi{{n}_{i}}+gen{{e}_{i}}\cdot\left( valueMa{{x}_{i}}-valueMi{{n}_{i}} \right)\quad\quad\quad(4)\]

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

Рис. 1. Загальна структура даних генетичного алгоритму

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

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

$2.$ Сортування популяції за фітнес-значенням. Виконується за кращими фітнес-значеннями (мінімальними чи максимальними).

$3.$ Селекція. Відбір хромосом для популяції здійснюємо за допомогою вибраного оператора: лінійного або нелінійного ранжування, за допомогою колеса рулетки чи турніру.

$4$. Відбір елітних хромосом. Копіюємо задану кількість кращих хромосом в проміжний буфер.

$5.$ Спаровування. Вибирається один з операторів: кращі з кращими, кращі з гіршими, випадковий відбір, відбір перемішуванням, половина на половину.

$6.$ Схрещування. Для бінарного представлення вибираємо один з операторів: одноточковий, двоточковий чи рівномірний (Uniform); для представлення в дійсних числах один з таких операторів: лінійний, одинарний арифметичний, простий арифметичний, цілий арифметичний чи аналогічний до бінарного одноточкового кросовера [7].

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

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

$9.$ Мутація. В залежності від вибраного представлення генів ці оператори відрізняються. Для бінарного представлення мутації зазнають довільні біти в будь-яких генах згідно встановленого відсотка ймовірності мутації бітів у цілій популяції. Для представлення генів в дійсних числах використовується оператор Uniform або Гаусовий оператор. При цьому найбільш пристосована хромосома виключається з процедури мутації.

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

$11.$ Сортуванняпопуляції за фітнес-значенням.

$12.$ Елітизм. Ця процедура вставляє на початок популяції відібрані елітні хромосоми у п. 4 із заміною гірших хромосом.

$13.$ Сортування популяції за фітнес-значенням.

$14.$ _Створення копії покоління._Ця копія буде необхідною, якщо ми вирішимо продовжити пошук оптимуму за допомогою генетичного алгоритму. Може бути ситуація, що під час роботи генетичного алгоритму нам буде потрібно змінити деякі із параметрів як об’єкту оптимізації, так і самого алгоритму, наприклад, зменшити відсоток ймовірності мутації чи змінити межі пошуку для досліджуваних параметрів. Для цього нам потрібно буде зупинити роботу генетичного алгоритму, вибрати нові параметри та продовжити оптимізацію.

$15.$ Якщо задана кількість поколінь пройдена, то завершуємо роботу генетичного алгоритму, а якщо ні, то переходимо до п. 3.

Реалізація генетичного алгоритму виконувалася мовою C#. Відповідно, ми скористалися вбудованим генератором псевдовипадкових чисел з рівномірним законом розподілу (клас Random) з бібліотеки .NET Framework, який побудований на основі субтрактивного алгоритму генератора випадкових чисел Д. Кнута. Реалізація генетичного алгоритму була апробована на тестових задачах для оптимізації [9]: De Jong's function 1, Axis parallel hyper-ellipsoid function, Rotatedhyper-ellipsoid function, Rastrigin's function 6, Schwefel's function 7. Для усіх тестових задач реалізований алгоритм знайшов визначені мінімуми та максимуми функцій.

Перелік посилань:

$1.$ Ziegler J.G. Optimum settings for automatic controllers / Ziegler J.G., Nichols N.B. // Trans. ASME.. – 1942. – № 42. – С. 759–768.

$2.$ Chien K.L. On automatic control of generalized passive systems / Chien K.L., Hrones J.A., Reswick J.B.. // Trans. ASME. – 1952. – № 74. – С. 175–185.

$3.$ Reiner Horst. Global Optimization: Deterministic Approaches. 3rd edition / Reiner Horst, Tuy Hoang. – Berlin, Germany: Springer-Verlag GmbH, 1996.

$4.$ Mordecai Avriel. Nonlinear Programming: Analysis and Methods / Mordecai Avriel.– NY, USA: Dover Publications: Mineola, 2003.

$5.$Thomas Weise. Global optimization algorithms: theory and application. 3rd edition / Thomas Weise., 2011.

$6$Sivanandam S.N. Introduction to Genetic Algorithms / Sivanandam S.N., Deepa S.N. – Berlin, Germany: Springer-Verlag Berlin Heidelberg, 2008.

$7.$ Randy L. Haupt. Practical genetic algorithms. 2nd edition / Randy L. Haupt, Sue Ellen Haupt. – New Jersey: John Wiley & Sons, Inc., Hoboken, 2004. – 272 с.

$8.$ Mitchell Melanie. An Introduction to Genetic Algorithms. – A Bradford Book The MIT Press, 1999.

$9.$ Hartmut Pohlheim. Examples of Objective Functions. – www.geatbx.com, 2006. – 21 с.

Mar 27, 2017