ТСМ-№3 (1088238)
Текст из файла
Лекция №3
Генетические алгоритмы. Операторы кроссовера
Кроссовер – генетический оператор реализующий обмен генетической информации между хромосомой родителя и преобразующий хромосомы родителей в хромосомы потомков
В настоящее время реализовано значительное количество операторов кроссовера вид которых существенно влияет на эффективность ГА.
Наиболее часто используются следующие операторы кроссовера:
-
простой (одноточечный) оператор кроссовера
-
многоточечный оператор кроссовера (в частности двухточечный оператор кроссовера)
-
упорядоченный оператор кроссовера
-
частично упорядоченный оператор кроссовера
-
циклический оператор кроссовера
-
универсальный оператор кроссовера
-
“Жадный” оператор кроссовера
Простой (одноточечный) оператор кроссовера
Этот оператор можно представить в виде последовательности следующих шагов:
Шаг 1. Две хромосомы выбираются случайно из множества родителей
Шаг 2. Выбираем случайно (на основе равномерного закона распределения) величину 
, где n- длина хромосомы. К определяет номер разряда, начиная с которого осуществляется обмен информацией между хромосомами родителей.
Шаг 3. Формируется 2 основные хромосомы потомков путем преставления их элементов согласно правилу:
Простой оператор кроссовера реализует преобразование двух хромосом родителей на основе частичного обмена информацией между ними, использующую одну точку разреза, выбираемую случайно.
Многоточечный оператор кроссовера
N – точечный оператор кроссовера делит хромосомы родителей на (N+1) блоков:
Пусть для определённости N – четное
|
| |||||
| A: | A1 | A2 | …. | AN | AN+1 |
| B: | B1 | B2 | …. | BN | BN+1 |
| A`: | A1 | B2 | …. | BN | AN+1 |
|
|
| ||||
| B`: | B1 | A2 | …. | AN | BN+1 |
Тогда возможно формирование хромосом потомков А` и В` по следующему правилу.
Хромосома А` образуется из нечетных блоков родителя А, и четных блоков родителя В.
Потомок В` образуется соответственно из нечетных блоков родителя В и четных блоков родителя А. Те происходит обмен информацией между хромосомами родителей, хранящейся в четных блоках.
Частным случаем многоточечного оператора является двухточечный оператор кроссовера
| 1 | 2 | ||
| A: | A1 | A2 | A3 |
|
| |||
| B: | B1 | B2 | B3 |
| A`: | A1 | B | B3 |
| B`: | B1 | A2 | A3 |
2Здесь обмен информацией происходит между четными блоками. Возможен взаимный обмен информацией между побочными блоками
| A | B1 | A2 | B3 |
| B`: | A1 | B2 | A3 |
Замечание: слишком большое количество разрезающих точек может привести к потере “хороших” свойств родительских хромосом.
Упорядоченный оператор кроссовера
Также как и выше выбирается разрезающая точка
| A: | A | B | C | D | E | F | G | H |
|
|
|
| ||||||
| B: | G | A | B | E | C | D | F | H |
|
|
|
| ||||||
| A`: | A | B | C | D | G | E | F | H |
| B`: | G | A | B | E | C | D | F | H |
Предположения: каждая хромосома образуется одним и тем же множеством элементов, образующим алфавит, но в различном порядке.
Формирование А`:
-
Получается левый сегмент А
-
Остальные элементы в правом сегменте берутся из В в упорядоченном виде слева направо, уже располагаются элементы попавшие в А`
Формирование В`:
-
остальные элементы в новом множестве В` образуется из А так же
Упорядоченный оператор кроссовера изменяется для решения комбинаторных задач, задач на графах и т.д.
Пример 1.
Точка разрыва 1 (A`B`) Точка разрыва 2 (A``B``)
| A: | A | G | I | H | B | >< | D | E | F | C | J |
| B: | J | B | C | I | A | >< | D | E | H | F | G |
| A`: | A | G | I | H | J | >< | B | C | D | E | F |
| B`: | J | B | C | I | A | >< | G | H | D | E | F |
| A``: | A | G | I | H | B | >< | D | E | J | C | F |
| B``: | J | B | C | I | A | >< | D | E | G | H | F |
Частично соответствующий оператор кроссовера
Здесь точные определения хромосомы определяются одним и тем же множеством, но в различном порядке, Тогда разрез выбирается случайно.
Далее анализируются части (сегменты) в обеих хромосомах и устанавливаются частичные соответствия между элементами 1-ого и 2-ого родителя с формированием потомков.
Пример 1.
Точка кроссовера
| P1: | A | B | C | D | E | F | G | H | I | J |
| P2: | E | C | I | A | D | H | J | B | F | G |
|
|
| |||||||||
| P1`: | A | H | C | D | E | I | J | B | F | G |
| P2`: | E | C | F | A | D | B | G | H | I | J |
Данное определение кроссовера состоит из следующих шагов:
Шаг 1. Случайным образом выбирается точка кроссовера. Пусть она установлена после 6-ого разряда.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
