Побудова і аналіз алгоритмів

Об'єм пам'яті для зберігання такого дерева може виявитися достатньо великим, але, якщо дотримуватися мір безпеки, можна обійтися зберіганням в пам'яті в будь-який заданий момент часу лише одного шляху - від кореня до того чи іншого вузла. Приведемо алгоритм пошуку, який виконує обхід дерева за допомогою послідовності рекурсивних викликів. Цей алгоритм передбачає виконання наступних умов:

1. Виграші є дійсними числами з обмеженого інтервалу, наприклад [-1, 1].

2. Константа більша, ніж будь-який додатній виграш, а - менша, ніж будь-який від'ємний виграш.

3. Дані типу modetype (тип режиму) можуть приймати два фіксовані значення - MIN, або MAX.

4. Передбачений тип даних boardtype (тип ігрової дошки), яка визначається способом представлення позицій на дошці.

5. Передбачена функція payoff (виграш), яка обчислює виграш для будь-якої позиції, яка є листком дерева.

float Search(boardtype B, modetype mode)

// Оцінює і повертає виграш для позиції В з передбачення,

// що наступним повинен ходити гравець 1 (mode=MAX) або гравець 2 (mode=MIN)

{

boardtype C;// нащадок позиції В

float Value;// тимчасове значення виграшу

if (B є листком)// 1

return payoff(B);// 2

else

{

if (mode==MAX)// 3

Value = -;// 4

Else

Value = ;// 5

For (для кожного сина С позиції В)// 6

{

if (mode==MAX)// 7

Value = max(Value, Search(C, MIN));// 8

Else

Value = min(Value, Search(C, MAX));// 9

return Value;// 10

}

}

}

6.5.3 Альфа-бета відсікання

Одна дуже проста умова дозволяє позбавитися від розгляду значної частини типового дерева гри. Цикл (6) в алгоритмі може ігнорувати певних нащадків, досить часто доволі велику їх кількість.

Загальне правило відсікання вузлів зв'язане з поняттям кінцевих і приблизних значень вузлів. Кінцеве значення - це то, що називають виграшем. Приблизне значення - це верхня межа значення вузла в режимі MIN, або нижня межа значення вузла в режимі MAX. Приведемо правила обчислення цих значень.

1. Якщо вже розглянуто або відсічено всіх нащадків вузла, то його приблизне значення стає кінцевим.

2. Якщо орієнтовне значення вузла в режимі MAX рівне v1, а кінцеве значення одного з його нащадків рівне v2, тоді встановити приблизне значення вузла рівним max(v1,v2). Якщо вузол знаходиться в режимі MIN - min(v1,v2).

3. Якщо p є вузлом в режимі MAX, і має батька q, а приблизні значення вузлів рівні v1 і v2, відповідно, причому v1<v2, тоді можна відсікти всіх нерозглянутих нащадків вузла p, якщо p є вузлом в режимі MAX, а q є, таким чином в режимі MIN, і v2<v1.

6.5.4 Метод гілок і границь

Метод гілок і границь є ще одним з методів відсікання гілок в дереві рішень, щоб не було необхідно розглядати всі гілки дерева. Загальний підхід при цьому полягає в тому, щоб відстежувати межі вже знайдених і можливих рішень. Якщо в якійсь точці найкраще з вже знайдених рішень краще, ніж краще можливе рішення в нижніх гілках, то можна ігнорувати всі шляхи вниз від вузла.

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

Задачі такого типу називаються задачею формування портфеля. Є декілька позицій (інвестицій), які повинні поміститися в портфель фіксованого розміру (100 мільйонів доларів). Кожна з позицій має вартість (гроші) і ціну (теж гроші). Необхідно знайти набір позицій, який поміщається в портфель і має максимально можливу ціну.

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

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

Щоб використати метод гілок і границь, створюють масив, який міститиме позиції з якнайкращого знайденого дотепер рішення. При ініціалізації масив повинен бути порожній. Можна також використати змінну для стеження за ціною цього рішення. Спочатку ця змінна може мати невелике значення, щоб перше ж знайдене реальне рішення було краще початкового.

При пошуку в дереві рішень, якщо в якійсь точці аналізоване рішення не може бути краще, ніж існуюче, то можна припинити подальший пошук цим шляхом. Також, якщо в якійсь точці вибрані позиції коштують більше 100 мільйонів, то можна також припинити пошук.

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

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

При пошуку методом гілок і границь кількість вузлів, які перевіряються, набагато менша ніж при повному переборі. Дерево рішень для задачі портфеля з 20 позиціями містить більше 2 мільйони вузлів. При повному переборі доведеться перевірити їх усіх, при пошуку методом гілок і границь знадобиться перевірити тільки приблизно 1500 з них.

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

6.6 Евристичні алгоритми

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

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

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

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

У попередньому прикладі метод гілок і границь використовувався для вибору інвестиційних можливостей. Проте, вкладення можуть бути ризикованими, і точні результати часто наперед невідомі. Можливо, що наперед буде невідомий точний дохід або навіть вартість деяких інвестицій. В цьому випадку, ефективне евристичне рішення може бути таким же надійним, як і якнайкраще рішення, яке ви може обчислити точно.

Отже, евристичні алгоритми - це алгоритми, які мають такі властивості:

Вони дозволяють знайти добрі, хоча і не завжди найкращі розв'язки з усіх, що існують.

Метод пошуку або побудови розв'язку звичайно значно простіший, ніж той що гарантує оптимальність розв'язку.

Поняття „добрий розв'язок” змінюється від задачі до задачі, тому його важко визначити точно. Припустимість використання евристики залежить від співвідношення часу та складності пошуку розв'язку обома способами та співвідношення якості обох розв'язків.

У цьому розумінні усі умови, що висуваються до розв'язку, звичайно ділять на дві групи щодо витрат праці:

ті, які легко задовольнити;

ті, що вимагають великої роботи.

З іншої сторони, вони поділяються на такі групи щодо їхньої важливості для кінцевої якості:

ті, які обов'язково слід задовольнити;

ті, що можуть бути послаблені або змінені.

Цю ситуацію образно показано в таблиці

	1	2
a	Слід задовольнити	?
b	?	Варто відмовитися

Повернемося до нашого прикладу - задачі про мандрівного крамаря. Якщо міст, про які йдеться - багато, то пошук точно мінімального за довжиною циклу може вимагати дуже багато часу. З іншої сторони, об'їзд слід зробити лише один раз. Якщо витрати на пошук оптимального маршруту можуть виявитися більшими або еквівалентними до витрат на пальне під час подорожі, то, можливо, варто просто рушати в путь, прямуючи до найближчого міста кожного разу.

Якщо ж слід відшукати найкращий маршрут для регулярного об'їзду (наприклад, вибирання пошти зі скриньок, розвезення хлібу з заводу по магазинах, маршрут для руки-маніпулятора робота під час монтування друкованих плат) , то все ж варто відшукати оптимальний маршрут, бо витрати на програмування є разовими, а витрати на зайвий рух є регулярними.

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

Частіше за все евристичні алгоритми базуються на методі сходження або на методі частинних цілей.

6.7 Імовірнісні алгоритми

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

Серед усієї гами цих алгоритмів розглянемо лише один для прикладу - обчислення площі фігури методом Монте-Карло.

Нехай слід обчислити площу криволінійної області S, рівняння межі якої таке складне, що виключає застосування аналітичних методів обчислення.



Якщо область S повністю можна включити у прямокутну область

,

то S ділить Q на долі пропорційно

Якщо за допомогою датчика випадкових чисел генерувати точки , які б рівномірно заповнювали прямокутник Q, то кількість тих точок, що потраплять усередину області S, та тих, що потраплять за її межі, буде відноситися приблизно так само

тоді

Кількість N_S та N_Q підраховуються під час експерименту.

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

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

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

6.8 Генетичні алгоритми

Генетичні алгоритми, будучи однією з парадигм еволюційних обчислень, є алгоритмами пошуку, побудованими на принципах, схожих з принципами природного відбору і генетики. Якщо говорити узагальнено, вони об'єднують в собі принцип виживання найперспективніших особин - рішень і структуризований обмін інформацією, в якому присутній елемент випадковості і який моделює природні процеси спадковості і мутації. Додатковою властивістю цих алгоритмів є невтручання людини в процес пошуку, який розвивається. Людина може впливати на нього лише опосередковано, задаючи певні параметри.

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

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

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

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

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

4. Генетичний алгоритм використовує як правило ймовірності для породження нових точок аналізу, так і детерміновані правила для переходу від одних точок до інших. Одночасне використовування елементів випадковості і детермінованості дає значно більший ефект, ніж роздільне.

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

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

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

Моделювання процесу мутації нових особин здійснюється за рахунок роботи оператора мутації. Основним параметром оператора мутації також є вірогідність мутації.

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

Оператори відбору, схрещування, мутації і редукції називають ще генетичними операторами.

Критерієм зупинки роботи генетичного алгоритму може бути одна з трьох подій:

Було сформовано задана користувачем кількість поколінь.

Популяція досягла заданого користувачем якості (наприклад, значення якості всіх особин перевищило заданий поріг).

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

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

Розглянемо тепер безпосередньо роботу генетичного алгоритму.

Формування початкової популяції відбувається, як правило, з використанням якого-небудь випадкового закону, на основі якого вибирається потрібна кількість точок пошукового простору. Початкова популяція може також бути результатом роботи якого-небудь іншого алгоритму оптимізації. Все тут залежить від розробника конкретного генетичного алгоритму.

В основі оператора відбору, який служить для вибору батьківських пар і знищення особин, лежить принцип „виживає сильніший”. Як приклад можна привести наступний оператор. Вибір особини для розмноження проводиться випадково. Імовірність участі особини в процесі розмноження обчислюється за формулою:

де n - розмір популяції, i - номер особини, Рi - імовірність участі особини в процесі розмноження, fi - значення цільової функції для i-ої особини. Очевидно, що одна особина може бути задіяна в декількох батьківських парах.

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

Оператор схрещування покликаний моделювати природний процес спадковості, тобто забезпечувати передачу властивостей батьків нащадкам.

Опишемо найпростіший оператор схрещування. Він виконується в два етапи. Нехай особина є рядком з n елементів. На першому етапі рівномірно вибирається натуральне число до від 1 до n-1. Це число називається точкою розбиття. Відповідно до нього обидва початкові рядки розбиваються на два рядки. На другому етапі рядки обмінюються своїми частинами, які лежать після точки розбиття, тобто елементами з k+l-го по n-й. Так виходять два нові рядки, які успадковували частково властивості обох батьків.

Вірогідність використання оператора схрещування звичайно вибирається достатньо великою, в межах від 0,9 до 1, щоб забезпечити постійну появу нових особин, що розширюють простір пошуку. При значенні вірогідності менше 1 часто використовують елітизм. Це особлива стратегія, яка припускає перехід в популяцію наступного покоління еліти, тобто кращих особин поточної популяції, без жодних змін. Використання елітизму сприяє збереженню загальної якості популяції на високому рівні. При цьому елітні особини беруть участь ще і в процесі відбору батьків для подальшого схрещування. Кількість елітних особин визначається звичайно за формулою:

де K - кількість елітних особин, Р - вірогідність використання оператора схрещування, N - розмір популяції.

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

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

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

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

Після завершення роботи генетичного алгоритму з кінцевої популяції вибирається та особина, яка дає максимальне (або мінімальне) значення цільової функції і є, таким чином, результатом роботи генетичного алгоритму. За рахунок того, що кінцева популяція краща початкової, отриманий результат є поліпшеним рішенням.

6.8.1 Розв'язок діофантового рівняння

Розглянемо діофантове (тільки цілі розв'язки) рівняння: , де a, b, c і d - деякі додатні цілі числа. Застосування генетичного алгоритму за дуже короткий час знаходить шуканий розв'язок (a, b, c, d).

Звичайно, можна просто підставити всі можливі значення a, b, c і d (очевидно, . Але архітектура систем генетичних алгоритмів дозволяє знайти розв'язок швидше за рахунок більш „осмисленого” перебору. Не перебирають усі значення підряд, а наближаємося від випадково вибраних рішень, до кращих.

Спершу виберемо 5 випадкових рішень: .

Щоб обчислити коефіцієнти виживання (fitness), підставимо кожний розв'язок у вираз . Відстань від отриманого значення до 30 і буде потрібним значенням.

Табл

Хромосома	(a, b, c, d)	Коефіцієнт виживання	Процент відходу
1	(1, 28, 15, 3)	|114-30| = 84	(1/84)/0.135266 = 8.80%
2	(14, 9, 2, 4)	|54-30| = 24	(1/24)/0.135266 = 30.8%
3	(13, 5, 7, 3)	|56-30| = 26	(1/26)/0.135266 = 28.4%
4	(23, 8, 16, 19)	|163-30| = 133	(1/133)/0.135266 = 5.56%
5	(9, 13, 5, 2)	|58-30| = 28	(1/28)/0.135266 = 26.4%

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

Отже, для вибору 5-ти пар батьків (кожна з яких буде мати 1 нащадка, всього - 5 нових рішень), генеруємо випадкові числа згідно розподілу імовірностей стати батьками:

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

Хромосома-батько	Хромосома-мати	Хромосома-нащадок	Коефіцієнт виживання
(13 | 5,7,3)	(1 | 28,15,3)	(13, 28, 15, 3)	|126-30| = 96
(9,13 | 5,2)	(14,9 | 2,4)	(9, 13, 2, 4)	|57-30| = 27
(13,5,7 | 3)	(9,13,5 | 2)	(13, 5, 7, 2)	|57-30| = 22
(14 | 9,2,4)	(9 | 13,5,2)	(14, 13, 5, 2)	|63-30| = 33
(13,5 | 7, 3)	(9,13 | 5, 2)	(13, 5, 5, 2)	|46-30| = 16

Середній коефіцієнт виживання нащадків виявилась 38.8, в той же час як у батьків цей коефіцієнт був рівним 59.4. Наступне покоління може піддаватися мутації. Наприклад, можна замінити одне з значень якої-небудь хромосоми на випадкове ціле від 1 до 30.

Продовжуючи таким чином, одна хромосома в конці кінців досягне коефіцієнта виживання 0, тобто стане розв'язком.

6.8.2 Програмна реалізація

Даний приклад застосування генетичних алгоритмів реалізований на мові С++ засобами об'єктно-орієнтованого програмування. Клас на C++ потребує 5 значень при ініціалізації: 4 коефіцієнти й результат. Для приведеного прикладу це буде мати вигляд:

CDiophantine dp(1,2,3,4,30);

Для розв'язку рівняння, викликають функцію Solve(), яка поверне структуру, що містить розв'язок. Виклик GetGene() дозволяє отримати ген з правильними значеннями a, b, c і d . Стандартна процедура main.cpp, яка використовує цей клас, може бути такою:

#include <iostream.h>

#include "diophantine.h"

void main()

{

CDiophantine dp(1,2,3,4,30);

int ans;

ans = dp.Solve();

if (ans == -1)

cout << "No solution found." << endl;

else

{

gene gn = dp.GetGene(ans);

cout << "The solution set to a+2b+3c+4d=30 is:\n";

cout << "a = " << gn.alleles[0] << "." << endl;

cout << "b = " << gn.alleles[1] << "." << endl;

cout << "c = " << gn.alleles[2] << "." << endl;

cout << "d = " << gn.alleles[3] << "." << endl;

}

}

Перш за все розглянемо заголовок класу:

#include <stdlib.h>

#include <time.h>

#define MAXPOP25

struct gene

{

int alleles[4];

int fitness;

float likelihood;

// Перевірка рівності.

operator==(gene gn)

{

for (int i=0;i<4;i++)

if (gn.alleles[i] != alleles[i])

return false;

return true;

}

};

class CDiophantine

{

public:

CDiophantine(int, int, int, int, int);

// Конструктор з коефіцієнтами для a,b,c,d.

int Solve();// Рішення рівняння.

// Повернення розв'язку.

gene GetGene(int i) { return population[i];}

protected:

int ca,cb,cc,cd;// Коефіцієнти.

int result;

gene population[MAXPOP];// Популяція.

int Fitness(gene &);// Функція приспособленості.

void GenerateLikelihoods();// Генерація необхідних імовірностей.

float MultInv();// Створення мутації.

int CreateFitnesses();

void CreateNewPopulation();

int GetIndex(float val);

gene Breed(int p1, int p2);

};

Існують дві структури: gene і клас CDiophantine. gene використовується для слідкування за різними наборами рішень. Створювана популяція - популяція генів. Ця генетична структура відслідковує свої коефіцієнти виживання й імовірність виявитися батьком. Також є невелика функція перевірки на рівність. Тепер опишемо функції:

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

int CDiophantine::Fitness(gene &gn)

{

int total = ca * gn.alleles[0] + cb * gn.alleles[1] +

cc * gn.alleles[2] + cd * gn.alleles[3];

return gn.fitness = abs(total - result);

}

int CDiophantine::CreateFitnesses()

{

float avgfit = 0;

int fitness = 0;

for(int i=0;i<MAXPOP;i++)

{

fitness = Fitness(population[i]);

avgfit += fitness;

if (fitness == 0)

return i;

}

return 0;

}

Зауважимо, що якщо fitness = 0, то знайдено рішення - повернення. Після обчислення коефіцієнту потрібно обчислити імовірність вибору цього гену в якості батьківського.

Імовірність обчислюється як сума обернених коефіцієнтів, поділена на величину, обернену до коефіцієнта даному значенню. Імовірності кумулятивні (додаються), що робить дуже легкими обчислення з батьками.

Отже, є дві функції: одна обчислює smi, а друга генерує імовірності виявитися батьком.

float CDiophantine::MultInv()

{

float sum = 0;

for(int i=0;i<MAXPOP;i++)

sum += 1/((float)population[i].fitness);

return sum;

}

void CDiophantine::GenerateLikelihoods()

{

float multinv = MultInv();

float last = 0;

for(int i=0;i<MAXPOP;i++)

population[i].likelihood = last = last +

((1/((float)population[i].fitness) / multinv) * 100);

}

Тепер є і коефіцієнти виживання, і необхідні імовірності, тобто можна переходити до розмноження.

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

void CDiophantine::CreateNewPopulation()

{

gene temppop[MAXPOP];

for(int i=0;i<MAXPOP;i++)

{

int parent1 = 0, parent2 = 0, iterations = 0;

while(parent1 == parent2 || population[parent1] == population[parent2])

{

parent1 = GetIndex((float)(rand() % 101));

parent2 = GetIndex((float)(rand() % 101));

if (++iterations > 25)

break;

}

temppop[i] = Breed(parent1, parent2);// Створення дитини.

}

for(i=0;i<MAXPOP;i++)

population[i] = temppop[i];

}

Спочатку створюють випадкову популяцію генів. Потім виконують цикл по всіх генах. Вибираючи гени, не хочуть, щоб вони виявилися однаковими. При виборі батька, генерують випадкове число, а потім викликають GetIndex. GetIndex використовує кумулятивність імовірностей, вона просто виконує ітерації по всіх генах, поки не знайде ген, який містить число:

int CDiophantine::GetIndex(float val)

{

float last = 0;

for(int i=0;i<MAXPOP;i++)

if (last <= val && val <= population[i].likelihood)

return i;

else

last = population[i].likelihood;

return 4;

}

Повертаючись до функції CreateNewPopulation(): якщо число ітерацій перевищує MAXPOP2, вона вибере будь-яких батьків. Після того, як батьки вибрані, вони схрещуються: їх індекси передаються вверх на функцію розмноження (Breed). Breed function повертає ген, який поміщається в тимчасову популяцію:

gene CDiophantine::Breed(int p1, int p2)

{

int crossover = rand() % 3+1;// Розмноження (не перше).

int first = rand() % 100;// Хто з батьків буде першим?

gene child = population[p1];// Ініціалізація усіх дітей.

int initial = 0, final = 3;// Початок схрещення.

if (first < 50)

initial = crossover;// Якщо перший батько є першим починаємо схрещення.

else

final = crossover+1;// Інакше завершуємо його.

for(int i=initial;i<final;i++) // Схрещення!

{

child.alleles[i] = population[p2].alleles[i];

if (rand() % 101 < 5)

child.alleles[i] = rand() % (result + 1);

}

return child;// Повернення дитини...

}

Нарешті визначають точку кросинговеру. Зауважимо, що не варто, щоб кросинговер складався лише з копіювання тільки одного з батьків. Генерують випадкове число, яке визначить точку кросинговеру. Також в програму добавлена невелика мутація, яка впливає на схрещування - 5% - імовірність появи нового числа.

Тепер розглянемо функцію Solve(), яка ітеративно викликає описані функції.

int CDiophantine::Solve()

{

int fitness = -1;

// Генерація початкової популяції.

srand((unsigned)time(NULL));

for(int i=0;i<MAXPOP;i++)// Заповнення популяції випадковими числами

for (int j=0;j<4;j++)// від 0 до результату.

population[i].alleles[j] = 1 + rand() % (result + 1);

if (fitness = CreateFitnesses())

return fitness;

int iterations = 0;// Кількість ітерацій.

while (fitness != 0 || iterations < 50)

// Повторення поки не знайдено розв'язок, або ітерацій > 50.

{

GenerateLikelihoods();// Генерація необхідних імовірностей.

CreateNewPopulation();

if (fitness = CreateFitnesses())

return fitness;

iterations++;

}

return -1;

}

Размещено на Allbest.ru

...