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



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

ВСТУП

Актуальність теми. Поява генетичних алгоритмів дає змогу розв’язувати задачі, непосильні ні для аналітичної математики, ні для числових методів. Генетичні алгоритми є відносно молодими методами. За два останні десятиліття реалізовано багато модифікацій генетичних алгоритмів. Їх використовують для розв’язування широкого класу задач, а саме знаходження глобального екстремуму багатопараметричної функції, апроксимації функції, налаштування нейронної мережі, розроблення ігрових стратегій тощо. Генетичний алгоритм є універсальним, оскільки складається зі строго визначеного набору процедур, які спрямовують вектор розв’язків у область глобального екстремуму. Однак, незважаючи на універсальність алгоритму, математичний базис кожної із процедур може бути модифікований [1].

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

Проблемою даної теми є відсутність простої і якісної реалізації штучного ігрового інтелекту. Багато сучасних розробників застосовують «читерський» ШІ в своїх іграх. Замість продвинутого алгоритму поведінки противника, йому надаються кращі умови ніж гравцеві. Це значно уодноманітнює ігровий процес і додаток швидко втрачає свою актуальність. Створення та оптимізація якісного ігрового інтелекту не тільки просуне ігрову індустрію, а також допоможе у створенні справжнього штучного інтелекту [4].

Серед багатьох науковців існує думка, згідно з якою задача оптимізації належить до класу задач лінійного програмування і розв'язується тільки симплекс-методом, який, однак, не буде ефективним з точки зору обчислювальної складності. Тому актуальним залишається пошук ефективних поліноміальних алгоритмів. Серед них виділяються еволюційні (генетичні) алгоритми, які широко застосовуються для розв’язання різних класів оптимізаційних задач. Генетичні алгоритми є новим напрямком у алгоритміці. Вони здатні не тільки вирішувати і скорочувати перебір у складних завданнях, але й легко адаптуватися до зміни проблеми [1].

Мета дослідження – підвищити ефективність функціонування штучного інтелекту за допомогою генетичних алгоритмів.

Об’єкт дослідження – процес обробки інформації з використанням алгоритмів еволюційного типу.

Предмет дослідження - методи обробки інформації в ігровому додатку.

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

1. ГЕНЕТИЧНІ АЛГОРИТМИ І ТРАДИЦІЙНІ МЕТОДИ ОПТИМІЗАЦІЇ




1.1 Виникнення генетичних алгоритмів

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

Теорія еволюції вплинула на зміну світогляду людей з самої своєї появи. Теорія, яку Чарльз Дарвін представив у роботі "Походження видів", в 1859 році, стала початком цієї зміни. Багато наукових областей в даний час можуть вільно розвиватись в різних напрямках, що багато в чому зобов'язано революції, викликаній теорією еволюції і розвитку. Але Дарвін, подібно багатьом своїм сучасникам, хто припускав, що в основі розвитку лежить природний відбір, не міг не помилятися [3]. Наприклад, він не зміг показати механізм успадкування, при якому підтримується мінливість. Його гіпотеза про Пангенезис виявилася неправильною. Це було за 50 років до того, як теорія спадковості почала поширюватися по світу, і за тридцять років до того, як "еволюційний синтез" зміцнив зв'язок між теорією еволюції і відносно молодий наукою генетикою. Однак Дарвін виявив головний механізм розвитку: відбір у поєднанні з мінливістю або "спуск з модифікацією". У багатьох випадках, специфічні особливості розвитку через мінливість і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, які спостерігаються в природі [2].

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

Історія еволюційних обчислень почалася з розробки ряду різних незалежних моделей. Основними з них були генетичні алгоритми і класифікаційні системи Голланда (Holland), опубліковані на початку 60-х років і одержали загальне визнання після виходу в світ книги, що стала класикою в цій області, - "Адаптація в природних і штучних системах" ("Adaptation in Natural and Artifical Systems ", 1975). У 70-х роках у рамках теорії випадкового пошуку Растрігіним Л.А. був запропонований ряд алгоритмів, що використовують ідеї біонічної поведінки особ. Розвиток цих ідей знайшов відображення у циклі робіт Букатовой І.Л. по еволюційному моделюванні. Розвиваючи ідеї Цетлін М.Л. про доцільність і оптимальну поведінку стохастичних автоматів, Неймарк Ю.І. запропонував здійснювати пошук глобального екстремуму на основі колективу незалежних автоматів, моделюючих процеси розвитку та елімінації особин. Великий внесок у розвиток еволюційного програмування внесли Фогел (Fogel) і Уолш (Walsh). Незважаючи на різницю у підходах, кожна з цих "шкіл" взяла за основу низку принципів, що існують у природі, і спростила їх до такої міри, щоб їх можна було реалізувати на комп'ютері [7].

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

Звичайно, еволюція біологічних систем не єдине "джерело натхнення" творців нових методів, що моделюють природні процеси. Нейронні мережі (neural networks), наприклад, засновані на моделюванні поведінки нейронів у мозку. Вони можуть використовуватися для ряду задач класифікації, наприклад, задачі розпізнавання образів, машинного навчання, обробки зображень тощо. Область їх застосування частково перекривається зі сферою застосування ГА. Модельований відпал (simulated annealing) - інша методика пошуку, яка заснована скоріше на фізичних, а не біологічних процесах [2,3].

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

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

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

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




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


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

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


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