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

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

Анализ ландшафтов целевых функций при генетическом поиске Работа выполнена при финансовой подержке РФФИ (проект № 00-01-07836)

А.В. Коляда347928, г. Таганрог, пер. Некрасовский, 44, В.М.Курейчик г. Таганрог, kur@tsure.ru

Цель работы - поиск методов сокращения времени выбора эффективной целевых функций (ЦФ) оптимизационных задач. Основная задача - определить взаимосвязь между сложностью поиска оптимального решения некоторой ЦФ при помощи генетических алгоритмов и её ландшафтом. Предлагается автоматизировать процесс выбора ЦФ, подходящей для генетических алгоритмов, сократив тем самым время на разработку метода решения новой оптимизационной задачи или время на анализ нового метода решения существующей задачи.

Введение

Большое число задач искусственного интеллекта сводится к оптимизационным задачам. К настоящему времени накоплен опыт решения оптимизационных задач, как для конкретных приложений, так и в обобщенном виде. Эффективным методом решения оптимизационных задач являются на эволюционные вычисления. Важным направлением являются генетические алгоритмы (ГА) [Holland, 1992], [Курейчик, 1998], [Емельянов и др., 2003], [Гладков и др., 2004].

При разработке новых алгоритмов решения оптимизационных задач разрабатываются новые целевые функции (ЦФ), обеспечивающие получение одного и того же оптимального решения. Однако новая целевая функция может приводить как к увеличению эффективности алгоритмов, так и к её ухудшению, если речь идёт об эволюционных алгоритмах. Используя одни целевые функции, эволюционные алгоритмы часто наталкиваемся на локальные оптимумы, а, используя другие, быстро отыскивают глобальный. Поэтому существует задача выбора эффективной целевой функции на ранней стадии разработки нового алгоритма. В настоящее время распространённым методом выбора эффективной целевой функции является метод, основанный на статистических исследованиях. Его основным недостатком является необходимость многократного запуска уже реализованного алгоритма на одних и тех же тестовых примерах. Поиск методов анализа ЦФ описан в работах [Stadler, 2002], [Redys и др., 2002], где особое внимание уделяется ландшафтам ЦФ. При этом по сравнению с традиционным подходом анализа ЦФ, подход в трудах [Stadler, 2002], [Redys и др., 2002] имеет следующие преимущества: во-первых, для его использования не требуется программная реализация генетического алгоритма; во-вторых, конкретная целевая функция на конкретном тестовом примере анализируется только один раз.

Описываемый в данном докладе метод анализа ландшафтов целевых функций основан на спектральной теории. При анализе ландшафтов целевых функций возникают следующие проблемы.

1. Разработка методов представления самих ландшафтов целевых функций.

2. Разработка интегральных параметров ландшафтов, а также методов и алгоритмов их получения.

3. Определение взаимосвязи между интегральными параметрами ландшафтов и эффективностью ЦФ для ГА. Эта связь является связующим звеном между интегральными параметрами ландшафтов и ГА. Без её определения любые интегральные параметры бесполезны.

4. Разработка программного обеспечения, позволяющего эффективно использовать предложенные методы.

Цель работы - поиск методов сокращения времени выбора эффективной ЦФ оптимизационных задач. Основная задача - определить взаимосвязь между сложностью поиска оптимального решения некоторой ЦФ при помощи генетических алгоритмов и её ландшафтом. Предлагается автоматизировать процесс выбора ЦФ, подходящей для генетических алгоритмов, сократив тем самым время на разработку метода решения новой оптимизационной задачи или время на анализ нового метода решения существующей задачи.

1. Спектральный метод

генетический алгоритм ландшафт спектральный

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

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

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

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

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

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

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

2. Исследования и развитие спектрального метода

С целью автоматизации анализа ландшафтов ЦФ был разработан алгоритм расчёта спектра. Для определения собственных чисел использовался QR-алгоритм, а для собственных векторов - метод Гаусса с выбором ведущего элемента. Разработанный алгоритм был реализован в программе SPECTR, основное окно которой показано на рис. 1.

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

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

Сервисные возможности программы включают:

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

· расчёт собственных чисел, собственных векторов, амплитудного спектра и ряда интегральных параметров спектра; отметим, что точностью расчетов можно управлять;

· настраиваемый вывод результатов вычислений в текстовом виде, а также отображение спектра в виде графика;

· возможность обмена входными и выходными данными с внешними программами, что позволяет сократить время анализа и создания отчёта по множеству ландшафтов;

· экспорт, импорт различных данных.

В качестве примера, на рис. 2 показана связь эффективности простого генетического алгоритма (ПГА) с видом спектра для нескольких ЦФ (ЭПГА - процентная доля запусков ПГА, в которых был найден оптимум).

Рис 2. Связь спектра со сложностью ЦФ для ПГА

Основной вывод анализа спектрального метода заключается в том, что, чем ближе поверхность к классу унимодальных и чем больше бассейн экстремума ЦФ, тем значительнее одна компонента её спектра отличается по величине от остальных компонент, а также эффективней данная целевая функция для генетических алгоритмов. Используя эту связь можно по виду спектра визуально сравнивать эффективности целевых функций.

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

1. ? - разность между величинами двух самых больших компонентов спектра. Чем больше эта разница, тем лучше ЦФ. Этот параметр отражает свойство, заключающееся в том, что, чем больше выделяется одна компонента спектра, тем лучше ЦФ.

2. Глубина D и сложность ? поверхности самого спектра. Эти параметры отражают как величину самой большой компоненты спектра, так и модальность поверхности спектра, которая также влияет на качество ЦФ.

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

Табл. 1

Вариант практического использования покажем на примере задачи о рюкзаке. Цель - показать, каким образом можно использовать практически разработанный комплекс алгоритмов для выбора эффективной ЦФ. Постановка задачи: дан набор элементов и рюкзак. Каждый элемент имеет объём v и стоимость c. Необходимо разместить элементы в рюкзаке таким образом, чтобы их суммарная стоимость была максимальной. Проблема заключается в том, что не все элементы могут поместиться в рюкзаке.

Имеется n вещей и рюкзак.

· V={v1,v2,…,vn} - вектор объёмов вещей.

· C={c1,c2,…cn} - вектор ценностей вещей.

· Vr - объём рюкзака.

Ограничения: ?aivi?Vr, ai=[0,1],

Стандартная целевая функция: F=?ci ,

Цель: F>max.

Был сформирован набор ЦФ, включающих традиционную ЦФ

(2.1)

и несколько модифицированных ЦФ

 (2.2)

и (2.3)

Разработан ПГА решения задачи о рюкзаке, который был протестирован на тех же примерах и со всеми выбранными целевыми функциями. Случайным образом был сгенерирован набор тестовых примеров, для каждого из которых построен ландшафт и рассчитан спектр. Для каждого тестового примера и каждой ЦФ ПГА запускался по 1000 раз. Пример выбора ЦФ для данной задачи показан на рис.3. Оказалось, что выбранная ЦФ(3) является наилучшей для решения задачи о рюкзаке при помощи простого генетического алгоритма.

Рис. 3. Выбор ЦФ для задачи о рюкзаке

Заключение

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

Также результатами проведенной работы является следующее.

· Выявлена зависимость между видом и параметрами амплитудного спектра поверхности ЦФ и её сложностью с точки зрения эволюционных вычислений.

· Разработан метод сравнения спектров.

· Разработан алгоритм, позволяющий получить параметры ландшафта ЦФ по методу, основанному на спектральной теории.

Проведённые экспериментальные исследования позволяют сделать ряд выводов

· Чем ближе поверхность к одномодальной и чем больше бассейн экстремума, тем значительнее одна компонента её спектра отличается по величине от остальных компонент.

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

Основной вывод по результатам расчётов спектров поверхностей и испытаний ПГА: спектр поверхности отражает модальность функции и размер бассейна, что для многих функций является достаточным для того, чтобы сказать, будет ли ПГА хорошо работать или нет.

Список литературы

2. Курейчик, 1998 Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: ТРТУ, 1998. - 242с.

3. Емельянов и др., 2003 В.В. Емельянов, В.В. Курейчик, В.М. Курейчик. Теория и практика эволюционного моделирования. - М.: ФИЗМАТЛИТ, 2003. - 432с.

4. Гладков и др., 2004 Л.А. Гладков, В.М. Курейчик, В.В. Курейчик. Генетические алгоритмы: учебное пособие. Ростов-на-Дону:ООО «Росиздат», 2004. - 400с.

5. Stadler, 2002 Peter F. Stadler “Fitness Landscapes” in M. Lassing, and A.Valleriani (eds.), Biological Evolution and Statistical Physics, Springer-Verlag, Berlin, 2002, pp 187-207.

6. Redys и др., 2002 Christian M. Redys and Peter F. Stadler “Combinatorial landscapes”. SIAM Review, 44, p.3-54, 2002.

7. Зинченко и др., 2003 Л.А.Зинченко, А.В.Коляда. “Анализ спектральных свойств поверхности функции пригодности и его применение в задачах эволюционного проектирования”. Перспективные информационные технологии и интеллектуальные системы. Таганрог 2003.

Размещено на Allbest.ur