Еволюційне програмування різновид еволюційних алгоритмів що характеризується незмінними структурами даних агентів які ви

Еволюційне програмування — різновид еволюційних алгоритмів, що характеризується незмінними структурами даних агентів, які виявляють «розумну поведінку» завдяки прогнозування наступних станів.

Було винайдено доктором Лоуренсом Дж. Фогелем в в 1960 році. Йому було доручено представити доповідь Конгресу США щодо суми інвестицій у фундаментальні дослідження. Одним з питань розгляду був штучний інтелект.

Історія

У той час штучний інтелект був обмежений двома основними напрямками досліджень: моделюванням людського мозку (нейронні мережі) і моделюванням вирішення проблем поведінки людини (евристичне програмування). Альтернативний варіант, передбачений доктором Фогелем, повинен був відмовитися від моделювання кінцевого продукту еволюції, і, швидше, моделювати , використовуючи себе як транспортний засіб для отримання розумної поведінки (Фогель, 1962, 1963). Фогель розглядає інтелект як складову частину здатності робити прогнози навколишнього середовища в поєднанні з перекладом кожного прогнозу у відповідну відповідь у світлі заданої мети (наприклад, для максимізації функції виграшу). Таким чином, на його думку прогнозування є необхідною умовою для розумної поведінки. Моделювання еволюції як оптимізації процесу стало наслідком досвіду доктора Фогеля в нових галузях «біотехнології», кібернетики і техніки. Доктор Фогель провів серію експериментів, в яких автомати представляли окремі організми. Автомати — це графові моделі, які використовуються для опису поведінки або програмного забезпечення та апаратних засобів, тому він назвав свій підхід еволюційним програмуванням.

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

У 1964 році Фогель отримав докторський ступінь у галузі електротехніки в університеті Каліфорнії в Лос-Анджелесі. Його дисертація «Про походження Інтелекту», була присвячена штучному інтелекту шляхом імітації еволюції. Ранні роботи також привели доктора Фогеля, д-ра Аль Оуенса, і д-ра Майкла Уолша до створення рішень для Science, Inc в 1965 році. Це була перша компанія у світі, що займалася виключно комерціалізацією еволюційних алгоритмів.

У 1970 р., завдяки в першу чергу керівництву професора Дональда Дерхольта в державному університеті Нью-Мехіко, було опубліковано більш широке дослідження обчислень для еволюційного програмування, ніж для будь-яких інших форм модельованої еволюції. Більшість цих досліджень використовували еволюційні програми для розпізнавання образів (Root, 1970; Корнетт, 1972; Lyle, 1972; Holmes, 1973; Trellue, 1973; Монтес, 1974; Атмар, 1976; Вінсент, 1976; Вільямс, 1977; Dearholt, 1976) . Як приклад для розпізнавання використовувалися головним чином . До експериментів включили параметри . Робота Атмара (1976) — один з ранніх прикладів імітації еволюції в обстановці штучного життя. Атмар (1976), можливо, перший запропонував і описав, як еволюційне програмування може бути розраховане на те, що зараз відомо як . Ангеліні і Поллак (1993) описали, як еволюційне програмування може бути використано для розвитку комп'ютерних програм.

Методи

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

Пошук залежності цільових змінних від інших проводиться у формі функцій якогось певного виду. Наприклад, в одному з найвдаліших алгоритмів цього типу — методі групового урахування аргументів (МГУА) залежність шукають у формі поліномів. Причому складні поліноми заміняються декількома простими, враховують лише деякі ознаки (групи аргументів). Зазвичай використовуються попарні об'єднання ознак. Цей метод не має великих переваг в порівнянні з нейронними мережами з готовим набором стандартних нелінійних функцій, але, отримані формули залежності, в принципі, піддаються аналізу і інтерпретації (хоча на практиці це все-таки складно).

Сучасне еволюційне програмування

Вивчення еволюційного програмування було продовжено в 1980-х у використанні довільних представлень даних і застосовувалося до узагальненої . Еволюційне програмування, засноване на і доборі, було застосовано до таких структур, як (Фогель і Атмар, 1990; Фогель, 1990; Девіс, 1994), перестановки (Фогель, 1998), матриці (Фогель, 1993), вектори змінної довжини (Фогель, 1990), (Фогель, 1989) і так далі. Девід Фогель (1988) представив форму відбору еволюційного програмування за допомогою . Фогель (1991, 1992) також висунув ідею зміни параметрів, в яких міститься інформація щодо шляхів вирішення проблеми, а також інформація про те, як створити потомство.

Галузі застосування

Еволюційне програмування було застосоване до різних інженерних завдань, включаючи маршрутизацію трафіку і планування (Макдоннелл, 1997), фармацевтичні дизайни (Дункан і Олсон, 1996; Фогель, 1996), епідеміологію (Фогель, 1986), виявлення раку (Фогель 1997, 1998), військове планування (Фогель, 1993), системи управління (Чон, 1997), системи ідентифікації (Фогель, 1990), обробки сигналів (Порто, 1990), енергетику (Лай Ма, 1996), навчання в іграх (Фогель і Бургін, 1969) і т. д.

Література

Рутковский Л. Методы и технологии искусственного интелекта. — М.: Горячая линия-Телеком, 2010. — 520 с.
Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы (Sieci neuronowe, algorytmy genetyczne i systemy rozmyte). — М.: Горячая линия-Телеком, 2008. — 452 с.