Трубаров Вячеслав Анатольевич | Реферат по магистерской работе | Генетический алгоритм оптимизации

Биография
Реферат по магистерской работе
Библиотека по теме магистерской работы
Ссылки по теме магистерской работы
Отчёт о результатах поиска по теме магистерской работы
Индивидуальное задание

Тема магистерской работы:
"Исследование генетических алгоритмов оптимизации в параллельной моделирующей системе"
Руководитель: проф. Святный В.А.

ДОСЛІДЖЕННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ ОПТИМІЗАЦІЇ В ПАРАЛЕЛЬНІЙ МОДЕЛЮЮЧІЙ СИСТЕМІ


ЗМІСТ

ВСТУП
1 МЕТОДИ ВИРІШЕННЯ ДИСКРЕТНИХ ЗАДАЧ ОПТИМІЗАЦІЇ
1.1 Огляд методів вирішення дискретних задач оптимізації
1.2 Локально-стохастичні алгоритми
2 ГЕНЕТИЧНИЙ АЛГОРИТМ
2.1 Природний добір та генетичне спадкування
2.2 Принцип "виживає найсильніший"
2.3 Виникнення еволюційних обчислень
2.4 Ідея генетичного алгоритму
2.5 Загальний зміст генетичного пошуку
2.6 Робота генетичного алгоритму
ВИСНОВОК
СПИСОК ДЖЕРЕЛ, ЩО ВИКОРИСТАЛИСЯ

ВСТУП

Задача оптимізації є зараз центральною проблемою науки, техніки та повсякденного життя. Що б не робила людина, вона намагається зробити це як можна краще. Будь-які скільки-небудь обґрунтовані висновки, дії або, нарешті, створені пристрої можна розглядати з якоїсь точки зору як оптимальні. Тому що ми обрали їх з безлічі інших висновків, дій або пристроїв, тобто визнали їх кращім.
Активна діяльність людини завжди та скрізь пов’язана з проблемою вибору, з прийняттям рішень, орієнтованих на досягнення тієї чи іншої мети. Прийняття рішень є щоденною діяльністю людини, частиною його повсякденної діяльності. Прості звичні рішення на рівні побутових проблем людина приймає легко, часто автоматично, не замислюючись. У складних та відповідальних випадках, наприклад при розробці плану або програми керування деякою системою, формуванні стратегій діяльності в мінливій обстановці або закону керування зі зворотним зв’язком, тощо, людині приходиться враховувати велику кількість факторів, оцінювати множину сил, впливів, інтересів та наслідків, які характеризують те чи інше рішення, тобто вирішувати задачу оптимізації [1].
Прийняття рішення в більшості випадків полягає в генерації всіх можливих альтернатив рішень, їх оцінці та обиранні кращої з них. Прийняти правильне рішення - значить обрати такий варіант з числа можливих, в якому при врахуванні усіх різноманітних факторів і суперечливих вимог буде оптимізована деяка загальна цінність, тобто рішення буде в максимальній ступіні сприяти досягненню поставленої мети [2].
З появою та розвитком обчислювальної техніки процеси генерації та вибору альтернатив рішень стали реалізовуватися на комп’ютерах. У зв’язку з цим з'явилися нові задачі формалізації і алгоритмізації процесу прийняття рішень, які на сьогоднішній день складають окрему велику область досліджень.
Формалізація тієї чи іншої задачі оптимізації, у загальному випадку, припускає опис усіх важливих факторів, які впливають на досягнення мети, їх взаємодії, обмежувальних умов та критерію оцінки якості рішення, що приймається, на базі якого можна здійснювати вибір між альтернативами. У якості критерію оцінки виступає цільова функція, аргументами якої є кількісні характеристики, які описують становище факторів, що впливають на досягнення мети в розв'язуваній задачі [3]. При цьому, рішенню, яке приводить до найкращого результату, як правило, відповідає екстремальне значення цільової функції, тобто точка її максимуму або мінімуму.
Отже, процес генерації варіантів рішення та вибору найкращої з отриманих альтернатив зводиться до створення всіх можливих комбінацій значень характеристик, які впливають на цільову функцію, і знайдення такої комбінації, яка приводить до її екстремального значення. Всі можливі комбінації аргументів при цьому утворять простір пошуку задачі, розмірність якого визначається числом аргументів цільової функції. А кожна з зазначених комбінації утворює точку в даному просторі.
Слід відзначити, що цільова концепція при постановці задачі вибору може знаходити відображення як при завданні множини допустимих альтернатив, так і при формулюванні вимог до отримання ефективних, зокрема строго оптимальних рішень.
Таким чином, метою задачі оптимізації як практичного, так і теоретичного характеру є вибір "найкращої" (припустимої або оптимальної) конфігурації з множини альтернатив для досягнення деякої поставленої мети. При цьому "найкращою" - в смислі забезпечення оптимуму (максимального або мінімального значення залежно від конкретної постановки задачі) заданої цільової функції при задоволенні певних обмежень.
За останні декілька десятиріч склалася ієрархія таких задач разом з відповідним набором методів їх вирішення. В даній науковій роботі буде розглянуто один з найефективніших методів вирішення дискретних задач оптимізації - локально-стохастичний еволюційний метод - генетичний алгоритм оптимізації.

1 МЕТОДИ ВИРІШЕННЯ ДИСКРЕТНИХ ЗАДАЧ ОПТИМІЗАЦІЇ

1.1 Огляд методів вирішення дискретних задач оптимізації

Наявність значних труднощів та специфічних особливостей у вирішенні задач оптимізації породило велику кількість методів і алгоритмів. Як показав аналіз, при їх розробці залучався дуже різноманітний математичний апарат від математичної логіки до теорії динамічних систем, що ускладнює проведення відповідної класифікації. Однак, усі розроблені на сьогоднішній день методи, залежно від необхідної якості отримання результату, можна віднести до одного з двох класів [4]:
Докладна класифікація наведена у табл. 1.1 [2].

Таблиця 1.1 - Методи і алгоритми дискретного програмування
Найменування алгоритму (методу) Достоїнства Недоліки
1 група (точні методи) Методи і алгоритми послідовного звуження множини рішень (повний та цілеспрямований перебір) Повний перебір варіантів Оптимальне рішення NPповнота. Неможливість реалізації при великій кількості вихідних даних
Метод гілок і границь
Метод динамічного програмування
Метод множників Лагранжа
Алгоритми попереднього розширення і послідовного звуження Алгоритми відсічень
Алгоритми кінцевого розширення і послідовного звуження
Композитні алгоритми
2 група (приблизні методи) Методи і алгоритми послідовного покращання рішень (евристичні алгоритми) Ітеративні (локальні) алгоритми Алгоритм найближчого сусіда Висока швидкість отримання результату Зріст погрішності зі збільшенням вихідних даних
Алгоритм середньої величини
Стохастичні алгоритми Випадковий пошук Перегляд області рішень із заданою імовірністю Імовірностний пошук
Спрямований випадковий пошук
Імітація відпалення Рішення, близьке до оптимального Низька швидкість отримання результату
Методи паралельної обробки даних (методи штучного інтелекту) Нейронні мережі Висока швидкість і точність отримання результату Складність аналізу, програмної й апаратної реалізації
Локально-стохастичні методи (методи, які використовують елемент випадковості - еволюційні методи) Еволюційні обчислення

Точні методи вирішення в теорії дискретного програмування є найбільш загальними, що призводить до появи все нових різновидів методів і алгоритмів. До даної групи відносяться алгоритми, в яких робиться спроба як повного перебору при невеликій розмірності задачі, так і максимального скорочення обсягу перебору в протилежному випадку. При цьому має місце неминучість експоненціального часу роботи алгоритмів.
Найбільш поширеними прийомами скорочення перебору є прийоми цілеспрямованого перебору, які засновані на методі "гілок та границь" або методи "неявного перебору". Ці прийоми складаються з побудови "часткових рішень", які представлені у вигляді дерева пошуку, та з використання потужних методів побудови оцінок. Ці оцінки використовуються для впізнання безперспективних часткових рішень, в результаті чого від дерева пошуку відразу відсікаються цілі гілки.
Для алгоритмів подібного скороченого перегляду варіантів характерною є організація пошуку з повертанням. Це означає, що при русі по дереву в деякому напрямку після "дослідження" даного напрямку виконується повертання до вихідної точки та рух відновляється в раніш "не досліджених" напрямках.
Відомі також інші підходи, коли процес пошуку організований інакше (вони інколи використовуються спільно з методом гілок та границь). До них відноситься метод динамічного програмування, метод відсічень (площин що відтинають) та метод Лагранжа. Використання даних алгоритмів дозволяє в тій чи іншій мірі прискорити пошук точного рішення при збереження в загальному випадку експоненціального закону залежності часу виконання алгоритму (трудомісткості) від вихідної кількості. Алгоритми даного підходу при вирішення практичних задач оптимізації мають лише теоретичний інтерес і, як показав аналіз, ефективність своєї реалізації для невеликої кількості вихідних даних [2].
До другої групи відносяться алгоритми послідовного покращання рішень, які є дуже розвиненими в теорії математичного програмування. Вони використовують прийом, який можна назвати "зниженням вимог". Він полягає у відмовленні від оптимального рішення, але в знаходженні "гарного" рішення за припустимий час.
Головною думкою даного напрямку є така організація пошуку на множині альтернатив, при якій поступово виділялися б все більш кращі припустимі рішення. Алгоритми, засновані на цьому прийомі, звичайно називають "евристичними", оскільки вони використовують розумні міркування без строгих обґрунтувань. При їх розробці використовуються інтуїтивні міркування, які не підкріплюються відповідним математичним обґрунтуванням.
Методи, які використовуються для побудови алгоритмів такого типу, дуже залежать від специфіки задачі. Ітеративні процедури, запропоновані для цієї мети, нагадують ітеративні процедури пошуку екстремуму при використанні алгоритмів градієнтного типу й алгоритмів методу можливих напрямків.
При використання подібних алгоритмів природно виникає питання про можливість досягнення при їх використанні глобального екстремуму або наближення до нього із заданої точністю e. Виявляється, що в більшості випадків на практиці може бути гарантоване лише досягнення локального екстремуму. Дані алгоритми є приблизними, але вони принципово відрізняються від приблизних алгоритмів e-оптимізації, які будуються на базі точних методів послідовного звуження множини рішень та гарантують наближення до екстремуму з точністю до e.
Евристичні алгоритми, побудовані вказаними вище способами, на практиці виявляються дуже задовільними. Однак, для отримання задовільних характеристик за часом і точності отримання результату звичайно потрібна велика робота по його доробці та синтезі нових підходів знаходження глобального екстремуму цільової функції. В результаті удається тільки в дуже рідких випадках передбачати й оцінювати поводження таких алгоритмів. Замість цього такі алгоритми оцінюються та порівнюються на базі сполучення емпіричних даних і аргументів, що спираються на здоровий глузд. Однак, евристичні алгоритми не завжди є настільки складними для формального аналізу. В деяких випадках удається довести, що рішення, отримані евристичними алгоритмами, завжди будуть відрізнятися в процентному відношенні від оптимального не більш ніж на певну величину.
Розглянемо докладніше один з найперспективніших класів евристичних алгоритмів - локально-стохастичні алгоритми.

1.2 Локально-стохастичні алгоритми

Методи, які використовують елементи випадковості, стали з'являтися відносно недавно, після того, як становилися очевидними недоліки локальних та стохастичних алгоритмів (див. табл. 1.1). В основі першого з таких методів лежить випадковий пошук в просторі задачі зі збереженням найкращого отриманого результату.
Функціонування даних алгоритмів здійснюється наступним чином. Випадковий пошук забезпечує добір вихідних точок для проведення локальної оптимізації. Отже, рішення покращуються не тільки шляхом локальної оптимізації, але й шляхом випадкового пошуку кращого з локально оптимальних рішень. Вихідну точку для реалізації локально-стохастичного пошуку доцільно підбирати за допомогою вагового алгоритму, який забезпечує "адаптацію" пошуку до параметрів задачі.
Відповідно до цієї послідовності визначається і фіксується досягнуте при цьому рішення. На кожному наступному кроці за допомогою процедури генерації випадкових переставлянь вводиться нова послідовність індексів і на основі обраного правила або алгоритму визначаються локально-оптимальні рішення з фіксацією досягнутих при цьому кращих рішень. Керування випадковим пошуком може при цьому виконуватися шляхом зміни або структури, або параметрів генерації нової послідовності.
Застосування такого методу не гарантує отримання оптимального рішення. Крім того, результат роботи методу не можу бути кращім, ніж в інших методах пошуку, оскільки в обох випадках розглядаються одні й ті ж дискретні точки простору пошуку задачі. Однак слід зазначити, що за рахунок високої швидкості отримання результату локально-стохастичні алгоритми відносяться до найбільш ефективних алгоритмів дискретного програмування та внаслідок цього отримали значний розвиток останнім часом. Один з ефективних методів даного класу, а саме алгоритм, побудований на основі моделювання еволюційних процесів розвитку живих організмів, і буде розглянуто у рамках даної наукової роботи.

2 ГЕНЕТИЧНИЙ АЛГОРИТМ

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

2.1 Природний добір та генетичне спадкування

Ідея алгоритму полягає в імітації процесу розвитку життя на Землі в цілому. Мається на увазі науковий підхід, який базується на еволюційній теорії Дарвіна. Як відомо, еволюційна теорія стверджує, що життя на нашій планеті виникла спочатку лише у найпростіших формах - у вигляді одноклітинних організмів. Ці форми постійно ускладнювалися, пристосовуючись до навколишнього середовища та породжуючи нові види, і тільки через багато мільйонів років з'явилися перші тварини та люди.
Завдяки відкриттям останніх ста років сучасній науці сталі відомі всі основні механізми еволюції, які пов’язані з природним добором і генетичним спадкуванням. Ці механізми є достатньо простими за своєю ідеєю та ефективними. Дивно, але просте моделювання еволюційного процесу на комп’ютері дозволяє отримати рішення багатьох практичних задач оптимізації.
Згідно з еволюційною теорією, кожний біологічний вид цілеспрямовано розвивається та змінюється для того, щоб найкращим чином пристосуватися до навколишнього середовища. В процесі еволюції багато видів комах та риб набули захисне забарвлення, їжак став невразливим завдяки голкам, людина стала власником найскладнішої нервової системи. Можна сказати, що еволюція - це процес оптимізації всіх живих організмів. Розглянемо, якими ж засобами природа вирішує цю задачу оптимізації.
Ключову роль в механізмі еволюції грає природний добір. Його суть в тому, що найбільш пристосовані істоти мають більше можливостей для виживання й розмноження і, таким чином, приносять більше потомства, ніж погано пристосовані істоти. При цьому завдяки передачі генетичної інформації (генетичному спадкуванню) нащадки успадковують від батьків основні їх якості. Отже, нащадки сильних індивідуумів також будуть відносно добре пристосованими, а їх доля у загальній вазі істот буде зростати. Після зміни декількох десятків або сотень поколінь середня пристосованість істот даного виду помітно зросте.
Щоб зробити зрозумілими принципи роботи еволюційних алгоритмів, треба пояснити, як побудовані механізми генетичного спадкування в природі, тобто як властивості нащадків залежать від властивостей батьків. Основний закон спадкування інтуїтивно зрозумілий кожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадки більш пристосованих батьків будуть, скоріш за все, одними з найбільш пристосованих у своєму поколінні. Щоб зрозуміти, на чому базується ця схожість, треба трохи поглибитися у побудову живої клітини - в світ генів і хромосом.
В кожній клітині будь-якого живого організму міститься вся генетична інформація цієї істоти. Ця інформація записана у вигляді набору дуже довгих молекул дезоксірібонуклеінової кислоти (ДНК). Кожна молекула ДНК - це ланцюг, який складається з молекул нуклеотидів чотирьох типів, які позначаються як А (аденін), Ц (цитозін) , Т (тимін) та Г (гуанін). Власне, інформацію несе порядок проходження нуклеотидів в ДНК. Таким чином, генетичний код індивідуума - це просто дуже довгий рядок символів, де використовується лише 4 букви. В клітині кожна молекула ДНК оточена оболонкою - таке утворення називається хромосомою.
Ген - це відрізок ланцюга ДНК, який відповідає за певну властивість істоти, наприклад за колір очей, тип волосся, колір шкіри, тощо. Вся сукупність генетичних ознак людини кодується за допомогою приблизно 60 тисяч генів, сумарна довжина яких складає більш 90 млн. нуклеотидів.
Розрізняють два види клітин: статеві (такі, як сперматозоїд та яйцеклітина) і соматичні. В кожній соматичній клітині людини міститься 46 хромосом. Ці 46 хромосоми - насправді 23 пари, причому в кожній парі одна з хромосом отримана від батька, а друга - від матері. Парні хромосоми відповідають за одні й ті ж ознаки - наприклад, батьківська хромосома може містити ген чорного кольору очей, а парна їй материнська - ген блакитноокості. Існують певні закони, які керують участю тих чи інших генів у розвитку істоти. Зокрема, у нашому випадку нащадок буде чорнооким, тому що ген блакитних очей є "слабким" (рецесивним) і придушується геном будь-якого іншого кольору.
В статевих клітинах хромосом тільки 23, та вони непарні. При заплідненні відбувається злиття чоловічої та жіночої статевої клітини й утворюється клітина зародка, яка містить саме 46 хромосом. Які властивості нащадок отримає від батька, я які - від матері? Це залежить від того, які саме статеві клітини приймали участь у заплідненні. Справа в тому, що процес вироблення статевих клітин (мейоз) в організмі є підданим випадковостям, завдяки яким нащадки все ж багато в чому відрізняються від своїх батьків. При мейозі, зокрема, відбувається наступне: парні хромосоми соматичної клітини зближуються впритул, потім їх нитки ДНК розриваються в декількох випадкових місцях і хромосоми обмінюються своїми частинами (рис. 2.1).


Рисунок 2.1 - Умовна схема кросинговеру

Цей процес забезпечує появу нових варіантів хромосом і має назву "кросинговер". Кожна з нових хромосом опиниться потім усередині однієї зі статевих клітин, та її генетична інформація може реалізуватися в нащадках даної істоти.
Другий важливий фактор, який впливає на спадковість - це мутації, які виражаються у зміні деяких ділянок ДНК. Мутації також випадкові і можуть бути викликані різними зовнішніми факторами, такими, наприклад, як хімічний вплив, радіоактивне опромінення, тощо. Якщо мутація відбулася у статевій клітині, то змінений ген може передатися нащадку та проявитися у вигляді успадкованої хвороби або в інших нових властивостях нащадка. Якщо ці нові властивості користі, вони, скоріше за все, збережуться в даному виді - при цьому відбудеться стрибкоподібне підвищення пристосованості виду. Вважається, що саме мутації є причиною появи нових біологічних видів, а кросинговер визначає вже мінливість усередині виду (наприклад, генетичні розходження серед людей).

2.2 Принцип "виживає найсильніший"

Як вже було зазначено вище, еволюція - це процес постійної оптимізації біологічних видів, де основною направляючою силою є природний добір. Тепер можна зрозуміти, як відбувається цей процес. Природний добір гарантує, що найбільш пристосовані істоти дадуть достатньо велике потомство, а завдяки генетичному спадкуванню ми можемо бути впевненими, що частина цього потомства не тільки збереже високу пристосованість батьків, але й буде мати деякі нові властивості. Якщо ці нові властивості виявляться корисними, то з великою імовірністю вони перейдуть і до наступного покоління [2].
Таким чином, відбувається накопичування корисних якостей і поступове покращання пристосованості біологічного виду в цілому. Саме добір найкращих об’єктів - принцип "виживає найсильніший", є ключовою евристикою всіх еволюційних методів вирішення задач оптимізації, які дозволяють достатньо часто зменшити час пошуку рішення не декілька порядків у порівнянні з іншими підходами. Якщо спробувати виразити цю евристику на природній мові, то отримаємо: складно отримати найкраще рішення, модифікуючи погане. Скоріше за все, воно вийде з декількох кращих на даний момент.
З базових особливостей еволюційних алгоритмів можна відзначити їх якусь складність у плані настроювання основних параметрів (виродження, або нестійкість рішення). Тому, експериментуючи з ними й отримавши не дуже гарні результати, необхідно спробувати випробувати його при інших настроюваннях.
Цей недолік випливає з базової евристики - можна "знищити" батька найкращого рішення, якщо зробити селекцію дуже "жорсткою" (не даремно ж біологам давно відомо, що якщо залишилося менше десятка істот зникаючого виду, то цей вид сам по собі зникне через виродження). Знаючи, як вирішується задача оптимізації видів у природі, ми тепер можемо застосувати схожий метод для вирішення різноманітних задач оптимізації на практиці.

2.3 Виникнення еволюційних обчислень

Теорія еволюції вплинула на зміну світогляду людей з моменту свого виникнення. Теорія, яку Чарльз Дарвін представив в роботі, відомій як "Походження видів" в 1859 році, стала початком цієї зміни. Багато галузей наукового знання на даний час насолоджуються вільністю думки в "атмосфері", яка багатьом зобов'язана революції, яку викликала теорія еволюції та розвитку. Дарвін виявив головний механізм розвитку: добір у сполученні з мінливістю або, як він її називав, "спускання з модифікацією". В багатьох випадках, специфічні особливості розвитку за допомогою мінливості та добору все ще не безперечні, проте основні механізми пояснюють неймовірно широкий спектр явищ, що спостерігаються в Природі.
Тому недивно, що вчені, які займаються комп’ютерними дослідженнями, звернулися до теорії еволюції у пошуках нових рішень і натхнення. Можливість того, що обчислювальна система, наділена простими механізмами мінливості та добору, могла б функціонувати за аналогією з законами еволюції в природних системах, була дуже привабливою. Ця надія стала причиною появи ряду обчислювальних систем, побудованих за принципами природного добору та генетичного спадкування.
Історія еволюційних обчислень почалася з розробки ряду різних незалежних моделей еволюційного процесу. Серед цих моделей можна виділити три основні парадигми:
Парадигму генетичних алгоритмів (Genetic Algorithms) запропонував Джон Холланд, опублікувавши на початку 60-х років її загальні положення. А всесвітнє признання вони отримала після виходу в світ у 1975 році його класичної праці "Адаптація в природних і штучних системах" [5]. Генетичний алгоритм був отриманий в процесі узагальнення й імітації в штучних системах таких властивостей живої природи, як природний добір, пристосовність до мінливих умов середовища, спадкування нащадками життєво важливих властивостей від батьків, тощо.
Алгоритми в процесі пошуку використовують якесь кодування множини параметрів замість самих параметрів, і тому вони ефективно можуть застосовуватися для вирішення дискретних та комбінаторних задач оптимізації, визначених як на чисельних, так і на кінцевих множинах довільної природи. Оскільки для роботи алгоритму як інформація про функцію, що оптимізується, використовується лише її значення в розгляданих точках простору пошуку, і не потребується обчислень ні похідних, ні будь-яких інших характеристик, то даний алгоритм можна застосовувати до широкого класу функції, зокрема, до тих, які не мають аналітичного опису.
Використання набору початкових точок дозволяє застосовувати для їх формування різні способи, які залежать від специфіки задачі оптимізації, що вирішується, у тому числі можливим є завдання такого набору безпосередньо людиною. Таким чином, основна відмінність генетичних алгоритмів міститься в представленні будь-якої альтернативи рішення у вигляді бітового рядка фіксованої довжини, маніпуляції з яким виконуються при відсутності будь-якого зв’язку з його значеннєвою інтерпретацією. Тобто в даному випадку використовується єдине універсальне представлення будь-якої задачі.
Еволюційні стратегії (Evolutions Strategies), напроти, оперують об’єктами, які тісно пов’язані з задачею, яка вирішується. Кожна з альтернатив рішення представляється як єдиний масив чисельних параметрів, за кожним з яких ховається, по суті, аргумент цільової функції. Вплив на дані масиви виконується, на відміну від генетичних алгоритмів, із врахуванням їх значеннєвого вмісту і є спрямованим на покращання значень параметрів, які входять до них. Парадигму еволюційних стратегій запропонував у 1973 році Реченберг у своїй праці "Еволюційні стратегії: оптимізація технічних систем на базі принципів біологічної еволюції" і в 1977 році Шефель у праці "Чисельна оптимізація комп’ютерних моделей за допомогою еволюційних стратегій".
Ідеї еволюційного програмування (Evolutionary Programming) були запропоновані в 1966 році Фогелем, Оуенсом і Уолшем у праці "Побудова систем штучного інтелекту шляхом моделювання еволюції". В основі напрямку еволюційного програмування лежить ідея представлення альтернатив у вигляді універсальних кінцевих автоматів, здатних реагувати на стимули, які поступають з навколишнього середовища. Відповідним чином розроблялися й оператори впливу на них.

2.4 Ідея генетичного алгоритму

Уявимо собі штучний світ, населений множиною істот, причому кожна істота - це якесь рішення нашої задачі. Будемо вважати істоту тим більш пристосованою, чим краще відповідне рішення (чим більше значення цільової функції воно дає). Тоді задача максимізації цільової функції зводиться до пошуку найбільш пристосованої істоти [6]. Певна річ, не можна оселити до нашого віртуального світу усіх істот відразу, тому що їх кількість визначається вихідною множиною альтернатив. Замість цього треба розглянути багато поколінь, які змінюють один одного.
Якщо ввести у дію природний добір та генетичне спадкування, то отриманий світ буде підпорядковуватися законам еволюції. Відповідно до визначення пристосованості, метою цієї штучної еволюції буде саме створення найкращих рішень.
Безперечно, еволюція - нескінченний процес, протягом якого пристосованість істот поступово підвищується. Примусово зупинивши цей процес через достатньо довгий час після його початку і обравши найбільш пристосовану істоту в поточному поколінні, отримаємо якщо не абсолютно точну, то близьку до оптимальної відповідь. Такою є, коротенько, ідея генетичного алгоритму. Тепер треба перейти до більш точних визначень та описати роботу генетичного алгоритму докладніше.

2.5 Загальний зміст генетичного пошуку

Генетичні алгоритми, являючись однією з парадигм еволюційних досліджень, є алгоритмами пошуку, побудованими на принципах, подібним принципам природного добору і генетики. Говорячи узагальнено, вони об’єднують у собі принцип виживання найбільш перспективних істот-рішень і структурований випадково-детермінований обмін інформацією, у якому присутній елемент випадковості, моделюючий природні процеси спадкування і мутації. Додатковою властивістю цих алгоритмів є невтручання людини в розвиток процесу пошуку. Людина може впливати на нього лише опосередковано, задаючи певні параметри.
Популярність генетичних алгоритмів обумовлена тим, що вони дозволяють знайти більш гарні або "раціональні" рішення NP-повних практичних задач оптимізації за менший час, ніж інші методи, які застосовуються у цих випадках. Звичайно ж, термін "гарні" або "раціональні" не є строгим в математичному значенні.
Під "раціональними" маються на увазі рішення, які задовольняють дослідника. Адже в більшості реальних задач немає необхідності знаходити саме глобальний оптимум. Найчастіше метою пошуку є рішення, які задовольняють певним обмеженням. Наприклад, час іспитів обладнання не повинен перевищувати певної заданої величини. В такому випадку достатньо знайти саме "раціональне", тобто розумне рішення. Друга немаловажна причина популярності ГА міститься в стрімкому зрості продуктивності сучасних комп’ютерів.
Переваги генетичних алгоритмів стають більш очевидними, якщо розглянути основні їх відмінності від традиційних методів. Основних відмінностей п’ять [2]:
  1. Генетичні алгоритми працюють з кодами, в яких представлений набір параметрів, безпосередньо залежних віх аргументів цільової функції.
  2. Для пошуку генетичний алгоритм використовує декілька точок пошукового простору одночасно (розпаралелювання), а не переходить від точки до точки, як це робиться в традиційних методах. Тобто ГА оперує одночасно всією сукупністю припустимих рішень.
  3. Генетичні алгоритми в процесі роботи не використовують ніякої додаткової інформації, що підвищує швидкість їх роботи.
  4. ГА використовує як імовірнісні правила для породження нових точок пошуку, так і детерміновані правила для переходу від одних точок до інших.
  5. Генетичні алгоритми здійснюють пошук оптимального рішення за однією й тією ж стратегією, як для унімодальних, так і для багатоекстремальних функцій.
ГА працює з кодовими послідовностями (КП) - кодами безвідносно щодо їх значеннєвої інтерпретації. Тому сама КП і її структура описуються поняттям генотип, а його інтерпретація, з боку задачі, що вирішується, поняттям фенотип. Кожна КП є, за змістом, точкою простору пошуку. Екземпляр КП називають хромосомою, істотою, індивідуумом.
В принципі, генетичні алгоритми не обмежені бінарним або цілочисельним представленням. Відомі й інші реалізації, побудовані виключно на векторах речовинних чисел. Не зважаючи на те, що для багатьох реальних задач більш підходять рядки перемінної довжини, на даний час структури фіксованої довжини є найбільш розповсюдженими й вивченими.
На кожному кроці роботи ГА використовує декілька точок пошуку одночасно. Сукупність цих точок є набором КП, які утворять вихідну множину рішень - К (популяцію). Кількість КП в популяції називають розміром популяції. На кожному кроці роботи ГА обновлює вихідну множину К шляхом створення нових КП та знищення "безперспективних", які не задовольняють критерію цільової функції. Кожне обновлення інтерпретується як зміна поколінь і звичайно ідентифікується за заданим розміром.
В процесі роботи алгоритму генерація нових КП відбувається на базі моделювання процесу розмноження. При цьому, природно, КП, що породжують, називаються батьками, а породжені КП - нащадками. Батьківська пара, як правило, породжує пару нащадків. Безпосередня генерація нових рядків з двох обраних відбувається за рахунок роботи оператора схрещування (випадково-детермінованого обміну), який в процесі роботи алгоритму може застосовуватися не до всіх пар батьків.
Частина цих пар може переходити до популяції наступного покоління безпосередньо. Те, як часто виникатиме така ситуація, залежить від імовірності застосування оператора схрещування, яка є одним із параметрів ГА.
Моделювання процесу генерації нових точок пошуку відбувається за рахунок роботи оператора мутації, який задається визначеною імовірністю. Оскільки еволюційний процес біологічних видів супроводжується загибеллю останніх, то породження нащадків повинно супроводжуватися знищенням інших безперспективних КП. Вибір пар батьків з популяції для породження нащадків виконує оператор добору, а вибір КП для знищення - оператор редукції.
Характеристики генетичного алгоритму обираються таким чином, щоб забезпечити невеликий час роботи, з одного боку, та пошук як можна кращого рішення, з іншого. Загальна структурна схема генетичного алгоритму при біологічній інтерпретації зображена на рис. 2.2.

2.6 Робота генетичного алгоритму

Розглянемо роботу ГА (рис. 2.2). Формування вихідної популяції К відбувається за допомогою якогось випадкового закону, наприклад, рівномірного, на базі якого обирається необхідна кількість точок пошукового простору. Вихідна популяція може також бути результатом роботи будь-якого іншого алгоритму оптимізації.

Рисунок 2.2 - Загальна структура генетичного алгоритму
Рисунок 2.2 - Загальна структура генетичного алгоритму

В основі оператору добору, який служить для вибору батьківських пар та знищення КП, лежить принцип "виживає найсильніший".
Імовірність участі i-ї КП в процесі обміну обчислюється за формулою:
Pi - Імовірність участі i-ї КП в процесі обміну,

де n - розмір вихідної множини К,
i - номер КП,
fi - значення цільової функції для i-ї КП.
Оператор випадково-детермінованого обміну (схрещування) моделює природний процес спадкування, тобто забезпечує передачу властивостей новим КП (нащадкам). В теперішній час знаходять широке застосування одноточкові, двоточкові та рівномірні оператори, залежно від типу розбивки КП [2]. На рис. 2.3 представлена структура одноточкового оператору схрещування.
Одноточковий оператор працює наступним чином. Спочатку, випадковим чином обирається одна з точок розриву (точка розриву - ділянка між сусідніми бітами в рядку). Обидві батьківські структури розриваються на два сегменти в цій точці. Потім відповідні сегменти різних батьків склеюються та утворюється два генотипи нащадків. Наприклад, припустимо, що один з батьків складається з 10 нулів, а інший - з 10 одиниць. Нехай з 9 можливих точок розриву обрана точка 3, тоді робота одноточкового оператору схрещування виглядає так, як показано на рис. 2.3.

Рисунок 2.3 - Структура одноточкового оператору схрещування
Рисунок 2.3 - Структура одноточкового оператору схрещування

Імовірність застосування оператору схрещування обирається достатньо великою, у межах від 0.9 до 1. Робиться це для того, щоб забезпечити постійну появу нових КП, які розширюють простір пошуку. Слід зазначити, що для операції схрещування можуть застосовуватися також двоточкові та рівномірні оператори схрещування. В двоточковому операторі обираються дві точки розриву, та батьківські хромосоми обмінюються сегментом, який знаходиться між двома цими точками. В рівномірному операторі схрещування кожен біт першого батька спадкується першим нащадком із заданою імовірністю, у протилежному випадку цей біт передається другому нащадку.
Після того, як закінчиться етап схрещування, виконуються оператори випадкової зміни КП (мутації). Оператор мутації служить для моделювання природного процесу мутації. Суть даного процесу полягає у наступному.
Будь-яка популяція, якою б великою вона не була, охоплює обмежену область простору пошуку. Оператор обміну (схрещування), безумовно, розширює цю область, але все ж до певної міри, оскільки використовує обмежений набір значень, заданий вихідною множиною К (вихідною популяцією). Внесення випадкових змін до КП дозволяє перебороти це обмеження, а інколи й значно скоротити час пошуку або покращити якість результату.
В процесі роботи алгоритму усі зазначені вище оператори використовується багатократно та ведуть до поступової зміни вихідної популяції. Оскільки всі оператори спрямовані на покращання кожної окремої КП, то результатом їх роботи є поступове покращання - еволюція до локально-оптимального (оптимального) рішення.
Критерієм зупинення генетичного алгоритму може бути одна з трьох подій:
Після роботи генетичного алгоритму з кінцевої популяції обирається та КП, яка дає мінімальне (або максимальне) значення цільової функції і є, у підсумку, результатом роботи генетичного алгоритму.
Ефективність ГА при вирішенні конкретної задачі оптимізації визначається видом генетичних операторів і вибором відповідних значень параметрів, а також способу представлення задачі на КП - хромосомі. Оптимізація цих факторів приводить до підвищення швидкості та стабільності пошуку, що є суттєвим для застосування генетичних алгоритмів.

ВИСНОВОК

В останні роки реалізовано багато генетичних алгоритмів і в більшості випадків вони мало схожі з розглянутим алгоритмом. Тому зараз під терміном "генетичні алгоритми" ховається не одна модель, а достатньо широкий клас алгоритмів, підчас мало схожих один з одним.
В даний час генетичні алгоритми представляють одну з галузей науки, що інтенсивно розвивається, та дослідження в якій ведуть до постійного підвищення ефективності їх використання, а також висуванню все нових підходів до побудови конкретних алгоритмів.
Область використання генетичних алгоритмів на сьогоднішній день є достатньо великою. Тому тема, яка була розглянута в даній наукової роботі, дозволяє не тільки мати загальну уяву про генетичні алгоритми, але й використовувати їх для вирішення багатьох наукових та технічних проблем.

СПИСОК ДЖЕРЕЛ, ЩО ВИКОРИСТАЛИСЯ

  1. В.Н. Калинин, Б.А. Резников, К.И. Варакин "Теория систем и оптимального управления. Понятия, модели, методы и модели оптимального выбора" - МО СССР, 1987. - 597 с.
  2. Назаров А.В., Лоскутов А.И. "Нейросетевые алгоритмы прогнозирования и оптимизации систем" - СПб.: Наука и Техника, 2003. - 384 с.
  3. В.В. Корнеев, А.Ф. Гареев, С.В. Васютин, В.В. Райх "Базы данных. Интеллектуальная обработка информации". - М.: "Нолидж", 2000 - 352 с.
  4. М. Свами, К. Тхуласираман "Графы, сети и алгоритмы" - М.: Мир, 1984. - 454 с.
  5. "Генетический алгоритм" http://g-u-t.chat.ru/ga/index.htm
  6. Л.Г. Косолапова, Б.Г. Ковров "Эволюция популяций. Дискретное математическое моделирование". Новосибирск: "Наука", 1988. - 93 с.

Биография
Реферат по магистерской работе
Библиотека по теме магистерской работы
Ссылки по теме магистерской работы
Отчёт о результатах поиска по теме магистерской работы
Индивидуальное задание

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Copyright © Вячеслав Трубаров, ДонНТУ