Створення та оптимізація засобів штучного інтелекту на основі генетичних алгоритмів



Сторінка5/10
Дата конвертації12.04.2017
Розмір0.65 Mb.
1   2   3   4   5   6   7   8   9   10

2.4 Формування нової популяції

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

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

Вибір «найкращої» хромосоми. Якщо умова зупинки алгоритму виконана, то слід вивести результат роботи, тобто представити шуканий розв'язок задачі. Кращим рішенням вважається хромосома з найбільшим значенням функції пристосованості.

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

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

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

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

Наприклад, якщо як батьків випадковим чином вибираються дві хромосоми з батьківського популяції чисельністю N, то pс = 2/N. Аналогічно, якщо з батьківського популяції чисельністю N вибирається 2z хромосом (z <= N / 2), які утворюють z пар батьків, то pс = 2z/N.

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

Операція мутації змінює значення генів у хромосомах із заданою вірогідністю рm способом, представленим при описі відповідного оператора. Це призводить до інвертування значень відібраних генів з 0 на 1 і навпаки. Значення рm, як правило, дуже мале, тому мутації піддається лише невелика кількість генів. Схрещування — це ключовий оператор генетичних алгоритмів, що визначає їх можливості та ефективність. Мутація грає більш обмежену роль. Вона вводить в популяцію деяку різноманітність і попереджає втрати, які могли б відбутися внаслідок виключення якого-небудь значимого гена в результаті схрещування [8].

Основний (класичний) генетичний алгоритм відомий у літературі в якості інструменту, в якому виділяються три види операцій: репродукція, схрещування і мутація. Терміни селекції та репродукція в даному контексті використовуються як синоніми. При цьому репродукція в даному випадку пов'язується радше з створенням копій хромосом батьківського пулу, тоді як більш поширений зміст цього поняття означає процес формування нових особин, що походять від конкретних батьків. Якщо ми приймаємо таке тлумачення, то оператори схрещування і мутації можуть вважатися операторами репродукції, а селекція — відбором особин (хромосом) для репродукції [7].


3. ЗАСТОСУВАННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ




3.1 Постановка задачі

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

Штучний інтелект — розділ комп'ютерної лінгвістики та інформатики, що займається формалізацією проблем та завдань, які нагадують завдання, виконувані людиною. При цьому, у більшості випадків алгоритм розв'язання завдання невідомий наперед. Точного визначення цієї науки немає, оскільки у філософії не розв'язане питання про природу і статус людського інтелекту. Немає і точного критерію досягнення комп'ютером «розумності», хоча перед штучним інтелектом було запропоновано низку гіпотез, наприклад, тест Тюринга або гіпотеза Ньюела-Саймона. Нині існує багато підходів як до розуміння задач штучного інтелекту, так і до створення інтелектуальних систем.

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

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


3.2 Огляд систем – аналогів.

Реалізація ШІ сильно впливає на геймплей, системні вимоги і бюджет гри, і розробники балансують між цими вимогами, намагаючись зробити цікавий і невимогливий до ресурсів ШІ малою ціною. Тому підхід до ігрового ШІ серйозно відрізняється від підходу до традиційного ШІ — широко застосовуються різного роду спрощення, обмани й емуляції. Наприклад: з одного боку, в шутерах від першої особи безпомилковий рух і миттєве прицілювання, властиве ботам, не залишає жодного шансу людині, так що ці здатності штучно знижуються. З іншого боку — боти повинні робити засідки, діяти командою й т.д., для цього застосовуються «костилі» у вигляді контрольних точок, розставлених на рівні.

В іграх, у яких важливий творчий потенціал гравця, ШІ не може боротися на рівні з людиною. Щоб зрівняти шанси, застосовують читерський, або оманний ШІ.

Оманний ШІ компенсує відсутність стратегічного мислення якими-небудь іншими перевагами над гравцем. Наприклад: більша кількість життів, швидше пересування або ігнорування туману війни. Поняття «читерський» вживається тільки стосовно привілеїв штучного характеру: так, нелюдська реакція, стрімкість і точність, властива комп'ютерам, читерством не вважається.

Звичайно, комп'ютер завжди має перевагу над людиною — людині доводиться покладатися на зір і слух з їхніми обмеженнями, у той час як комп'ютер має прямий (хоча й обмежений) доступ до абстракцій рушія. Однак ніхто серйозно не вважає, що «правдивий» ігровий ШІ повинен мати й використовувати алгоритми візуальної обробки, тим більше, що відтворення людського зору в цей час є недосяжною метою для систем машинного зору.

Нижче наведений один загальний приклад читерського ігрового ШІ, що є присутнім у багатьох гоночних іграх. Якщо ШІ-Гравець досить сильно відстає від основної маси гонщиків, він раптово отримує величезне збільшення швидкості або інші параметри, що дозволяють йому нагнати інших гонщиків і знову стати конкурентоспроможним суперником. Цей метод відомий як «метод гумової нитки», тому що він дозволяє ШІ-Персонажеві негайно повернутися назад у конкурентоспроможну позицію. Подібний метод також застосовується в таких спортивних іграх, як серія «Madden NFL». У просунутіших іграх конкурентоспроможність неігрових персонажів або ботів може досягатися завдяки динамічному ігровому балансуванню, яке можна вважати справедливішим, хоча все ще технічним обманом, тому що ШІ-Гравці все ще отримують переваги, навіть при тому, що вони дотримують правил віртуального світу.

Культова аркада Pac-Man (1980) застосовує шаблони поведінки до ігрового лабіринту, а також додає відмінності для кожного ворога. Деякі боти як орієнтир використовують поточне місце знаходження гравця, чи точку недалеко від нього. Інші враховують напрям руху і намагаються вирахувати приблизне місцезнаходження через певний проміжок часу.

GoldenEye 007 (1997) є одним з перших шутерів від першої особи, у якому ігрові боти реагують на рухи й дії гравця, а також використовують укриття й виконують перекати, щоб уникнути влучення в них. Боти також здатні кидати ручні гранати у відповідний час. Творці цієї гри поліпшили ігровий ШІ в грі Perfect Dark. Важливою вадою ігрового ШІ в обох іграх є те, що боти завжди знають точне місцезнаходження гравця, навіть якщо жоден з них не бачив його.

Шутер від першої особи Far Cry (2004) має дуже просунутий ігровий ШІ для свого часу, хоча й не без помилок. Вороги реагують на стиль гри гравця й намагаються по можливості оточити його. У боротьбі із гравцем боти використовують реальні воєнні тактики. Вороги не мають «читерского» ШІ в тому розумінні, що вони не знають точне місце розташування гравця, а лише діють відповідно до позиції, яку вони запам'ятовували.

Мережний кооперативний шутер від першої особи Left 4 Dead (2008) використовує нову систему ігрового ШІ з назвою «Режисер» (англ. The Director). «Режисер» використовується для процедурного генерування різного ігрового досвіду (experience) для гравців при кожному запуску гри. Розроблювачі гри називають спосіб, відповідно до якого працює «Режисер», «процедурним наративом». Замість строго встановлених і статичних рівнів складності «Режисер» аналізує дії й «ступінь виживання» гравців і відповідно до цього динамічно додає наступні події, роблячи гру цікавою, але також і прохідною. Проте, поряд з «Режисером» у грі присутні й рівні складності, які впливають на стійкість і ступінь ушкоджень ігрових персонажів.






Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   10


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал