|
|
0h |
0 |
0000 |
0h |
|
|
1 |
0001 |
1h |
1 |
0001 |
1h |
|
2 |
0010 |
2h |
3 |
0011 |
3h |
|
3 |
0011 |
3h |
2 |
0010 |
2h |
|
4 |
0100 |
4h |
6 |
0110 |
6h |
|
5 |
0101 |
5h |
7 |
0111 |
7h |
|
6 |
0110 |
6h |
5 |
0101 |
5h |
|
7 |
0111 |
7h |
4 |
0100 |
4h |
|
8 |
1000 |
8h |
12 |
1100 |
Ch |
|
9 |
1001 |
9h |
13 |
1101 |
Dh |
|
10 |
1010 |
Ah |
15 |
1111 |
Fh |
|
11 |
1011 |
Bh |
14 |
1110 |
Eh |
|
12 |
1100 |
Ch |
10 |
1010 |
Ah |
|
13 |
1101 |
Dh |
11 |
1011 |
Bh |
|
14 |
1110 |
Eh |
9 |
1001 |
9h |
|
15 |
1111 |
Fh |
8 |
1000 |
8h |
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины [10]. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит
0010
1010
1001
0100
1101
теперь мы можем определить значения признаков
Признак
Значение гена
Двоичное значение признака
Десятичное значение признака
Признак 1
0010
0011
3
Признак 2
1010
1100
12
Признак 3
1001
1110
14
Признак 4
0100
0111
7
Признак 5
1101
1001
9
1.3 Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:
o из популяции выбираются две особи, которые будут родителями;
o определяется (обычно случайным образом) точка разрыва;
o потомок определяется как конкатенация части первого и второго родителя.
Рассмотрим функционирование этого оператора
Хромосома_1:
0000000000
Хромосома_2:
1111111111
Допустим, разрыв происходит после 3-го бита хромосомы, тогда получаем.
Хромосома_1:
0000000000
>>
000
1111111
Результирующая хромосома 1
Хромосома_2:
1111111111
>>
111
0000000
Результирующая хромосома 2
Итак, рассмотрим все же операторы по порядку:
1) кроссинговер - создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется. Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом:
000
1111111
>>
1111111
000
2) инверсия - перестановка в структуре некоторой ее части наоборот
При использовании материалов активная ссылка на источник обязательна.