Схема (генетические алгоритмы)

Часть серии о
Эволюционный алгоритм
Искусственное развитие Искусственная жизнь Клеточный эволюционный алгоритм Культурный алгоритм Дифференциальная эволюция Эффективный фитнес Эволюционные вычисления Стратегия развития Гауссовская адаптация Эволюционная мультимодальная оптимизация Грамматическая эволюция Оптимизация роя частиц Меметический алгоритм Стратегия естественной эволюции Нейроэволюция Генетический алгоритм на основе промотора Алгоритм спиральной оптимизации Самомодифицирующийся код Полиморфный код
Генетический алгоритм
Хромосома Алгоритм клонального отбора Кроссовер Мутация Генетическая память Генетические нечеткие системы Выбор Алгоритм полета
Генетическое программирование
Декартово генетическое программирование Линейное генетическое программирование Программирование с несколькими выражениями Схема Eurisko Контрольный показатель паритета
v т е

Схема представляет собой шаблон , в информатике используется в области генетических алгоритмов , который идентифицирует подмножество строк с сходством в определенных позициях строк. Схемы - это частный случай наборов цилиндров ; и таким образом образуют топологическое пространство . ^[1]

Описание [ править ]

Например, рассмотрим двоичные строки длины 6. Схема 1 ** 0 * 1 описывает набор всех слов длины 6 с единицами в первой и шестой позициях и 0 в четвертой позиции. * - это подстановочный знак, который означает, что позиции 2, 3 и 5 могут иметь значение 1 или 0. Порядок схемы определяется как количество фиксированных позиций в шаблоне, а определяющая длина - это расстояние. между первой и последней конкретными позициями. Порядок 1 ** 0 * 1 равен 3, а его определяющая длина равна 5. Соответствие схемы - это средняя пригодность всех строк, соответствующих схеме. Пригодность строки - это мера ценности закодированного решения проблемы, вычисленная с помощью функции оценки конкретной проблемы.${\ displaystyle \ delta (H)}$

Длина [ править ]

Длина вызываемой схемы определяется как общее количество узлов в схеме. также равно количеству узлов в совпадающих программах . ^[2]${\ displaystyle H}$${\ Displaystyle N (H)}$${\ Displaystyle N (H)}$${\ displaystyle H}$

Разрушение [ править ]

Если ребенок индивидуума , который соответствует Schema H не сам соответствует Н, схема , как утверждается, была нарушена . ^[2]

Распространение схемы [ править ]

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

Операторы расширения и сжатия [ править ]

Недавно схемы были изучены с помощью теории порядка . ^[3]

Для схемы определены два основных оператора: расширение и сжатие. Расширение отображает схему на набор слов, которые она представляет, в то время как сжатие отображает набор слов на схему.

В следующих определениях обозначает алфавит, обозначает все слова длины по алфавиту , обозначает алфавит с дополнительным символом . обозначает всю схему длины по алфавиту, а также пустую схему .${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {l}}$${\ displaystyle l}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma _ {*}}$${\ displaystyle \ Sigma}$${\ displaystyle *}$${\ displaystyle \ Sigma _ {*} ^ {l}}$${\ displaystyle l}$${\ displaystyle \ Sigma _ {*}}$${\ displaystyle \ epsilon _ {*}}$

Для любой схемы следующий оператор , называемый the of , сопоставляется с подмножеством слов в :${\ displaystyle s \ in \ Sigma _ {*} ^ {l}}$${\ displaystyle {\ uparrow} s}$${\displaystyle expansion}$${\displaystyle s}$${\displaystyle s}$${\displaystyle \Sigma ^{l}}$

Где нижний индекс обозначает символ в позиции в слове или схеме. Когда тогда . Проще говоря, это набор всех слов, которые можно составить, заменив символы на символы из . Например, если , а потом .${\displaystyle i}$${\displaystyle i}$${\displaystyle s=\epsilon _{*}}$${\displaystyle {\uparrow }s=\emptyset }$${\displaystyle {\uparrow }s}$${\displaystyle \Sigma ^{l}}$${\displaystyle *}$${\displaystyle s}$${\displaystyle \Sigma }$${\displaystyle \Sigma =\{0,1\}}$${\displaystyle l=3}$${\displaystyle s=10*}$${\displaystyle {\uparrow }s=\{100,101\}}$

И наоборот, для любого, который мы определяем , называемого of , который отображается в схему :${\displaystyle A\subseteq \Sigma ^{l}}$${\displaystyle {\downarrow }{A}}$${\displaystyle compression}$${\displaystyle A}$${\displaystyle A}$${\displaystyle s\in \Sigma _{*}^{l}}$

где - схема такой длины , что символ в позиции в определяется следующим образом: если для всех, то в противном случае . Если тогда . Можно думать об этом операторе как о складывании всех элементов, и если все элементы в столбце эквивалентны, символ в этой позиции принимает это значение, в противном случае есть символ подстановки. Например, пусть тогда .${\displaystyle s}$${\displaystyle l}$${\displaystyle i}$${\displaystyle s}$${\displaystyle x_{i}=y_{i}}$${\displaystyle x,y\in A}$${\displaystyle s_{i}=x_{i}}$${\displaystyle s_{i}=*}$${\displaystyle A=\emptyset }$${\displaystyle {\downarrow }A=\epsilon _{*}}$${\displaystyle A}$${\displaystyle s}$${\displaystyle A=\{100,000,010\}}$${\displaystyle {\downarrow }A=**0}$

Схемы можно заказать частично . Для любого мы говорим, если и только если . Из этого следует , что это частичный порядок на множестве схем из рефлексивности , антисимметричности и транзитивности из подмножества отношения. Например, . Это потому что .${\displaystyle a,b\in \Sigma _{*}^{l}}$${\displaystyle a\leq b}$${\displaystyle {\uparrow }a\subseteq {\uparrow }b}$${\displaystyle \leq }$${\displaystyle \epsilon _{*}\leq 11\leq 1*\leq **}$${\displaystyle {\uparrow }\epsilon _{*}\subseteq {\uparrow }11\subseteq {\uparrow }1*\subseteq {\uparrow }**=\emptyset \subseteq \{11\}\subseteq \{11,10\}\subseteq \{11,10,01,00\}}$

Операторы сжатия и расширения образуют связность Галуа , где - нижний сопряженный и верхний сопряженный. ^[3]${\displaystyle \downarrow }$${\displaystyle \uparrow }$

Завершение схемы и схематическая решетка [ править ]

Для набора мы называем процесс вычисления сжатия на каждом подмножестве A, то есть схематическое завершение , обозначенным . ^[3]${\displaystyle A\subseteq \Sigma ^{l}}$${\displaystyle \{{\downarrow }X|X\subseteq A\}}$${\displaystyle A}$${\displaystyle {\mathcal {S}}(A)}$

Например, пусть . В результате схематического завершения получается следующий набор: ${\displaystyle A=\{110,100,001,000\}}$${\displaystyle A}$

Посет всегда образует полную решетка называется схематическая решеткой. ${\displaystyle ({\mathcal {S}}(A),\leq )}$

Схематическая решетка подобна решетке понятий, найденной в формальном анализе понятий .

См. Также [ править ]

• Теорема схемы Холланда
• Формальный анализ концепции

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