Генетичнi алгоритми в теоретичних дослiдженнях еволюцiйних процесiв

Анотація.

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

Ключові слова:

Генетичні алгоритми, еволюційні алгоритми, нейронні мережі, нейрон, прості організми, елітизм, мутація, схрещування.еволюційний алгоритм, генетичний алгоритм, задача комівояжера. Еволюція - це основний механізм, за допомогою якого життя адаптується для того, щоб виживати та розвиватися. Це біологічне явище надихає такі успішні оптимізаційні методи, як генетичні алгоритми. Як відомо еволюція спирається на поняття випадкової мутації та випадкової генетичної рекомбінації. Ці поняття стають основою для генетичного алгоритму. Еволюція і навчання - це дві структури оптимізації, які в живих системах працюють в різних масштабах та з різними перевагами. Відповідні комбінації двох забезпечують взаємодоповнюваність і є важливою частиною успіху живих систем. Генетичні алгоритми та нейронні мережі стануть основую для реалізації моделі мікроеволюційної поведінки групи простих організмів. Поведінка та розвиток організмів повинні відповідати реальним прикладам. В даній моделі будуть реалізовані такі біологічні поняття, як розвиток, схрещування, селекція. Також на основі реалізованої моделі буде розглянути залежність поведінки членів популяції від набору параметрів. А саме розмір популяції та еліт в самій популяції та складності організмів. Актуальність роботи. Нейронні мережі на даний момент використовують у широкому спектрі задач. Використання генетичних алгоритмів для оптимізації нейронних мереж дозволяє отримати позитивний виграш в часових ресурсах. Дослідження на тлі широкого спектру існуючих моделей дозволить виявити найкращі рішення, та отримати нові підходи до розв’язку задачі. Еволюційна теорія стверджує, що кожен біологічний вид цілеспрямовано розвивається і змінюється для того, щоб щонайкраще пристосуватися до навколишнього середовища. У процесі еволюції багато видів комах і риб придбали захисне фарбування, їжак став невразливим завдяки голкам, людина стала власником дуже складної нервової системи. Можна сказати, що еволюція - це процес оптимізації всіх живих організмів. Розглянемо, якими ж засобами природа вирішує цю задачу оптимізації. Генетичний алгоритм— це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.Особливістю генетичного алгоритму є акцент на використання оператора «схрещення», який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі. «Батьком-засновником» генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого «Адаптація в природних і штучних системах» (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень. Перші спроби симуляції еволюції були проведені у 1954 році Нільсом Баричелліна комп'ютері, встановленому в Інституті перспективних досліджень Принстонського університету. Його робота, що була опублікована у тому ж році, привернула увагу громадськості. З 1957 року, австралійський генетик Алекс Фразер опублікував серію робіт з симуляції штучного відбору серед організмів з множинним контролем вимірюваних характеристик. Це дозволило комп'ютерній симуляції еволюційних процесів та методам, які були описані у книгах Фразера та Барнела(1970) та Кросбі(1975), з 1960-х років стати більш розповсюдженим видом діяльності серед біологів. Симуляції Фразера містили усі найважливіші елементи сучасних генетичних алгоритмів. До того ж, Ганс-Іоахім Бремерман в 1960-х опублікував серію робіт, які також приймали підхід використання популяції рішень, що піддаються відбору, мутації та рекомбінації, в проблемах оптимізації. Дослідження Бремермана також містили елементи сучасних генетичних алгоритмів. Також варто відмітити Річарда Фрідберга, Джоржа Фрідмана та Майкла Конрада.Хоча Баричеллі у своїй роботі 1963 р. займався симуляцією можливості машини грати у просту гру, штучна еволюція стала загальновизнаним методом оптимізації після роботи Інго Рехенберга та Ханса-Пауля Швереля у 60-х та на початку 70-х років двадцятого століття — група Рехенсберга змогла вирішити складні інженерні проблеми згідно зі стратегіями еволюції. Іншим підходом була техніка еволюційного програмування Лоренса Дж. Фогеля, яка була запропонована для створення штучного інтелекту. Еволюційне програмування, яке спочатку використовувало кінцеві автомати для передбачення обставин, та використовували різноманіття та відбір для оптимізації логіки передбачення. Генетичні алгоритми стали особливо відомі завдяки роботі Дж. Холанда на початку 70-х років та його книзі «Адаптація у природних та штучних системах» (1975).Його дослідження були основані на експериментах з клітинними автоматами та на його роботах, що були написані в університеті Мічигану. Він ввів формалізований підхід для передбачення якості наступного покоління, відомий як Теорема схем. Дослідження в області генетичних алгоритмів залишалось більше теоретичним до середини 80-х років, коли була, нарешті, проведена Перша міжнародна конференція з генетичних алгоритмів (Піттсбург, Пенсильванія (США)). З ростом дослідницького інтересу суттєво виросла обчислювальна потужність комп'ютерів, що дозволило використовувати нову обчислювальну техніку на практиці. Наприкінці 80-х років, компанія General Electric почала продаж першого в світі продукту, який працював з використанням генетичного алгоритму. Це був набір промислових обчислювальних засобів. В 1989 інша компанія Axcelis, Inc. випустила Evolver — перший у світі комерційний продукт на генетичному алгоритмі для персональних комп'ютерів. Журналіст The New York Times в технологічній сфері Джон Маркофф писав про Evolver у 1990 році.Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції допасованості, в результаті якої кожній особі присвоюється певне значення допасованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень допасованості вибираються особи, допущені до схрещення (селекція). До осіб застосовується «генетичні оператори» (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation)), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:знаходження глобального, або надоптимального вирішення;вичерпання числа поколінь, що відпущені на еволюцію;вичерпання часу, відпущеного на еволюцію. Генетичні алгоритми можуть використовувати для пошуку рішень в дуже великих і важких просторах пошуку.

Генетичні алгоритми застосовується для вирішення наступних задач:

1. Оптимізація функцій 2. Оптимізація запитів в базах даних 3. Різноманітні задачі на графах (задача комівояжера, розфарбування) 4. Налаштування і навчання штучної нейронної мережі 5. Задачі компоновки 6. Створення розкладів 7. Ігрові стратегії 8. Апроксимація функцій 9. Штучне життя 10. Біоінформатика (згортання білків) 11. Синтез конструкцій антен

Схема роботи генетичного алгоритму

Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції допасованості, в результаті якої кожній особі присвоюється певне значення допасованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень допасованості вибираються особи, допущені до схрещення (селекція). До осіб застосовується «генетичні оператори» (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation)), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути: • знаходження глобального, або надоптимального вирішення; • вичерпання числа поколінь, що відпущені на еволюцію; • вичерпання часу, відпущеного на еволюцію. Генетичні алгоритми можуть використовувати для пошуку рішень в дуже великих і важких просторах пошуку. Різновиди і особливості алгоритму в різних галузях хімії • У комбінаторній хімії — метод дизайну бібліотеки шляхом оцінки відповідності певних бажаних властивостей (пр., рівня активності в біологічних пошуках, або розрахунково визначених властивостей набору речовин), передбачених за допомогою функції, встановленої статистичними методами при аналізі співвідношення структура — властивість. Ще більш оптимальний дизайн пов'язаний з евристичним процесом, який нагадує генетичну селекцію, де застосовується реплікація, мутація, вилучення. • У хемометриці — механізм оптимізації, заснований на механізмі дарвінівської еволюції, де використовуються випадкові мутації, процедури схрещення та відбору для розробки кращої моделі чи розв'язку порівняно з тим, які було отримано, виходячи зі стартової сукупності чи вибірки. • У комп'ютерній хімії — комп'ютерний метод генерування та тестування комбінацій можливих вхідних параметрів для знаходження оптимальних вихідних значень. Використовується для оптимізації у випадку систем з великою кількістю змінних параметрів, зокрема при конформаційному аналізі багатоатомних складних молекул. Включає методи, що базуються на поняттях природної еволюції, такі як генетична комбінація, мутація та природний відбір.

Етапи генетичного алгоритму

Можна виділити такі етапи генетичного алгоритму: 1. Створення початкової популяції: 2. Обчислення функції допасованості для осіб популяції (оцінювання) 3. Повторювання до виконання критерію зупинки алгоритму: 1. Вибір індивідів із поточної популяції (селекція) 2. Схрещення або/та мутація 3. Обчислення функції допасованості для всіх осіб 4. Формування нового покоління Створення початкової популяції Перед першим кроком необхідно випадковим чином створити деяку початкову популяцію. Навіть якщо популяція виявиться абсолютно неконкурентоздатною, генетичний алгоритм все одно достатньо швидко переведе її в придатну для життя популяцію. Таким чином, на першому кроці можна не старатися зробити надто допасованих осіб, достатньо, щоб вони відповідали формату осіб популяції, і на них можна було порахувати функцію допасованості. Наслідком першого кроку є популяція H, що налічує N осіб. Відбір Оператори вибору На етапі відбору необхідно із всієї популяції вибрати її певну долю, яка залишиться в «живих» на цьому етапі популяції. Є декілька способів провести відбір. Ймовірність виживання особи h повинна залежати від значення її допасованості Fitness(h). Сама ж доля відібраних s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. Внаслідок відбору із N осіб популяції H повинні залишитись sN осіб, які ввійдуть в наступну популяцію H'. Решта осіб «загине». Розмноження Розмноження в генетичних алгоритмах зазвичай статеве — щоб «народити» нащадка, необхідно декілька батьків, зазвичай потрібна участь двох. Розмноження в різних алгоритмах описується по різному — воно, звісно, залежить від формату осіб. Головна вимога до розмноження — щоб нащадок чи нащадки мали можливість успадкувати риси всіх батьків, «змішавши» їх якимось достатньо розумним чином. Розмноження або оператор рекомбінації застосовують відразу ж після оператора відбору батьків для отримання нових особин-нащадків. Сенс рекомбінації полягає в тому, що створені нащадки повинні наслідувати генну інформацію від обох батьків. Розрізняють дискретну рекомбінацію і кросинговер. Приклад операції розмноження: Вибрати (1-s)p/2 пар гіпотез із H і провести з ними розмноження, отримавши по два нащадка від кожної пари (якщо розмноження описано так, щоб давати одного нащадка, необхідно вибрати (1 — s)p пар), і додати цих нащадків в H'. В результаті H' буде складатися з N осіб. Особи для розмноження зазвичай вибираються із всієї популяції H, а не із тих, що вижили на першому кроці (хоча останній варіант теж має право на існування). Справа в тому, що головна проблема генетичних алгоритмів — недостача різноманітності (diversity) в особах. Достатньо швидко виділяється єдиний генотип, який являє собою локальний максимум і згодом всі елементи популяції програють йому в відборі, і вся популяція «забивається» копіями цієї особи. Існують різні способи боротьби із таким небажаним ефектом; один з них — вибір для розмноження не з самих «допасованих», а взагалі зі всіх осіб.

Мутації

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

Важливою особливістю, властивою практично всім науковим і технічним проблемам, є їхній оптимізаційний характер. На сучасному етапі перед людством стоять оптимізаційні задачі, які потребують розв’язування і прийняття виважених та ефективних рішень. Процес прийняття таких рішень може бути доволі різноманітним. Але в будь-якому випадку прийняти виважене ґрунтовне рішення складно без використання математичних моделей і методів. Для того, щоб використати адекватну модель, необхідно насамперед сформулювати проблему, з'ясувати, до якого класу задач вона відноситься і які математичні моделі й методи доречно застосовувати для її розв’язування. За допомогою еволюційних методів проводять аналіз і адаптацію вже створених популяцій (рішень) до нових умов середовища, тим самим скорочують час роботи алгоритмів, їх машинної реалізації та навчання. Питаннями оптимізації та еволюційними алгоритмами займалися такі вчені як Растригін Л. А. [8], Холанд Дж. [1-3], Голденберг Д. [12], Курейчик В. М. [2, 6], Погорілий С. Д., Білоус Р. В. [2], Самотній В., Дзелендзяк У. [3], Дубровін В. І., Федорченко Є.М. [1], Рутковська Д., Піліньский М., Рутковський Л. [9], Погорілий С. Д. [6], Субботін С. О., Олійник А. О., Олійник О. О. [4] та інші. Історія еволюційних алгоритмів починається з розробок різних незалежних моделей. Перші публікації «Симбіогенетичні еволюційні процеси, реалізовані штучними методами» («Symbiogenetic evolution processes realised by artificial methods» (1957)) та «Цифрова перевірка еволюційних теорій» («Numerical testing of evolution theories" (1962)), які належать Барічеллі H. А., були спрямовані насамперед на розуміння механізмів природного феномену спадковості. Відомі початківці штучного моделювання еволюційних процесів і генетичних систем А.Фрейзер, Г.Бремерманн, Г.-Ф.Швефель, I. Рехенберг досліджували еволюційні стратегії. У 1966 році Л.Фогель, А.Оуенз та М.Волш запропонували і провели дослідження еволюції простих автоматів, у яких були передбачені символи у числових послідовностях, заснувавши таким чином еволюційне програмування [10]. Системи моделювання еволюційних процесів можна розподілити на дві категорії: 1. Cистеми, в яких використовуються лише еволюційні принципи. Їх використовують для опису математичних моделей функціональної оптимізації. До таких систем відносять еволюційні алгоритми, такі як еволюційне програмування, генетичні алгоритми, еволюційні стратегії. 2. Системи, які є реалістичнішими з біологічної точки зору, але які не мають широкого прикладного застосування. Їх менше використовують для аналізу технічних завдань. За допомогою таких систем моделюють складні, наближені до реальних природних процесів, дії, до них відносять так зване «штучне життя». Наразі назвою еволюційні алгоритми охоплюють усі обчислювальні і оптимізаційні методи, в основу яких покладена еволюційна метафора: – еволюційні стратегії, – еволюційне програмування, – генетичні алгоритми, – генетичне програмування. Ці методи вирізняються здебільшого представленнями можливих розв'язків задачі. В еволюційних стратегіях набори хромосом представляють векторами дійсних чисел, в генетичних алгоритмах - векторами двійкових чисел, в еволюційному програмуванні – скінченними автоматами, а в генетичному програмуванні – деревами (списками). Еволюційне програмування винайдене Лоуренсом Фогелем у 1960-1965 роках. Він помітив можливість ще одного, альтернативного підходу до проблем штучного інтелекту – моделювання не кінцевого результату еволюції, а моделювання самого процесу еволюції як засобу «відпрацювання розумної поведінки» і можливостей передбачення різних явищ у середовищі. Л. Фогель виконав низку експериментів, у яких скінченні автомати представляли собою особин у популяції розв’язків задачі. У цих скінченних автоматах було передбачено використання символів у цифрових послідовностях, які, еволюціонуючи, ставали все придатнішими до розв’язування поставленої задачі. В еволюційному програмуванні популяцію скінченних автоматів розглядають в експериментальному середовищі та отримують певну послідовність символів. Для кожного автоматабатька виконується процедура звірення кожного наступного символу з відповідним йому прогнозованим вихідним символом з автомата і оцінюється значення функції втрат для цього виходу. Після останнього прогнозу обчислюється «життєздатність» такого автомату чи програми. Автоматинащадки утворюють випадковою мутацією автоматів-батьків і теж оцінюють. Найкращі автомативідбираються для наступного покоління, і процес повторюється. У разі необхідності прогнозу нових символів, нове спостереження додається до старих [11]. Таким чином, в еволюційному програмуванні, на відміну від генетичних алгоритмів, моделюють еволюцію більш як процес пристосувальної поведінки особин популяції або виду, аніж процес адаптації генів. Еволюційні стратегії у багатьох аспектах подібні і до генетичних алгоритмів, і до еволюційного програмування, бо в них теж імітують процеси природної еволюції. Однак, вони мають суттєву відмінність на прикладному рівні. У той час як генетичні алгоритми створені для оптимізації дискретних або цілочислових розв’язків задач, еволюційні стратегії застосовують для неперервних значень, які є типовішими для експериментальних задач. Основні відмінності еволюційних стратегій від інших оптимізаційних методів і еволюційних алгоритмів [14]: пошук від однієї популяції до іншої на противагу від однієї особини до іншої; використання даних про саму функцію, а не її похідних; використання ймовірнісних, а не детермінованих, методів за переходу від популяції до популяції; кодування розв’язків векторами дійсних чисел; зосередження уваги на вплив генетичних операторів на зміни фенотипу; адаптивний крок мутації – крок мутації еволюціонує разом з розв'язком, оскільки цей параметр пов’язаний з хромосомами; невелика різниця між батьками та нащадками в процесі схрещування, що обумовлено сильною взаємопов'язаністю – невеликі зміни у перших відображаються невеликими змінами в останніх. Технологія еволюційних стратегій була винайдена І. Рехенбергом, а згодом розвинута Г.- П. Швефелем та іншими вченими. Генетичне програмування було розроблене у Сполучених Штатах у 90-их роках, серед перших дослідників − Дж. Коза. Особливістю цього виду еволюційних алгоритмів є використання нелінійних хромосом (графи, дерева). Здебільшого використовують або мутацію, або схрещування. Мутація полягає в заміні випадковим деревом деякого піддерева розв'язку, а схрещування - в обміні батьківських хромосом піддеревами. На відміну від лінійного подання даних, подано через деревадає можливість отримувати більш гнучкі зміни у розв'язках, а також оперувати хромосомами різного розміру (деревами з різною глибиною чи величиною). Генетичні алгоритми використовуються для розв’язування задач оптимізації і моделювання шляхом послідовного добору, комбінування і варіацій шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Батьком сучасної теорії генетичних алгоритмів вважається Дж. Е. Голланд. Він розпочав роботу над алгоритмами, пов’язаними з діями над послідовностями двійкових чисел, які за аналогією до біологічних понять назвали хромосомами. В його алгоритмах виконувались операції над цими хромосомами, імітуючи процеси природного відбору і еволюції. В 1975 році Дж. Голланд опублікував найвідомішу свою працю «Адаптація у природних і штучних системах» («Adaptation in Natural and Artificial Systems»). Після цієї публікації інтерес до новоствореної галузі безупинно зростав. У книзі вводиться власне ідея генетичного алгоритму («репродуктивний план Голланда» [7, с. 6]) і пропонується схема такого алгоритму, який згодом назвали класичним або канонічним генетичним алгоритмом (canonical GA). Від традиційних методів оптимізації генетичні алгоритми вирізняються тим, що в них використовують не значення параметрів задачі, а їх закодовані форми (кодування параметрів); здійснюють пошук розв’язку не з єдиної вихідної точки, а відштовхуючись від деякої популяції (операції над популяціями); використовують лише цільову функцію, а не її похідні чи інші допоміжні дані; застосовують ймовірнісні, а не детерміновані правила вибору (рандомізація операцій); їх застосовують до задач, які раніше розв’язувалися лише через повне комбінаторне перебирання, або лише за допомогою нейронних мереж, а також до раніше нерозв’язних задач. Генетичні алгоритми застосовуються для розв’язування таких задач: оптимізація функцій, оптимізація запитів в базах даних, різноманітні задачі на графах, налаштування і навчання штучної нейронної мережі, задачі компоновки, створення розкладів, ігрові стратегії, штучне життя, біоінформатика, створення дизайну за допомогою комп'ютера, складання порядку розв’язування завдань, тощо. Генетичні алгоритми є одним з найперспективніших напрямів розвитку комп’ютерних технологій, оскільки охоплюють широке коло оптимізаційних (і не тільки) задач. Еволюційні алгоритми широко застосовують у сучасній теорії оптимізації. Однією з найпоширеніших галузей їх застосування є комбінаторна оптимізація. Так, еволюційні алгоритми з успіхом можна використовувати для розв'язування класичних NP (Nonlinear Programming)-повних проблем, таких як задача комівояжера, задача пакування рюкзака, розбиття чисел, знаходження максимальної незалежної множини, розфарбовування графів тощо. До інших некласичних, але важливих, задач, для розв'язування яких застосовано еволюційні алгоритми, належать планування, складання розкладів, обчислення маршрутів, задачі розташування та транспортування. Також еволюційні алгоритми використовують для оптимізації структур та електронних схем, в медицині та в економіці. На сьогоднішній день існує ряд прикладних програмних продуктів, в яких реалізовано інструментарій еволюційних алгоритмів. Залежно від сфери використання, ступеня автономності та призначення, їх можна класифікувати, зокрема, наступним чином: – спеціалізоване програмне забезпечення – створені для розв’язування вузького кола прикладних задач. Нескладні для освоєння та користування, але обмежені для використання широким колом користувачів через свою вузьконаправленість; – додатки до математичних та аналітичних пакетів – через них надаються можливості розв'язувати широке коло задач, але більшість математичних пакетів не є вільно поширюваними та їх використання потребує певного рівня знань та навичок від користувачів; – фреймворки – є безкоштовним програмним забезпеченням. За їх допомогою користувач може будувати власні програмні засоби на основі існуючого коду, але це також потребує певних знань і навичок у програмуванні. Розглянемо приклади окремих програмних продуктів, які відносяться до кожного з наведених класів. Спеціалізоване програмне забезпечення (ПЗ): 1. NeuroShell Trader − ПЗ для створення торгової системи. Це інструмент, за допомогою якого користувач створює торгові моделі, поєднуючи штучний інтелект і традиційні методи. Можна будувати моделі для акцій, товарів, FOREX, індексів, та ін. Можна створювати моделі для фондових бірж у всьому світі, таких як NYSE (New York Stock Exchange Index), FTSE (Financial Times Stock Exchange Index), DAX (Deutscher Aktienindex (German stock index)) та ін. Створені моделі автоматично тестуються та надають сигнали-прогнози з надходженням нових даних; 2. StrategyQuant − потужна платформа для розробки торгових систем для будь-яких ринків та часових періодів. Не потребує безпосереднього програмування та автоматично тестує згенеровані стратегії; 3. Genetic System Search for Technical Analysis – програмний засіб, використання якого допомагає користувачеві визначати правила роботи та розробляти власні інвестиційні торгові системи. Додатки та надбудови до математичних та аналітичних пакетів: 1. XL BIT – додаток до MS Excel, універсальний інструмент для оптимізації та прогнозування. До задач, які можна розв’язування за його допомогою відносяться опрацювання зображень, складання розкладів, вибір акцій, розпізнавання підозрюваних, управління задачами, торгівля на Forex. Особливостями даного програмного засобу є те, що у роботі з еволюційним алгоритмом, зокрема генетичними, можна використовувати до 100 популяцій, три методи схрещування на вибір та два види масштабування функції пристосовуваності, доступна можливість налаштування рівнів схрещування та мутацій під час роботи з програмою та відстежування значення змінних, а кількість оптимізованих змінних залежить тільки від швидкодії та об'єму запам’ятовуючих пристроїв комп'ютера; є можливість налаштування випадкових вихідних даних та генерації детального звіту і графіка пристосовуваності; 2. Excel Solver – надбудова Microsoft Excel. За допомогою засобу пошуку рішення знаходять розв’язку оптимізаційних задач, зокрема за еволюційним методом. 3. Global Optimization Toolbox є додатком для програмного пакету MATLAB. За його допомогою знаходять глобальні розв'язки многокритеріальних задач. Цей засіб можна використовувати для розв’язування оптимізаційних задач, в яких цільова функція є скінченною, нескінченною, стохастичною, не містить похідних, або включає симуляції чи закриті функції з неявно заданими значеннями для параметрів у налаштуваннях. До особливостей даного інструменту можна віднести вибір оптимального компоненту шляхом використання змішано-цілочислового генетичного алгоритму; обмежену мінімізацію та многокритеріальну оптимізацію, можливість налаштування генетичного алгоритму та застосування гібридних схем. Фреймворки: 1. фреймворк Pyevolve – розроблений з метою побудови цілісного фреймворку для генетичних алгоритмів. Його особливостями є мультиплатформне використання, просте для використання API, надання можливості користувачеві створювати нові представлення та генетичні оператори і використовувати еволюційну статистику; висока швидкодія; багатий набір стандартних функцій та параметрів за замовчуванням; відкритий код. Перелік зазначених вище програмних засобів не є вичерпним, його можна доповнити такими програмними засобами: Evolver, Excel Genetic Algorithm Tool, GeneHunter. Крім того, в Інтернеті також можна знайти багато корисних сайтів, присвячених реалізації еволюційних алгоритмів. Зокрема, на сайті www.basegroup.ru запропоновано бібліотеку компонентів "Delphi GeneBase", на сайтах www.generation5.org та www.sourceforge.net є достатня кількість прикладів реалізації генетичного алгоритму різними мовами програмування. Теорія еволюційних алгоритмів дала поштовх для створення нових підходів і до розв’язування класичних задач. Розглянемо задачу комівояжера, яка є однією із найбільш відомих задач комбінаторики. Умова задачі була сформульована в 1934 році, і перед багатьма математиками, які розв’язували її, поставали досить складні проблеми. Еволюційні обчислення - термін, зазвичай використовують для загального опису алгоритмів пошуку, оптимізації або навчання, заснованих на формалізованих принципах природного еволюційного процесу. Еволюційні методи призначені для пошуку переважних рішень і засновані на статистичному підході до дослідження ситуацій та ітераційному наближенні до шуканого стану систем. На відміну від точних методів дослідження операцій еволюційні методи дозволяють знаходити рішення, близькі до оптимальних, за прийнятний час, а у відмінності від відомих евристичних методів оптимізації характеризуються істотно меншою залежністю від особливостей додатку (тобто більш універсальні) і у багатьох випадках забезпечують кращий ступінь наближення до оптимального рішення. Основна перевага еволюційної теорії полягає в можливості вирішення багатомодальних (що мають декілька локальних екстремумів) задач із великою розмірністю за рахунок поєднання елементів випадковості і детермінованості точно так, як це відбувається в природному середовищі. Детермінованість цих методів полягає в моделюванні природних процесів відбору, розмноження і спадкоємства, що відбуваються по строго певних правилах, основним з яких є закон еволюції - «виживає сильніший». Іншим важливим чинником ефективності еволюційних обчислень є моделювання процесів розмноження і спадкоємство. Дані варіанти рішень можуть за певним правилом породжувати нові рішення, які успадковуватимуть кращі риси своїх «предків». Як випадковий елемент в теорії еволюційних обчислень використовується моделювання процесу мутації. З її допомогою характеристики того або іншого рішення можуть бути випадково змінені, що приведе до нового напряму в процесі еволюції рішень і може прискорити процес вироблення кращого рішення. Методи еволюційної теорії також часто використовуються для опису процесів еволюції програм або функцій (генетичне програмування), кінцевих автоматів (еволюційне програмування) і систем, заснованих на продукційних правилах (класифікаційні системи). Вони застосовуються для навчання штучних нейронних мереж або разом з нейронними мережами для локального пошуку екстремуму цільової функції, а також часто з нечіткою логікою. Для того, щоб описувати генетичні алгоритми, нейроні мережі і нечітку логіку в їх різних поєднаннях, був навіть введений спеціальний термін «м'які обчислення». Історія еволюційних обчислень почалася з розробки ряду різних незалежних моделей еволюційного процесу. Серед цих моделей слід виділити декілька основних парадигм: генетичні алгоритми, генетичне програмування, еволюційні стратегії, еволюційне програмування. Поняття «еволюційне моделювання» вперше сформувалося в роботах Л. Фогеля, А. Оуені, М. Уолша. 1966 році вийшла їх спільна книга «Штучний інтелект і еволюційне моделювання». У далекі 60-і роки Інго Рехенберг (I. Rechenberg), зацікавлений методом «органічної еволюції», висунув ідею вирішення оптимізаційних проблем в аеродинаміці, застосовуючи мутації до вектора параметрів. Ця процедура стала відома під назвою «еволюційної стратегії» (Evolution Strategies). У 1981 році Швефель (H. Schwefel) при дослідженні гідродинамічних задач увів рекомбінації в еволюційну систему та виконав порівняльний аналіз з класичними методами оптимізації. Приблизно в той же час в США незалежно виконувалися дослідження Лоуренсом Фогелем (Lawrence Fogel) еволюції штучного інтелектуального автомата з скінченим числом станів, використовуючи метод, названий «еволюційним програмуванням» (Evolutionary Programming). Джон Холланд (John Holland) аналізував клас репродуктивних систем методом, який нам відомий як генетичний алгоритм (Genetic Algorithms). Така класифікація еволюційних алгоритмів була б неповною без робіт Lynn Cramer (1985), Jac Hicklin (1986), Gory Fujiki (1987), результати яких узагальнив і розширив Джон Коза (John Koza). Запропонований метод назвали генетичним програмуванням (Genetic Programming). Еволюційні алгоритми відрізняються один від одного. Але всі вони базуються на принципах еволюції: 1. Особі мають скінчений час життя; розмноження необхідне для продовження роду. 2. В деякій мірі нащадки відрізняються від батьків. 3. Особі існують в середовищі, в якому виживання є боротьбою за існування, і їх зміни сприяють кращій адаптації до умов зовнішнього середовища. 4. За допомогою природної селекції краще адаптовані особі мають тенденцію до довшого життя і виробництва більшої кількості нащадків. 5. Нащадкам властиво успадковувати корисні характеристики своїх батьків, що спричиняє збільшенню пристосованості особі в часі. Розвиток теорії еволюційних обчислень в нашій країні почався ще з початку 80-х років, проте отримані результати довгий час залишалися, в основному, мало відомими. Ці дослідження в значній мірі базуються на раніше опубліковані роботи по самонавчальних системах (Івахненко, Ципкін), по стохастичній оптимізації (Растрігин). Кожна з цих «шкіл» взяла за основу ряд принципів, що існують в природі, і спростила їх до такого ступеня, щоб їх можна було реалізувати на комп'ютерах того часу. Були розроблені цікаві теорії, щоб описати переваги запропонованих підходів, але всі вони були змушені розділити і загальну проблему того часу - комп'ютери були недостатньо потужними, щоб вирішувати прикладні задачі такої розмірності, які не могли бути розв’язані традиційними методами. Це пояснюється тим, що еволюційні методи не здатні «забиратися» на найближчий «пагорб», виявляти оптимальні навчальні правила і тому подібне з такою ж швидкістю, як це можуть робити інші методи. Проте, коли задача не може бути вирішена іншими, простішими методами, еволюційні обчислювальні методи можуть знайти оптимальні або близькі до них рішення. Необхідний при цьому обсяг підрахунків може виявитися великим, але швидкість, з якою цей обсяг зростає при збільшенні «розмірності» задачі, часто менше, ніж для інших методів. Тому, як тільки обчислювальні потужності стали відносно доступними і недорогими, еволюційні обчислення перетворилися на важливий інструмент пошуку субоптимальних рішень тих задач, які до останнього часу вважалися за нерозв'язні. У даний час відомою світовою школою, що представляє новий напрям в еволюційному моделюванні, є школа Кандіда Феррера (Candida Ferreira) у Великобританії. Основний напрям її досліджень зосереджений в програмуванні генетичних виразів. Нові алгоритми, які розробляються представниками школи, використовують специфічні оператори комбінаторного пошуку, що включають інверсію, вставку і видалення генів та їх послідовностей, обмеження і узагальнення перестановок, які збільшують їх ефективність. Самі автори визначають програмування генетичних виразів як мультигенне генотип/фенотип кодування дерев виразів, зв'язаних приватною взаємодією. Іншою відомою школою, в якій досліджують генетичні алгоритми, еволюційні стратегії, генетичне програмування і еволюційне програмування є лабораторія еволюційних обчислень Департаменту комп'ютерних наук в університеті Джорджа Мейсона. У США керівництво школою здійснює учень Джона Холланда К. Де Йонг (K. De Jong). Лабораторія працює над проектами і додатками моделей еволюції (у дарвінівському сенсі). Такі моделі необхідні для кращого розуміння еволюційних систем, вони використовуються для забезпечення робастності, гнучкості і адаптивності обчислювальних систем. Головну увагу фахівці лабораторії приділяють вирішенню складних наукових і технічних проблем, таких, як інноваційне проектування, оптимізація і машинне навчання. У аналогічному напрямі, але з акцентом на генетичні алгоритми працює наукова школа Девіда Голдберга ( David E. Goldberg). Лабораторія генетичних алгоритмів знаходиться в Іллінойському університеті США. Оскільки концепція еволюційних обчислень має бути заснована на деяких формалізованих принципах природного еволюційного процесу, то виникають питання про методологічні відмінності і сферу застосування основних форм еволюційних технологій. Результати порівняльного аналізу відомих форм еволюційних алгоритмів показують певні методологічні відмінності між ними. Ці відмінності стосуються форми представлення цільової функції і альтернативних рішень, операторів рекомбінації, мутації і ймовірності їх використання, стратегії селективного відбору і методів підвищення ефективності еволюційних обчислень шляхом адаптації. Методологічні відмінності між різними формами еволюційних обчислень дозволяють говорити про базові постулати, такі як універсальність і фундаментальність, властивих еволюції незалежно від форми і рівня абстракції моделі. Вирішальною обставиною для оцінки практичної придатності і результативності еволюційного алгоритму є швидкість (час, необхідний для виконання заданого користувачем числа ітерацій) і стійкість пошуку (здатність постійно від покоління до покоління збільшувати якість популяції та стійкість до попадання в точки локальних екстремумів). З цієї точки зору еволюційні обчислення володіють наступними перевагами і недоліками. Переваги еволюційних обчислень: широка сфера застосування; можливість проблемно-орієнтованого кодування рішень, підбору початкової популяції, комбінування еволюційних обчислень з не еволюційними алгоритмами, продовження процесу еволюції до тих пір, поки є необхідні ресурси; придатність для пошуку в складному просторі рішень великої розмірності; відсутність обмежень на вигляд цільової функції; ясність схеми і базових принципів еволюційних обчислень; інтегрованість еволюційних обчислень з іншими некласичними парадигмами штучного інтелекту, такими, як штучні нейромережі і нечітка логіка. Недоліками еволюційних обчислень є: евристичний характер еволюційних обчислень не гарантує оптимальності отриманого рішення (правда, на практиці, часто, важливо за заданий час отримати одне або декілька субоптимальних альтернативних рішень, тим більше, що початкові дані в задачі можуть динамічно мінятися, бути неточними або неповними); відносно висока обчислювальна трудомісткість, яка проте долається за рахунок розпаралелювання на рівні організації еволюційних обчислень і на рівні їх безпосередньої реалізації в обчислювальній системі; відносно невисока ефективність на завершальних фазах моделювання еволюції (оператори пошуку в еволюційних алгоритмах не орієнтовані на швидке попадання в локальний оптимум); невирішеність питань самоадаптації. Таким чином, порівняльний аналіз показує, що еволюційні обчислення найменше підходять для вирішення задач, в яких потрібно знайти глобальний оптимум; є ефективний не еволюційний алгоритм; змінні, від яких залежить рішення незалежні; для задачі характерний високий ступінь епістазії (одна змінна пригнічує іншу); значення цільової функції в усіх точках, за винятком оптимуму, є приблизно однаковими. Принципово підходящими для вирішення за допомогою еволюційних обчислень є задачі багатовимірної оптимізації з мультимодальними цільовими функціями, для яких немає відповідних не еволюційних методів рішення; стохастичні задачі; динамічні задачі з блукаючим оптимумом; задачі комбінаторної оптимізації; задачі прогнозування і кластеризації. Еволюційні обчислювальні методи сьогодні успішно застосовуються для вирішення ряду великих і економічно значущих задач в бізнесі і інженерних розробках. За їх допомогою були розроблені промислові проекти, що дозволили заощадити мільйони доларів. Фінансові компанії широко використовують еволюційні методи прогнозування розвитку фінансових ринків для управління портфелями цінних паперів і так далі Методи еволюційної теорії зазвичай використовуються для оцінки значень безперервних параметрів моделей великої розмірності, для вирішення NP-повних комбінаторних задач, для оптимізації моделей, що включають одночасно безперервні і дискретні параметри, в системах видобування нових знань з великих баз даних (data mining), для побудови і навчання стохастичних мереж та байєсовських мереж довіри, для навчання нейронних мереж, для оцінки параметрів в багатовимірного статистичного аналізу, а також у поєднанні з різними евристичними процедурами. Сферами застосування таких технологій є проектування механічних пристроїв, розводка друкованих плат і розміщення на них електронних компонентів, проектування деталей реактивних двигунів, розробка складних планів і розкладів, оптимізація розміщення промислового устаткування, а також багаточисельні приклади вирішення оптимізаційних задач великої розмірності звеликим числом обмежень. Ніхто не стверджує, що еволюційні обчислення однаково «гарні» для вирішення всіх типів задач; при цьому є досить багато прикладів їх успішного застосування, хоча успіх зазвичай досягається тільки після ретельного налаштування структури і параметрів еволюційного методу. 9.2. Основні положення теорії генетичних алгоритмів Еволюційна теорія стверджує, що кожен біологічний вид цілеспрямовано розвивається і змінюється для того, щоб якнайкраще пристосуватися до навколишнього середовища. В процесі еволюції багато видів комах і риб придбали захисне забарвлення, їжак став невразливим завдяки голкам, людина стала володарем складної нервової системи. Можна сказати, що еволюція - це процес оптимізації всіх живих організмів. Розглянемо, якими ж засобами природа вирішує цю задачу оптимізації. Основний механізм еволюції - це природний відбір. Його суть полягає в тому, що більш пристосовані особини мають більше можливостей для виживання і розмноження і, отже, приносять більше потомства, чим погано пристосовані особини. При цьому завдяки передачі генетичній інформації (генетичному спадкоємству) нащадки успадковують від батьків основні їх якості. Таким чином, нащадки сильних індивідуумів також будуть відносно добре пристосованими, а їх частка в загальній масі особин зростатиме. Після зміни декількох десятків або сотень поколінь середня пристосованість особин даного вигляду помітно зростає. Щоб зробити зрозумілими принципи роботи генетичних алгоритмів, пояснимо також, як влаштовані механізми генетичного спадкоємства в природі. У кожній клітці будь-якої тварини міститься вся генетична інформація цієї особини. Ця інформація записана у вигляді набору дуже довгих молекул ДНК (Дезоксирибонуклеїнова Кислота). Кожна молекула ДНК - це ланцюжок, що складається з молекул нуклеотидів чотирьох типів, що позначаються А, T, C і G. Власне, інформацію несе порядок проходження нуклеотидів в ДНК. Таким чином, генетичний код індивідуума - це просто дуже довгий рядок символів, де використовуються всього 4 букви. У тваринній клітці кожна молекула ДНК оточена оболонкою – таке утворення називається хромосомою. Кожна природжена якість особини (колір очей, спадкові хвороби, тип волосся і так далі) кодується певною частиною хромосоми, яка називається геном цієї властивості. Наприклад, ген кольору очей містить інформацію, що кодує певний колір очей. Різні значення гена називаються його алелями. При розмноженні тварин відбувається злиття двох батьківських статевих кліток і їх ДНК взаємодіють, утворюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками. При спадкоємстві можливі мутації із-за радіоактивності або інших впливів, в результаті яких можуть змінитися деякі гени в статевих клітинах одного з батьків. Змінені гени передаються нащадкові і наділяють його новими властивостями. Якщо ці нові властивості корисні, вони, швидше за все, збережуться в даному виді - при цьому відбудеться стрибкоподібне підвищення пристосованості виду. Як вже було відмічено, еволюція - це процес постійної оптимізації біологічних видів. Знаючи, як вирішується задача оптимізації видів в природі, застосуємо схожий метод для вирішення різних реальних задач. Хай дана деяка складна функція (цільова функція), залежна від декількох змінних, і потрібно знайти такі значення змінних, при яких значення функції максимальне. Один з найбільш наглядних прикладів - задача розподілу інвестицій. У цієї задачі змінними є обсяги інвестицій в кожен проект (наприклад, 10 змінних), а функцією, яку потрібно максимізувати, - сумарний дохід інвестора. Також задані значення мінімального і максимального обсягу вкладення в кожен з проектів, які задають область зміни кожній із змінних. Спробуємо вирішити цю задачу, застосовуючи відомі нам природні способи оптимізації. Розглядатимемо кожен варіант інвестування (набір значень змінних) як індивідуума, а прибутковість цього варіанту - як пристосованість цього індивідуума. Тоді в процесі еволюції пристосованість індивідуумів зростатиме, а значить, з'являтимуться все більш і більш прибуткові варіанти інвестування. Зупинивши еволюцію в деякий момент і вибравши самого кращого індивідуума, ми отримаємо досить хороше рішення задачі. Генетичний алгоритм (ГА) - це проста модель еволюції в природі, реалізована у вигляді комп'ютерної програми. Він широко використовується, для проектування структури мостів, для пошуку максимального відношення міцність/вага, для визначення найменш марнотратного розміщення при нарізці форм з тканини. ГА можуть також використовуватися для інтерактивного управління процесом, наприклад на хімічному заводі, або балансуванні завантаження на багатопроцесорному комп'ютері. У генетичному алгоритмі використовується як аналог механізму генетичного спадкоємства, так і аналог природного відбору. При цьому зберігається біологічна термінологія в спрощеному вигляді. Щоб змоделювати еволюційний процес, згенеруємо спочатку випадкову популяцію - декілька індивідуумів з випадковим набором хромосом (числових векторів). Генетичний алгоритм імітує еволюцію цієї популяції як циклічний процес схрещування індивідуумів і зміни поколінь. Життєвий цикл популяції - це декілька випадкових схрещувань (за допомогою кросовера) і мутацій, в результаті яких до популяції додається якась кількість нових індивідуумів. Відбір в генетичному алгоритмі - це процес формування нової популяції із старої, після чого стара популяція гине. Після відбору до нової популяції знову застосовуються операції кросовера і мутації, потім знову відбувається відбір, і так далі. Таким чином, модель відбору визначає, яким чином слід будувати популяцію наступного покоління. Як правило, вірогідність участі індивідуума в схрещуванні береться пропорційній його пристосованості. Часто використовується так звана стратегія елітизма, при якій декілька кращих індивідуумів переходять в наступне покоління без змін, не беручи участь в кросовері і відборі. У будь-якому випадку кожне наступне покоління буде в середньому краще попереднього. Коли пристосованість індивідуумів перестає помітно збільшуватися, процес зупиняють і як рішення задачі оптимізації беруть якнайкращого із знайдених індивідуумів. Перша публікація, яку можна віднести до генетичних алгоритмів з'явилася в 1957 році, автором якої був Н.А. Барічеллі (N.A. Barricelli), і називалася вона «Symbiogenetic Evolution Processes realised by artificial methods». У 1962 році з'явилася ще одна його робота «Numerical testing of evolution theories». Приблизно в той же час ще один дослідник А.С.Фрейзер (A.S.Fraser) також опублікував дві статті: «Simulation of genetic systems by automatic digital computers: S-linkage, dominance, and epistasis» (1960) і «Simulation of genetic systems» (1962). Не дивлячись на те, що роботи обох авторів були направлені перш за все на розуміння природного феномену спадковості, робота Фрейзера має багато спільного з сьогоднішнім баченням генетичних алгоритмів. Він моделював еволюцію 15-бітових рядків і підраховував процентний зміст особин з вдалим фенотипом в успішних поколіннях. Його роботи нагадують оптимізацію функцій, проте в роботах Фрейзера немає жодної згадки про можливість використовувати ГА для штучних задач. У багатьох джерелах саме Холланда називають батьком сучасної теорії генетичних алгоритмів. Проте, Холланд займався ними не із самого початку. На даний час генетичні алгоритми в різних формах застосовуються до багатьох наукових і технічних проблем, зокрема для інтелектуального аналізу даних. Слід зазначити, що Data Mining не основна сфера застосування генетичних алгоритмів. Їх потрібно розглядати швидше як потужний засіб вирішення всіляких комбінаторних задач і задач оптимізації. Проте генетичні алгоритми увійшли зараз до стандартного інструментарію методів Data Mining. Можливо найбільш популярним додатком генетичних алгоритмів є оптимізація багатопараметричних функцій. Багато реальних задач можуть бути сформульовані як пошук оптимального значення, де значення - складна функція, залежна від деяких вхідних параметрів. В деяких випадках, представляє інтерес знайти ті значення параметрів, при яких досягається найкраще точне значення функції. У інших випадках, точний оптимум не потрібний - рішенням може вважатися будь-яке значення, яке краще за деяку задану величину. В цьому випадку, генетичні алгоритми - часто найбільш прийнятний метод для пошуку «хороших» значень. Сила генетичного алгоритму поміщена в його здатності маніпулювати одночасно багатьма параметрами, ця особливість ГА використовувалося в сотнях прикладних програм, включаючи проектування літаків, налаштування параметрів алгоритмів і пошуку стійких станів систем нелінійних диференціальних рівнянь. Таким чином, перевагами генетичних алгоритмів є: не вимагання жодної інформації про поверхню відповіді; розриви, що існують на поверхні відповіді мають незначний ефект та не впливають на ефективність оптимізації; стійкість до попадання в локальний оптимум; добре працюють при вирішенні великомасштабних проблем оптимізації; можуть бути використані для широкого класу задач, зокрема; з середовищем, що змінюється. Недоліками генетичних алгоритмів слід вважати: складність роботи у разі, коли необхідно знайти точний глобальний оптимум; час виконання функції оцінки великий; конфігурація є не простою (кодування рішення). Мета інтелектуального аналізу даних за допомогою ГА полягає в тому, аби знайти краще можливе рішення задачі по одному або декільком критеріям. Аби реалізувати генетичний алгоритм, потрібно спочатку вибрати відповідну структуру для представлення цих рішень. У постановці задачі пошуку об'єкт цієї структури даних представляється точкою в просторі пошуку всіх можливих рішень. Властивості об'єктів представлені значеннями параметрів, що об'єднуються в запис, названий в еволюційних методах хромосомою. У генетичних методах оперують хромосомами, що відносяться до множини об'єктів - популяції. Імітація генетичних принципів - імовірнісний вибір батьків, серед членів популяції, схрещування їх хромосом, відбір нащадків для включення в нові покоління об'єктів на основі оцінки цільової функції - веде до еволюційного поліпшення значень цільової функції (функції пристосованості) від покоління до покоління. Робота ГА є ітераційним процесом, який продовжується до тих пір, поки не пройде задане число поколінь або не виконається який-небудь інший критерій зупинки. У оптимізаційних задачах традиційними критеріями зупинки алгоритму є, наприклад, тривала відсутність прогресу в сенсі поліпшення значення середньої (або кращої) пристосованості популяції, мала різниця між кращим і гіршим значенням пристосованості для поточної популяції і тому подібне 9.3. Моделі генетичних алгоритмів Канонічний ГА (Canonical GA - J. Holland). Ця модель алгоритму є класичною. Вона була запропонована Джоном Холландом в його знаменитій роботі «Адаптація в природних і штучних середовищах» [62]. Часто можна зустріти опис простого ГА (Simple GA), він відрізняється від канонічного тим, що використовує або рулеточний, або турнірний відбір. Модель канонічного ГА має наступні характеристики. Фіксований розмір популяції. Фіксована розрядність генів. Пропорційний відбір. Одноточковий кросовер і одноточкова мутація. Наступне покоління формується з нащадків поточного покоління без «елітизму». Генітор (Genitor). У моделі генітор використовується специфічний спосіб відбору. Спочатку, як і завжди, популяція ініціалізується, і її особини оцінюються. Потім вибираються випадковим чином дві особини, схрещуються, причому виходить лише один нащадок, який оцінюється і займає місце менш пристосованої особини в популяції (а не одного з батьків). Після цього знову випадковим чином вибираються дві особини, і їх нащадок займає місце батьківської особини з найнижчою пристосованістю. Таким чином, на кожному кроці в популяції оновлюється лише одна особина. Процес продовжується до тих пір, поки придатності хромосом не стануть однаковими. У даний алгоритм можна додати мутацію нащадка після його створення. Критерій закінчення процесу, як і вигляд кросинговера і мутації, можна вибирати різними способами. Підводячи підсумки, можна виділити наступні характерні особливості. Фіксований розмір популяції. Фіксована розрядність генів. Особини для схрещування вибираються випадковим чином. Обмежень на типа кросовера і мутації немає. В результаті схрещування особин виходить один нащадок, який займає місце найменш пристосованої особини. Метод переривистої рівноваги. Даний метод заснований на палеонтологічній теорії переривистої рівноваги, яка описує швидку еволюцію за рахунок вулканічних і інших змін земної кори. Для вживання даного методу в задачах інтелектуального аналізу даних пропонується після кожної генерації проміжного покоління випадковим чином перемішувати особині в популяції, а потім застосовувати основний ГА. У даній моделі для відбору батьківських пар використовується панміксія. Нащадки, що вийшли в результаті кросинговера, і найбільш придатні батьки випадковим чином змішуються. Із загальної маси в нове покоління попадуть лише ті особини, придатність яких вище середньою. Тим самим досягається управління розміром популяції залежно від наявності кращих особин. Така модифікація методу переривистої рівноваги може дозволити скоротити неперспективні популяції і розширити популяції, в яких знаходяться кращі індивідуальності. Гібридний алгоритм (Hybrid Algorithm - L. «Dave» Davis). Ідея гібридних алгоритмів полягає в поєднанні генетичного алгоритму з деяким іншим класичним методом пошуку, відповідним до даної задачі [34]. У кожному поколінні всі згенеровані нащадки оптимізуються вибраним методом і потім заносяться в нову популяцію. Тим самим виходить, що кожна особина в популяції досягає локального оптимуму, поблизу якого вона знаходиться. Далі виробляються звичайні для ГА дії: відбір батьківських пар, кросинговер і мутації. На практиці гібридні алгоритми виявляються дуже вдалими. Це пов'язано з тим, що вірогідність попадання однієї з особин в область глобального максимуму досить велика. Після оптимізації така особина буде рішенням задачі. Відомо, що генетичний алгоритм здатний швидко знайти у всій зоні пошуку хороші рішення, але він може зазнавати труднощі в здобутті з них найкращих. Звичайний оптимізаційний метод може швидко досягти локального максимуму, але не може знайти глобальний. Поєднання двох алгоритмів дозволяє використовувати переваги обох. CHC (Eshelman). CHC розшифровується як Cross-population selection, Heterogeneous recombination and Cataclysmic mutation. Даний алгоритм досить швидко сходиться через те, що в ньому немає мутацій, наступних за оператором кросинговера, використовуються популяції невеликого розміру, і відбір особину наступне покоління ведеться і між батьківськими особинами, і між їх нащадками. У даному методі для кросинговера вибирається випадкова пара, але не допускається, аби між батьками була маленька хеммінгова відстань або мала відстань між крайніми бітами. Для схрещування використовується різновид однорідного кросовера HUX (Half Uniform Сrossover), при якому нащадкові переходить рівно половина бітів кожного батька. Для нового покоління вибираються N кращих різних особин серед батьків і дітей. При цьому дублювання рядків не допускається. У моделі СНС розмір популяції відносно малий - близько 50 особин. Це виправдовує використання однорідного кросинговера і дозволяє алгоритму зійтися до рішення. Для здобуття більш менш однакових рядків CHC застосовує cataclysmic mutation: всі рядки, окрім самого пристосованого, піддаються сильній мутації (змінюється біля третини бітів). Таким чином, алгоритм перезапускається і далі продовжує роботу, застосовуючи лише кросинговер. ГА з нефіксованим розміром популяції (Genetic Algorithm with Varying Population Size - GAVaPS). У генетичному алгоритмі з нефіксованим розміром популяції кожній особини приписується максимальний вік, тобто число поколінь, після яких особина гине. Впровадження в алгоритм нового параметра - віку - дозволяє виключити оператор відбору в нову популяцію. Вік кожної особини індивідуальний і залежить від її пристосованості. Простий паралельний ГА (Parallel implementations). Генетичні алгоритми застосовуються і при паралельних обчисленнях. При цьому формується декілька популяцій, що живуть окремо. На етапі формування нового покоління за деяким правилом відбираються особини з різних популяцій. Згенерована таким чином популяція, в деяких випадках замінює всі інші. Таким чином, так або інакше, відбувається міграція особин однієї популяції в інші популяції. Тому паралельні ГА називають міграціями. Міграція (Migration). Модель міграції представляє популяцію як множину підпопуляцій. Кожна підпопуляція обробляється окремим процесором. Ці підпопуляції розвиваються незалежно одна від одної протягом однакової кількості поколінь (час ізоляції). Після закінчення часу ізоляції відбувається обмін особинами між підпопуляціями (міграція). Кількість особин, що піддалися обміну (вірогідність міграції), метод відбору особин для міграції і схема міграції визначає частоту виникнення генетичного різноманіття в підпопуляціях і обмін інформацією між популяціями. Окремі підпопуляції в паралельних ГА можна умовно прийняти за вершини деякого графа. У зв'язку з цим можна розглядати топологію графа міграційного ГА. Найбільш поширеною топологією міграції є повний граф, при якій особині з будь-якої підпопуляцій можуть мігрувати в будь-яку іншу підпопуляцію. Для кожної підпопуляції повна кількість потенційних іммігрантів будується на основі всіх підпопуляцій. Мігруюча особина випадковим чином вибирається з цього загального числа. При використанні в необмеженій міграції пропорційного відбору спочатку формується масив з найбільш придатних особин, відібраних по всіх підпопуляціях. Випадковим чином з цього масиву вибирається особина, і нею замінюють найменш придатну особину в підпопуляції 1. Аналогічні дії проробляємо з останніми підпопуляціями. Можливо, що якась популяція отримає дублікат своєї «хорошої» особини. Інша основна міграційна схема - це топологія кільця. Тут особини передаються між сусідніми (по напряму обходу) підпопуляціями. Модель дифузії, або острівна модель ГА (Island Model GA). Острівна модель є найбільш поширеною моделлю паралельного ГА. Її суть полягає в тому, що популяція, яка як правило складається з дуже великого числа особин, розбивається на однакові за розміром підпопуляції. Кожна підпопуляція обробляється окремим процесором за допомогою одного з різновидів непаралельного ГА. Зрідка, наприклад, через п'ять поколінь, підпопуляції обмінюватимуться декількома особинами. Такі міграції дозволяють підпопуляціям спільно використовувати генетичний матеріал. Шима (Schema). Хоча зовні здається, що ГА обробляє рядки, насправді при цьому неявно відбувається обробка шим, які представляють шаблони подібності між рядками. ГА практично не може займатися повним перебором всіх представлень в просторі пошуку. Проте він може виробляти вибірку значного числа гіперплощин в зонах пошуку з високою пристосованістю. Кожна така гіперплощина відповідає множині схожих рядків з високою пристосованістю. Шима - це рядок довжини l (як і довжина будь-якого рядка популяції), що складається із знаків алфавіту {0; 1; *}, де {*} - невизначений символ. Кожна шима визначає множину всіх бінарних рядків довжини l , що мають у відповідних позиціях або 0, або 1, залежно від того, який біт знаходиться у відповідній позиції самої шими. Шима, що не містить жодного невизначеного символу, є деяким рядком. Шима з одним невизначеним символом описує два бінарні рядки, а з двома — чотири рядки. Неперервні генетичні алгоритми. При роботі з оптимізаційними задачами в неперервних просторах цілком природно представляти гени безпосередньо дійсними числами. В цьому випадку хромосома є вектор дійсних чисел. Довжина хромосоми збігатиметься з довжиною вектора-рішення оптимізаційної задачі, інакше кажучи, кожен ген відповідатиме за одну змінну. Генотип об'єкту стає ідентичним його фенотипу. Використання неперервних генів робить можливим пошук у великих просторах (навіть у невідомих), що важко робити в разі двійкових генів, коли збільшення простору пошуку скорочує точність вирішення при незмінній довжині хромосоми. Однією з важливих рис неперервних ГА є їх здібність до локального налаштування рішень. Використання неперервних алгоритмів для представлення рішень зручно, оскільки близько до постановки більшості прикладних задач. Крім того, відсутність операцій кодування/декодування, які необхідні в класичному ГА, підвищує швидкість роботи алгоритму. Як відомо, появу нових особин в популяції канонічного ГА забезпечують декілька біологічних операторів: відбір, схрещування і мутація. Як оператори відбору особин в батьківську пару тут підходять будь-які відомі : пропорційний, турнірний, відбір усіканням. Проте оператори схрещування і мутації не годяться: у класичних реалізаціях вони працюють з бітовими рядками. Потрібні власні реалізації, що зважають на специфіку неперервних алгоритмів. Оператор схрещування неперервного ГА породжує одного або декількох нащадків від двох хромосом. Власне кажучи, потрібно з двох векторів дійсних чисел отримати нові вектори за якими-небудь законами. Більшість неперервних алгоритмів генерують нові вектори в околиці батьківських пар. 9.4. Мурашині алгоритми та генетичне програмування За останні два десятиліття при оптимізації складних систем дослідники все частіше застосовують природні механізми пошуку найкращих рішень. Ці механізми забезпечують ефективну адаптацію флори і фауни до довкілля впродовж мільйонів років. Останніми роками інтенсивно розробляється науковий напрям Natural Computing - «Природні обчислення», який об'єднує математичні методи з природними механізмами прийняття рішень, а саме: Genetic Algorithms - генетичні алгоритми; Evolution Programming - еволюційне програмування; Neural Network Computing – еволюційне нейромережеві обчислення; DNA Computing - ДНК обчислення; Cellular Automata - клітинні автомати; Ant Colony Algorithms – мурашині алгоритми. Імітація самоорганізації мурашиної колонії складає основу мурашиних алгоритмів оптимізації - нового перспективного методу природних обчислень. Колонія мурах може розглядатися як багатоагентна система, в якій кожен агент (мурашка) функціонує автономно по дуже простих правилах. На противагу майже примітивній поведінці агентів, поведінка всієї системи виходить на подив розумною. Мурашині алгоритми серйозно досліджуються європейськими вченими з середини 90-х років. Вперше підхід був запропонований бельгійським дослідником Марко Доріго (Marco Dorigo). На сьогодні вже отримані важливі результати мурашиної оптимізації таких складних комбінаторних задач, як: задача комівояжера, задача оптимізації маршрутів вантажівок, задача розфарбовування графа, квадратичної задачі про призначення, оптимізації мережевих графіків, задача календарного планерування і інших. Особливо ефективні мурашині алгоритми при оптимізації процесів в розподілених нестаціонарних системах, наприклад трафіків в телекомунікаційних мережах. Кожен, хто хоч раз в житті спостерігав за мурахами, обов'язково повинен був відмітити: вся діяльність цих комах має яскраво виражене групове забарвлення. Працюючи разом, група мурах здатна затаскати в мурашник шматок їжі або будівельного матеріалу, в 10 разів більше самих працівників. Вчені давно знають про це, але лише останнім часом задумалися про корисне застосування мурав’їнного досвіду в повсякденному житті. Сам по собі мурашка - досить примітивна істота. Всі його дії, по суті, зводяться до елементарних інстинктивних реакцій на навколишнє оточення і своїх побратимів. Проте декілька мурах разом утворюють складну систему, яку деякі вчені називають «колективним розумом». Тому алгоритми мурав’їнних колоній часто називають алгоритмами «роєвого інтелекту». Наприклад, група мурах прекрасно здатна знаходити найкоротшу дорогу до їжі. Якщо яка-небудь перешкода - палиця, камінь, нога людини - встає на дорозі, браві добувачі швидко знаходять новий оптимальний маршрут. Принципи поведінки мурах витримали випробування впродовж 100 мільйонів років - саме стільки часу тому мурашки «колонізували» Землю. Вони відносяться до соціальних комах, що живуть усередині деякого колективу - колонії. На Землі близько двох відсотків комах є соціальними, половину з них складають мурахи - невеликі істоти масою від 1 до 5 міліграма. Число мурах в одній колонії вагається від 30 штук до декількох мільйонів. На Землі близько 1016 мурах із загальною масою, приблизно рівній масі людства. Які ж механізми забезпечують настільки складну поведінку мурах, і що можна запозичити у цих істот для вирішення своїх глобальних задач? Основу «соціальної» поведінки мурашок складає самоорганізація - множина динамічних механізмів, що забезпечують досягнення системою глобальної мети в результаті низькорівневої взаємодії її елементів. Принциповою особливістю такої взаємодії є використання елементами системи лише локальній інформації. При цьому виключається будь-яке централізоване управління і звернення до глобального образу, що репрезентує систему на зовнішньому світі. Мурахи використовують два способи передачі інформації: прямий - обмін їжею, мандибулярний, візуальний і хімічний контакти, і непрямий - стігмержи (stigmergy). Стігмержи - це рознесений в часі тип взаємодії, коли один суб'єкт взаємодії змінює деяку частину довкілля, а останні використовують інформацію про її стан пізніше, коли знаходяться в її околиці. Біологічно стігмержи здійснюється через феромон (pheromone) - спеціальний секрет, що відкладається як слід при переміщенні мурав’їв. Феромон - досить стійка речовина, він може сприйматися мурашками декілька діб. Чим вище концентрація феромону на стежці, тим більше мурах по ній рухатиметься. З часом феромон випаровується, що дозволяє мурашкам адаптувати свою поведінку під зміни зовнішнього середовища. Розподіл феромону по простору пересування мурах є свого роду динамічно змінною глобальною пам'яттю мурашника. Будь-яка мурашка у фіксований момент часу може сприймати і змінювати лише один локальний елемент цієї глобальної пам'яті. Експерименти з Argentine ants, які проводилися Госсом в 1989 і Денеборгом в 1990 році послужили відправною точкою для дослідження роєвого інтелекту. Дослідження застосування отриманих знань для дискретної математики почалися на початку 90-х років XX століття, автором ідеї є Марко Доріго з Університету Брюсселю, Бельгія. Саме він вперше зумів формалізувати поведінку мурах і застосувати стратегію їх поведінки для вирішення задач про найкоротші шляхи. Пізніше за участю Гамбарделли, Тайлларда і Ді Каро були розроблені і багато інших підходів до вирішення складних оптимізаційних задач при допомогою мурашиних алгоритмів. Ідея мурашиного алгоритму полягає в наступному: дві мурашки з мурашника повинні дістатися до їжі, яка знаходиться за перешкодою. Під час переміщення кожна мурашка виділяє трохи феромону, використовуючи його як маркер. При інших рівних умовах кожна мурашка вибере свою дорогу. Перша мурашка вибирає верхню дорогу, а друга - нижню. Оскільки нижня дорога в два рази коротше верхньої, друга мурашка досягне мети за час t1 . Перша мурашка у цей момент пройде лише половину дороги. Коли одна мурашка досягає їжі, вона бере один з об'єктів і повертається до мурашника по тій же дорозі. За час t2 друга мурашка повернеться в мурашник з їжею, а перша мурашка досягне їжі. При переміщенні кожної мурашки на дорозі залишається трохи феромону. Для першої мурашки за час t0t2 дорога була покрита феромонами лише один раз. У той же самий час друга мурашка покрила дорогу феромонами двічі. За час t4 перша мурашка повернулася в мурашник, а друга мурашка вже встигла ще раз сходити до їжі і повернутися. При цьому концентрація феромону на нижній дорозі буде в два рази вище, ніж на верхній. Тому перша мурашка наступного разу вибере нижню дорогу, оскільки там концентрація феромону вища. У цьому і полягає базова ідея мурашиного алгоритму - оптимізація шляхом непрямого зв'язку між автономними агентами. Розглянемо покроковий опис алгоритму. Передбачимо, що довкілля для мурашок є повний неорієнтований граф. Кожне ребро має вагу, яка позначається як відстань між двома вершинами, сполученими їм. Граф двонаправлений, тому мурашка може подорожувати по грані в будь-якому напрямку. Імовірність включення ребра в маршрут окремої мурашки пропорційна кількості феромону на цьому ребрі, а кількість феромону, що відкладається, пропорційна довжині маршруту. Чим коротше маршрут тим більше феромону буде відкладено на його ребрах, отже, більша кількість мурашок включатиме його в синтез власних маршрутів. Моделювання такого підходу, що використовує лише позитивний зворотний зв'язок, приводить до передчасної збіжності - більшість мурашок рухаються по локально-оптимальному маршруту. Уникнути цього можна моделюючи негативний зворотний зв'язок у вигляді випару феромону. Причому, якщо феромон випаровується швидко, то це наводить до втрати пам'яті колонії і забуванню хороших рішень, з іншого боку, великий час випарів може привести до здобуття стійкого локального оптимального рішення. Мурашка. Мурашка - це програмний агент, який є членом великої колонії і використовується для вирішення якої-небудь проблеми. Агент забезпечується набором простих правил, які дозволяють йому вибирати дорогу у графі. Він підтримує список вузлів, які вже відвідав. Таким чином, мурашка повинна проходити через кожен вузол лише один раз. Дорога між двома вузлами графа, по якому мурашка відвідав кожен вузол лише один раз називається шляхом Гамільтона. Рух мурашок. Рух мурашок ґрунтується на одному простому ймовірнісному рівнянні. Якщо мурашка ще не закінчила дорогу, тобто не відвідала всі вузли мережі, для визначення наступного ребра дороги використовується рівняння. Подорож мурашок. Пройдений мурашкою шлях відображується, коли вона відвідає всі вузли графа. Цикли заборонені, оскільки в алгоритм включений список табу. Після завершення довжина дороги може бути підрахована - вона дорівнює сумі довжин всіх ребер, по яких подорожувала мурашка. Рівняння показує кількість феромону, який був залишений на кожному ребрі шляху для мурашки k . Результат рівняння є засобом виміру шляху, - коротка дорога характеризується високою концентрацією феромону, а довша дорога - нижчою. Потім отриманий результат використовується в іншому рівнянні, аби збільшити кількість феромону уздовж кожного ребра пройденої мурашкою дороги. Важливо, що дане рівняння застосовується до всього шляху, при цьому кожне ребро позначається феромоном пропорційно довжині дороги. Тому слід діждатися, поки мурашка закінчить подорож і тільки потім відновити рівні феромону, інакше дійсна довжина дороги залишиться невідомою. Випар феромону. На початку шляху в кожного ребра є шанс бути обраним. Аби поступово видалити ребра, які входять в гірші шляхи графа, до всіх ребер застосовується процедура випару феромону. Повторний запуск. Після того, як дорога мурашки завершена, ребра оновлені відповідно до довжини шляху і стався випар феромону на всіх ребрах, алгоритм запускається повторно. Список табу очищається, і довжина дороги обнуляється. Мурашкам дозволяється переміщатися по графові, засновуючи вибір ребра на першому рівнянні. Цей процес може виконуватися для постійної кількості шляхів або до моменту, коли впродовж декількох запусків не було відмічено повторних змін. Потім визначається кращий шлях, який і є рішенням. Генетичне програмування (genetic programming, GP) - одна з найзручніших і універсальних методик вирішення задач, що встають перед аналітиками. Воно застосовується для вирішення широкого круга проблем: символьної регресії (symbolic regression), аналізу даних (data mining), оптимізації і дослідження поведінки потомства (emergent behavior), що з'являється, в біологічних співтовариствах. Ідею генетичного програмування (ГП) вперше запропонував Дж. Коза в 1992 році, спираючись на концепцію генетичних алгоритмів. Генетичне програмування - це розширення генетичної моделі навчання в область програмного забезпечення. Його об'єктом на відміну від генетичних алгоритмів є не символьні рядки фіксованої довжини, що кодують можливі рішення проблеми, а власне програми, виконуючи які і отримують різні варіанти рішення задачі. У генетичному програмуванні програми представляються у вигляді дерева граматичного розбору, а не у вигляді рядків коду, тому в ГП всі операції виконуються не над рядками, а над деревами. При цьому використовуються такі ж оператори, як і в генетичному алгоритмі: селекція, схрещування і мутація. У ГП хромосомами є програми. Програми представлені як дерева з функціональними (проміжними) і термінальними (кінцевими) елементами. Термінальними елементами є константи, дії і функції без аргументів, функціональними - функції, що використовують аргументи. Для того, щоб застосувати ГП до якої-небудь проблеми, необхідно визначити: множину термінальних елементів; множину функціональних елементів; міру пристосованості; параметри, контролюючі еволюцію; критерій зупинки еволюції. Генетичні програми не пишуться програмістами, а створюються в результаті наступного ітераційного покрокового процесу. 1. Генерується початкова популяція програм, що є випадковими композиціями функцій (арифметичних, логічних та ін. операцій) і терміналів (змінних і констант), узятих з множини функціональних і термінальних елементів, що відносяться до вирішуваної проблеми. Якщо ми збираємося вивести програму, яка управляє транспортною логістикою, то до набору терміналів увійдуть наступні змінні - відстань до об’єкта, швидкість і вантажопідйомність, тип транспортних засобів і так далі. Набор функцій в цьому випадку включатиме різні математичні операції, як прості (множення, ділення, віднімання, складання), так і складніші. 2. Кожна програма виконується і їй привласнюється значення пристосованості, відповідне тому, наскільки добре вона вирішує задачу. 3. Створюється нова популяція комп'ютерних програм за рахунок: копіювання в неї найкращих програм старої популяції; створення нових програм за допомогою мутацій (випадкової зміни функцій і терміналів або навіть цілих піддерев); створення нових програм за допомогою схрещування тих, що існують. Операція схрещування реалізується за рахунок обміну піддерев двох хромосом, вибраних випадково (відповідно до їх пристосованості). 4. Всі програми знову виконуються і цикл повторюється до тих пір, поки не буде отриманий необхідний результат. Слід зазначити, що алгоритм роботи ГП такий же, як і ГА: селекція, схрещування і мутація. Проте оскільки ГП оперує над деревами, а не над рядками, то оператори схрещування і мутації мають відмінності. До перспективних напрями розвитку ГП слід віднести роботи по так званих автоматично визначаємих функціях (ADF), ідея яких полягає в підвищенні ефективності ГП за рахунок модульної побудови програм, що складаються з головної програми і ADF-модулів, які генеруються в ході моделювання еволюції. До початку еволюції визначається структура програми, число ADF-модулів і параметри кожної ADF. Всі вершини даної структури мають свій номер, список аргументів включає окремі локальні змінні, які визначаються при виклику ADF. Задання функції головної програми завершує установку загальної програми. Налаштування ADF (їх число, аргументи і тому подібне) залежить від вирішуваної задачі, наявних обчислювальних ресурсів і попереднього досвіду. Іншим перспективним напрямом є реалізація ГП на транскомп’ютерних обчислювальних системах. Еволюційні алгоритми — напрям в штучному інтелекті (розділ еволюційного моделювання), що використовує і моделює біологічну еволюцію [1]. Еволюційні алгоритми найчастіше використовують як пошукові алгоритми, які змінюють набір розв’язків через повторювані трансформації. Факт того, що множину розв’язків одночасно змінюється якісно відрізняє еволюційні алгоритми від традиційних алгоритмів. Іншою важливою різницею є те, що згадані трансформації використовують оператори трансформації взяті з теорії біологічної еволюції (мутації, природній відбір, самовідтворення). Існує три базових варіанти еволюційних алгоритмів: Генетичні алгоритми, еволюційні стратегії, та еволюційне програмування. Хоча ці методи мають спільну основу, всі вони були створені та реалізовані абсолютно незалежно один від одної. В генетичних алгоритмах, у всіх розв’язків є їх оцінка, що визначає їх пристосованість. Наприклад в Генетичних алгоритмах, множина розв’язків представлена множиною хромосом. В цілому, всі види еволюційних алгоритмів працюють по стандартному набору кроків. Для початку генерується випадкова популяція певних індивідів. Далі розраховується пристосованість кожного індивіда. 1.1Еволюційні алгоритми Еволюційне обчислення є загальним терміном для методів оптимізації, натхненних еволюційною теорією Дарвіна. У природній еволюції люди прагнуть до виживання і відтворення в конкурентному середовищі. Ті, у кого 12 більше сприятливі риси, отримані внаслідок успадкування або мутації, мають більше шансів на успіх. Еволюційні алгоритми є специфічними реалізаціями концепції еволюційного обчислення. Еволюційні алгоритми вирішують обчислювальні проблеми, керуючи набором (населення) осіб. Кожен індивідуум кодує рішення кандидата на обчислювальну задачу в своєму геномі. Для вивчення простору рішення породжує потомство батьківської популяції через операторів рекомбінації поєднувати властивості батьків. Додатково оператори мутації застосовуються для введення випадкових варіацій з метою розширення досліджень і запобігання передчасній конвергенції. Нова популяція створюється шляхом вибору з безліч осіб з батьківської популяції і та їх потомства. Це процес рекомбінації, мутації і працює в одному поколінні і повторюється протягом всього виконання алгоритму. Для керівництва пошуком найкращого розвязку, використовується еволюційний тиск у вигляді функції пристосованості. Пристсовані індивіди мають більший шанс на продовження роду та виживання. Завдяки своїй паралелізованій конструкції та пристосованості для складних задач, еволюційне алгоритми є цінним інструментом у створенні моделей там де класичні методи не є ефективними. Ключовим завданням у застосуванні та реалізації еволюційних алгоритмів є вибір еволюційних параметрів. Навіть найпростіші реалізації мають значну кількість параметрів. Вибір значень параметрів має значний вплив на ефективність еволюційного алгоритму для різних проблем та різних видів однакових задач. Крім того, використання фіксованих параметрів протягом всі поколінь може бути неоптимальним. Для врахування цього бажано, щоб еволюційні алгоритми були адаптивними. У цьому контексті йдеться про адаптацію та динамічний 13 контроль параметрів еволюції (не слід плутати з біологічною терміновою адаптацією). Існують різні види адаптації, які можна використовувати в еволюційних алгоритмах : 1) Адаптація рівня навколишнього середовища змінює спосіб, у який окремі особи оцінюються навколишнім середовищем, наприклад, змінюючи функцію фітнесу. 2) Адаптація на рівні населення змінює параметри, які впливають на всю або деяку частину населення, наприклад, шляхом зміни чисельності населення. 3) Адаптація на індивідуальному рівні дозволяє вибирати параметри специфічних особин у популяції, наприклад підвищення ймовірності мутацій у осіб з низьким значення функції фітнесу. 4) Адаптація на рівні компонентів змінює параметри, які є специфічними для певної частини генома, наприклад, шляхом управління ймовірністю мутації одного гену. 1.2 Генетичні алгоритми Генетичні алгоритми - це алгоритм оптимізації, який використовує принципи генетики та природнього відбору. Його часто використовують для пошуку оптимальних рішень для складних задач. Він часто використовується для розв'язання задач оптимізації, досліджень і машинного навчання. Генетичні алгоритми мають можливість знайти «достатньо швидко» «досить точний» розв’язок. Це робить генетичні алгоритми привабливими для використання при розв'язанні задач оптимізації. Генетичні алгоритми, вперше були запропоновані Джоном Холандом в 1975. Вони були створені на основі ідеї Дарвіна про природній відбір. Центральна ідея, якого це селекція та виживання сильнішого. Важливими в 14 даній теоріє є наступні поняття, які варто, перед початком обговорення генетичних алгоритмів зазначити і, які будуть використовуватися надалі. Покоління - це множина можливих розв’язків даної проблеми. Хромосома є Рисунок 1.1- Загальне представлення моделі одним з таких рішень даної проблеми. Ген - один з елементів хромосоми. Аллелі - це значення певної хромосоми. Функція пристосованості визначається як функція, яка на вході приймає розв’язок, і на виході видає його відповідність даній проблемі. Генетичні оператори змінюють генетичний склад потомства. До них відносяться перехід, мутація, відбір і т.п. Через процес природньої селекції організми адаптуються та оптимізують свої шанси на виживання в даному їм природньому середовищі. Також відбуваються випадкові мутації генів організмів, які передаються їх дітям. Якщо мутація виявилась вдалою, ці діти мають більший шанс для виживання, і в свою чергу для продовження роду. Якщо мутація виявилась невдалою, то діти індивіда мають менший шанс на виживання та продовження роду, тому невдалі гени помруть з ними. 15 Аналогічно, ГА підтримують ―популяцію‖ кандидатів розв’язків для даної задачі. Елементи випадково обираються з даної популяції та продовжую свій рід комбінуючи частини двох батьківських розв’язків. Ключова особливість в тому, що ймовірність елемента бути обраним для репродукції основана на їх пристосованості, по суті функції рішення. З часом непридатні розв’язки зникають з популяції та замінюються на дітей кращих розв’язків. В генетичних алгоритмах розв’язки представляються бінарно. Значення пристосованості оцінює ці розв’язки Теоретичні дослідження були викликані інтересом до розуміння та підвищення ефективності роботи ГА. Кінцева ціль полягала у проектуванні ефективного та надійного ГА. Для досягнення даної мети важливо розуміти, як ГА працюють та для якого типу задач їх варто використовувати. Майже всі теоретичні роботи в ГА випливають з цих двох фундаментальних питань[1]. 1.3 Структура генетичних алгоритмів Багато різних ГА були створені використовуючи одну і ту ж ідею природнього відбору. Вони можуть мати різні оператори, але більшість ГА основані на простому прототипі стандартної ГА, який має лише базові оператори. Модель складається з наступних елементів: ініціалізація населення, а потім ітераційний, що включає у себе оцінку та розмноження(селекція, кросове, мутація). Перший крок у будь-якій ГА полягає в тому, щоб розробити відповідну схему представлення хромосом, які є кандидати на розв’язок для розглянутих задач. Шифрування - процес презентації потенціального розв’язку, який містить набір змінних рішень, у вигляді рядка коду. Потенціальний розв’язок можна представити у різних видах форматів: бінарний код, букви, дійсні числа. Залежно від характеру проблеми може бути обрана відповідна схема подання. Класичним вважається бінарне 16 представлення. Зашифровані змінні називаються генами, а значення цих генів (0,1) називаються алелями. Рисунок 1.2 - Модель ГА Представивши розв’язок у зручному для нас вигляді, ми маємо знати на скільки хорошим цей розв’язок є. Для цього ми маємо визначити цільову функцію. Так як ГА працює лише з зашифрованими даними, тому йому не важливий фізичний аспект завдання, то одним з його найбільших плюсів є можливість оптимізації розв’язків, де зв'язок між ними та функції пристосованості невідомі чи занадто складні для формулювання. Значення цільової функції індивідуального рішення можна отримати, через відомі значення чи за допомогою комп'ютерної симуляції. Цей крок встановлює відповідність між змінними та функцією в чорному ящику. Завданням може бути, як максимізація, так і мінімізація цільової функції. Після того, як розв’язки зашифровані, можна перейти до процесу еволюції. Спершу, популяція зашифрованих розв’язків, іншими словами 17 хромосом, створюється випадково. Далі, популяція проходить ітераційний процес розвитку та репродукції. Кожна хромосома отримує своє значення функції пристосованості відповідно до цільової функції. Далі, хромосоми нового покоління створюються використовуючи оператори репродукції на старому поколінні. Це три базових оператори: селекція, кросове, мутація. Новостворені хромосоми знову оцінюються. Ітерація продовжиться поки популяція розв’язків не дійде до оптимального розв’язку[2]. 1.3.1 Популяція Популяція - це підмножина рішень у поточному поколінні. Вона також може бути визначена як набір хромосом. Є кілька речей, які необхідно мати на увазі при роботі з населенням ГА. Перше це те, що різноманітність населення завжди потрібно підтримувати, інакше ми можемо прийти до завчасного сходження до розв’язку. Друге це те, що розмір популяції має бути не занадто великим, так як це може привести до сповільнення роботи генетичного алгоритму, але занадто мала популяція може бути недостатньою для продовження роду. Таким чином, оптимальний розмір популяції обирається методом спроб та помилок. Популяція зазвичай визначається як двовимірний масив - розмір популяції, розмір хромосом. Існує два методи для ініціалізації популяції. Перший - випадкова ініціалізація. В цьому способі популяції заповнюється абсолютно випадковими розв’язками. Другий – евристична ініціалізація. В ньому популяції заповнюється на основі, якихось евристичних даних. Було доведено, що популяції не варто повністю заповнювати за допомогою евристичного методу, так як результат в популяції, що всі розв’язки в популяції мають маленьку різноманітність. Було доведено, що саме випадкові розв’язки, приводять популяцію до оптимального значення. Тому, використовуючи евристичну ініціалізацію, ми просто встановлюємо 18 декілька хороших розв’язків, заповнюючи решту популяції випадковими індивідами. Також спостерігалося, що евристична ініціалізація в деяких випадках лише впливає на початкову придатність населення, але в кінцевому підсумку саме різноманіття рішень призводить до оптимального значення. Існують дві широко використовувані моделі населення. У моделі стаціонарного стану ГА, у кожній ітерації генерується один або два нащадки і вони замінюють одну чи дві особи з популяції. Стаціонарний стан ГА також відомий як інкрементний ГА. У моделі покоління ми генеруємо n нащадків, де n - розмір популяції, і в кінці ітерації все населення замінюється новим[3]. 1.3.2 Функція пристосованості Функція пристосованості є функцією, яка приймає кандидата на розв’язок проблеми в якості вхідних даних і видає, на скільки «підходить» наше «хороше» рішення стосовно розглянутої проблеми. Розрахунок значення функції пристосованості проводиться багаторазово в ГА, а тому він повинен бути досить швидким. Повільне обчислення значення функція пристосованості може негативно вплинути на ГА і зробити даний метод надзвичайно повільним. У більшості випадків функція пристосованості та цільова функція однакові, оскільки метою є або максимізація, або мінімізація даної цільової функції. Однак, для більш складних проблем з кількома цілями та обмеженнями, конструктор алгоритму може вибрати іншу функцію придатності. Функція фітнесу повинна бути достатньо швидкою для обчислення. Також вона повинна кількісно виміряти, наскільки підходить дане рішення або як придатні особи можуть бути отримані з даного рішення. У деяких випадках розрахунок функціональної придатності безпосередньо може бути неможливим через властиві складності проблеми. 19 У таких випадках ми апроксимуємо функцію пристосованості до відповідних потреб. 1.3.3 Представлення генотипу Одним з найважливіших рішень, які необхідно прийняти під час реалізації генетичного алгоритму, є прийняття представлення, яке буде використано для представлення наших рішень. Було відмічено, що неправильне представлення може призвести до некоректної роботи ГА. Тому, вибираючи правильне представлення, маємо знайти належне визначення відображення між фенотипом і просторами генотипу, що є суттєвим для успіху ГА. У цьому розділі я представлю деякі з найбільш часто використовуваних представлень для генетичних алгоритмів. Двійкове представлення. Це одне з найпростіших і найбільш широко використовуваних представлень у ГА. У цьому типі подання генотип складається з бітових рядків. Для деяких завдань, коли простір рішення складається з нульових змінних рішення - двійкове представлення є природним. Візьмемо, наприклад, проблему 0/1 Кнапсака. Якщо є n елементів, то ми можемо представити рішення двійковим рядком з n елементів, де x-елемент вказує, чи вибрано елемент x (1) чи ні (0). Для інших проблем, зокрема тих, що стосуються чисел, ми можемо представляти числа у вигляді двійковим поданням. Проблема з цим типом кодування полягає в тому, що різні біти мають різне значення і тому оператори мутації і кросовера можуть мати небажані наслідки. Це може бути 20 вирішено певною мірою за допомогою програми Grey Coding, оскільки зміна одного біта не має масового впливу на рішення. Реальне представлення. Для задач, де ми хочемо визначити гени за допомогою неперервних, а не дискретних змінних, реальне ціннісне представлення є найбільш природним. Точність цих справжніх чисел із плаваючою точкою обмежена лише комп'ютером. Цілочислене представлення. Для дискретно представлення генів ми не завжди можемо обмежити простір рішення двійковим "так" або "ні". Наприклад, якщо ми хочемо кодувати чотири відстані - Північ, Південь, Схід і Захід, ми можемо кодувати їх як {0,1,2,3}. У таких випадках краще ціле уявлення. Представлення перестановок. У багатьох задачах рішення представляється порядком елементів. У таких випадках найбільш підходящим є перестановочне представлення. Класичним прикладом такого подання є проблема торгового агента (TSP). При цьому продавець повинен провести екскурсію по всіх містах, відвідати кожне місто рівно один раз і повернутися до стартового міста. Загальна довжина туру повинна бути мінімізована. Рішення цього TSP, природно, є впорядкованістю або перестановкою всіх міст і тому використання представлення перестановок має сенс для цієї проблеми. 21 1.3.4 Селекція Селекція батьків – це процес вибору батьків, які продовжують свій рід тобто рекомбінуються, щоб створити нащадків для наступного покоління. Вибір батьків є дуже важливим для швидкості конвергенції ГА, оскільки хороші батьки приводять нащадків до кращого та точнішого рішення. Важливо, уважно розглядати процес селекції, щоб запобігти одній частій проблемі, коли один правильний розв’язок, забирає на себе всю популяцію, протягом декількох поколінь, що приводить до того, що усі рішення будуть близькими один до одного в просторі розв’язків, що в свою чергу приведе до втрати різноманітності. Підтримка великого розмаїття населення надзвичайно важливо для успіху ГА. Захоплення всієї популяції одним надзвичайно придатним рішенням відоме як передчасне зближення і є небажаним станом в ГА. Оператор селекції створює число копій кожної хромосоми для подальших операцій. Процедура селекції працює по правилу виживання сильнішого, яке виділяє більше квот для копій кращих розв’язків. Існують різні способи селекції. Найчастіше використовується пропорційна селекція, яка виділяє стільки копій кожної хромосоми пропорційно значенню їх функції придатності. Далі новостворене покоління замінить собою оригілну популяцію для подальших операцій. Таким чином, ймовірність виникнення хромосом, які нам підходять росте. На етапі відбору потрібно з усієї популяції вибрати певну її частку, яка залишиться «в живих» на цьому етапі еволюції. Є різні способи проводити відбір. Пропорційна селекція є одним з найпопулярніших способів вибору батьків. При цьому кожен може стати батьком з вірогідністю, яка пропорційна його придатності. Імовірність виживання особини повинна залежати від значення функції пристосованості. Сама частка тих, хто вижив s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. За підсумками відбору з N особин популяції S повинні 22 залишитися особини, які увійдуть до підсумкової популяцію S . Таким чином, кращі індивіди мають більше шансів на спаровування і поширення своїх особливостей на наступне покоління. Таким чином, така стратегія відбору дає більше можливостей продовження роду та розвитку тим Рисунок 1.3- Турнірний метод індивідам, хто краще підходить. Якщо розглянути кругову діаграму, в якій кільце ділиться на n-індивідів. Кожен індивід отримує ту частину, яка відповідає його функції пристосованості. Турнірна селекція - спочатку випадково вибирається встановлену кількість особин (зазвичай дві), а потім з них вибирається особина з кращим значенням функції пристосованості. Зазвичай, прийнято розмір групи особин приймати за двійку. Такий турнір називають двійковим. Головна перевага турнірного відбору у тому, що він не втрачає вибірковості у випадку, коли у ході еволюції всі елементи популяції стають приблизно рівними[4]. Метод рулетки - ймовірність вибору особини тим імовірніше, чим краще її значення функції пристосованості. У методі рулетки аналогічно використовується колесо. На окружності кола обирається фіксована точка, та 23 колесо обертається. Область колеса, що приходить перед фіксованою точкою, вибирається у якості батьків. Для другого батька повторюється той самий процес. Зрозуміло, що індивіди з більшим значенням функції пристосованості мають більший шанс на продовження роду. Тому ймовірність вибору особи безпосередньо залежить від його придатності. Хоча ймовірність вибору кандидата з більшим значення функцію пристосованості більша, все ще існує ймовірність того, що вони зникнуть бо ймовірність їх вибору не дорівнює 1. Рисунок 1.4- Метод рулетки Порівняйте це з іншими способами відбору, що виключають відсоток найслабших кандидатів. В даному методі існує ймовірність того, що деякі слабкі рішення переживуть процес відбору. Зрозуміло, що індивіди з більшим значенням функції пристосованості мають більший шанс на продовження роду. Тому ймовірність вибору особи безпосередньо залежить від його придатності. Хоча ймовірність вибору кандидата з більшим значенням функції пристосованості більша, але все ще існує ймовірність того, що вони зникнуть, бо ймовірність їх вибору не дорівнює 1. Порівняйте це з іншими способами відбору, що виключають відсоток найслабших кандидатів. В даному методі існує ймовірність того, що деякі слабкі рішення переживуть процес відбору. Це відбувається тому, що навіть якщо 24 ймовірність того, що слабкі рішення виживуть, є низькою, вона не є нульовою, а це означає, що вони все ще можуть вижити. Це є перевагою, оскільки існує ймовірність того, що навіть слабкі розв’язки можуть мати деякі особливості або характеристики, які можуть виявитися корисними після процесу рекомбінації. Інші методи відбору, такі як стохастична універсальна вибірка або вибір турніру, часто використовуються на практиці. Це пояснюється тим, що вони мають менше стохастичних шумів або є швидшими, легкими для реалізації. Для реалізації даного методу потрібно зробити наступне. Обчислити S фітнес. Створити випадкове число між (0,1). Нейронні мережі є набором алгоритмів, змодельованих по прикладу мозку людини, призначених для розпізнавання закономірностей. Вони інтерпретують дані за допомогою свого роду машинного сприйняття, маркування або кластеризації вихідних даних. Моделі, які вони розпізнають, є числовими, містяться у векторах, в які повинні бути перекладені всі дані реального світу, будь то зображення, звук, текст або часові ряди. В обчисленях великої кількості інформації, нейронні мережі показують хороші результати. Їхня здатність вчитися на прикладі робить їх дуже гнучкими і потужними. Крім того, немає необхідності розробляти алгоритм для виконання певного завдання; тобто немає необхідності розуміти внутрішні механізми цього завдання. Вони також дуже добре підходять для систем реального часу через їх швидку реакцію та час обчислень, що зумовлено їх паралельною архітектурою. Застосовані алгоритми дозволили отримати модель в , якій кожен організм складається з нейронної мережі, в якій ваги штучних нейронів та з’єднань грають роль генетичного коду. Який в свою чергу оптимізується за допомогою генетичних алгоритмів (ГА). У першому розділі було основні положення та визначення, що відносять до сфери Еволюційних (ЕА) та Генетичних алгоритмів (ГА). Крім того докладно поданий математичний апарат для побудови ГА. Проаналізовано можливі підходи для реалізації мутації, схрещування та селекції для кожного поняття були отримані результати та висновки щодо найкращого варіанту їх реалізації., з урахуванням особливостей предметної області. Навчання і використання еволюційних алгоритмів з комп’ютерною підтримкою сприяє розвитку математичних та інформатичних компетентностей майбутніх фахівців.

Список використаних джерел

1. Дубровін В.І., Федорченко Є.М. Дослідження та розроблення генетичних алгоритмів та операторів схрещування // Інформаційні системи та мережі: Вісник Національного університету «Львівська політехніка». – №673. – Львів, 2010. – C. 97-104. 2. Погорілий С.Д., Білоус Р.В. Генетичний алгоритм розв'язання задачі маршрутизації в мережах // Проблеми програмування. – 2010.– №2–3: Спец. вип. – С. 171–178. 3. Самотній В., Дзелендзяк У. Використання генетичних алгоритмів для апроксимації функції дійсними числами // Комп'ютерні науки та інформаційні технології: Вісник Національного університету «Львівська політехніка». – №694. – Львів, 2011. – C. 313-318. 4. Субботін С.О., Олійник А.О., Олійник О.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / За заг. ред. С.О. Субботіна. – Запоріжжя: ЗНТУ, 2009. – 374 с. 5. Погорілий С.Д., Білоус Р.Б. Генетичний алгоритм розв’язання задачі маршрутизації в мережах // Проблеми програмування. – 2010. – № 2–3 Спец. вип. – С. 171–178. 6. Вакал Л.П. Генетичні алгоритми для чебишовської апроксимації // Комп’ютерні засоби, мережі та системи. – 2013. – № 12. – С. 20–26. 7. Abu-Arqub Omar, Abo-Hammour Zaer, Momani Shaher. Application of continuous genetic algorithm for nonlinear system of second-order boundary value problems // Appl. Math. Inf. Sci. – 2014. – Vol. 8, N 1. – P. 235 – 248. 8. Holland J.H. Adaptation in natural and artificial systems. – Ann Arbor: Univ. of Michigan Press, 1975. – 219 p. 9. Wright A. Genetic algorithms for real parameter optimization // Foundations of Genetic Algorithms. – 1991. – Vol. 1. – P. 205 – 218. 10 Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis // Artificial Intelligence Review. – 1998. – Vol. 12, N 4. – P. 265 – 319. 11. Fogel J. А. Retrospective View and Outlook on Evolutionary Algorithms / Fogel J., Lawrence J. A. // Proc. of the Int. Conf. On Computational Intelligence Theory and Applications: Lecture Notes In Computer Science. – 1997. – Vol. 1226. – P. 337-342. 12. Goldberg David E. Genetic algorithms in search, optimization, and machine learning / David E. Goldberg – USA: Addison-Wesley publishing company, Inc., 1989. – 482 р. 13. Holland John H. Adaptation in natural and artificial systems: an introductory analysis with application to biology, control and artificial intelligence. / John H. Holland – USA: University of Michigan, 1975. – 211 p.

Посилання

• ЧОРНОБАЙ ЮРІЙ МИКОЛАЙОВИЧ
• Русин_Богдан_Павлович
• Ihor_Ohirko
• Юзевич_Володимир_Миколайович

Для студентів старших років навчання. Основною метою є ознайомлення студентів з основами проведення наукових досліджень. Огірко І.В. Електронне наукове видання. Навчально-методичний посібник. Elektroniczna publikacja naukowa. Akademia Kujawsko-Pomorska KPSW. Bydgoszcz, Poland. ‎ 22. 02. 2024 Автори курсу - Юзевич Володимир, Огірко Ігор, Дуцяк Олег, Якубович Максим.