→ Пошук по сайту       Увійти / Зареєструватися
Приклад генетичного алгоритму: розв'язання Діофантова рівняння
Знання → Генетичні алгоритми

Приклад генетичного алгоритму: розв'язання Діофантова рівняння

Розглянемо діофантовe (тільки цілі рішення) рівняння: a 2b 3c 4d = 30, де a, b, c і d - деякі додатні цілі числа. Застосування ГА за дуже короткий час знаходить шуканий розв'язок (a, b, c, d). Звичайно, Ви можете запитати: чому б не використати метод грубої сили: просто не підставити всі можливі значення a, b, c, d (очевидно, 1 <= a, b, c, d <= 30)?
Архітектура ГА-систем дозволяє знайти рішення швидше за рахунок більш 'осмисленого' перебору. Ми не перебираємо всі підряд, але наближаємося від випадково вибраних рішень до кращих. Для початку виберемо 5 випадкових рішень. Взагалі кажучи, ми можемо використовувати меншу обмеження для b, c, d, але для спрощення хай буде 30.

Хромосома (a,b,c,d)
1 (1,28,15,3)
2 (14,9,2,4)
3 (13,5,7,3)
4 (23,8,16,19)
5 (9,13,5,2)
Таблица 1: 1-е покоління хромосом і їх вміст

Щоб обчислити коефіцієнти пристосованості (fitness), підставимо кожне рішення у вираз a 2 b +3 c +4 d. Відстань від отриманого значення до 30 і буде потрібним значенням.
Хромосома Коефіцієнт пристосованості
1 |114-30|=84
2 |54-30|=24
3 |56-30|=26
4 |163-30|=133
5 |58-30|=28
Таблица 2: Коефіцієнти пристсованості першого покоління хромосом (набору рішень)

Так як менші значення ближче до 30,пристосованості то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтів підходять, на жаль, менше. Щоб створити систему, де хромосоми з більш придатними значеннями мають великі шанси опинитися батьками, ми повинні обчислити, з якою вірогідністю (у%) може бути обрана кожна. Одне рішення полягає в тому, щоб взяти суму зворотних значень коефіцієнтів, і виходячи з цього обчислювати відсотки. (Зауважимо, що всі рішення були згенеровані генератором випадкових чисел - ГВЧ)
Хромосома Відповідність
1 (1/84)/0.135266 = 8.80%
2 (1/24)/0.135266 = 30.8%
3 (1/26)/0.135266 = 28.4%
4 (1/133)/0.135266 = 5.56%
5 (1/28)/0.135266 = 26.4%
Таблица 3: Імовірність виявитися батьком

Для вибору 5-ти пар батьків (кожна з яких буде мати 1 нащадка, всього - 5 нових рішень), уявімо, що у нас є 10000-стороння гральна кістка, на 880 сторонах відзначена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 і на 2640 сторонах відзначена хромосома 5. Щоб вибрати першу пару кидаємо кістка два рази і вибираємо випали хромосоми. Таким же чином вибираючи інших, отримуємо:
Хромосома батька Хромосома матері
3 1
5 2
3 5
2 5
5 3
Таблица 4: Симуляція вибору батьків

Кожен нащадок містить інформацію про гени і батька і від матері. Взагалі кажучи, це можна забезпечити різними способами, однак у нашому випадку можна використовувати т.з. "Кроссовер" (cross-over). Нехай мати містить наступний набір рішень: a1, b1, c1, d1, а батько - a2, b2, c2, d2, тоді можливо 6 різних крос-овер (| = розділова лінія):
Хромосома-батько Хромосома-матір Хромосома-нащадок
a1 | b1,c1,d1 a2 | b2,c2,d2 a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1 a2,b2 | c2,d2 a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1 a2,b2,c2 | d2 a1,b1,c1,d2 or a2,b2,c2,d1
Таблица 5: Кроссовери між батьками

Є досить багато шляхів передачі інформації нащадкові, і крос-овер - тільки один з них. Розташування роздільник може бути абсолютно довільним, як і те, батько або мати будуть ліворуч від межі.
А тепер спробуємо зробити це з нашими нащадками
Хромосома-батько Хромосома-матір Хромосома-нащадок
(13 | 5,7,3) (1 | 28,15,3) (13,28,15,3)
(9,13 | 5,2) (14,9 | 2,4) (9,13,2,4)
(13,5,7 | 3) (9,13,5 | 2) (13,5,7,2)
(14 | 9,2,4) (9 | 13,5,2) (14,13,5,2)
(13,5 | 7, 3) (9,13 | 5, 2) (13,5,5,2)
Таблица 6: Симуляція кроссоверів хромосом батьків

Тепер ми можемо обчислити коефіцієнти виживаності (fitness) нащадків.
Хромосома-нащадок Коефіцієнт пристосованості
(13,28,15,3) |126-30|=96
(9,13,2,4) |57-30|=27
(13,5,7,2) |57-30|=22
(14,13,5,2) |63-30|=33
(13,5,5,2) |46-30|=16
Таблица 7: Коефіцієнт пристосованості нащадків (fitness)
#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;
   }
}

Зверніть увагу на додаткові посилання

Якщо вас цікавить...

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

Головний розділ

Генетичні алгоритми
загрузка...
Сторінки, близькі за змістом
Генетичні алгоритми
Генетичний алгоритм (англ. genetic algorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.