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

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

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

Введение

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

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

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

Теоретическая основа

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

Развитие МА

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

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

Псевдокод

   Procedure Memetic Algorithm
   Initialize: Generate an initial population, evaluate the individuals and assign a quality value to them;
   while Stopping conditions are not satisfied do
       Evolve a new population using stochastic search operators.
       Evaluate all individuals in the population and assign a quality value to them.
       Select the subset of individuals, $\Omega _{il}$, that should undergo the individual improvement procedure.
       for each individual in $\Omega _{il}$ do
           Perform individual learning using meme(s) with frequency or probability of $f_{il}$, with an intensity of $t_{il}$.
           Proceed with Lamarckian or Baldwinian learning.
       end for
   end while

Ламарковское обучение в этом контексте означает обновление хромосомы в соответствии с улучшенным решением, найденным на индивидуальном этапе обучения, в то время как болдуинское обучение оставляет хромосому неизменной и использует только улучшенную приспособленность. Этот псевдокод оставляет открытым вопрос, какие шаги основаны на физической подготовленности людей, а какие нет. Под вопросом стоят эволюция новой популяции и отбор $\Omega _{il}$.

Поскольку большинство реализаций МА основаны на советниках, здесь же вслед за Красногором приведен псевдокод соответствующего представителя первого поколения:

Псевдокод

   Procedure Memetic Algorithm Based on an EA
   Initialization: $t=0$;  // Initialization of the generation counter
                   Randomly generate an initial population $P(t)$;
                   Compute the fitness $f(p)\ \ \forall p\in P(t)$;
   while Stopping conditions are not satisfied do
       Selection:  Accordingly to $f(p)$ choose a subset of $P(t)$ and store it in $M(t)$;
       Offspring: Recombine and mutate individuals $p\in M(t)$ and store them in $M'(t)$;
       Learning: Improve $p'$ by local search or heuristic $\forall p'\in M'(t)$;
       Evaluation: Compute the fitness $f(p')\ \ \forall p'\in M'(t)$;
       if Lamarckian learning then
          Update chromosome of $p'$ according to improvement $\forall p'\in M'(t)$;
       fi
       New generation: Generate $P(t+1)$ by selecting some individuals from $P(t)$ and $M'(t)$;
       $t=t+1$;  // Increment the generation counter
   end while
   Return best individual $p\in P(t-1)$ as result;

Есть несколько альтернатив этой схеме МА. Например:

• Все или некоторые из первоначальных людей могут быть улучшены с помощью мема(ов).
• Вместо потомства локально улучшаются родители.
• Вместо всего потомства локальному улучшению может подвергнуться только случайно выбранная или зависящая от приспособленности фракция. Последнее требует оценки потомства в $M'(t)$ до этапа обучения .

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

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

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

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

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

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

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

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

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

Определение индивидуальной частоты обучения

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

Отбор лиц, к которым применяется индивидуальное обучение

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

Уточнение интенсивности индивидуального обучения

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

Выбор ламаркистского или болдуинского обучения

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

Приложения

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

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

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

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

• Семинар IEEE по меметическим алгоритмам (WOMA 2009). Руководители программы: Джим Смит, Университет Западной Англии, Великобритания; Ю-Сун Онг, Наньянский технологический университет, Сингапур; Густавсон Стивен, Ноттингемский университет; Великобритания; Мэн Хиот Лим, Наньянский технологический университет, Сингапур; Наталио Красногор, Ноттингемский университет, Великобритания
• Memetic Computing Journal , первый выпуск вышел в январе 2009 года.
• 2008 Всемирный конгресс IEEE по вычислительному интеллекту (WCCI 2008) , Гонконг, специальная сессия по меметическим алгоритмам .
• Специальный выпуск «Новые тенденции в мягких вычислениях - меметический алгоритм». Архивировано 27 сентября 2011 г. в Wayback Machine , Soft Computing Journal, завершено и в печати, 2008 г.
• Целевая группа по новым технологиям Общества вычислительной разведки IEEE по меметическим вычислениям. Архивировано 27 сентября 2011 г. в Wayback Machine.
• Конгресс IEEE по эволюционным вычислениям (CEC 2007) , Сингапур, специальная сессия по меметическим алгоритмам .
• «Меметические вычисления» от Thomson Scientific's Essential Science Indicators как новая область исследований.
• Специальный выпуск по меметическим алгоритмам , Транзакции IEEE в системах, человеке и кибернетике - Часть B: Кибернетика, Том. 37, № 1, февраль 2007 г.
• Последние достижения в меметических алгоритмах , Серия: Исследования нечеткости и мягких вычислений, Vol. 166, ISBN   978-3-540-22904-9 , 2005 г.
• Специальный выпуск о меметических алгоритмах , Evolutionary Computation, осень 2004 г., Vol. 12, № 3: в-vi.