Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Кодирование информации и формирование популяции




Читайте также:
  1. I. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ - ОТ ТЕХНОЛОГИЙ К ИНФОРМАЦИИ
  2. V. Семинар. Тема 6. Формирование информационной среды общества
  3. VII этап. Формирование эффективных условий привлечения кредитов
  4. Абсолютные и относительные параметры дохода. Источники информации о доходах и расходах населения.
  5. Автоматизированные системы обработки экономической и финансовой информации
  6. Автоматические идентификационные системы (АИС). Назначение, использование информации АИС
  7. Агрегатный индекс может быть преобразован а среднеарифметический и среднегармонический индекс при отсутствии исходной информации для расчета агрегатной формы индекса.
  8. Анализ и подготовка ценовой информации
  9. Анализ отечественного рынка средств защиты информации
  10. Антигитлеровская коалиция. Формирование коалиции

Выбор способа кодирования является одним из важнейших этапов при использовании эволюционных алгоритмов. В частности, должно выполняться следующее условие: должна быть возможность закодировать (с допустимой погрешностью) в хромосоме любую точку из рассматриваемой области пространства поиска.

Невыполнение этого условия может привести как к увеличению времени эволюционного поиска, так и к невозможности найти решение поставленной задачи.

Как правило, в хромосоме кодируются численные параметры решения. Для этого возможно использование целочисленного и вещественного кодирования.

Целочисленное кодирование.В классическом генетическом алгоритме хромосома представляет собой битовую строку, в которой закодированы параметры решения поставленной задачи. На рис. 5.2 показан пример кодирования 4-х 10-разрядных параметров в 40-разрядной хромосоме.

 

Рис. 5.2. Пример целочисленного кодирования

 

Как правило, считают, что каждому параметру соответствует свой ген. Таким образом, можно также сказать, что хромосома на рис. 5.2 состоит из 4-х 10-разрядных генов. Несмотря на то, что каждый параметр закодирован в хромосоме целым числом (в виде двоичной последовательности), ему могут быть поставлены в соответствие и вещественные числа. Ниже представлен один из вариантов прямого и обратного преобразования «целочисленный ген → вещественное число».

Если известен диапазон [xmin ; xmax], в пределах которого лежит значение параметра и m – разрядность гена, то этот диапазон разбивают на 2m равных отрезков, и каждому отрезку соответствует определенное значение гена. При этом для перевода значений из закодированного значения в дробные применяют следующие формулы:

,

,

где r – вещественное (декодированное) значение параметра, g – целочисленное (закодированное) значение параметра.

Например, если искомое значение параметра лежит в промежутке [1; 2] и каждый ген кодируется 16 разрядами, то, если содержимое гена равно ABCD16 = 4398110, то соответствующее дробное значение равно:

r = 43981 * (2 – 1)/(216 – 1) + 1 = 0,6711 + 1 = 1,6711.

Если же декодированное значение равно 1,3275, то соответствующий ген после обратного преобразования будет содержать (с округлением в меньшую сторону):



g = (1,3275 – 1)(216 – 1) / (2 – 1) = 0,3275 * 65535 = 21462,7125 » 2146210 = 0101 0011 1101 01102.

Вещественное кодирование. Часто бывает удобнее кодировать в гене не целое число, а вещественное. Это позволяет избавиться от операций кодирования/декодирования, используемых в целочисленном кодировании, а также увеличить точность найденного решения. Пример вещественного кодирования представлен на рис. 5.3.

Формирование начальной популяции.Как правило, начальная популяция формируется случайным образом. При этом гены инициализируются случайными значениями. Пример случайной инициализации популяции на псевдоязыке представлен ниже.

 

Рис.5.3. Пример вещественного кодирования

 

 

i = 0;

ПОКА (i < РАЗМЕР_ПОПУЛЯЦИИ) {

j = 0;

ПОКА (j < ЧИСЛО_ГЕНОВ) {

ОСОБЬ[i].ГЕН[j] = СЛУЧАЙНАЯ_ВЕЛИЧИНА;

j = j+1;

}

i = i+1;

}


Дата добавления: 2014-12-23; просмотров: 15; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2022 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты