Генетические алгоритмы - продвинутые темы

В этом разделе мы познакомим вас с некоторыми дополнительными темами генетических алгоритмов. Читатель, который хочет просто познакомиться с GA, может пропустить этот раздел.

Ограниченные проблемы оптимизации

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

В таком сценарии операторы кроссовера и мутации могут дать нам решения, которые невозможно реализовать. Следовательно, при решении задач оптимизации с ограничениями в GA должны использоваться дополнительные механизмы.

Некоторые из наиболее распространенных методов -

С помощью penalty functions что снижает пригодность недопустимых решений, предпочтительно так, чтобы соответствие снижалось пропорционально количеству нарушенных ограничений или расстоянию от допустимой области.
С помощью repair functions которые принимают недопустимое решение и модифицируют его таким образом, чтобы удовлетворялись нарушенные ограничения.
Not allowing infeasible solutions вообще не входить в популяцию.
Использовать special representation or decoder functions что обеспечивает выполнимость решений.

Основные теоретические основы

В этом разделе мы обсудим теорему схемы и NFL, а также гипотезу о строительных блоках.

Схема теоремы

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

В этом разделе мы не углубляемся в математику теоремы схемы, а скорее пытаемся развить базовое понимание того, что такое теорема схемы. Основная терминология, которую необходимо знать, заключается в следующем:

А Schemaэто «шаблон». Формально это строка в алфавите = {0,1, *},

где * не имеет значения и может принимать любое значение.

Следовательно, * 10 * 1 может означать 01001, 01011, 11001 или 11011.

Геометрически схема - это гиперплоскость в пространстве поиска решений.
Order схемы - это количество указанных фиксированных позиций в гене.

Defining length расстояние между двумя самыми дальними фиксированными символами в гене.

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

Гипотеза строительных блоков

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

Теорема об отсутствии бесплатного обеда (НФЛ)

Вольперт и Макреди в 1997 году опубликовали статью под названием «Теоремы об отсутствии бесплатных обедов для оптимизации». По сути, он утверждает, что если мы усредним пространство всех возможных проблем, то все алгоритмы черного ящика без пересмотра будут демонстрировать одинаковую производительность.

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

Машинное обучение на основе GA

Генетические алгоритмы также находят применение в машинном обучении. Classifier systems являются формой genetics-based machine learning(GBML), которые часто используются в области машинного обучения. Методы GBML - нишевый подход к машинному обучению.

Есть две категории систем GBML -

The Pittsburg Approach - При таком подходе одна хромосома кодирует одно решение, поэтому решениям присваивается соответствие.
The Michigan Approach - одно решение обычно представлено множеством хромосом, поэтому пригодность присваивается частичным решениям.

Следует иметь в виду, что стандартные проблемы, такие как кроссовер, мутация, ламаркистский или дарвиновский и т. Д., Также присутствуют в системах GBML.