В області штучного інтелекту еволюційний алгоритм (ЕА) є підмножиною з обчислення загальної кількості населення на основі метаэвристической оптимізації. ЕА використовує механізми, натхненні біологічним розвитком, такі як розмноження, мутація, рекомбінація і відбір. Кандидатське рішення в задачі еволюційних алгоритмів оптимізації відіграє роль індивідів у популяції. А також функція придатності визначає якість відповідей.
Еволюційні алгоритми часто добре апроксимують вирішення всіх типів проблем. Тому що в ідеалі вони не роблять будь-яких припущень про базову фітнес-ландшафті. Методи, що застосовуються для еволюційного моделювання і генетичних алгоритмів, зазвичай обмежуються дослідженнями мікроеволюційних процесів і моделями планування, заснованими на клітинних етапах. У більшості реальних додатків радників складність обчислень є фактором заборонним.
Фактично ця проблема пов’язана з оцінкою фітнес-функції. Фітнес-апроксимація є одним з рішень для подолання цієї труднощі. Проте, здавалося б, простий ЕА може вирішити часто складні проблеми. Отже, не може бути прямого зв’язку між складністю послідовності і проблеми. Більш докладно можна прочитати в книгах «Еволюційні алгоритми».
Реалізація
Крок перший – створення початкового населення з індивідуумів у випадковому порядку.
Крок другий – оцінка придатності кожного індивідуума в цій групі (обмеження по часу, достатня підготовленість і т. д.).
Крок третій – повторення наступних пунктів регенерації до завершення:
Типи
Генетичний алгоритм — це еволюційна послідовність, самий популярний тип радника. Шукається рішення проблеми у вигляді рядків чисел (традиційно двійкових, хоча найкращими виставами зазвичай є ті, які відображають більше в розв’язуваної задачі) шляхом застосування таких операторів, як рекомбінація і мутація (іноді одного, у окремих обох випадках). Цей тип радника часто використовується в задачах оптимізації. Інша назва для цього — fetura (від латинського «народження»):
Порівняння з біологічними процесами
Можливе обмеження багатьох еволюційних алгоритмів — відсутність чіткого відмінності між генотипом і фенотипом. У природі запліднена яйцеклітина піддається складного процесу, відомого як ембріогенез, щоб стати зрілою. Вважається, що це непряме кодування робить генетичний пошук більш надійним (тобто зменшує ймовірність фатальних мутацій), а також може поліпшити здатність організму розвиватися. Такі непрямі (інакше кажучи, породжують або розвиваючі) кодування також дозволяють еволюції експлуатувати регулярність в навколишньому середовищі.
Останні роботи в області штучного ембріогенезу або системи розвитку прагнуть вирішити ці проблеми. При програмуванні експресії генів успішно досліджується область генотип-фенотипу, де перший складається з лінійних мультигенных хромосом фіксованої довжини, а другий з безлічі дерев експресії або комп’ютерних програм різних розмірів і форм.
Пов’язані техніки
Алгоритми включають в себе:
Інші популяційні методи метаэвристические
Меметический
Гібридний метод, заснований на ідеї Річарда Докінза про меме. Він зазвичай приймає форму алгоритму на основі сукупності в поєднанні з індивідуальними процедурами навчання, здатними виконувати локальні уточнення. Підкреслює використання проблемно-специфічних знань і намагається організувати точений і глобальний пошук синергетичним способом.
Еволюційні алгоритми являють собою евристичний підхід до проблем, які не можуть бути легко вирішені за полиномиальное час, таких як класично NP-складні завдання і все інше, що займе занадто багато для вичерпної обробки. При самостійному використанні вони зазвичай застосовуються для комбінаторних задач. Проте генетичні алгоритми часто вживаються в тандемі з іншими методами, діючи як швидкий спосіб знаходження кілька оптимальних початкових місць для роботи.
Передумова еволюційного алгоритму (відомого як радник) досить проста, враховуючи, що ви знайомі з процесом природного відбору. Вона містить чотири основних етапи:
- ініціалізація;
- вибір;
- генетичні оператори;
- завершення.
Кожен з цих кроків приблизно відповідає певному аспекту природного відбору і надає прості способи модульної реалізації цієї категорії алгоритмів. Простіше кажучи, в ЕА більш пристосовані члени виживуть і розмножуватися, в той час як непридатні учасники помруть і не внесуть свій внесок у генофонд наступних поколінь.
Ініціалізація
Щоб почати алгоритм, необхідно спочатку створити сукупність рішень. Населення буде містити довільну кількість можливих постанов проблеми, часто званих учасниками. Вони часто створюються випадковим чином (в рамках обмежень задачі) або, якщо відомі деякі попередні знання, орієнтовно зосереджені навколо того, який вважається ідеальним. Важливо, щоб популяція охоплювала широкий спектр рішень, тому що вона, по суті, являє собою генофонд. Отже, якщо необхідно досліджувати безліч різних можливостей у рамках алгоритму, потрібно прагнути мати багато різних генів.
Вибір
Після того як популяція створена, її члени повинні оцінюватися у відповідності з функцією придатності. Фітнес-функція приймає характеристики члена і видає числове уявлення про те, наскільки він життєздатний. Їх створення часто може бути дуже важким. Важливо знайти хорошу систему, яка точно представляє дані. Це дуже специфічно для проблеми. Тепер необхідно розраховувати придатність всіх учасників і відбирати частину кращих членів.
Кілька цільових функцій
Радники також можуть бути розширені для використання даних систем. Це дещо ускладнює процес, тому що, замість того щоб ідентифікувати одну оптимальну точку, виходить набір при їх використанні. Безліч рішень називається кордоном Парето і містить елементи, які однаково придатні в тому сенсі, що жодна з них не домінує над будь-яким іншим.
Генетичні оператори
Цей крок включає в себе два підетапи: кросовер і мутація. Після вибору кращих членів (зазвичай 2 верхніх, але це число може змінюватись), вони тепер використовуються для створення наступного покоління в алгоритмі. Застосовуючи характеристики вибраних батьків, створюються нові діти, які являють собою суміш якостей. Це часто може бути ускладнене у залежності від типу даних, але зазвичай в комбінаторних задачах цілком реально змішувати і виводити дійсні комбінації.
Тепер необхідно ввести новий генетичний матеріал в покоління. Якщо не зробити цього важливого кроку, то вчений дуже швидко застрягне у локальних екстремумах і не отримає оптимальних результатів. Цей крок є мутацією, і робиться вона досить просто, змінюючи невелику частину дітей таким чином, щоб вони переважно не відображали підмножин генів батьків. Мутація зазвичай відбувається ймовірносно, оскільки можливість того, що дитина отримає, а також її серйозність, визначаються розподілом.
Припинення
Зрештою алгоритм повинен закінчитися. Зазвичай це відбувається у двох випадках: або він досяг деякого максимального часу виконання, або порогу продуктивності. На цьому етапі остаточне рішення вибирається і повертається.
Приклад еволюційних алгоритмів
Тепер, щоб проілюструвати результат цього процесу, необхідно переглянути радника в дії. Для цього можна згадати, як кілька поколінь динозаврів вчилися ходити (поступово освоюючи сушу), оптимізуючи структуру свого тіла і прикладаючи м’язові сили. Незважаючи на те що рептилії раннього покоління не могли ходити, радник зміг згодом еволюціонувати їх допомогою мутації і кросовера в форму, здатну ходити.
Дані алгоритми стають все більш актуальними в сучасному світі, оскільки рішення на їх основі все ширше використовуються в таких галузях, як цифровий маркетинг, фінанси та здоров’я.
Де ЕА використовуються?
У більш широкому сенсі еволюційні алгоритми застосовуються в самих різних додатках, таких як обробка зображень, маршрутизація транспортних засобів, оптимізація мобільного зв’язку, розробка програмного забезпечення і навіть навчання штучних нейронних мереж. Ці інструменти лежать в основі багатьох додатків і веб-сайтів, які люди використовують щодня, включаючи Google Maps і навіть такі ігри, як The Sims. Крім того, медична сфера використовує ЕА для допомоги в прийнятті клінічних рішень щодо лікування раку. Насправді еволюційні алгоритми настільки надійні, що їх можна використовувати для вирішення практично будь-яких задач оптимізації.
Закон Мура
Зростаюча поширеність ЕВ зумовлена двома основними факторами: доступної обчислювальної потужності і накопиченням великих наборів даних. Перший може бути описаний Законом Мура, який, по суті, свідчить, що обсяг обчислювальної потужності комп’ютера подвоюється приблизно кожні два роки. Цей прогноз тримається протягом десятиліть. Другий фактор пов’язаний із зростаючою залежністю від технологій, яка дозволяє закладам збирати неймовірно велику кількість даних, що дозволяє їм аналізувати тенденції і оптимізувати продукти.
Як еволюційні алгоритми можуть допомогти маркетологам?
Кон’юнктура ринку швидко змінюється і дуже конкурентоспроможна. Це змусило менеджерів з маркетингу змагатися за рахунок кращого прийняття рішень. Збільшення доступної обчислювальної потужності призвело працівників до використання ЕА для постановлення завдань.
Оптимізація конверсії
Одна з головних цілей — підвищити коефіцієнт відвідувачів на сайті. Ця проблема зводиться до оптимізації кількості користувачів, які роблять те, що маркетолог хоче. Наприклад, якщо компанія продає ноутбуки, в ідеалі необхідно збільшити кількість відвідувачів сайту, які в кінцевому підсумку купують продукт. В цьому суть оптимізації коефіцієнта конверсії.
Одним з дивно важливих аспектів є вибір користувальницького інтерфейсу. Якщо веб-дизайн не дуже зручний для користувачів, є ті, які в кінцевому підсумку не купують продукт з тієї чи іншої причини. Тоді мета полягає в тому, щоб зменшити кількість користувачів, які в кінцевому підсумку не конвертуються, що збільшує загальну прибуток.
