Ренгач С. М.

Вінницький торгово-економічний інститут Київського торгово-економічного університету

Застосування генетичних алгоритмів в сучасних інформаційних технологіях

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

· Опрацьовують не значення параметрів самої задачі, а їх закодовану форму (кодування параметрів);

· Здійснюють пошук рішення виходячи не з єдиної точки, а із деякої популяції (операції на популяціях);

· Використовують тільки цільову функцію, а не її похідні або додаткову інформацію (використання мінімуму інформації про задачу);

· Застосовують імовірнісні (не детерміновані) правила вибору (рандомізація операцій).

Для генетичних алгоритмів використовують визначення, залучені з генетики. Це популяція особин, ген, хромосома, генотип, фенотип, алель. Також використовують технічні терміни, такі як ланцюг, бінарна послідовність, структура. Популяція – кінцева кількість особин. Особи, що входять в популяцію, в генетичних алгоритмах представляються хромосомами із закодованими в них множинами параметрів задачі, або рішень, які ще називаються точками в просторі пошуку. Хромосоми(інша назва – ланцюги, кодові послідовності) – це упорядковані послідовності генів. Ген(або властивість, знак чи детектор) – це атомарний елемент генотипу, хромосоми. Генотип(структура) – це набір хромосом даної особи. Фенотип – це набір значень, що відповідає даному генотипу, тобто декодована структура або множина параметрів задачі (рішення, точки простору пошуку). Алель – це значення конкретного гена, також визначається як значення властивості або варіант властивості. Локус або позиція вказує місце розміщення даного гена в хромосомі (ланцюжку). Множина позицій генів – це локи. Дуже важливим поняттям в генетичних алгоритмах вважається функція пристосування, або функція оцінки. Вона визначає міру пристосування даної особи в популяції. Ця функція відіграє важливу роль, оскільки дозволяє оцінити ступінь пристосування конкретних особин в популяції і вибирати із них найбільш пристосованих (тобто тих, які мають найбільше значення функції пристосування) у відповідності з еволюційним принципом виживання найсильнішого (найкраще пристосованого). Функція пристосування чинить сильний вплив на функціонування генетичних алгоритмів і повинна мати точне і конкретне визначення. В задачах оптимізації цільова функція як правило і називається цільовою функцією. В теорії управління функція пристосування має вигляд функції погрішності, а в теорії ігор – вартості функції. У прогнозуванні функція пристосування повинна відображати точність прогнозу. На кожній ітерації генетичного алгоритму пристосованість кожної особини даної популяції оцінюється за допомогою функції пристосування, і на цій основі створюється наступна популяція особин, що утворюють множину потенційних рішень проблеми. Класичний генетичний алгоритм (простий генетичний алгоритм) складається з наступних етапів:

· Ініціалізація, вибір початкової популяції хромосом;

· Оцінка пристосованості хромосом в популяції;

· Перевірка умови зупинки алгоритму;

· Застосування генетичних операторів;

· Формування нової популяції;

· Вибір найкращої хромосоми.

Найбільш популярним програмним продуктом для вирішення задач оптимізації за допомогою генетичних алгоритмів є комплект Genetic Algorithm Tool математичного пакету Matlab. Даний пакет дозволяє знайти оптимальне рішення для оптимізовуваної функції, виходячи з деякої початкової популяції рішень а також дозволяє визначити масштабування, оператори відбору, репродукції, мутації, схрещування. Для створення власних програмних продуктів на основі генетичних алгоритмів використовують бібліотеку класів Galib, написану на С++, що поширюється на основі ліцензії GPL.

Література:

1. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. С польск. И. Д. Рудинского. – М.: Горячая линия – Телеком, 2006. – 452 с.: ил.

2. Панченко, Т. В. Генетические алгоритмы : учебно-методическое

пособие / под ред. Ю. Ю. Тарасевича. — Астрахань : Издательский дом

«Астраханский университет», 2007. — 87 .

3. www.habrahabr.ru – стаття «Генетические алгоритмы в MATLAB»