Спектральный метод. 
Анализ ландшафтов целевых функций при генетическом поиске

Он применяется для дискретных задач и работает с ландшафтами, представленными в виде графов. При построении таких ландшафтов используется тот факт, что эволюционные алгоритмы на каждой итерации выбирают не произвольное решение, а решение, являющееся результатом преобразования решения на предыдущей итерации по заранее заданному правилу. Если построить граф, отражающий возможные преобразования всех возможных решений, и снабдить его вершины весами, равными значениям целевой функции соответствующих этим вершинам решений, то получится ландшафт целевой функции. В генетических алгоритмах для преобразования решений используются генетические операторы. К основным операторам относятся мутация и кроссинговер. В случае гомологичных хромосом, когда каждый ген может принимать любые значения из фиксированного алфавита, мутация может состоять в изменении значения некоторого гена. В этом случае ландшафтом будет являться граф Хемминга. В частном случае, если хромосома бинарная, получается гиперкуб. В случае негомологичных хромосом можно использовать мутацию, при которой первый ген меняется местами с другим произвольным геном хромосомы. Ландшафт подобной мутации будет являться графом Кэйли. Если на каждой итерации могут меняться местами любые 2 гена хромосомы, а не только первый, то получится граф перестановочной мутации.

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

Спектральный метод базируется на том, что целевую функцию можно представить в виде ряда Фурье [Stadler, 2002], [Redys и др., 2002].

где {?k} - ортонормальный базис собственных векторов ?.

С использованием коэффициентов ряда Фурье, вычисляется спектр, который является набором (вектором) чисел, количество которых равно количеству разных собственных чисел [Redys и др., 2002]:

Запись k:??k=??k означает, что для вычисления амплитудного спектра B собственного числа? берутся только те собственные вектора? k, которые удовлетворяют соотношению: ??k=??k. Обычно амплитудный спектр нормализуется. По известному амплитудному спектру определяется среднее собственное число [Stadler, 2002], [Redys и др., 2002]:

которое может служить альтернативной мерой модальности ландшафта. Полученный спектр может быть графически отображён в виде гистограммы и визуально проанализирован.