Размещено на http://www.allbest.ru/

УДК 621.372

Таганрогский государственный радиотехнический университет, Таганрог

Повышение эффективности эволюционного проектирования на основе анализа спектральных свойств поверхности функции пригодности

Л.А.Зинченко,

А.В.Коляда

Введение

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

Один из них состоит в выборе эффективной функции пригодности [3, 4, 6]. Операторы селекции и репродукции отбирают лучшие элементы популяции на основе сведений о желаемых свойствах проектируемых объектов, представленных в виде интегрированной совокупности как функции пригодности. Для повышения эффективности эволюционного поиска функция пригодности должна конструироваться таким образом, чтобы отражать все требуемые характеристики проектируемого объекта и в то же время минимизировать вероятность возникновения явления преждевременной сходимости.

Для сравнения функций пригодности применяются различные методы. Одним из мощных когнитивных средств анализа является понятие ландшафта функции пригодности. Ландшафт функции пригодности подобен природному ландшафту [1, 2]. Поэтому, как и для природных ландшафтов, для ландшафтов функций пригодности применимы такие понятия как: хребты, пики, барьеры, равнины, впадины. Применительно к ландшафтам функций пригодности аналогом впадин являются локальные минимумы. Анализируя двух или трёхмерную поверхность функции пригодности, человек может визуально оценить, насколько хорошей для эволюционных вычислений является данная функция пригодности. Например, если поверхность имеет ярко выраженный один глубокий глобальный минимум, то вероятность нахождения его больше по сравнению с нахождением глобального минимума функции пригодности, ландшафт которой изрезан множеством примерно одинаковых локальных минимумов, не сильно отличающихся по величине от глобального минимума. Однако визуальное сравнение ландшафтов функций пригодности применимо только для одно- и двухкритериальных оптимизационных задач. Поэтому необходимы методы, позволяющие числено оценивать ландшафты функций пригодности.

Одним из методов анализа ландшафтов функций пригодности является метод барьерных деревьев [1,2,7]. Он позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Для сравнения ландшафтов функций пригодности используются 2 параметра - глубина D и сложность . Расчёт этих параметров выполняется с использованием программы LAND [7, 8].

В данной статье обсуждается метод анализа поверхности функции пригодности, основанный на спектральной теории [1, 2].

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

Суть рассматриваемого метода анализа спектральных свойств поверхности функции пригодности [1, 2] заключается в том, что поверхность представляется в виде графа, весами вершин которого являются значения функции пригодности, а рёбра показывают возможность перехода от одного значения к другому. Для графа определяются собственные значения и собственные вектора. Спектр поверхности строится как совокупность спектров найденных собственных чисел.

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

,

где

Д - симметричная матрица.

Функцию пригодности можно представить в виде ряда Фурье [1, 2]:

,

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

Для произвольного ландшафта амплитудный спектр определяется соотношением:

.

По известному амплитудному спектру определяется среднее собственное число:

,

которое может служить альтернативной мерой модальности ландшафта [1, 2].

При больших размерах матрицы вычисление собственных чисел аналитически наталкивается на большие трудности, поэтому применяются различные итерационные алгоритмы. В описываемом подходе был применён QR-алгоритм [5], заключающийся в том, что исходная матрица многократно умножается на матрицу поворота, построенную так, чтобы происходило гарантированное преобразование исходной матрицы A к диагональной матрице. После того, как будет получена диагональная матрица, на её главной диагонали будут находиться искомые собственные числа.

В описываемом подходе для ускорения QR-алгоритма применено предварительное преобразование исходной матрицы к правой почти треугольной матрице Гессинберга [5]. После расчёта собственных чисел рассчитываются собственные векторы. В описываемом алгоритме для этого используется метод Гаусса.

Для реализации и тестирования описанного выше подхода была разработана программа SPECTR. Она написана на языке C++ в среде разработки Microsof Visual C++ и функционирует в операционной системе Windows 98 и выше.

Основное окно программы SPECTR показано на рис. 1.

Рис.1. Основное окно программы SPECTR

Ввод исходных данных осуществляется во встроенном редакторе графов. Он позволяет: редактор граф экстремум функция

· Осуществлять ввод, удаление, перемещение, копирование и вставку группы вершин.

· Устанавливать веса вершин.

· Вводить и удалять рёбра.

· Масштабировать и перемещать рабочую область.

· Настраивать параметры отображения графа.

· Автоматически создавать гиперкуб с возможностью последующего задания веса вершин.

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

После внесения любых изменений в граф спектр рассчитывается автоматически. По окончании процесса расчёта в соответствующем окне отображаются:

· собственные числа

· собственные вектора

· спектр

· исходные данные

· время расчёта

Выходные данные оформляются в виде текста. Рассчитанный спектр отображается также в виде графика.

Программа SPECTR может обмениваться входными и выходными данными с внешними программами.

2. Экспериментальные исследования

Для определения эффективности реализованных в программе SPECTR методов расчёта спектра поверхности экспериментально установлена зависимость времени расчёта спектра от числа вершин (табл. 1). Экспериментальные исследования проводились на процессоре Pentium II 400МГц в операционной системе Windows Millennium.

Таблица 1