Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии о
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование
Часть серии по
Искусственный интеллект
Основные цели
Подходы
  • Символический
  • Глубокое обучение
  • Байесовские сети
  • Эволюционные алгоритмы
Философия
  • Этика
  • Экзистенциальный риск
  • Тест Тьюринга
  • Китайская комната
  • Проблема управления
  • Дружелюбный ИИ
История
  • График
  • Прогресс
  • AI зима
Технологии
  • Приложения
  • Проекты
  • Языки программирования
Глоссарий
  • Глоссарий
  • v
  • т
  • е

В вычислительного интеллекта (КИ), эволюционный алгоритм ( EA ) является подмножеством из эволюционных вычислений , [1] общая численность населения на основе метаэвристического оптимизации алгоритма . EA использует механизмы, вдохновленные биологической эволюцией , такие как воспроизведение , мутации , рекомбинация и отбор . Кандидатское решение к задаче оптимизации играет роль индивидов в популяции, а также функция пригодностиопределяет качество решений (см. также функцию потерь ). Затем после повторного применения вышеуказанных операторов происходит эволюция популяции.

Эволюционные алгоритмы часто хорошо приближают решения всех типов проблем, потому что в идеале они не делают никаких предположений о лежащей в основе ландшафте пригодности . Методы эволюционных алгоритмов, применяемые для моделирования биологической эволюции, обычно ограничиваются исследованием микроэволюционных процессов и моделей планирования, основанных на клеточных процессах. В большинстве реальных приложений советников вычислительная сложность является запрещающим фактором. [2] Фактически, эта вычислительная сложность связана с оценкой функции пригодности. Аппроксимация пригодности - одно из решений, позволяющих преодолеть эту трудность. Однако, казалось бы, простой советник может решать часто сложные задачи; [ цитата необходима] поэтому может не быть прямой связи между сложностью алгоритма и сложностью задачи.

Реализация [ править ]

Ниже приводится пример универсального одноцелевого генетического алгоритма .

Шаг первый: создание первоначального населения из индивидуумов в случайном порядке. (Первое поколение)

Шаг второй: повторите следующие шаги восстановления до завершения:

  1. Оцените приспособленность каждого человека в популяции (ограничение по времени, достигнутая пригодность и т. Д.)
  2. Выберите наиболее приспособленных для воспроизводства особей . (Родители)
  3. Выращивайте новых особей с помощью операций скрещивания и мутации, чтобы дать потомство .
  4. Замените наименее приспособленных особей населения новыми особями.

Типы [ править ]

Подобные методы различаются генетическим представлением и другими деталями реализации, а также характером конкретной прикладной проблемы.

  • Генетический алгоритм - это самый популярный тип советников. Решение проблемы ищут в виде цепочек чисел (традиционно двоичных, хотя лучше всего представляют собой те, которые отражают что-то о решаемой проблеме) [2] , применяя такие операторы, как рекомбинация и мутация (иногда один, иногда оба). Этот тип советников часто используется в задачах оптимизации .
  • Генетическое программирование - здесь решения представлены в виде компьютерных программ, и их пригодность определяется их способностью решать вычислительную задачу.
  • Эволюционное программирование - похоже на генетическое программирование, но структура программы фиксирована, а ее числовые параметры могут изменяться.
  • Программирование экспрессии генов. Подобно генетическому программированию, GEP также развивает компьютерные программы, но исследует систему генотип-фенотип, в которой компьютерные программы разных размеров закодированы в линейных хромосомах фиксированной длины.
  • Стратегия эволюции - работает с векторами действительных чисел как с представлениями решений и обычно использует самоадаптивные скорости мутации.
  • Дифференциальная эволюция - основана на векторных различиях и поэтому в первую очередь подходит для задач численной оптимизации .
  • Нейроэволюция - похоже на генетическое программирование, но геномы представляют собой искусственные нейронные сети, описывая структуру и веса связей. Кодирование генома может быть прямым или косвенным.
  • Система обучающих классификаторов - здесь решение представляет собой набор классификаторов (правил или условий). Michigan-LCS развивается на уровне отдельных классификаторов, тогда как Pittsburgh-LCS использует совокупности наборов классификаторов. Первоначально классификаторы были только двоичными, но теперь они включают реальные типы, типы нейронных сетей или S-выражения . Пригодность обычно определяется с помощью обучения с подкреплением на основе силы или точности или обучения с учителем .

Сравнение с биологическими процессами [ править ]

Возможное ограничение [ согласно кому? ] многих эволюционных алгоритмов заключается в том, что в них отсутствует четкое различие между генотипом и фенотипом . В природе оплодотворенная яйцеклетка подвергается сложному процессу, известному как эмбриогенез, чтобы стать зрелым фенотипом . Считается, что это косвенное кодирование делает генетический поиск более надежным (т.е. снижает вероятность фатальных мутаций), а также может улучшить эволюционируемость организма. [3] [4] Такие косвенные (также известные как генеративные или эволюционные) кодировки также позволяют эволюции использовать регулярность окружающей среды. [5] Последние работы в областиискусственный эмбриогенез , или искусственные системы развития, стремится решить эти проблемы. И экспрессия генов программирования успешно исследует систему генотип-фенотип, где генотип состоит из линейных мультигенных хромосом фиксированной длины и фенотип состоит из нескольких деревьев выражений или компьютерных программ , различных размеров и форм. [6] [ неправильный синтез? ]

Связанные методы [ править ]

Алгоритмы Swarm [ необходимы пояснения ] включают

  • Оптимизация колонии муравьев - основана на идеях поиска пищи муравьями с помощью феромонной коммуникации для формирования путей. В первую очередь подходит для комбинаторной оптимизации и задач с графами .
  • Алгоритм корневого побега (RRA) основан на функции побегов и корней растений в природе [7]
  • Алгоритм искусственной пчелиной колонии - основан на поведении медоносных пчел при кормлении. В первую очередь предлагается для численной оптимизации и расширен для решения задач комбинаторной, ограниченной и многокритериальной оптимизации.
  • Алгоритм пчел основан на поведении медоносных пчел при кормлении. Он применялся во многих приложениях, таких как маршрутизация и планирование.
  • Поиск кукушки вдохновлен задумчивым паразитизмом видов кукушек . Он также использует полеты Леви и поэтому подходит для задач глобальной оптимизации .
  • Оптимизация Electimize - основана на поведении потока электронов через ветви электрической цепи с наименьшим электрическим сопротивлением. [8]
  • Оптимизация роя частиц - основана на идеях поведения стай животных. Также в первую очередь подходит для задач численной оптимизации .

Другие метаэвристические методы, основанные на популяциях [ править ]

  • Охотничий поиск - метод, вдохновленный групповой охотой на некоторых животных, таких как волки, которые организуют свою позицию, чтобы окружить добычу, каждое из них относительно положения других, и особенно положения их лидера. Это метод непрерывной оптимизации [9], адаптированный как метод комбинаторной оптимизации. [10]
  • Адаптивный поиск по измерениям - в отличие от метаэвристических методов, вдохновленных природой, алгоритм адаптивного поиска по измерениям не реализует никаких метафор в качестве основного принципа. Скорее, он использует простой ориентированный на производительность метод, основанный на обновлении параметра отношения размерности поиска (SDR) на каждой итерации. [11]
  • Алгоритм Firefly основан на поведении светлячков, которые привлекают друг друга мигающим светом. Это особенно полезно для мультимодальной оптимизации.
  • Поиск гармонии - основан на представлениях о поведении музыкантов в поисках лучших гармоний. Этот алгоритм подходит как для комбинаторной оптимизации, так и для оптимизации параметров.
  • Адаптация по Гауссу - на основе теории информации. Используется для максимизации выхода продукции, средней пригодности или средней информации . См., Например, Энтропия в термодинамике и теории информации .
  • Меметический алгоритм - гибридный метод, основанный на концепции мема Ричарда Докинза , он обычно принимает форму популяционного алгоритма в сочетании с индивидуальными процедурами обучения, способными выполнять локальные уточнения. Подчеркивает использование специфических для проблемы знаний и пытается согласовать локальный и глобальный поиск синергетическим образом.

Примеры [ править ]

В 2020 году Google заявил, что их AutoML-Zero может успешно заново открыть для себя классические алгоритмы, такие как концепция нейронных сетей. [12]

Компьютерное моделирование Tierra и Avida пытается смоделировать макроэволюционную динамику.

Галерея [ править ]

[13] [14] [15]

  • Двухпопуляционный поиск EA по ограниченной функции Розенброка с ограниченным глобальным оптимумом.

  • Двухпопуляционный поиск EA по ограниченной функции Розенброка . Глобальный оптимум не ограничен.

  • Оценка алгоритма распределения по функции Кина

  • Двухпопуляционный поиск ограниченного оптимума функции Симионеску с помощью EA .

Ссылки [ править ]

  1. ^ Vikhar, PA (2016). «Эволюционные алгоритмы: критический обзор и его перспективы на будущее». Труды Международной конференции по глобальным тенденциям в обработке сигналов, информационных вычислениях и коммуникации 2016 г. (ICGTSPICC) . Джалгаон: 261–265. DOI : 10.1109 / ICGTSPICC.2016.7955308 . ISBN 978-1-5090-0467-6. S2CID  22100336 .
  2. ^ a b Cohoon, Дж; и другие. (2002-11-26). Эволюционные алгоритмы для физического проектирования схем СБИС (PDF) . Достижения в эволюционных вычислениях: теория и приложения . Springer, стр. 683-712, 2003. ISBN  978-3-540-43330-9.
  3. ^ GS Hornby и JB Pollack. «Создание компонентов высокого уровня с генеративным представлением для эволюции тела и мозга». Искусственная жизнь , 8 (3): 223–246, 2002.
  4. ^ Джефф Клун, Бенджамин Бекманн, Чарльз Офриа и Роберт Пеннок. «Развитие скоординированных походок четвероногих с помощью генеративного кодирования HyperNEAT». Архивировано 3 июня 2016 года в Wayback Machine . Труды специальной секции Конгресса IEEE по эволюционным вычислениям по эволюционной робототехнике , 2009 г. Тронхейм, Норвегия.
  5. ^ Дж. Клун, К. Офриа и Р. Т. Пеннок, «Как генеративное кодирование работает по мере уменьшения регулярности проблемы» , в PPSN (Г. Рудольф, Т. Янсен, С. М. Лукас, К. Полони и Н. Бойм, ред. .), т. 5199 конспектов лекций по информатике , стр. 358–367, Springer, 2008.
  6. ^ Феррейра, С., 2001. «Программирование экспрессии генов: новый адаптивный алгоритм для решения проблем» . Сложные системы , Vol. 13, выпуск 2: 87–129.
  7. ^ Ф. Меррих-Баят, "Алгоритм" раннер-корень ": метаэвристика для решения задач одномодальной и мультимодальной оптимизации, вдохновленная побегами и корнями растений в природе", " Прикладные мягкие вычисления" , Vol. 33. С. 292–303, 2015.
  8. ^ Khalafallah Ахмед; Абдель-Рахим Мохамед (01.05.2011). «Electimize: новый эволюционный алгоритм оптимизации с применением в строительстве». Журнал вычислительной техники в гражданском строительстве . 25 (3): 192–201. DOI : 10.1061 / (ASCE) CP.1943-5487.0000080 .
  9. ^ Oftadeh, R .; Махджуб, MJ; Шариатпанахи, М. (октябрь 2010 г.). «Новый алгоритм метаэвристической оптимизации, вдохновленный групповой охотой на животных: поиск по охоте». Компьютеры и математика с приложениями . 60 (7): 2087–2098. DOI : 10.1016 / j.camwa.2010.07.049 .
  10. ^ Амин Agharghor; Мохаммед Эссаид Риффи (2017). "Первая адаптация алгоритма поиска охоты для задачи квадратичного назначения". Успехи сотрудничества Европы и MENA в области информационных и коммуникационных технологий . Достижения в интеллектуальных системах и вычислениях. 520 : 263–267. DOI : 10.1007 / 978-3-319-46568-5_27 . ISBN 978-3-319-46567-8.
  11. ^ Хасансеби, О., Каземзаде Азад, С. (2015), «Адаптивный размерный поиск: новый метаэвристический алгоритм для оптимизации размеров дискретной фермы», Компьютеры и структуры , 154, 1–16.
  12. ↑ Гент, Эдд (13 апреля 2020 г.). «Искусственный интеллект развивается сам по себе» . Наука | AAAS . Архивировано из оригинального 16 апреля 2020 года . Проверено 16 апреля 2020 года .
  13. ^ Simionescu, PA; Бил, Д.Г.; Дозье, GV (2004). «Решение задач ограниченной оптимизации с использованием оценки алгоритмов распределения» (PDF) . Proc. Конгресса 2004 г. по эволюционным вычислениям - CEC2004. Портленд, штат Орегон: 1647–1653. DOI : 10,1109 / CEC.2006.1688506 . S2CID 1717817 . Проверено 7 января 2017 года .   Cite journal requires |journal= (help)
  14. ^ Simionescu, PA; Dozier, GV; Уэйнрайт, Р.Л. (2006). «Эволюционный алгоритм для двух популяций для задач оптимизации с ограничениями» (PDF) . 2006 Международная конференция IEEE по эволюционным вычислениям . Proc 2006 Международная конференция IEEE по эволюционным вычислениям. Ванкувер, Канада. С. 1647–1653. DOI : 10,1109 / CEC.2006.1688506 . ISBN  0-7803-9487-9. S2CID  1717817 . Проверено 7 января 2017 года .
  15. ^ Simionescu, PA (2014). Инструменты компьютерного построения графиков и моделирования для пользователей AutoCAD (1-е изд.). Бока-Ратон, Флорида: CRC Press . ISBN 978-1-4822-5290-3.

Внешние ссылки [ править ]

  • Обзор истории и разновидностей эволюционных алгоритмов

Библиография [ править ]

  • Эшлок, Д. (2006), Эволюционные вычисления для моделирования и оптимизации , Springer, ISBN 0-387-22196-4 . 
  • Бэк Т. (1996), Эволюционные алгоритмы в теории и практике: стратегии эволюции, эволюционное программирование, генетические алгоритмы , Oxford Univ. Нажмите.
  • Бек Т., Фогель Д., Михалевич З. (1997), Справочник по эволюционным вычислениям , Oxford Univ. Нажмите.
  • Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction , Morgan Kaufmann, San Francisco
  • Эйбен, А.Е., Смит, Д.Е. (2003), Введение в эволюционные вычисления , Springer.
  • Холланд, Дж. Х. (1992), Адаптация в естественных и искусственных системах , Издательство Мичиганского университета, Анн-Арбор
  • Михалевич З., Фогель ДБ (2004). Как это решить: современная эвристика, Springer.
  • Бенко, Аттила; Доса, Дьердь; Туза, Жолт (2010). «Упаковка / закрытие бункеров с доставкой, решенная эволюцией алгоритмов». 2010 Пятая Международная конференция IEEE по биоинженерным вычислениям: теории и приложения (BIC-TA) . С. 298–302. DOI : 10.1109 / BICTA.2010.5645312 . ISBN 978-1-4244-6437-1. S2CID  16875144 .
  • Poli, R .; Лэнгдон, ВБ; Макфи, Н.Ф. (2008). Полевое руководство по генетическому программированию . Lulu.com, свободно доступный в Интернете. ISBN 978-1-4092-0073-4. Архивировано из оригинала на 2016-05-27 . Проверено 5 марта 2011 .[ самостоятельно опубликованный источник ]
  • Прайс, К., Сторн, Р.М., Лампинен, Дж. А. (2005). «Дифференциальная эволюция: практический подход к глобальной оптимизации» , Спрингер.
  • Инго Рехенберг (1971): Стратегия развития - Оптимизация технической системы для принципов биологической эволюции (докторская диссертация). Перепечатано Фромман-Хольцбугом (1973).
  • Ханс-Пауль Швефель (1974): Numerische Optimierung von Computer-Modellen (докторская диссертация). Перепечатано Биркхойзером (1977).
  • Саймон Д. (2013): Алгоритмы эволюционной оптимизации , Wiley.
  • Вычислительный интеллект: методологическое введение Крузе, Боргельта, Клавона, Моуэса, Штайнбрехера, Хельда, 2013 г., Springer, ISBN 978-1-4471-5012-1 
  • Rahman, Rosshairy Abd .; Кендалл, Грэм; Рамли, Разамин; Джамари, Зайноддин; Ку-Махамуд, Ку Рухана (2017). «Составление корма для креветок с помощью эволюционного алгоритма с эвристикой мощности для обработки ограничений» . Сложность . 2017 : 1–12. DOI : 10.1155 / 2017/7053710 .