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

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

Описание

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

Длина

Длина схемы $H$, называется $N(H)$, определяется как общее количество узлов в схеме. $N(H)$ также равно количеству узлов в программах, соответствующих $H$.

Нарушение

Если потомок индивидуума, который соответствует схеме H, сам не соответствует H, говорят, что схема нарушена .

Распространение схемы

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

Операторы расширения и сжатия

В последнее время схемы изучаются с использованием теории порядка .

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

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

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

$${\uparrow }s:=\{b\in \Sigma ^{l}|b_{i}=s_{i}{\mbox{ or }}s_{i}=*{\mbox{ for each }}i\in \{1,...,l\}\}$$

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

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

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

Операторы сжатия и расширения образуют связность Галуа , где $\downarrow$ является нижним сопряженным и $\uparrow$ верхний примыкающий.

Схематическое завершение и схематическая решетка

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

Например, пусть $A=\{110,100,001,000\}$. Схематическое завершение $A$, приводит к следующему набору: $${\mathcal {S}}(A)=\{001,100,000,110,00*,*00,1*0,**0,*0*,***,\epsilon _{*}\}$$

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

Схематическая решетка формируется из схематических завершений набора. $A=\{111,011,001\}$. Вот схематическая решетка $({\mathcal {S}}(A),\leq )$ представлена ​​в виде диаграммы Хассе .

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

См. также

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