Щоб почати роботу із генетичним алгоритмом, необхідно в командному вікні MATLAB задати команду gatool. У результаті відкриється графічне вікно роботи із генетичним алгоритмом, яке умовно складається

Щоб почати роботу із генетичним алгоритмом, необхідно в командному вікні MATLAB задати команду gatool. У результаті відкриється графічне вікно роботи із генетичним алгоритмом, яке умовно складається із трьох частин:

- основної (Problem Setup and Results), де задається необхідна вхідна інформація та виводяться результати реалізації генетичного алгоритму;

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

- довідки (Quick Reference), де можна знайти інформацію про всі елементи двох попередніх складових інтерфейсу роботи із генетичним алгоритмом.

Тепер детальніше розглянемо елементи основної (Problem Setup and Results) частини вікна роботи із генетичним алгоритмом. За необхідності із елементами підменю налаштувань (Options) можна ознайомитись з допомогою довідки та шляхом безпосереднього експериментування.

Finless function – ім’я функції (m-файлу), значення якої необхідно мінімізувати. У випадку, якщо потрібно знайти максимальне значення функції, то достатньо лише поставити перед результуючим значенням знак “-”. Поле заповнюють у такому форматі – @Ім’я_функції.

Number of variables – кількість незалежних змінних, за якими буде оптимізуватися значення функції.

Linear inequalities – обмеження моделі у вигляді лінійних нерівностей. У векторній формі A*x ≤ b, де A – матрицякоефіцієнтів; x – вектор незалежних змінних; b – праві частини нерівностей (обмеження).

Linear equalities –обмеження моделі у вигляді лінійних рівнянь. У векторній формі за аналогією до попереднього поля Aeq*x = beq.

Bounds – нижні та верхні межі значень незалежних змінних, що задаються у формі векторів. Lower – нижні межі; Upper – верхні межі.

Nonlinear constraint function – обмеження моделі у вигляді нелінійних фунцій. Задаються за допомогою відсилання до відповідної функції (m-файла), що здійснює розрахунок значень лівих частин рівнянь та нерівностей.

Integer variable indices –поле задання обмежень на цілочисельність окремих незалежних змінних.

Далі розглянемо реалізацію генетичного алгоритму на прикладі вирішення задачі комівояжера.

Нехай необхідно, перебуваючи в Києві, побувати в Тернополі, Житомирі, Рівному та Харкові і повернутися знову до Києва. Загальна подолана відстань при цьому має бути мінімальною. Наведемо таблицю відстаней:

	Київ	Тернопіль	Житомир	Рівне	Харків
Київ
Тернопіль
Житомир
Рівне
Харків

Для розв’язання даної задачі за допомогою генетичного алгоритму в середовищі MATLAB перш за все необхідно описати функцію для визначення загальної відстані. Для цього із початкового вікна MATLAB створюємо новий m-файл: File -> New -> Function. Функція матиме наступний вигляд:

function [S] = Dovzhyna(X)

n=5

S=0

A=[0 427 131 318 478; 427 0 298 162 987; 131 298 0 187 690; 318 162 187 0 805; 478 987 690 805 0];

S=S+A(1,X(1));

for i=2:1:n-1

S=S+A(X(i-1),X(i));

end

S=S+A(X(n-1),1);

end

Тут n – загальна кількість міст; X – вектор, елементи якого є порядковими номерами Тернополя, Житомира, Рівного та Харкова відповідно до черговості їх відвідування комівояжером; A – матриця (таблиця) відстаней між містами. S – загальна відстань, яку має подолати комівояжер.

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

Тепер необхідно задати обмеження на значення елементів вектора X, а саме, щоб вектор складався із порядкових чисел 2,3,4,5, які можуть повторюватися лише один раз. Для цього перш за все необхідно задати нижнє та верхнє значення кожного елемента вектора, увівши в поле Lower вектор [2 2 2 2], а поле Upper - вектор [5 5 5 5], а також вказати на цілочисельність значень елементів вектора, увівши в поле Integer variable indices вектор [1 2 3 4]. Це означає, що 1-й, 2-й, 3-й та 4-й елемент вектора X має бути цілим числом від 2 до 5.

Для того, щоб значення елементів вектора не повторювалися, введемо наступні обмеження:

У нашому випадку обмеження у вигляді рівнянь ми у MATLAB задати не можемо. Тому перетворимо дані вирази, щоб отримати нерівності, праві частини яких нулі:

Реалізуємо дані обмеження у вигляді функції (m-файлу):

function [c, ceq] = eqCon(X)

ceq = [];

n=5;

s=0;

d=1;

seq=0;

deq=1;

for i=2:1:n

s=s+X(i-1);

d=d*X(i-1);

seq=seq+i;

deq=deq*i;

end

c1=s-seq-0.1;

c2=-s+seq-0.1;

c3=d-deq-0.1;

c4=-d+deq-0.1;

c = [c1;c2;c3;c4]

end

Тепер можемо ввести усі необхідні властивості у вікні роботи з генетичним алгоритмом. Problem Setup and Results має бути заповнено наступним чином:

На попередньому скріншоті представлені також результати, отримані після натиснення кнопки Start. Як бачимо, поїздка комівояжера буде наступною: Київ -> Рівне -> Харків -> Житомир -> Тернопіль -> Київ. Загальна відстань становитиме 1874 км.

Якщо обрати в підменю опцій виведення графіків Bets Fitness та Best Individual, то можна побачити, яким чином генетичний алгоритм здійснював оптимізацію.

Дата добавления: 2015-09-29