Меметический алгоритм

редактировать

В информатике и исследования операций, меметическая алгоритм (МА) является продолжением традиционного генетического алгоритма. Он использует технику локального поиска, чтобы уменьшить вероятность преждевременного схождения.

Меметические алгоритмы представляют собой одну из последних растущих областей исследований в области эволюционных вычислений. Термин MA в настоящее время широко используется как синергия эволюционного или любого популяционного подхода с отдельными процедурами индивидуального обучения или местного улучшения для поиска проблем. Довольно часто МА также упоминаются в литературе как балдвиновские эволюционные алгоритмы (ЭА), ламарковские советники, культурные алгоритмы или генетический локальный поиск.

СОДЕРЖАНИЕ

  • 1 Введение
  • 2 Разработка МА
    • 2,1 1-го поколения
    • 2.2 2-го поколения
    • 2.3 3-го поколения
  • 3 Некоторые примечания к дизайну
    • 3.1 Как часто следует применять индивидуальное обучение?
    • 3.2 На каких решениях следует использовать индивидуальное обучение?
    • 3.3 Как долго нужно проводить индивидуальное обучение?
    • 3.4 Какой индивидуальный метод обучения или мем следует использовать для конкретной проблемы или человека?
  • 4 Приложения
  • 5 Недавние действия в меметических алгоритмах
  • 6 Ссылки

Вступление

Вдохновленный как дарвиновскими принципами естественной эволюции, так и представлением Докинза о меме, термин меметический алгоритм (MA) был введен Пабло Москато в его техническом отчете в 1989 году, где он рассматривал MA как близкую к форме популяционно-гибридного генетического алгоритма. алгоритм (GA) в сочетании с индивидуальной процедурой обучения, способной выполнять локальные уточнения. Метафорические параллели, с одной стороны, дарвиновской эволюции и, с другой стороны, между мемами и эвристикой, зависящей от предметной области (локальный поиск), улавливаются меметическими алгоритмами, таким образом создавая методологию, которая хорошо балансирует между общностью и специфичностью проблемы. Эта двухэтапная природа делает их особым случаем двухфазной эволюции.

В более разнообразном контексте меметические алгоритмы теперь используются под разными именами, включая гибридные эволюционные алгоритмы, эволюционные алгоритмы Балдвина, эволюционные алгоритмы Ламарка, культурные алгоритмы или генетический локальный поиск. В контексте комплексной оптимизации сообщалось о множестве различных реализаций меметических алгоритмов в широком диапазоне областей приложений, в целом сходящихся к высококачественным решениям более эффективно, чем их традиционные эволюционные аналоги.

В общем, использование идей меметики в вычислительной структуре называется меметическими вычислениями или меметическими вычислениями (MC). С помощью MC более уместно уловить черты универсального дарвинизма. С этой точки зрения MA - это более ограниченное понятие MC. В частности, MA охватывает одну область MC, в частности, касается областей эволюционных алгоритмов, которые сочетаются с другими детерминированными методами уточнения для решения задач оптимизации. MC расширяет понятие мемов, чтобы охватить концептуальные сущности процедур или представлений с расширенными знаниями.

Развитие МА

1-е поколение

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

Псевдокод
 Procedure Memetic Algorithm Initialize: Generate an initial population; while Stopping conditions are not satisfied do Evaluate all individuals in the population. Evolve a new population using stochastic search operators. Select the subset of individuals,      Ω  i l {\displaystyle \Omega _{il}}, that should undergo the individual improvement procedure. for each individual in      Ω  i l {\displaystyle \Omega _{il}} do Perform individual learning using meme(s) with frequency or probability of      f  i l {\displaystyle f_{il}}, for a period of      t  i l {\displaystyle t_{il}}. Proceed with Lamarckian or Baldwinian learning. end for end while

2-е поколение

Мультимемные, гиперэвристические и металамаркианские МА относятся к МА второго поколения, демонстрируя в своей конструкции принципы меметической передачи и отбора. В Multi-meme MA меметический материал кодируется как часть генотипа. Впоследствии декодированный мем каждого соответствующего человека / хромосомы затем используется для выполнения локального уточнения. Затем меметический материал передается через простой механизм наследования от родителей к потомкам. С другой стороны, в гиперэвристической и металамаркианской MA пул рассматриваемых мемов-кандидатов будет конкурировать, основываясь на их прошлых заслугах в создании локальных улучшений с помощью механизма вознаграждения, решая, какой мем будет выбран для дальнейшего локального использования. уточнения. Мемы с более высокой наградой имеют больше шансов быть воспроизведенными или скопированы. Для обзора МА второго поколения; то есть степень магистра, рассматривающая несколько индивидуальных методов обучения в рамках эволюционной системы, к читателю отсылается.

3-е поколение

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

Некоторые примечания к дизайну

Частота и интенсивность индивидуального обучения напрямую определяют степень эволюции (исследования) по сравнению с индивидуальным обучением (эксплуатацией) в поиске MA при заданном фиксированном ограниченном вычислительном бюджете. Ясно, что более интенсивное индивидуальное обучение дает больше шансов на сходимость к локальным оптимумам, но ограничивает объем эволюции, которая может быть затрачена без чрезмерных вычислительных ресурсов. Следовательно, при установке этих двух параметров следует соблюдать осторожность, чтобы сбалансировать доступный вычислительный бюджет для достижения максимальной производительности поиска. Когда только часть населения проходит обучение, необходимо рассмотреть вопрос о том, какое подмножество людей следует улучшить, чтобы максимизировать полезность поиска МА. И наконец, что не менее важно, индивидуальная процедура обучения / мем также способствует другой структуре окружения, поэтому необходимо решить, какой мем или мемы использовать для данной задачи оптимизации.

Как часто следует применять индивидуальное обучение?

Одна из первых проблем, связанных с разработкой меметических алгоритмов, - это рассмотрение того, как часто следует применять индивидуальное обучение; т.е. индивидуальная частота обучения. В одном случае было рассмотрено влияние индивидуальной частоты обучения на эффективность поиска MA, где были исследованы различные конфигурации индивидуальной частоты обучения на разных этапах поиска MA. Напротив, в другом месте было показано, что, возможно, стоит применить индивидуальное обучение к каждому человеку, если вычислительная сложность индивидуального обучения относительно невысока.

На каких решениях следует использовать индивидуальное обучение?

По вопросу выбора подходящих людей среди популяции EA, которые должны пройти индивидуальное обучение, были изучены стратегии, основанные на фитнесе и распределении, для адаптации вероятности применения индивидуального обучения к популяции хромосом в задачах непрерывного параметрического поиска с расширением работы Лэнда. к задачам комбинаторной оптимизации. Bambha et al. представила технику моделирования нагрева для систематической интеграции параметризованного индивидуального обучения в эволюционные алгоритмы для достижения максимального качества решения.

Как долго нужно проводить индивидуальное обучение?

Интенсивность индивидуального обучения, - сумма вычислительного бюджета, выделенная на итерацию индивидуального обучения; т. е. максимальный вычислительный бюджет, допустимый для индивидуального обучения, который можно потратить на улучшение отдельного решения. т я л {\ displaystyle t_ {il}}

Какой индивидуальный метод обучения или мем следует использовать для конкретной проблемы или человека?

В контексте непрерывной оптимизации индивидуальное обучение существует в форме локальной эвристики или обычных методов точного перечисления. Примеры индивидуальных стратегий обучения включают восхождение на холм, симплекс-метод, метод Ньютона / квази-Ньютона, методы внутренней точки, метод сопряженного градиента, линейный поиск и другие локальные эвристики. Обратите внимание, что большинство общих методов индивидуального обучения детерминированы.

С другой стороны, в комбинаторной оптимизации индивидуальные методы обучения обычно существуют в форме эвристики (которая может быть детерминированной или стохастической), адаптированной к конкретной интересующей проблеме. Типичные эвристические процедуры и схемы включают обмен k-генами, обмен ребрами, первое улучшение и многие другие.

Приложения

Меметические алгоритмы успешно применялись для решения множества реальных проблем. Хотя многие люди используют методы, тесно связанные с меметическими алгоритмами, также используются альтернативные названия, такие как гибридные генетические алгоритмы. Более того, многие люди называют свои меметические методы генетическими алгоритмами.

Исследователи использовали меметические алгоритмы для решения многих классических проблем NP. Приведем некоторые из них: разбиение графов, многомерная ранец, задача коммивояжера, квадратичной задачи о назначениях, поставленной задачи сопроводительное, минимальный график расцветку, макс независимое множество проблемы, бен проблема упаковки и обобщенной задачи о назначениях.

Более свежие приложения включают (но не ограничиваются ими) бизнес-аналитику и науку о данных, обучение искусственных нейронных сетей, распознавание образов, планирование движения роботов, ориентацию луча, проектирование схем, восстановление электрических услуг, медицинские экспертные системы, планирование отдельных машин, автоматическое составление расписаний. ( в частности, график для НХЛ ), планирование кадров, медсестра Rostering оптимизации, распределения процессоров, планирования технического обслуживания (например, электрической распределительной сети), многомерной задачи о рюкзаке, СБИС дизайн, кластеризация из профилей экспрессии генов, функция выбора / ген, определение параметров для внедрения аппаратных сбоев и многоклассовый, многоцелевой выбор функций.

Недавние действия в меметических алгоритмах

Рекомендации

Последняя правка сделана 2024-01-02 06:35:01
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте