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

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

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

Що таке генетичний алгоритм?

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

Населення:Популяція - це підмножина всіх можливих або ймовірних рішень, які можуть вирішити дану проблему.Хромосоми:Хромосома є одним із рішень у популяції даної проблеми, а колекція генів генерує хромосому.ген:Хромосома розділена на інший ген або є елементом хромосоми.Алелі:Алель - це значення, надане гену в конкретній хромосомі.Функція фітнесу:Фітнес-функція використовується для визначення індивідуального рівня фізичної підготовки в популяції. Це означає здатність індивіда конкурувати з іншими індивідами. У кожній ітерації індивідууми оцінюються на основі їх фітнес-функції.Генетичні оператори:Згідно з генетичним алгоритмом, найкраща особина пари відновлює потомство краще, ніж батьки. Тут генетичні оператори відіграють певну роль у зміні генетичного складу наступного покоління.Вибір

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

Доступні типи стилів виділення

Вибір колеса рулетки Вибір події Ранговий відбір

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

що таке ім'я користувача

Як працює генетичний алгоритм?

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

В основному він включає п’ять етапів вирішення складних задач оптимізації, які наведені нижче:

Ініціалізація Фітнес завдання Вибір Розмноження Припинення

1. Ініціалізація

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

2. Фітнес завдання

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

3. Відбір

Селекційна фаза передбачає відбір особин для відтворення потомства. Потім усі відібрані особини об’єднуються в пари по дві особини для збільшення відтворення. Потім ці особини передають свої гени наступному поколінню.

java перетворює ціле число на рядок

Існує три типи методів вибору, а саме:

• Вибір колеса рулетки
• Вибір турніру
• Відбір на основі рангу

4. Розмноження

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

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

Гени батьків обмінюються між собою, поки не буде досягнута точка кросинговеру. Ці щойно згенеровані нащадки додаються до популяції. Цей процес також називають кросовером. Доступні типи кросоверних стилів:
• Кросовер в одну точку
• Двоточковий кросовер
• Ліврея кросовера
• Кросовер успадкованих алгоритмів
Мутація
Оператор мутації вставляє випадкові гени в потомство (нову дитину), щоб підтримувати різноманітність популяції. Це можна зробити, перевернувши деякі біти в хромосомах.
Мутація допомагає вирішити проблему передчасної конвергенції та посилює диверсифікацію. На зображенні нижче показано процес мутації:
Типи доступних стилів мутації,
Фліп-бітова мутація Мутація Гауса Мутація обміну/свопу

5. Припинення

Після фази відтворення критерій зупинки застосовується як основа для припинення. Алгоритм припиняє роботу після досягнення порогового рішення відповідності. Він визначить остаточне рішення як найкраще серед населення.

Загальний робочий процес простого генетичного алгоритму

Переваги генетичного алгоритму

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

Обмеження генетичних алгоритмів

• Генетичні алгоритми не є ефективними алгоритмами для вирішення простих задач.
• Це не гарантує якість остаточного вирішення проблеми.
• Повторне обчислення значень придатності може спричинити певні обчислювальні проблеми.

Різниця між генетичними алгоритмами та традиційними алгоритмами

• Простір пошуку - це сукупність усіх можливих рішень проблеми. У традиційному алгоритмі підтримується лише один набір рішень, тоді як у генетичному алгоритмі можна використовувати кілька наборів рішень у просторі пошуку.
• Традиційні алгоритми потребують більше інформації для здійснення пошуку, тоді як генетичні алгоритми потребують лише однієї цільової функції для обчислення придатності особи.
• Традиційні алгоритми не можуть працювати паралельно, тоді як генетичні алгоритми можуть працювати паралельно (обчислення придатності індивідуальностей є незалежним).
• Однією великою відмінністю генетичних алгоритмів є те, що успадковані алгоритми працюють не безпосередньо з результатами шукача, а з їхніми представленнями (або візуалізаціями), які часто називають хромосомами.
• Одна з великих відмінностей між традиційним алгоритмом і генетичним алгоритмом полягає в тому, що він безпосередньо не працює з потенційними рішеннями.
• Традиційні алгоритми можуть зрештою генерувати лише один результат, тоді як генетичні алгоритми можуть генерувати кілька оптимальних результатів із різних поколінь.
• Традиційний алгоритм навряд чи генерує оптимальні результати, тоді як генетичні алгоритми не гарантують отримання оптимальних глобальних результатів, але також є велика ймовірність отримати оптимальний результат для проблеми, оскільки він використовує генетичні оператори, такі як Crossover і Mutation.
• Традиційні алгоритми є детермінованими за своєю природою, тоді як генетичні алгоритми є ймовірнісними та стохастичними за своєю природою.