Оператор - кроссинговер
Cтраница 1
Оператор кроссинговера реализуется как взаимный обмен короткими фрагментами двоичных строк гомологичных хромосом. [1]
Рассмотрим модифицированный оператор кроссинговера, ориентированный на задачу трассировки. Два родителя выбираются независимо друг от друга. Пусть, например, ра и рр - копии родителей ( рис. 6.43); р7 - полученный в результате применения ОК потомок. [2]
Последними выполняются операторы кроссинговера. На рисунке OK - одноточечный, ОК2 - двухточечный, ОКз - упорядоченный, ОК4 - циклический и OKs - модифицированный. Наилучшие результаты показывают жадные, фрактальные и дихотомические стратегии. В данной схеме порядок выполнения генетических операторов зависит от внешней среды, блока эволюционной адаптации и может иметь любой установленный порядок. Блок эволюционной адаптации может задать хаотичный ( случайный) порядок выполнения генетических операторов. [3]
После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. [4]
Таким образом, у оператора кроссинговера имеется тенденция к сохранению указанного темпа выборки в отношении тех разбиений, определяющие фрагменты которых малы по сравнению с /, имеется также тенденция к разрушению в отношении разбиений с большими определяющими фрагменатми. Но поскольку структуры, принадлежащие специфическим разбиениям, обеспечивающим высокое качество функционирования, с малыми определяющими фрагментами со временем начинают преобладать в базе знаний, то произойдет эффективное уменьшение числа определяющих фрагментов других разбиений, ослабляющее разрушительное влияние оператора кроссинговера на темп, с которым последние выбираются. Оператор мутации оказывает незначительное влияние на фактор выбора, поскольку ему отводится в поиске фоновая роль. [5]
Главным средством создания новых структур является оператор кроссинговера. Набор различных возможных реализаций определяется конкретными решениями относительно того, следует ли обе полученные структуры включать в базу знаний, следует ли сохранить их родителей и какие из других структур, если это вообще необходимо, должны быть удалены. [6]
В оптимизационных задачах находят применение различного типа жадные операторы кроссинговера. Они основаны на анализе ЦФ решений после каждого шага жадного ОК. Он может быть реализован на двух и более хромосомах, а в пределе - на всей популяции. [7]
При построении новых структур для последующего их опробывания оператор кроссинговера использует лишь информацию, присутствующую в структурах текущей базы знаний. Если конкретная информация отсутствует либо в силу ограниченности памяти, либо из-за потери в процессе отбора на предыдущем этапе итерации, то этот оператор не в состоянии создать содержащую ее новую структуру. Для привнесения новой информации в базу знаний предусмотрен оператор мутации, который произвольным образом изменяет одну или несколько компонент выбранной структуры. [8]
 |
Одноточечный кроссинговер.| Оператор мутации. [9] |
Значительное улучшение качества и скорости сходимости ГА дает комбинирование ГА с классическими детерминированными методами оптимизации, разработка модифицированных операторов кроссинговера и мутации, основанных на знании решаемой задачи. [10]
Заметим, что принятые нами условия в отношении представления в данном анализе накладывают некоторые ограничения на одновременное применение в процессе поиска операторов кроссинговера и инверсии. В частности, необходимо сохранять знания о местоположении, каждой компоненты в данной структуре, чтобы гарантировать, что оператор кроссинговера всегда применяется к аналогично представленным структурам. [11]
Если в результате работы генетического алгоритма удалось найти схемы типа ( 11) и ( 111), то, применив к ним оператор кроссинговера, можно получить хромосому ( 11111), обладающую наилучшим значением целевой функции. [12]
Если в результате работы генетического алгоритма удалось найти схемы типа ( Ц) и ( 111), то, применив к ним оператор кроссинговера, можно получить хромосому ( 1111 1), обладающую наилучшим значением целевой функции. [13]
ГА - генетический алгоритм; Р - исходная популяция; г - количество элементов популяции; / - длина битовой строки, кодирующей решение; si - оператор селекции; Fit - функция фитнесса ( функция полезности), определяющая пригодность решения; сг - оператор кроссинговера, определяющий возможность получения нового решения; т - оператор мутации; ot - оператор отбора. [14]
Значение вероятности выживания хромосомы изменяется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызывать увеличение или уменьшение числа схем в популяции. Если кроссинговер не применяется, то обмен между хромосомами отсутствует, поэтому поисковое пространство не увеличивается, и процесс затухает. [15]
Страницы: 1 2