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

                                    6
 странстве поиска всех возможных решений. Свойства объектов представле-
 ны значениями параметров, объединяемыми в запись, называемую в эволю-
 ционных методах хромосомой. В генетических методах оперируют хромо-
 сомами, относящимися к множеству объектов � �          популяции. Имитация
 генетических принципов � � вероятностный выбор родителей, среди чле-
 нов популяции, скрещивание их хромосом, отбор потомков для включения в
 новые поколения объектов на основе оценки целевой функции � � ведет к
эволюционному улучшению значений целевой функции (функции приспо-
собленности) от поколения к поколению.
       Чаще всего хромосома � � это битовая строка. Однако ГА не ограни-
чены бинарным представлением данных. Некоторые реализации используют
 целочисленное или вещественное кодирование. Несмотря на то, что для
 многих реальных задач, видимо, больше подходят строки переменной дли-
 ны, в настоящее время структуры фиксированной длины наиболее распро-
 странены и изучены. Вначале и мы ограничимся только структурами, кото-
 рые являются одиночными строками по n бит.
       Каждая хромосома (строка) представляет собой конкатенацию ряда
подкомпонентов, называемых генами. Гены располагаются в различных по-
зициях или локусах хромосомы и принимают значения, называемые аллеля-
ми. В представлениях с бинарными строками ген � � бит, локус � � его
позиция в строке и аллель � � его значение (0 или 1). Биологический тер-
мин "генотип" относится к полной генетической модели особи и соответст-
вует структуре в ГА. Термин "фенотип" относится к внешним наблюдае-
мым признакам и соответствует вектору в пространстве параметров. Чрез-
 вычайно простой, но иллюстративный пример - задача максимизации сле-
 дующей функции двух переменных:
              f (x1, x2) = x1x2, где 0 <= x1 < =1 и 0 < = x2 <= 1.
       Обычно методика кодирования реальных переменных x1 и x2 состоит в
 их преобразовании в двоичные целочисленные строки достаточной длины
� � достаточной для того, чтобы обеспечить желаемую точность. Предпо-
 ложим, что 10-разрядное кодирование достаточно и для x1, и x2. Установить
соответствие между генотипом и фенотипом закодированных особей можно,
 разделив соответствующее двоичному представлению целое число на зна-
 чение 210-1. Например, код [0000000000] соответствует вещественному зна-
 чению 0/1023 или 0, тогда как код [1111111111] соответствует 1023/1023 или
 1. Оптимизируемая структура данных � � 20-битная строка, представляю-
 щая конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних
 левых 10-разрядах, тогда как x2 размещается в правой части генотипа особи
 (20-битовой строке). Генотип � � точка в 20-мерном бинарном пространст-
 ве, исследуемом ГА. Фенотип � � точка в двумерном пространстве пара-
 метров.