Схема (генетические алгоритмы)
Схема ) — это ( мн. : схема шаблон в информатике, используемый в области генетических алгоритмов , который идентифицирует подмножество строк со сходством в определенных позициях строк. Схемы — это частный случай наборов цилиндров , образующий основу топологии произведения на строках. [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]
Например, пусть . Схематическое завершение , приводит к следующему набору:
Посет всегда образует полную решетку, называемую схематической решеткой.
Схематическая решетка аналогична решетке понятий, найденной в формальном анализе понятий .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Холланд, Джон Генри (1992). Адаптация в природных и искусственных системах (переиздание). Массачусетский технологический институт Пресс. ISBN 9780472084609 . Проверено 22 апреля 2014 г.
- ^ Перейти обратно: а б «Основы генетического программирования» . UCL Великобритании . Проверено 13 июля 2010 г.
- ^ Перейти обратно: а б с Джек Маккей Флетчер и Томас Веннкерс (2017). «Естественный подход к изучению обработки схем». arXiv : 1705.04536 [ cs.NE ].