Короткі теоретичні відомості

Генетичний алгоритм (англ. genetic algorithm) – це евристичний алгоритм пошуку, що використовується для розвязання завдань оптимізації й моделювання шляхом випадкового підбору, комбінування й варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію, є різновидом еволюційних обчислень. Відмінною рисою генетичного алгоритму є акцент на використанні оператора «схрещування», що виконує операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещування в живій природі.

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

Індивідуум – деяка точка, у якій можливий розрахунок функції придатності. Значення функції придатності індивідуалізованого об'єкта саме і є її кількісний показник. Наприклад, якщо функція придатності має такий вигляд:

f(x1,x2,x3) = (2x1 + 1)² + (3x2 + 4)² + (x3 – 2)²,

то вектор (2, 3, 1), розмірність якого дорівнює числу змінних даної задачі, і є індивідуум. Кількісний показник індивідуума як об'єкта (2, 3, 1) буде f(2, -3, 1) = 51. Об'єкт індивідуума іноді називається геном, а компоненти вектора називаються генами.

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

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

Genetic Algorithm and Direct Search Toolbox

Genetic Algorithm and Direct Search Toolbox призначений для розширення функціональних можливостей пакета MATLAB і, зокрема, Optimization Toolbox новими видами алгоритмів оптимізації. Подібні методи й алгоритми найчастіше використовуються у випадку, коли цільова функція є переривчастою, істотно нелінійною, стохастичною і не має похідних або ці похідні є недостатньо визначеними. Genetic Algorithm and Direct Search Toolbox допоможе розв’язати задачі, які або неможливо розв’язати звичайними методами, або виникають нестійкі рішення при застосуванні стандартних математичних
методів.

Genetic Algorithm and Direct Search Toolbox містить у собі програми для розв’язання задач оптимізації на основі використання наступних методів:

- генетичний алгоритм;

- метод прямого пошуку.

Завданням даного тулбоксу є пошук мінімуму функції придатності.

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

type function_name.

Генетичний алгоритм – це метод розв’язання задач оптимізації на основі природного добору, аналогічно тому, як це відбувається в процесі біологічної еволюції. У генетичному алгоритмі відбувається багаторазова модифікація сімейства окремих розв’язків. На кожному кроці проводиться відбір вибраних навмання суб'єктів з отриманого поточного розв’язання, що називається батьківським і яке використовується для генерації наступного дочірнього покоління. За допомогою послідовного відбору поколінь відбувається "еволюція" у напрямку до оптимального розв’язання. Генетичний алгоритм можна застосовувати до різноманітних задач оптимізації, які недостатньо чітко вписуються в стандартні оптимізаційні алгоритми.

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

- правило відбору – відбирає об'єкти, що називаються батьківськими та які становлять основу наступного покоління з поточного розв’язання;

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

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

Генетичний алгоритм відрізняється від стандартних методів оптимізації наступними особливостями (табл. 6.1):

Таблиця 6.1 – Порівняння стандартного й генетичного алгоритмів

Стандартний алгоритм	Генетичний алгоритм
На кожній ітерації генерується одна єдина точка. Отримана послідовність точок сходиться до оптимального рішення.	На кожній ітерації генерується сімейство точок. Отримане сімейство сходиться до оптимального розв’язання.
Вибір наступної точки здійснюється на основі детермінованих розрахунків.	Вибір наступного сімейства точок здійснюється на основі стохастичних розрахунків.

Структура алгоритму

Генетичний алгоритм працює відповідно до наступної схеми:

1) для організації початку рахунку створюється довільне вихідне
сімейство;

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

– відмічається кожний член поточного сімейства за допомогою обчислення відповідного значення придатності;

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

– вибираються батьківські значення на основі значень їхньої
придатності;

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

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

– заміна поточного сімейства на дочірнє з метою формування наступного покоління;

3) зупинка алгоритму здійснюється тоді, коли виконується будь-який критерій зупинки.

Графічний інструментарій генетичного алгоритму

Інструментарій генетичного алгоритму – це фактично графічний інтерфейс користувача, за допомогою якого користувач має можливість роботи з генетичним алгоритмом без звернення до нього з командного рядка. Для звернення до Інструментарію генетичного алгоритму варто виконати команду gatool, при виконанні якої відкривається наступний інструментарій (рис. 6.1):

Рисунок 6.1 – Графічний інструментарій

Для роботи з Інструментарієм генетичного алгоритму варто ввести наступну інформацію:

- Fitness function – підлягаюча мінімізації цільова функція. У форму @fitnessfun вводиться функція придатності, де fitnessfun.m – це М-файл для розрахунку функції придатності. Знак «@» створює описувач функції для fitnessfun.

- Number of variables – розмір вхідного вектора для функції
придатності.

Для виконання генетичного алгоритму варто клікнути мишкою на кнопку " Start ". Далі в інструментарії в панелі " Status and Results " здійснюється відображення результатів оптимізації.

За допомогою панелі " Options " можливо настроїти опції генетичного алгоритму. Для огляду опцій для заданого режиму в даній панелі варто клікнути на знак "+".

Основними параметрами в GATool є:

- популяція (вкладка "Population");

- масштабування (вкладка "Fitness Scaling");

- оператор відбору (вкладка "Selection");

- оператор репродукції (вкладка "Reproduction");

- оператор мутації (вкладка "Mutation");

- оператор схрещування (вкладка "Crossover");

- перенесення особин між популяціями (вкладка "Migration");

- спеціальні параметри алгоритму (вкладка "Algorithm settings");

- задання гібридної функції (вкладка "Hybrid function");

- задання критерію зупинки алгоритму (вкладка "Stopping criteria");

- відображення різної додаткової інформації у ході роботи генетичного алгоритму (вкладка "Plot Functions");

- відображення результатів роботи алгоритму у вигляді нової функції (вкладка "Output function");

- задання набору інформації для виведення в командне вікно (вкладка " Display to command window ");

- спосіб обчислення значень оптимізованої й обмежувальної функцій (вкладка " User function evaluation ").

У вкладці настроювання популяцій (" Population ") користувач має можливість вибрати тип математичних об'єктів, до якого будуть належать особини всіх популяцій (подвійний вектор, бітовий рядок або користувацький тип). При цьому варто враховувати, що використання бітового рядка й користувацьких типів накладають обмеження на перелік припустимих операторів створення, мутації й схрещування особин. Також вкладка популяції дозволяє налаштовувати розмір популяції (Population size – зі скількох особин буде складатися кожне покоління) і яким чином буде створюватися початкове покоління (Creation function: Uniform – якщо відсутні обмеження, в іншому випадку – Feasible population). Крім того, є можливість задати вручну початкове покоління (використовуючи пункт Initial population) або його частину, початковий рейтинг особин (пункт Initial scores), а також задати обмежувальний числовий діапазон, якому повинні належати особини початкової популяції (Initial range).

У вкладці масштабування (" Fitness Scaling ") зазначається функція масштабування, яка конвертує значення, що досягаються оптимізуючою функцією в значення, що лежать у межах, припустимих для оператора відбору. При виборі як функції масштабування параметра Rank масштабування буде приводитися до рейтингу, тобто особинам присвоюється рейтинговий номер (для кращої особини – одиниця, для наступної – двійка і так далі). Пропорційне масштабування (Proportional) задає ймовірності пропорційно заданому числовому ряду для особин. При виборі опції Top найбільше рейтингове значення присвоюється відразу декільком найбільш значущим особинам (їхнє число вказується у вигляді параметра). При виборі масштабування типу Shift linear є можливість указати максимальну ймовірність найкращої особини.

Вкладка " Selection " дозволяє вибрати оператор відбору батьківських особин на основі даних з функції масштабування. Як доступні для вибору варіантів оператора відбору пропонуються наступні:

- Tournament – випадково вибирається зазначене число особин, серед них на конкурсній основі вибираються кращі;

- Roulette – імітується рулетка, у якій розмір кожного сегмента встановлюється відповідно до його ймовірності;

- Uniform – батьки вибираються випадковим чином відповідно до заданого розподілу й з урахуванням кількості батьківських особин і їхніх
імовірностей;

- Stochastic uniform – будується лінія, у якій кожному батькові ставиться у відповідність її частина певного розміру (залежно від імовірності батька), потім алгоритм пробігає по лінії кроками однакової довжини й вибирає батьків залежно від того, на яку частину лінії потрапив крок.

Вкладка репродукції (" Reproduction ") уточнює, яким чином відбувається створення нових особин. Пункт Elite count дозволяє вказати число особин, які гарантовано перейдуть до наступного покоління. Пункт Crossover fraction указує частину особин, які створюються шляхом схрещування. Інша частина створюється шляхом мутації.

У вкладці оператора мутації (" Mutation ") вибирається тип оператора мутації. Доступні наступні варіанти:

- Gaussian – додає невелике випадкове число (відповідно до розподілу Гаусса) до всіх компонентів кожного вектора-особини;

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

- Adaptive feasible – генерує набір напрямків залежно від останніх найбільш удалих і невдалих поколінь і з урахуванням обмежень, що накладаються, просувається вздовж усіх напрямків на різну довжину;

- Custom – дозволяє задати власну функцію.

Вкладка схрещування (" Crossover ") дозволяє вибрати тип оператора схрещування: одноточкове, двоточкове, евристичне, арифметичне або розсіяне.

У вкладці " Migration " можна задавати правила, згідно з якими особини будуть переміщатися між підпопуляціями в межах однієї популяції. Підпопуляції створюються, якщо як розмір популяції зазначений вектор, а не натуральне значення. У даній вкладці можна вказати напрямок міграції (forward – у наступну підпопуляцію, both – у попередню й наступну), частину мігруючих особин (Fraction) і частоту міграції (скільки поколінь проходить між міграціями).

Вкладка спеціальних опцій алгоритму (" Algorithm settings ") дозволяє задавати параметри розв’язання системи нелінійних обмежень, що накладаються на алгоритм.

Вкладка " Hybrid function " дозволяє задати ще одну функцію мінімізації, що буде використовуватися після закінчення роботи алгоритму. Як можливі гібридні функції доступні наступні вбудовані в саме середовище MATLAB
функції:

- none (не використовувати гібридну функцію);

- fminsearch (пошук мінімального зі значень);

- patternsearch (пошук за зразком);

- fminunc (для необмеженого алгоритму);

- fmincon (для алгоритму із заданими обмеженнями).

У вкладці критерію зупинки (" Stopping criteria ") зазначаються ситуації, при яких алгоритм робить зупинку. При цьому задаються наступні параметри:

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

- Time limit – ліміт часу на роботу алгоритму;

- Fitness limit – якщо оптимізоване значення менше або дорівнює даному ліміту, то алгоритм зупиниться;

- Stall generations – алгоритм зупиняється у випадку, якщо немає поліпшення для цільової функції в послідовності наступних один за одним поколінь довжиною Stall generations;

- Stall time limit – алгоритм зупиняється у випадку, якщо немає поліпшення для цільової функції протягом інтервалу часу в секундах рівного Stall time limit;

- Function tolerance і Nonlinear constraint tolerance – мінімальні значення змін оптимізованої та обмежувальної функцій відповідно, при яких алгоритм продовжить роботу.

Вкладка " Plot Functions " дозволяє вибирати різну інформацію, що виводиться у ході роботи алгоритму й показує як коректність його роботи, так і конкретні результати, що досягаються алгоритмом. Найбільш важливими й використовуваними для відображення параметрами є:

- Plot interval – число поколінь, по закінченні якого відбувається чергове відновлення графіків;

- Best fitness – відображення найкращого значення оптимізованої функції для кожного покоління;

- Best individual – відображення найкращого представника покоління при найкращому результаті в кожному з поколінь;

- Distance – відображення інтервалу між значеннями особин у
поколінні;

- Expectation – виводить ряд імовірностей і відповідні їм особини
поколінь;

- Genealogy – відображення генеалогічного дерева особин;

- Range – відображення найменшого, найбільшого й середнього значень оптимізованої функції для кожного покоління;

- Score diversity – вивести гістограму рейтингу в кожному поколінні;

- Scores – відображення рейтингу кожної особини в поколінні;

- Selection – відображення гістограми батьків;

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

- Custom – відображення на графіку деякої зазначеної користувачем функції.

Вкладка виведення результатів у вигляді нової функції (" Output function ") дозволяє включити виведення історії роботи алгоритму в окремому вікні із заданим інтервалом поколінь (прапор History to new window і поле Interval відповідно), а також дозволяє задати й вивести довільну вихідну функцію, що задається в поле Custom function.

Вкладка " User function evaluation " описує, у якому порядку відбувається обчислення значень оптимізованої та обмежувальної функцій (окремо, паралельно в одному виклику або одночасно).

Вкладка " Display to command window " дозволяє задавати інформацію, що відображається в основному командному вікні MATLAB при роботі алгоритму. Можливі наступні значення: Off – немає виведення в командне вікно, Iterative – виведення інформації про кожну ітерацію працюючого алгоритму, Diagnose – виведення інформації про кожну ітерацію й додаткові відомості про можливі помилки й змінені ключові параметри алгоритму, Final – виводиться тільки причина зупинки й кінцеве значення.