Исполнение ввода исходных данных во встроенном редакторе графов. Определение эффективности реализованных в программе Spectr методов расчета спектра поверхности. Нахождение глобальных экстремумов функций с использованием простого генетического алгоритма.
Аннотация к работе
Повышение эффективности эволюционного проектирования на основе анализа спектральных свойств поверхности функции пригодностиХромосома является закодированным решением, а поскольку каждому альтернативному решению соответствует значение функции пригодности, то в процессе проектирования можно выделить лучшие хромосомы (альтернативные решения). В случае многомодальных функций пригодности для них возможно возникновение эффекта преждевременной сходимости, когда результаты работы алгоритма не улучшаются, хотя оптимальное решение не найдено. Анализируя двух или трехмерную поверхность функции пригодности, человек может визуально оценить, насколько хорошей для эволюционных вычислений является данная функция пригодности. Например, если поверхность имеет ярко выраженный один глубокий глобальный минимум, то вероятность нахождения его больше по сравнению с нахождением глобального минимума функции пригодности, ландшафт которой изрезан множеством примерно одинаковых локальных минимумов, не сильно отличающихся по величине от глобального минимума. Суть рассматриваемого метода анализа спектральных свойств поверхности функции пригодности [1, 2] заключается в том, что поверхность представляется в виде графа, весами вершин которого являются значения функции пригодности, а ребра показывают возможность перехода от одного значения к другому.Проведенные исследования позволяют сделать вывод, что чем ближе поверхность к одномодальной, тем значительнее одна компонента ее спектра отличается по величине от остальных компонент.
Введение
Один из наиболее эффективных подходов к автоматизации проектирования основан на эволюционных вычислениях. Их особенность состоит в том, что они моделируют процессы, протекающие в живой природе. Генетические алгоритмы, являющиеся одним из разделов эволюционных вычислений, основаны на механизмах натуральной селекции и генетики. Они моделируют процессы репродукции, скрещивания и мутации хромосом в живой природе. Хромосома является закодированным решением, а поскольку каждому альтернативному решению соответствует значение функции пригодности, то в процессе проектирования можно выделить лучшие хромосомы (альтернативные решения). Генетические алгоритмы работают не с одной хромосомой, а с популяцией хромосом (альтернативными решениями), производя тем самым поиск эффективного проектного решения сразу из нескольких точек поискового пространства. На каждой итерации генетического алгоритма происходит смена старой популяции на новую. При этом одни хромосомы переходят из старой популяции в новую, другие умирают, т.е. удаляются из популяции, а третьи являются потомками альтернативных решений старой популяции. Генетические алгоритмы используют информацию, накопленную в процессе эволюции. Это обеспечивается тем, что, в соответствии с принципом Дарвина, хромосома, имеющая лучшую функцию пригодности, имеет больше шансов «выжить», т.е. перейти в новую популяцию. Известно, что алгоритмы эволюционных вычислений хорошо находят решения для одномодальных функций пригодности. В случае многомодальных функций пригодности для них возможно возникновение эффекта преждевременной сходимости, когда результаты работы алгоритма не улучшаются, хотя оптимальное решение не найдено. Для выхода из подобной ситуации существует множество методов.
Один из них состоит в выборе эффективной функции пригодности [3, 4, 6]. Операторы селекции и репродукции отбирают лучшие элементы популяции на основе сведений о желаемых свойствах проектируемых объектов, представленных в виде интегрированной совокупности как функции пригодности. Для повышения эффективности эволюционного поиска функция пригодности должна конструироваться таким образом, чтобы отражать все требуемые характеристики проектируемого объекта и в то же время минимизировать вероятность возникновения явления преждевременной сходимости.
Для сравнения функций пригодности применяются различные методы. Одним из мощных когнитивных средств анализа является понятие ландшафта функции пригодности. Ландшафт функции пригодности подобен природному ландшафту [1, 2]. Поэтому, как и для природных ландшафтов, для ландшафтов функций пригодности применимы такие понятия как: хребты, пики, барьеры, равнины, впадины. Применительно к ландшафтам функций пригодности аналогом впадин являются локальные минимумы. Анализируя двух или трехмерную поверхность функции пригодности, человек может визуально оценить, насколько хорошей для эволюционных вычислений является данная функция пригодности. Например, если поверхность имеет ярко выраженный один глубокий глобальный минимум, то вероятность нахождения его больше по сравнению с нахождением глобального минимума функции пригодности, ландшафт которой изрезан множеством примерно одинаковых локальных минимумов, не сильно отличающихся по величине от глобального минимума. Однако визуальное сравнение ландшафтов функций пригодности применимо только для одно- и двухкритериальных оптимизационных задач. Поэтому необходимы методы, позволяющие числено оценивать ландшафты функций пригодности.
Одним из методов анализа ландшафтов функций пригодности является метод барьерных деревьев [1,2,7]. Он позволяет оценить глубину каждого локального минимума и степень его влияния на процесс эволюционного проектирования. Для сравнения ландшафтов функций пригодности используются 2 параметра - глубина D и сложность y. Расчет этих параметров выполняется с использованием программы 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
Степень гиперкуба 2 3 4 5 6 7 8
Число вершин 4 8 16 32 64 128 256
Время (сек.) 0,08 0,1 0,12 0,27 1,31 12,65 131,38
На рис. 2-7 представлены ландшафты и их спектры следующих шести функций, традиционно использующихся в качестве тестовых в эволюционных вычислениях:
;
;
;
;
;
.
В таблице 2 приведены данные по спектральным компонентам и значения средних собственных чисел.
Рис 2. Ландшафт (а) и спектр ландшафта (б) функции f1(x,y)
Рис 3. Ландшафт (а) и спектр ландшафта (б) функции f2(x,y)
Рис 4 Ландшафт (а) и спектр ландшафта (б) функции f3(x,y)
Рис 5 Ландшафт (а) и спектр ландшафта (б) функции f4(x,y)
Рис 6. Ландшафт (а) и спектр ландшафта (б) функции f5(x,y)
Рис 7. Ландшафт (а) и спектр ландшафта (б) функции f6(x,y)
Таблица 2 l1 l2 l3 l4 l5 l6 l7 l8 lcp
F1 0.000 0.579 0.125 0.164 0.096 0.019 0.008 0.008 3.81873
В табл. 3 приведены результаты экспериментальных исследований по нахождению глобальных экстремумов вышеприведенных функций с использованием простого генетического алгоритма (ПГА). Для каждой функции ПГА запускался 1000 раз.
Таблица 3
Функция Количество найденных решений (%)
ПГА1 ПГА2
F1 26.8 15.5
F2 27.8 15
F3 13.7 10.2
F4 2 1.6
F5 21.8 16.3
F6 0.1 0.2
В табл. 3 приведены данные, полученные при выборе управляющих параметров генетического алгоритма: во втором столбце - вероятность кроссинговера 50%, вероятность мутации 20%, вероятность инверсии 50%, в третьем столбце - вероятность кроссинговера 80%, вероятность мутации 2%, вероятность инверсии 2%,
Вывод
Проведенные исследования позволяют сделать вывод, что чем ближе поверхность к одномодальной, тем значительнее одна компонента ее спектра отличается по величине от остальных компонент. Анализ спектральных свойств поверхности функции пригодности позволяет определить эффективность использования генетических алгоритмов.
Список литературы
1. Peter F. Stadler “Fitness Landscapes” in M. Lassing, and A.Valleriani (eds.), Biological Evolution and Statistical Physics, Springer-Verlag, Berlin, 2002, pp 187-207.
2. Christian M. Redys and Peter F. Stadler “Combinatorial landscapes”. SIAM Review, 44, p.3-54, 2002.
3. Зинченко Л.А. «Алгоритмы численно-аналитического моделирования и средства САПР». Таганрог 1999
4. Kureichik V.M., Zinchenko L.A. Evolutionary Modelling with Hierarchy in Innovative Computer-Aided Circuit Design, IETE Journal of Research, Vol. 48, No5, 2002, pp. 361-367.
5. Корн Г., Корн Т. Справочник по математике. М.: Наука, 1980. 720 с.
6. Muehlenbein H., Kureichik V.M., Mahnig T., Zinchenko L.A., A Comparison of Different Fitness Functions for Evolutionary Analog Circuit Design, Evolutionary Methods for Design, Optimization and Control, CIMNE, Barcelona, Spain, 2003, pp.49-50.
7. Зинченко Л.А., Сорокин С.Н., Коляда А.В. “Сравнение поверхностей функций пригодности для систем эволюционного проектирования”. II-й Международный научно-практический семинар, “Интегрированные модели и мягкие вычисления в искусственном интеллекте”. Сборник научных трудов, Коломна 2003
8. Зинченко Л.А., Сорокин С.Н., Коляда А.В. Программа расчета параметров ландшафтов целевых функций (LAND). Свидетельство Гос. Патента РФ об официальной регистрации программы для ЭВМ №2003611016 от 28.04.2003