Jump to content

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

(Перенаправлено из «Распространение схемы »)

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

Описание

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

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

Длина схемы , называется , определяется как общее количество узлов в схеме. также равно количеству узлов в программах, соответствующих . [2]

Нарушение

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

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

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

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

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

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

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

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

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

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

Для любой схемы следующий оператор , называемый из , который отображает к подмножеству слов в :

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

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

Схемы можно частично заказать . Для любого мы говорим тогда и только тогда, когда . Отсюда следует, что представляет собой частичное упорядочение набора схем с учетом рефлексивности , антисимметрии и транзитивности подмножества отношения . Например, .Это потому, что .

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

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

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

Для набора , мы называем процесс вычисления сжатия на каждом подмножестве A, то есть , схематическое завершение , обозначенный . [3]

Например, пусть . Схематическое завершение , приводит к следующему набору:

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

Схематическая решетка формируется из схематических завершений набора. . Вот схематическая решетка представлена ​​в виде диаграммы Хассе .

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

См. также

[ редактировать ]
  1. ^ Холланд, Джон Генри (1992). Адаптация в природных и искусственных системах (переиздание). Массачусетский технологический институт Пресс. ISBN  9780472084609 . Проверено 22 апреля 2014 г.
  2. ^ Перейти обратно: а б «Основы генетического программирования» . UCL Великобритании . Проверено 13 июля 2010 г.
  3. ^ Перейти обратно: а б с Джек Маккей Флетчер и Томас Веннкерс (2017). «Естественный подход к изучению обработки схем». arXiv : 1705.04536 [ cs.NE ].
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e06643ca537d4a5712c499e82cbea92c__1696609920
URL1:https://arc.ask3.ru/arc/aa/e0/2c/e06643ca537d4a5712c499e82cbea92c.html
Заголовок, (Title) документа по адресу, URL1:
Schema (genetic algorithms) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)