Визначення генетичного алгоритму

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

популяції індивідів, що репрезентують розв’язки задачі;

функцію корисності, що відіграє роль оточення;

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

значення параметрів, що використовуються генетичним алгоритмом.

Ці елементи можуть бути охоплені наступним формальним визначенням генетичного алгоритму [Error: Reference source not found].

Означення. Генетичний алгоритм (GA) – це імовірнісний адаптивний алгоритм, який містить такі оператори і параметри:

Р – популяція N індивідів Кожен індивід , i=1,2,...,N, – це вектор двійкових значень фіксованої довжини n, що відображає допустимий розв’язок задачі, тобто . Представлення вектора часто називають хромосомним набором індивіда ;

f – функція корисності, що ставить у відповідність кожному , i=1,2,...,N деяке дійсне число:

;

– оператор вибору батьків, що вибирає індивідів з популяції P:

;

– набір генетичних операторів, що містить оператор схрещування , оператор мутацій і, можливо, інші оператори, які використовують для утворення v нащадків , i=1,2,...,v, від вибраних u батьків:

;

– оператор знищення (або смерті), певних індивідів з популяції Р. Перехід від старої популяції до нової виконують за формулою

,

де Р(t) – популяція в момент часу t;

– критерій зупинки алгоритму

.

Особливості застосування генетичних алгоритмів для розв’язування задач розподілу ресурсів серед вузлів комп’ютерних мереж

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

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

(Ошибка! Текст указанного стиля в документе отсутствует..1)

за умов

, (Ошибка! Текст указанного стиля в документе отсутствует..2)

, (Ошибка! Текст указанного стиля в документе отсутствует..3)

(Ошибка! Текст указанного стиля в документе отсутствует..4)

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

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

M – кількість різних файлів бази даних, кількість різних задач або кількість різних типів задач, призначених до розв’язування;

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

N – кількість вузлів локальної комп’ютерної мережі, кластера чи грід-мережі;

X – розподіл копій файлів серед вузлів мережі або розподіл задач серед вузлів кластера.

Такі задачі є підвидом більш широкого класу задач цілочислового математичного програмування або задач дискретної оптимізації. Дана задача належить до класу NP-повних задач [Error: Reference source not found, Error: Reference source not found] і невідомий ніякий поліноміальний алгоритм її розв’язування, тому будемо шукати оптимальний розподіл використовуючи генетичний алгоритм.