Эволюционное программирование
Эволюционное программирование — является одной из четырёх основных парадигм эволюционного алгоритма. Это похоже на генетическое программирование, но структура оптимизируемой программы является фиксированной, а её числовые параметры могут изменяться.
История
Эволюционное программирование было изобретено доктором Лоренсом Дж. Фогелом в Национальном научном фонде в 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. — ISBN 5-9912-0105-6.
- Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечёткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд.. — М.: Горячая линия-Телеком, 2008. — С. 452. — ISBN 5-93517-103-1.
- J.W. Atmar. «Speculation on the evolution of intelligence and its possible realization in machine form». — 1976.
- F.N. Cornett. «An application of evolutionary programming to pattern recognition». — 1972.
- D.B. Fogel. «Speculation on the evolution of intelligence and its possible realization in machine form». — 1990.
- L.J. Fogel. «Biotechnology: Concepts and Applications». — 1963.
См. также
- Эволюционные алгоритмы
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Эволюционное программирование, Что такое Эволюционное программирование? Что означает Эволюционное программирование?
Evolyucionnoe programmirovanie yavlyaetsya odnoj iz chetyryoh osnovnyh paradigm evolyucionnogo algoritma Eto pohozhe na geneticheskoe programmirovanie no struktura optimiziruemoj programmy yavlyaetsya fiksirovannoj a eyo chislovye parametry mogut izmenyatsya IstoriyaEvolyucionnoe programmirovanie bylo izobreteno doktorom Lorensom Dzh Fogelom v Nacionalnom nauchnom fonde v 1960 godu Emu bylo porucheno predstavit doklad Kongressu SShA na summu investicij v fundamentalnye issledovaniya Odnim iz voprosov rassmotreniya byl iskusstvennyj intellekt V to vremya iskusstvennyj intellekt byl ogranichen dvumya osnovnymi napravleniyami issledovanij modelirovaniem chelovecheskogo mozga nejronnye seti i modelirovaniem resheniya problem povedeniya cheloveka evristicheskoe programmirovanie Alternativnyj variant predusmotrennyj Fogelom dolzhen byl otkazatsya ot modelirovaniya konechnogo produkta evolyucii i skoree modelirovat process evolyucii ispolzuya sebya v kachestve transportnogo sredstva dlya polucheniya razumnogo povedeniya Fogel 1962 1963 Fogel rassmatrivaet intellekt kak sostavnuyu chast sposobnosti delat predskazaniya okruzhayushej sredy v sochetanii s perevodom kazhdogo prognoza v podhodyashij otvet v svete zadannoj celi naprimer dlya maksimizacii funkcii vyigrysha Takim obrazom po ego mneniyu prognozirovanie yavlyaetsya neobhodimym usloviem dlya razumnogo povedeniya Modelirovanie evolyucii kak optimizacii processa yavilos sledstviem opyta Fogela v novyh oblastyah biotehnologii kibernetiki i tehniki Fogel provyol seriyu eksperimentov v kotoryh avtomaty predstavlyali otdelnye organizmy Avtomaty eto graficheskie modeli ispolzuemye dlya opisaniya povedeniya ili programmnogo obespecheniya i apparatnyh sredstv poetomu on nazval svoj podhod evolyucionnym programmirovaniem Dostoinstva evolyucionnogo programmirovaniya byli izucheny Fogelom posle ego vozvrasheniya v San Diego v iyule 1961 pri obrashenii k problemam prognozirovaniya sistemy identifikacii i kontrolya v serii issledovanij vozglavlyaemyh togda Fogelom i ego kollegami vedushimi uchyonymi v oblasti evolyucionnyh vychislenij V nekotoryh rannih opisaniyah evolyucionnogo programmirovaniya Fogel nepravilno utverzhdal chto ono bylo ogranicheno odnim roditelem i odnim potomkom V 1964 godu Fogel poluchil doktorskuyu stepen v oblasti elektrotehniki v Kalifornijskom universitete v Los Andzhelese Ego dissertaciya O proishozhdenii intellekta byla posvyashena iskusstvennomu intellektu putyom imitacii evolyucii Rannie raboty takzhe priveli Fogela Alya Ouensa i Majkla Uolsha k sozdaniyu reshenij dlya Science Inc v 1965 godu Eto byla pervaya kompaniya v mire zanimavshayasya isklyuchitelno kommercializaciej evolyucionnyh algoritmov V 1970 blagodarya v pervuyu ochered rukovodstvu professora Donalda Dirholta v Universitete shtata Nyu Meksiko bylo opublikovano bolee shirokoe issledovanie vychislenij dlya evolyucionnogo programmirovaniya chem dlya lyubyh drugih form modeliruemoj evolyucii Bolshinstvo etih issledovanij ispolzovali evolyucionnye programmy dlya raspoznavaniya obrazov Root 1970 Kornett 1972 Lyle 1972 Holmes 1973 Trellue 1973 Montes 1974 Atmar 1976 Vinsent 1976 Vilyams 1977 Dearholt 1976 V kachestve primera dlya raspoznavaniya ispolzovalis glavnym obrazom rukopisnye simvoly V eksperimenty vklyuchili parametry adaptivnyh mutacij Rabota Atmara 1976 odin iz rannih primerov imitacii evolyucii v obstanovke iskusstvennoj zhizni Atmar 1976 vozmozhno pervyj predlozhil i opisal kak evolyucionnoe programmirovanie mozhet byt rasschitano na to chto sejchas izvestno kak rasshirennaya baza oborudovaniya Angeline i Pollak 1993 opisali kak evolyucionnoe programmirovanie mozhet byt ispolzovano dlya razvitiya kompyuternyh programm Gipotezy o vide zavisimosti celevoj peremennoj ot drugih peremennyh formuliruyutsya sistemoj v vide programm na nekotorom vnutrennem yazyke programmirovaniya Esli eto universalnyj yazyk to teoreticheski na nyom mozhno vyrazit zavisimost lyubogo vida Process postroeniya takih programm stroitsya kak evolyuciya v mire programm etim metod nemnogo pohozh na geneticheskie algoritmy Esli sistema nahodit programmu kotoraya tochno vyrazhaet iskomuyu zavisimost ona nachinaet vnosit v neyo nebolshie modifikacii i otbiraet sredi postroennyh takim obrazom dochernih programm te kotorye povyshayut tochnost Sistema vyrashivaet neskolko geneticheskih linij programm konkuriruyushih mezhdu soboj v tochnosti nahozhdeniya iskomoj zavisimosti Specialnyj transliruyushij modul perevodit najdennye zavisimosti s vnutrennego yazyka sistemy na ponyatnyj polzovatelyu yazyk matematicheskie formuly tablicy i dr delaya ih legkodostupnymi Dlya togo chtoby sdelat poluchennye rezultaty bolee ponyatnymi dlya polzovatelya nematematika sushestvuet bolshoj arsenal raznoobraznyh sredstv vizualizacii vyyavlennyh zavisimostej Poisk zavisimosti celevyh peremennyh ot drugih provoditsya v forme funkcij kakogo nibud opredelyonnogo vida Naprimer v odnom iz naibolee udachnyh algoritmov etogo tipa metode gruppovogo uchyota argumentov MGUA zavisimost ishut v forme polinomov Prichyom slozhnye polinomy zamenyayutsya neskolkimi prostymi uchityvayushimi lish nekotorye priznaki gruppy argumentov Obychno ispolzuyutsya poparnye obedineniya priznakov Etot metod ne imeet bolshih preimushestv po sravneniyu s nejronnymi setyami s gotovym naborom standartnyh nelinejnyh funkcij no poluchennye formuly zavisimosti v principe poddayutsya analizu i interpretacii hotya na praktike eto vsyo taki slozhno Sovremennoe evolyucionnoe programmirovanieIzuchenie evolyucionnogo programmirovaniya bylo prodolzheno v 1980 h v ispolzovanii proizvolnyh predstavlenij dannyh i primenyalos k obobshyonnoj probleme optimizacii Evolyucionnoe programmirovanie osnovannoe na sluchajnoj izmenchivosti i otbore bylo primeneno k takim strukturam kak veshestvennye vektory Fogel i Atmar 1990 Fogel 1990 Devis 1994 perestanovki Fogel 1998 matricy Fogel 1993 vektory peremennoj dliny Fogel 1990 binarnye stroki Fogel 1989 i tak dalee Devid Fogel 1988 predstavil formu otbora evolyucionnogo programmirovaniya pri pomoshi turnira Fogel 1991 1992 takzhe vydvinul ideyu samostoyatelnoj adaptacii izmeneniya parametrov v kotoryh soderzhitsya informaciya o putyah resheniya problemy a takzhe informaciya o tom kak sozdat potomstvo Oblasti primeneniyaEvolyucionnoe programmirovanie bylo primeneno k razlichnym inzhenernym zadacham vklyuchaya marshrutizaciyu trafika i planirovanie Makdonnell 1997 farmacevticheskie dizajny Dunkan i Olson 1996 Fogel 1996 epidemiologiyu Fogel 1986 vyyavlenie raka Fogel 1997 1998 voennoe planirovanie Fogel 1993 sistemy upravleniya Chon 1997 sistemy identifikacii Fogel 1990 obrabotki signalov Porto 1990 energetiku Laj Ma 1996 obuchenie v igrah Fogel i Burgin 1969 i t d LiteraturaRutkovskij L Metody i tehnologii iskusstvennogo intellekta M Goryachaya liniya Telekom 2010 S 520 ISBN 5 9912 0105 6 Rutkovskaya D Pilinskij M Rutkovskij L Nejronnye seti geneticheskie algoritmy i nechyotkie sistemy Sieci neuronowe algorytmy genetyczne i systemy rozmyte 2 e izd M Goryachaya liniya Telekom 2008 S 452 ISBN 5 93517 103 1 J W Atmar Speculation on the evolution of intelligence and its possible realization in machine form 1976 F N Cornett An application of evolutionary programming to pattern recognition 1972 D B Fogel Speculation on the evolution of intelligence and its possible realization in machine form 1990 L J Fogel Biotechnology Concepts and Applications 1963 Sm takzheEvolyucionnye algoritmy
