В задачах структурного синтеза любая структура (альтернатива) представляется значениями структурных параметров множества . В генетических методах (ГМ) множеству соответствует запись, называемая хромосомой, элементы хромосомы соответствуют параметрам xi, их называют генами, а значения генов - аллелями. Каждый ген размещается в хромосоме в некоторой позиции - локусе. В случае геометрической интерпретации каждому гену соответствует одна из осей координатного пространства, а хромосоме – некоторая точка поискового пространства.
Очевидно, что в большинстве практически значимых задач структурного синтеза число возможных альтернатив столь велико, что явное представление множества альтернатив невозможно. Поэтому в каждый момент поиска генетический алгоритм (ГА) оперирует подмножеством альтернатив мощности N, представляющим некоторые N точек пространства структурных параметров. Это подмножество называют популяцией, а N - размером популяции. Хромосома, представленная конкретными значениями своих генов, есть проектная альтернатива или экземпляр хромосомы.
Основная идея ГА заключается в эволюции популяции, повторяющей некоторые черты эволюции организмов в живой природе. Если цель эволюции в живой природе - обеспечение наибольшей жизнеспособности популяции в условиях окружающей среды, то цель эволюции в ГА - получение экземпляров с наилучшими значениями определенных критериев, характеризующих качество экземпляра, т.е. синтезируемой структуры. Как и в других методах синтеза, в ГМ при наличии нескольких критериев задача должна быть сведена к однокритериальной путем свертки векторного критерия. Получающуюся целевую функцию часто называют функцией полезности. Любой конкретный экземпляр хромосомы называют генотипом, а множество значений характеризующих хромосому критериев - фенотипом.
Таким образом, цель генетического поиска - найти экземпляр хромосомы, имеющий значение функции полезности, максимально близкое к ее экстремальному значению. Направленный поиск малой окрестности экстремума осуществляется в ГА с помощью генетических операторов выбора родителей, кроссовера, мутации, селекции, переупорядочения, поясняемых ниже.
Генетические алгоритмы имитируют эволюционный процесс приближения к оптимальному результату, начиная с некоторого исходного поколения структур, представленных экземплярами хромосом. Этот процесс в базовом ГА является вложенным циклическим вычислительным процессом. Внешний цикл имитирует смену поколений. Во внутреннем цикле формируются члены очередного поколения.
Члены исходного поколения генерируются случайным образом. При этом для каждого гена задана область определения, например, в виде интервала [Xmini, Xmaxi], и значения генов выбираются с равной вероятностью в его пределах.
Результатом каждого очередного витка внешнего цикла является новое поколение, о качестве которого судят по экземпляру хромосомы с лучшим значением функции полезности F.
Характер приближения к экстремуму обычно таков, что на начальных витках скорость улучшения целевой функции довольно значительная, но по мере приближения к экстремуму она замедляется и может наступить прекращение улучшения F на некотором удалении от экстремальной точки. Это явление называют стагнацией. Обычно оно происходит из-за вырождения популяции - потери разнообразия генного материала. Поиск прекращают чаще всего при появлении признаков стагнации, о чем свидетельствует неулучшение целевой функции на протяжении нескольких последних поколений, либо по исчерпании лимита отведенного времени на решение задачи.
Во внутреннем цикле базового ГА выполняется следующая последовательность генетических операторов: выбор родителей, кроссовер (скрещивание), мутации, формирование нового поколения.
Порождение новых экземпляров хромосом происходит в процессе скрещивания (кроссовера) родительских пар. Выбор пары членов популяции в качестве родителей производится случайным образом среди членов данного поколения. При этом вероятность выбора экземпляров в качестве родителей в базовом генетическом алгоритме зависит от их значений функции полезности, т.е. чем лучше значение F, тем выше должна быть вероятность выбора.
Чаще всего для выбора родителей применяют правило, называемое правилом рулетки. В нем вероятность Pk выбора k-го члена популяции в качестве родителя определяется как отношение полезности данного члена к суммарной полезности всех членов популяции. Если целевая функция минимизируется, то
=(-)/(-)
где - функция полезности -го экземпляра, - максимальное значение функции полезности среди членов данного поколения, - размер популяции.
Кроссовер (кроссинговер) заключается в разрыве двух выбранных родительских хромосом и рекомбинировании образовавшихся хромосомных отрезков, что дает пару хромосом потомков. На рис. 1 представлен пример кроссовера (разрыв после третьего локуса) и рекомбинации отрезков. Здесь два верхних экземпляра - родители, два нижних - потомки. Для наглядности гены одного родителя обозначены буквами, другого - цифрами.
Рис. 1.  Кроссовер и рекомбинация
Мутации, т.е. случайные изменения некоторых аллелей, предназначены для реализации поиска в пространстве всех возможных экземпляров хромосом. Без мутаций поиск не может выйти за пределы того подмножества экземпляров хромосом, в котором аллели совпадают с сгенерированными значениями генов в начальной популяции. Например, если в некотором гене, отображающем дни недели, в хромосомах начальной популяции оказались сгенерированными только значения "понедельник", "среда", "четверг" и "воскресенье", то при выполнении операторов кроссовера или селекции значения "вторник", "пятница" и "суббота" появиться не могут. Мутации устраняют этот недостаток. Они происходят в очередном гене с некоторой заданной вероятностью Рм, эта вероятность обычно выбирается достаточно малой (сотые-тысячные доли). При мутациях значение гена выбирается случайным образом среди множества возможных значений, т.е. в нашем примере произойдет равновероятный выбор среди всех семи возможных дней недели.
Формирование нового поколения (селекция) - это отбор членов нового поколения среди потомков, полученных в результате кроссовера и мутаций в данном поколении. В базовом ГА в новое поколение включается лучший из двух потомков, порожденных после кроссовера. Внутренний цикл заканчивается, когда окажется сформированным новое поколение, т.е. в нем окажется N членов.