Введение в эволюционное моделирование. Каширина И.Л. - 7 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

7
Кодирование решений
После того как выбраны параметры, их число и разрядность, необхо-
димо решить, как непосредственно записывать данные. Можно использовать
обычное кодирование, когда, например, 1011
2
=11
10
, либо коды Грея, когда
1011
G
= 1110
2
= 14
10
. Несмотря на то, что коды Грея влекут неизбежное ко-
дирование/декодирование данных, они позволяют избежать некоторых про-
блем, которые появляются в результате обычного кодирования. Можно лишь
сказать, что преимущество кода Грея в том, что если два числа являются по-
следовательными при кодировании, то и их двоичные коды различаются
только на
один разряд, а в двоичных кодах это не так. Стоит отметить, что
кодировать и декодировать в коды Грея можно так: сначала копируется са-
мый старший разряд, затем:
• из двоичного кода в код Грея: G[i] = XOR(B[i+1], B[i]) ;
• из кода Грея в двоичный код: B[i] = XOR(B[i+1], G[i]).
Здесь, G[i] i-й разряд кода Грея, а B[i] - i-й разряд бинарного кода. На-
пример, последовательность чисел от 0 до 7 в двоичном коде: {000, 001, 010,
011, 100, 101, 110, 111}, а в кодах Грея: {000, 001, 011, 010, 110, 111, 101,
100}.
Общая схема генетического алгоритма
Общая схема такого алгоритма может быть записана следующим образом.
1. Формирование начальной популяции.
2. Оценка особей популяции.
3. Отбор (селекция).
4. Скрещивание.
5. Мутация.
6. Формирование новой популяции.
7. Если популяция не сошлась, то 2. Иначе –останов.
Остановимся подробнее всех этапах этого алгоритма.
Формирование начальной популяции
Стандартный генетический алгоритм начинает свою работу с форми-
рования начальной популяции I
0
— конечного набора допустимых решений
задачи. Эти решения могут быть выбраны случайным образом или получены
с помощью простых приближенных алгоритмов. Выбор начальной популя-
ции не имеет значения для сходимости процесса в асимптотике, однако фор-
мирование "хорошей" начальной популяции (например, из множества ло-
кальных оптимумов) может заметно сократить время достижения глобально-
го
оптимума. Если отсутствуют предположения о местоположении глобаль-
ного оптимума, то индивиды из начальной популяции желательно распреде-
лить равномерно по всему пространству поиска решения. 
                                     7
Кодирование решений
      После того как выбраны параметры, их число и разрядность, необхо-
димо решить, как непосредственно записывать данные. Можно использовать
обычное кодирование, когда, например, 10112=1110, либо коды Грея, когда
1011G = 11102 = 1410. Несмотря на то, что коды Грея влекут неизбежное ко-
дирование/декодирование данных, они позволяют избежать некоторых про-
блем, которые появляются в результате обычного кодирования. Можно лишь
сказать, что преимущество кода Грея в том, что если два числа являются по-
следовательными при кодировании, то и их двоичные коды различаются
только на один разряд, а в двоичных кодах это не так. Стоит отметить, что
кодировать и декодировать в коды Грея можно так: сначала копируется са-
мый старший разряд, затем:
   • из двоичного кода в код Грея: G[i] = XOR(B[i+1], B[i]) ;
   • из кода Грея в двоичный код: B[i] = XOR(B[i+1], G[i]).
Здесь, G[i] � � i-й разряд кода Грея, а B[i] - i-й разряд бинарного кода. На-
пример, последовательность чисел от 0 до 7 в двоичном коде: {000, 001, 010,
011, 100, 101, 110, 111}, а в кодах Грея: {000, 001, 011, 010, 110, 111, 101,
100}.
Общая схема генетического алгоритма
Общая схема такого алгоритма может быть записана следующим образом.
   1. Формирование начальной популяции.
   2. Оценка особей популяции.
   3. Отбор (селекция).
   4. Скрещивание.
   5. Мутация.
   6. Формирование новой популяции.
   7. Если популяция не сошлась, то 2. Иначе –останов.
Остановимся подробнее всех этапах этого алгоритма.
                  Формирование начальной популяции
      Стандартный генетический алгоритм начинает свою работу с форми-
рования начальной популяции I0 — конечного набора допустимых решений
задачи. Эти решения могут быть выбраны случайным образом или получены
с помощью простых приближенных алгоритмов. Выбор начальной популя-
ции не имеет значения для сходимости процесса в асимптотике, однако фор-
мирование "хорошей" начальной популяции (например, из множества ло-
кальных оптимумов) может заметно сократить время достижения глобально-
го оптимума. Если отсутствуют предположения о местоположении глобаль-
ного оптимума, то индивиды из начальной популяции желательно распреде-
лить равномерно по всему пространству поиска решения.

Страницы