Биоинспирированные алгоритмы

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере, установленном в Институте перспективных исследований Принстонского университета.^[2][3] Его работа, опубликованная в том же году, привлекла широкое внимание общественности. С 1957 года,^[4] австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Положенное начало позволило компьютерной симуляции эволюционных процессов и методам, описанным в книгах Фразера и Барнелла(1970)^[5] и Кросби (1973)^[6], с 1960-х годов стать более распространенным видом деятельности среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Вдобавок к этому, Ганс-Иоахим Бремерманн в 1960-х опубликовал серию работ, которые также принимали подход использования популяции решений, подвергаемой рекомбинации, мутации и отбору, в проблемах оптимизации. Исследования Бремерманна также включали элементы современных генетических алгоритмов.^[7] Среди прочих пионеров следует отметить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Множество ранних работ были переизданы Давидом Б. Фогелем (1998).^[8]

Хотя Баричелли в своей работе 1963 года симулировал способности машины играть в простую игру,^[9] искусственная эволюция стала общепризнанным методом оптимизации после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов двадцатого века — группа Рехенсберга смогла решить сложные инженерные проблемы согласно стратегиям эволюции.^{[10][11][12][13]} Другим подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование, первоначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали особенно популярны благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975)^[14]. Его исследование основывалось на экспериментах с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предсказывания качества следующего поколения, известный как Теорема схем. Исследования в области генетических алгоритмов оставались в основном теоретическими до середины 80-х годов, когда была, наконец, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом исследовательского интереса существенно выросла и вычислительная мощь настольных компьютеров, это позволило использовать новую вычислительную технику на практике. В конце 80-х, компания General Electric начала продажу первого в мире продукта, работавшего с использованием генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал^[15] об Evolver в 1990 году.

1. Одним из биоинспирированных подходов является метод роевого интеллекта включающий в себя муравьиные алгоритмы, пчелиные алгоритмы, метод роя частиц, алгоритм капель воды и др. Роевой интеллект описывает коллективное поведение децентрализованной самоорганизующейся системы, которая состоит из множества агентов, локально взаимодействующих между собой и с окружающей средой. Агенты обычно довольно просты, но, локально взаимодействуя, вместе создают, так называемый, роевой интеллект.
2. Пчелиный алгоритм − это оптимизационный алгоритм, в основе которого лежит поведение пчёл в живой природе. Применительно к задаче оптимизации в пчелином алгоритме каждое решение представляется в виде пчелы, которая знает (хранит) расположение (координаты или параметры многомерной функции) какого-то участка.
3. Алгоритм пастушьей собаки^[16] — предлагает решение проблемы выпаса. С помощью набора простых эвристик пастух может пасти автономных, взаимодействующих между собой агентов в направлении к пункту назначения. Эвристика пастуха основана на адаптивном переключении между сбором агентов, когда они слишком рассредоточены, и их вождением, как только они агрегируют. Эти правила действуют для уменьшения вероятности того, что группа распадается, и позволяют пастуху вести группу в направлении целевого местоположения. Движение пастуха из стороны в сторону также является следствием этих правил, в отличие от других моделей, где такое поведение было жестко закодировано в правилах движения управляющего объекта для повышения эффективности работы^[17][18][19].