Возможны два подхода к формированию хромосом (кодировке решений) при использовании генетических методов для структурного синтеза.
Первый из них основан на использовании в качестве генов проектных параметров. Например, в задаче размещения микросхем на плате локусы соответствуют посадочным местам на плате, а генами являются номера (имена) микросхем. Другими словами, значением -го гена будет номер микросхемы в -й позиции. Область значений вещественных параметров аппроксимируется множеством целых чисел. Часто управляемые параметры кодируют двоичными числами, тогда. хромосомы представляются битовыми строками, а параметры — частями этих строк.
Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так, для задачи размещения можно применять несколько эвристик. По одной из них в очередное посадочное место нужно помещать микросхему, имеющую наибольшее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т.д. Генетический поиск в этом случае есть поиск последовательности эвристик, обеспечивающей оптимальный вариант размещения.
Второй подход относится к генетическому программированию и реализован в методе, названном методом комбинирования эвристик (или мультиметодным генетическим алгоритмом). Этот метод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т.е. проектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на обслуживание. Пусть — число работ, — число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь генов и общее число отличающихся друг от друга хромосом заметно превышает наибольшее из чисел и .
Согласно методу комбинирования эвристик, число генов в хромосоме в два раза меньше, чем в первом подходе, и равно . Поэтому если число используемых эвристик равно , то мощность множества возможных хромосом уже несравнимо меньше, а именно

Очевидно, что меньший размер хромосомы ведет к лучшей вычислительной эффективности, а меньшее значение позволяет быстрее найти окрестности искомого экстремума. Кроме того, в методе комбинирования эвристик все хромосомы, генерируемые при кроссовере, будут допустимыми. В то же время при применении обычных генетических методов необходимо использовать процедуры типа PMX для корректировки генов, относящихся к номерам в очереди на обслуживание, что также снижает эффективность поиска.
Список литературы
1. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации// Информационные технологии, 1999, № 1.