Приклад генетичного алгоритму: розв'язання Діофантова рівняння
ADO в Delphi AJAX Android C++ CakePHP CMS COM CSS Delphi Flash Flex HTML Internet Java JavaScript MySQL PHP RIA SCORM Silverlight SQL UML XML Бази даних Веб-розробка Генетичні алгоритми ГІС Гітара Дизайн Економіка Інтелектуальні СДН Колір Масаж Математика Медицина Музика Нечітка логіка ООП Патерни Подання знань Розкрутка сайту, SEO САПР Сесії в PHP Системне програмування Системний аналіз Тестологія Тестування ПЗ Фреймворки Штучний інтелект
|
Приклад генетичного алгоритму: розв'язання Діофантова рівнянняРозглянемо діофантовe (тільки цілі рішення) рівняння: a 2b 3c 4d = 30, де a, b, c і d - деякі додатні цілі числа. Застосування ГА за дуже короткий час знаходить шуканий розв'язок (a, b, c, d).
Звичайно, Ви можете запитати: чому б не використати метод грубої сили: просто не підставити всі можливі значення a, b, c, d (очевидно, 1 <= a, b, c, d <= 30)?
Щоб обчислити коефіцієнти пристосованості (fitness), підставимо кожне рішення у вираз a 2 b +3 c +4 d. Відстань від отриманого значення до 30 і буде потрібним значенням.
Так як менші значення ближче до 30,пристосованості то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтів підходять, на жаль, менше. Щоб створити систему, де хромосоми з більш придатними значеннями мають великі шанси опинитися батьками, ми повинні обчислити, з якою вірогідністю (у%) може бути обрана кожна. Одне рішення полягає в тому, щоб взяти суму зворотних значень коефіцієнтів, і виходячи з цього обчислювати відсотки. (Зауважимо, що всі рішення були згенеровані генератором випадкових чисел - ГВЧ)
Для вибору 5-ти пар батьків (кожна з яких буде мати 1 нащадка, всього - 5 нових рішень), уявімо, що у нас є 10000-стороння гральна кістка, на 880 сторонах відзначена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 і на 2640 сторонах відзначена хромосома 5. Щоб вибрати першу пару кидаємо кістка два рази і вибираємо випали хромосоми. Таким же чином вибираючи інших, отримуємо:
Кожен нащадок містить інформацію про гени і батька і від матері. Взагалі кажучи, це можна забезпечити різними способами, однак у нашому випадку можна використовувати т.з. "Кроссовер" (cross-over). Нехай мати містить наступний набір рішень: a1, b1, c1, d1, а батько - a2, b2, c2, d2, тоді можливо 6 різних крос-овер (| = розділова лінія):
Є досить багато шляхів передачі інформації нащадкові, і крос-овер - тільки один з них. Розташування роздільник може бути абсолютно довільним, як і те, батько або мати будуть ліворуч від межі. А тепер спробуємо зробити це з нашими нащадками
Тепер ми можемо обчислити коефіцієнти виживаності (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) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. |
Copyright © 2008—2024 Портал Знань.
При використанні матеріалів посилання, для інтернет-ресурсів — гіперпосилання, на Znannya.org обов'язкове.
Зв'язок
|
НТУУ "КПІ" Інженерія програмного забезпечення КПІ Лабораторія СЕТ |
|