Эволюционные алгоритмы

Поделись знанием:
(перенаправлено с «Эволюционные вычисления»)
Перейти к: навигация, поиск

Эволюционные алгоритмы — направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует процессы естественного отбора.





Виды алгоритмов

Все они моделируют базовые положения в теории биологической эволюции — процессы отбора, мутации и воспроизводства. Поведение агентов определяется окружающей средой. Множество агентов принято называть популяцией. Такая популяция эволюционирует в соответствии с правилами отбора в соответствии с целевой функцией, задаваемой окружающей средой. Таким образом, каждому агенту (индивидууму) популяции назначается значение его пригодности в окружающей среде. Размножаются только наиболее пригодные виды. Рекомбинация и мутация позволяют изменяться агентам и приспособляться к среде. Такие алгоритмы относятся к адаптивным поисковым механизмам.

Эволюционные алгоритмы успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на математическом языке.

Отрасли использования

Эволюционные алгоритмы используются при комбинаторной оптимизации, в частности при решении классических NP-полных проблем, таких как задача коммивояжера, задача упаковки ранца, разбитие чисел, максимально независимое множество и зарисовка графов.[1]

Возможность использования эволюционных алгоритмов в музыке активно исследуется в Австрии, в первую очередь при попытках моделирования игры на музыкальных инструментах известными людьми разных эпох.[2]

Напишите отзыв о статье "Эволюционные алгоритмы"

Примечания

  1. Olariu Stephan, Zomaya Albert Y. Handbook of Bioinspired Algorithms and Applications (Chapman Hall/Crc Computer Information Science). — Chapman Hall/CRC. — ISBN 1-58488-475-4.
  2. [www.insota.com/fileadmin/publications/Evolutionary-Search-for-Musical-Parallelism.pdf Madsen, S. T. and Widmer, G.: Evolutionary Search for Musical Parallelism, Applications of Evolutionary Computing, proceedings of the EvoWorkshops 2005, LNCS 3449 p. 488—497, Lausanne, Switzerland, 30 March — 1 April 2005. Springer Verlag.]

Литература

  • Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003. — С. 432. — ISBN 5-9221-0337-7.
  • Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. — М.: Физматлит, 2006. — С. 272. — ISBN 5-9221-0749-6.
  • Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд.. — М.: Физматлит, 2006. — С. 320. — ISBN 5-9221-0510-8.
  • Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. — М.: Физматлит, 2009. — С. 384. — ISBN 978-5-9221-1101-0.
  • Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд.. — М.: Горячая линия-Телеком, 2008. — С. 452. — ISBN 5-93517-103-1.
  • Рутковский Л. Методы и технологии искусственного интеллекта. — М.: Горячая линия-Телеком, 2010. — С. 520. — ISBN 5-9912-0105-6.
  • Волович И. В., Хохлова М. Н. O теории моделирования и гиперграфе классов // Труды Математического института им. В.А.Стеклова. — 2004. — Т. 245. — С. 281-287.

Ссылки

  • [www.csit.narod.ru/subject/mag_SShI/mono.pdf Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.]
  • [algolist.manual.ru/ai/ga/ga1.php Популярно о генетических алгоритмах]
  • [artint.com.ua/index_a.htm Основы теории и применение эволюционных алгоритмов в практических приложениях]

Отрывок, характеризующий Эволюционные алгоритмы

С раннего утра начали двигаться щегольски вычищенные и убранные войска, выстраиваясь на поле перед крепостью. То двигались тысячи ног и штыков с развевавшимися знаменами и по команде офицеров останавливались, заворачивались и строились в интервалах, обходя другие такие же массы пехоты в других мундирах; то мерным топотом и бряцанием звучала нарядная кавалерия в синих, красных, зеленых шитых мундирах с расшитыми музыкантами впереди, на вороных, рыжих, серых лошадях; то, растягиваясь с своим медным звуком подрагивающих на лафетах, вычищенных, блестящих пушек и с своим запахом пальников, ползла между пехотой и кавалерией артиллерия и расставлялась на назначенных местах. Не только генералы в полной парадной форме, с перетянутыми донельзя толстыми и тонкими талиями и красневшими, подпертыми воротниками, шеями, в шарфах и всех орденах; не только припомаженные, расфранченные офицеры, но каждый солдат, – с свежим, вымытым и выбритым лицом и до последней возможности блеска вычищенной аммуницией, каждая лошадь, выхоленная так, что, как атлас, светилась на ней шерсть и волосок к волоску лежала примоченная гривка, – все чувствовали, что совершается что то нешуточное, значительное и торжественное. Каждый генерал и солдат чувствовали свое ничтожество, сознавая себя песчинкой в этом море людей, и вместе чувствовали свое могущество, сознавая себя частью этого огромного целого.
С раннего утра начались напряженные хлопоты и усилия, и в 10 часов всё пришло в требуемый порядок. На огромном поле стали ряды. Армия вся была вытянута в три линии. Спереди кавалерия, сзади артиллерия, еще сзади пехота.
Между каждым рядом войск была как бы улица. Резко отделялись одна от другой три части этой армии: боевая Кутузовская (в которой на правом фланге в передней линии стояли павлоградцы), пришедшие из России армейские и гвардейские полки и австрийское войско. Но все стояли под одну линию, под одним начальством и в одинаковом порядке.
Как ветер по листьям пронесся взволнованный шопот: «едут! едут!» Послышались испуганные голоса, и по всем войскам пробежала волна суеты последних приготовлений.
Впереди от Ольмюца показалась подвигавшаяся группа. И в это же время, хотя день был безветренный, легкая струя ветра пробежала по армии и чуть заколебала флюгера пик и распущенные знамена, затрепавшиеся о свои древки. Казалось, сама армия этим легким движением выражала свою радость при приближении государей. Послышался один голос: «Смирно!» Потом, как петухи на заре, повторились голоса в разных концах. И всё затихло.
В мертвой тишине слышался топот только лошадей. То была свита императоров. Государи подъехали к флангу и раздались звуки трубачей первого кавалерийского полка, игравшие генерал марш. Казалось, не трубачи это играли, а сама армия, радуясь приближению государя, естественно издавала эти звуки. Из за этих звуков отчетливо послышался один молодой, ласковый голос императора Александра. Он сказал приветствие, и первый полк гаркнул: Урра! так оглушительно, продолжительно, радостно, что сами люди ужаснулись численности и силе той громады, которую они составляли.
Ростов, стоя в первых рядах Кутузовской армии, к которой к первой подъехал государь, испытывал то же чувство, какое испытывал каждый человек этой армии, – чувство самозабвения, гордого сознания могущества и страстного влечения к тому, кто был причиной этого торжества.
Он чувствовал, что от одного слова этого человека зависело то, чтобы вся громада эта (и он, связанный с ней, – ничтожная песчинка) пошла бы в огонь и в воду, на преступление, на смерть или на величайшее геройство, и потому то он не мог не трепетать и не замирать при виде этого приближающегося слова.
– Урра! Урра! Урра! – гремело со всех сторон, и один полк за другим принимал государя звуками генерал марша; потом Урра!… генерал марш и опять Урра! и Урра!! которые, всё усиливаясь и прибывая, сливались в оглушительный гул.
Пока не подъезжал еще государь, каждый полк в своей безмолвности и неподвижности казался безжизненным телом; только сравнивался с ним государь, полк оживлялся и гремел, присоединяясь к реву всей той линии, которую уже проехал государь. При страшном, оглушительном звуке этих голосов, посреди масс войска, неподвижных, как бы окаменевших в своих четвероугольниках, небрежно, но симметрично и, главное, свободно двигались сотни всадников свиты и впереди их два человека – императоры. На них то безраздельно было сосредоточено сдержанно страстное внимание всей этой массы людей.
Красивый, молодой император Александр, в конно гвардейском мундире, в треугольной шляпе, надетой с поля, своим приятным лицом и звучным, негромким голосом привлекал всю силу внимания.
Ростов стоял недалеко от трубачей и издалека своими зоркими глазами узнал государя и следил за его приближением. Когда государь приблизился на расстояние 20 ти шагов и Николай ясно, до всех подробностей, рассмотрел прекрасное, молодое и счастливое лицо императора, он испытал чувство нежности и восторга, подобного которому он еще не испытывал. Всё – всякая черта, всякое движение – казалось ему прелестно в государе.