|
|
| |
Введення в генетичні алгоритми
|
|
|
Генетичні алгоритми являють собою новий напрямок в алгоритмах. Вони здатні не тільки вирішувати та скорочувати перебір в складних задачах, але і легко адаптуватися до зміни проблеми.
Спочатку ГА-функція генерує визначену кількість можливих рішень, а потім вираховує для кожного "рівень виживання" (fitness) – близькість до істини. Ці рішення дають нащадків. Ті з них, хто є "сильнішими", тобто більше підходять, мають більший шанс до відтворення, а "слабші" поступово відмирають. Іде еволюція.
Процес повторюється до тих пір, поки не знайдеться вірне рішення, або не отримається рішення, достатньо наближене до нього. Правильно запрограмовані генетичні алгоритми можуть бути супер-ефективними.
Схема генетичного алгоритму:
1. Генерація випадкового початкового стану.
Перше покоління створюється з довільно вибраних рішень (хромосом). Це відрізняється від стандартних методів, коли початковий стан завжди один і той самий.
2. Обчислення коефіцієнта виживання (fitness).
Кожному рішенню (хромосомі) підставляється певне числове значення, залежне від близькості до відповіді.
3. Відтворення
Хромосоми, які мають велику здатність до виживання (fitness), потрапляють до нащадків ( які потім можуть мутувати) с більшою вірогідністю. Нащадок, результат злиття "батька" та "матері", являє собою комбінацію їх генів. Цей процес називається "схрещення" або "кросинговер" (crossing over).
4. Наступне покоління.
Якщо нове покоління містить рішення, достатньо близьке до відповіді, то задача вирішена. В протилежному випадку воно проходить через той самий процес. Це продовжується до досягнення розв'язку.
|
|
Книга Фріланс на західному ринку
|
|
