Огляд генетичного алгоритму

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

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

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

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

Фази генетичного алгоритму

Нижче наведені різні фази генетичного алгоритму:

1. Ініціалізація населення (кодування)

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

2. Фітнес-функція

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

3. Вибір

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

4. Відтворення

Покоління потомства відбувається двома способами:

  • Кросовер
  • Мутація

а) Кросовер

Кросовер - найважливіший етап генетичного алгоритму. Під час кросовера вибирається випадкова точка під час спарювання пари батьків для створення потомства.

Існує 3 основних типи кросоверів.

  • Кроссовер з однією точкою: Точка на хромосомах обох батьків вибирається випадковим чином і позначається «точкою перехрещення». Біти праворуч від цієї точки обмінюються між двома вихідними хромосомами.
  • Двухточковий кроссовер: дві точки кросовер відбираються випадковим чином із батьківських хромосом. Шматочки між двома точками поміняються між материнськими організмами.
  • Уніфікований кроссовер: У єдиному кросовер звичайно кожен біт вибирається з будь-якого з батьків з однаковою ймовірністю.

Нове потомство додається до населення.

б) Мутація

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

5. Конвергенція (коли зупинити)

Мало дотриманих правил, які вказують, коли зупинитись, наступні:

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

Застосування генетичного алгоритму

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

1. Маршрут подорожі та відправлення

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

2. Робототехніка

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

  • Вибір важливих особливостей у даному наборі даних.
  • У традиційному методі важливі функції в наборі даних вибираються за допомогою наступного методу. тобто ви дивитесь на важливість цієї моделі, тоді встановлюєте порогове значення для ознак, і якщо функція має значення важливості більше, ніж поріг, вона вважається.
  • Але тут ми використовуємо метод, який називається проблемою рюкзака.
  • Ми знову почнемо з популяції хромосоми, де кожна хромосома буде двійковою струною. 1 позначатиме «включення» ознаки в модель, а 0 позначатиме «виключення» ознаки в моделі.
  • Функція фітнесу тут буде нашою метрикою точності змагань. Чим точніше наш набір хромосом у прогнозуванні значення, тим більше він буде відповідати.
  • Існує багато інших застосувань генетичних алгоритмів, таких як аналіз ДНК, програми планування, інженерний дизайн.

Висновок

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

Рекомендовані статті

Це посібник щодо того, що таке генетичний алгоритм? Тут ми обговорюємо вступ, етапи та застосування генетичного алгоритму. Ви також можете ознайомитися з іншими запропонованими нами статтями -

  1. Алгоритми маршрутизації
  2. Типи алгоритмів
  3. Алгоритми нейронної мережі
  4. Алгоритми майнінгу даних
  5. посібник із прикладів алгоритму C ++

Категорія:

Великі дані