Еволюційне програмування
Еволюційне програмування — різновид еволюційних алгоритмів, що характеризується незмінними структурами даних агентів, які виявляють «розумну поведінку» завдяки прогнозування наступних станів.
Було винайдено доктором Лоуренсом Дж. Фогелем в Національному Науковому Фонді США в 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 с.