автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Исследование ландшафтов целевых функций при эволюционной оптимизации

На правах рукописи

КОЛЯДА Александр Владимирович

ИССЛЕДОВАНИЕ ЛАНДШАФТОВ ЦЕЛЕВЫХ ФУНКЦИЙ «'РИ ЭВОЛЮЦИОННОЙ ОПТИМИЗАЦИИ

Специальность:

05.13 01 - системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Таганрог 2005

Работа выполнена в Таганрогском Государственном Радиотехническом Университете (ТРТУ)

Научный руководитель:

заслуженный деятель науки РФ, д-р техн. наук, проф. Курейчик В.М.

Официальные оппоненты:

д-р техн. наук, проф. Колесников A.A. д-р техн наук, проф. Ромм Я.Е.

Ведущая организация: Федеральное Государственное унитарное предприятие Таганрогский НИИ связи (г.Таганрог).

Защита состоится « 1 » июля 2005г. в 14.20 на заседании диссертационного совета Д212.259.03 по защите диссертаций при Таганрогском государственном радиотехническом университете по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в библиотеке Таганрогского Государственного радиотехнического университета.

Автореферат разослан «_» июня 2005г.

Учёный секретарь диссертационного совета д-р техн. наук, проф.

А. Н. Целых

Щ-Г

е/м

3 М^г//

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы.

В настоящее время разрабатываются эволюционные (ЭА) и генетические алгоритмы (ГА) для решения оптимизационных задач. При этом строятся новые целевые функции (ЦФ), обеспечивающие получение одинаковых оптимальных решений. Используя одни ЦФ, ЭА постоянно попадают в локальные оптимумы, а, используя другие, отыскивают июбальный. Поэтому актуальной является задача выбора эффективной ЦФ на ранней стадии разработки новою алгоритма. Для выбора такой функции распространённым является метод, основанный на статистических исследованиях. Его основным недостатком является необходимость многократного запуска уже реализованного алгоритма на одних и тех же тестовых примерах Поэтому задача поиска новых подходов к анализу ЦФ является важной. Другой подход основан на анализе ландшафтов ЦФ. Разработанные в его рамках методы ориентированы на получение интегральных параметров ландшафта ЦФ, которые определённым образом характеризуют её сложность для ЭА По сравнению с традиционным подходом анализа ЦФ, данный подход имеет следующие преимущества: во-первых, для сп использования не требуется программная реализация ГА и, во-вторых, ЦФ па конкретном тестовом примере анализируется один раз По данным методам нет чётких рекомендаций, каким образом используя интегральные параметры ландшафтов сравнивать эффективности ЦФ. В спектральном методе в качестве интегрального параметра ландшафта выступает спектр, то есть вектор чисел, что усложняет его использование для автоматического сравнения эффективностей ЦФ. Таким образом, исследование ландшафтов ЦФ эволюционных и генетических алгоритмов является актуальной задачей.

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

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

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

3. Разработаны модифицированные алгоритмы для - реализации и тестирования, найденных методов анализа ландшафтов ЦФ, позволяющие автоматизировать процесс расчета интегральных параметров:

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

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

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

Научная новизна диссертационной работы заключается в следующем:

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

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

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

4 Разработан алгоритм аппроксимации многомерной поверхности при помощи нейронной сети.

Практическую ценность работы представляют:

1. Алгоритм и программа оценки ЦФ по методу барьерных деревьев.

2. Алгоритм и программа оценки ЦФ по методу, основанному на спектральной теории.

3 Алгоритм и программа аппроксимации ландшафта ЦФ при помощи нейронной сети.

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

5. Осуществлена проверка разработанного комплекса программ на предмет правильности принимаемых решений относительно целесообразности применения той или иной ЦФ для решения оптимизационных задач ГА. В качестве тестовых использовались задача о рюкзаке и выбора оптимальных параметров вибраторных антенн.

Реализация результатов работы.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также в научно-исследовательских работах, выполненных по гранту «Многоальтернагивные алгоритмы эволюционных вычислений».

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтенир лекций по курсам «Методы оптимизации-), «Эволюционное

моделирование и генетические алгоритмы», «Лингвистическое и программное обеспечение».

Основные положения. выносимые на защиту: 1. Модифицированные алгоритмы расчета инте1ральных параметров ландшафтов ЦФ на основе барьерных деревьев и спектральной теории. • 2. Принципы выбора эффективных ЦФ на основе анализа интегральных параметров их ландшафтов.

3. Метод сравнения спектров на основе новых интегральных параметров, р позволяющий точнее определять эффективность ЦФ, а также автоматизировать этот процесс.

Апробация работы и публикации.

Результаты работы докладывались и обсуждались на Всероссийской научной конференции с международным участием молодых учёных и аспирантов, "Новые ' информационные технологии. Разработка и аспекты применения" (г. Таганрог 2002г ), на Международном научно-практическом семинаре, "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна 2003г.), на Научной сессии МИФИ-2003 "Интеллектуальные системы и технологии" (Москва 2003г.), на Всероссийских научных конференциях студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог 2000г., 2002г., 2004г.).

Публикации.

Результаты диссертации отражены в 9 печатных работах. Структура и объём диссертационной работы.

Диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и приложения. Работа содержит 164 стр.. а также 46 рис., 13 таблицы, список литературы из 105 наименований, 50 стр. приложений и актов об использовании.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, сформулированы пели, приведены сведения о полученных научных и практических результатах, реализации и внедрении результатов работы, апробации, дано общее описание выполненной работы

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

Выделен класс задач дчя которых строятся непрерывные ландшафты ЦФ На примере выбора оптимальных параметров вибраторной антенны проиллюстрированы

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

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

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

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

h{x,) = f(xt,xj) - f(x, )\Xj :f(Xj) < fix,),

где: x - локальный минимум, f(x) - значение ЦФ в нём,

f(x„xj) - минимальный барьер ,

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

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

В(х,) = гшп{я*,, ) - fix, )\Xj: f(Xj) < f(x,)},

где:

' fix,) и fix,) - значения ЦФ в локальных оптимумах i и j,

fix^) - минимальный барьер, который необходимо преодолеть, чтобы

попасть из локального оптимума i в локальный оптимум j.

' Барьер - это наивысшая точка некоторого пути.

Параметр В это минимальная высота, на которую нужно подняться относительно некоторого минимума г, чтобы попасть в один из минимумов, имеющих меньшее значение, чем значение минимума г. Для того чтобы получить только один интегральный парамегр для всего ландшафта достаточно выделить из всех локальных оптимумов, тот локальный оптимум, выход из которого наиболее сложен. Значение В такого оптимума называется глубиной ландшафта и обозначается символом D. Для сравнения ландшафтов, различающихся по величине, берётся отношение глубины D '/ общей высоте ландшафта, которое называется сложностью iff. Для сравнения ландшафтов ЦФ используются 2 параметра - глубина D и сложность у/. Г чубина D определяется соотношением:

D = тах{й(л- )\xt * хтт }.

Сложность поверхности определяется соотношением:

{ Ш.) ] V = max „ , „-г К ^ ■

Для гладкой поверхности (с одним минимумом, являющимся глобальным) все эти параметры равны нулю. Таким образом, чем ближе к нулю глубина и сложность поверхности, тем поверхность ближе к классу гладких Следует отметить, что сложность поверхности !// является относительным параметром и поэтому может применяться для сравнения различных по размеру ландшафтов ЦФ.

В данной главе приводится описание разработанных алгоритмов, позволяющих решить следующие проблемы:

• Выделение из исходного набора точек поверхности точек локальных оптимумов.

• Нахождение пути из одного локального оптимума в дру1 ой.

• Построение барьерного дерева.

Основная идея определения всех локальных оптимумов состоит в предварительной дискретизации пространства неравномерной сеткой После этого для определения является ли некоторая точка локальным или глобальным оптимумов достаточно просмотреть соседние для неё точки. В результате получается линейный алгоритм порядка 0(3 n N), где N - количество точек исходной выборки, an- размерность пространства. Структурная схема разработанного алгоритма показана на рис. 1.

Рис. 1. Структурная схема алгоритма выделения всех локальных оптимумов

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

Описывайся метод анализа ландшафтов ЦФ, основанный на спектральной теории. Этот метод предназначен для анализа ландшафтов ЦФ, представленных в виде графов. Д1я матрицы, являющейся результатом разности диагональной матрицы степеней вершин и матрицы смежности графа:

А

определяются собс!венные значения и собственные вектора Далее собственные значения вместе с собственными векторами сортируются в порядке возрастания '.об', тонных значений, а из собственных векюров формируется матрица. Далее эта машину умно,кается на вектор весов графа. Получается вектор вида у=(а!а->а? а„| Для произвольного ландшафта амплитудный спектр определяется соотношением:

А Л <рк

Запись к.Дф^=?.фк означает, что для вычисления амплитудного спектра В собственною числа X берутся только те собственные вектора фу, которые удовлетворяют соотношению Лф^Х.фь другими словами используются только те компоненты, полученного вектора V, которые соответствуют данному собственному числу. Обычно, амплитудный спектр нормализуется путём его деления на величину

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

к

число:

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

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

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

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

• Ввод исходных данных.

• Возможность визуальной оценки ЦФ экспертом.

• Нахождение всех локальных минимумов.

• Нахождение глобального минимума.

• Определение барьерных деревьев.

• Определение глубины

• Определение сложности.

Описана проблема, связанная с тем, что некоторые точки ландшафта могут быть приняты за локальные минимумы, хотя таковыми не являются. Это связано с

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

Программа LANDS написана на языке С++ в среде разработки Microsoft Visual С++ • и функционирует в операционной системе Windows 98 и выше. Для анализа одной поверхности ЦФ, содержащей 1000 точек, требуется примерно 3 Мб оперативной памяти. При этом на 1ВМ®-совместимом компьютере с процессором Pentium II 400МГц и оперативной памятью 300Мб анализ такой поверхности выполняется за 0.3 секунды. Вычислительные эксперименты показали, что временная сложность реализованных в ней алгоритмов линейна, что подтверждает теоретические оценки. Эксперименты подтвердили первоначальное предположение о том, чго чем ближе к нулю глубина и сложность ландшафта, тем эффективнее его ЦФ для ГА.

Программа SPECTR предназначена для расчёта спектра ландшафта ЦФ. Сервисные возможности программы включают.

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

» Расчёт собственных чисел, собственных векторов, амплшудного спектра и ряда интегральных параметров спектра

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

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

Программа SPECTR написана на языке С......• в среде разработки Microsof Visual С++

я функционирует в операционной системе Windows 98 и выше. Пространственная сложность пропорциональна О(гг), а временная сложность - 0(п3) Например, для анализа одного гиперкуба 7-й степени, то есть графа со 128 вершинами требуется примерно 2 Мб оперативной памяти При этом на 1ВМф-совместимом компьютере с процессором Pentium II 400МГц и оперативной памятью 300Мб его анализ выполняется примерно за 13 секунд. В таблице I приводятся результаты вычислительных экспериментов по определению ВСА.

Таблица 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 показана взаимосвязь компонентов комплексного подхода

Запр-х-на^* гонвращчс тар ътуав

, Решатель

---2X3

\ эадв<*и ' I

«а

ГврЯ^^А

[Нарамвтрк/

—гировщик |

-Г-^Ч -

Решатель г встироащикк

г----

-■I Реш*тегь

/

1 тдам^ж-з!

Рис 2 Связь компонентов комплексного подхода выбора эффективного алгоритма Описана программа, реализующая разрабоханный комплексный подход, в которую был ¡аложен следующий набор различных вариантов описанных элементов

1. Генератор параметров задачи.

• Параметры задачи генерируются случайным обраюм.

• Параметры задачи принимаются извне

2. Решатель задачи;

• Г1ГА дгя решения задачи о рюкзаке.

• Удалённый Позволяет запрашивать решение задачи извне

3 Анализатор (тестировщик), тестирующий алгоритм и вьщаюший некоторую интегральную численную оценку эффективности алгоритма

• Традиционный Осуществтяет статистический анализ.

• Спектральный

• На основе метода барьерных деревьев.

Датее описываются чкснсриментальныс исстедования по выявлению зависимости спектра от характера поверхности На рис 3 приводится связь спектра с характером ландшафта.

На основе проведённых вычислительных экспериментов сделаны следующие

выводы:

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

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

3 Исходя из формулы расчёта Яср видно, что чем больше выделяется одна составляющая спектра, тем ближе значение Аср к значению одного из собственных чисел. Это подтверждается вычислительным экспериментом.

[у 3 96657 )

Спектр не зависит от

типа экстремума

I- I:

_ J . _1

1

Вид спектра существен---- но зависит

^^ от | , соотношени

я размеров

|___^ глобального

1 У"4 592271 и локальных оптимумов

IV 5 26586 |

(V6 75165 | Спектр

1 - 1, 1 фактически

---------, игнорирует

незначи-

Г - IV з ш< | |1 . . тельные

■ шерохова-

тости

поверхности

1 ~\Г - 1 | у 3 718871

4. __] : . И ....; .

IV4 ид»| Чем больше

бассейн, , , , тем сильнее

выделяется !У<э«в| одна

' компонента

I 1 I , ; . спектра

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

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

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

Проведённые экспериментальные исследования позволили сделать выводы о визуальном сравнении спектров. Для возможности автоматического сравнения спектров необходимо по возможности свести вектор спектра к интегральному параметру, выражающемуся одним числом Указывается, что использование среднего собственного числа лср не однозначно. Поэтому были разработаны новые интегральные параметры спектра, которыми являются:

1. Разность ц между величинами двух самых больших компонентов спектра Чем больше эта разница, тем эффективнее ЦФ для ГА.

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

Рис 4. Результаты вычислительных экспериментов по выявлению связи вида спектра с

эффективностью ПГА. Далее приводится анализ тестовых функций де Йонга. При этом исполыуются как ранее известные параметры ландшафтов- (непосредственно спектр и среднее собственное число1), так и новые интегральные параметры спектра (разность между

величинами двух самых больших компонентов спектра ц и сложность поверхности спектра у). Отмечается, в частности, что:

• спектральный метод можеьбыть применён только для дискретных ландшафтов;

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1 Разработан алгоритм анализа ландшафтов ЦФ по методу барьерных деревьев Построен алгоритм поиска локальных оптимумов и путей из одного локального оптимума в другой, основанный на волновом принципе Приведён алгоритм построения барьерного дерева Временная сложность алгоритма равна О(п) Программа написана на языке в среде разработки Microsof Visual С4— и функционирует в операционной системе Windows 98 и выше. 2. Разработан алгоритм анализа ландшафтов ЦФ по спектральному методу. Для этого выбран метод расчёта собственных чисел и собственных векторов. Осуществлена программная реализация разработанного алгоритма, которая позволяет

автоматизировать процесс анализа ЦФ по спектральному методу. Проведенные исследования подтвердили временную сложность 0(п3) и пространственную сложность 0(п2). Программа написана на языке С++ в среде разработки Microsof Visual C+_L и функционирует в операционной системе Windows 98 и выше.

3. Установлена зависимость между видом и параметрами амплитудного спектра ландшафта ЦФ и её сложностью.

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

i автоматизировать процесс выбора эффективной ЦФ.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. A.B. Коляда "Графический редактор для синтеза нейронных сетей". Тезисы докладов. VI Всероссийская научная конференция студентов и аспирантов, "Техническая Кибернетика, Радиоэлектроника и системы управления", КРЭС 2002, с.105.

2. A.B. Коляда, Л.А. Зинченко "Исследование ландшафтов целевых функций в многокритериальной эволюционной оптимизации". Материалы докладов. Пятая всероссийская научная конференция с международным участием молодых учёных и аспирантов, "Новые информационные технологии. Разработка и аспекты применения", Таганрог 2002, с.53-54.

3. AB. Коляда "Выбор целевых функций в системах эволюционного проектирования". Сборник научных трудов. Научная сессия МИФИ-2003, Том 3 "Интеллектуальные

' системы и технологии", Москва 2003, с.126-127.

4 Зинченко Л.А, Сорокин С.Н., Коляда A.B. "Сравнение поверхностей функций пригодности для систем эволюционного проектирования". П-й Международный

" научно-практический семинар, "Интегрированные модели и мягкие вычисления в

искусственном интеллекте'". Сборник научных трудов, Коломна 2003, с 265-269.

5 А.В.Коляда, И.В Мухлаева, В.В. Янушко "Ландшафты функции пригодности в эволюционной оптимизации". Тезисы - докладов "4V всероссийская научная конференция с международным участием ТРТУ, Таганрог, 2003, с. 316-319.

16

€1020 4

5 Л.А.Зинченко, А В.Коляда. "Анализ спе пригодности и его применение в з< Перспективные информационные тех №4(16)/2003. Таганрог 2003,. с. 16-25.

и

>i

7. A.B. Коляда. "Программа аппроксимащ помощи нейронной сети". Тезисы

и я

конференция студентов и аспи 01Э1 t, «

Радиоэлектроника и системы управления' 8 Зинченко JI.A., Сорокин С.Н., Коляда a.b. программа расчета параметров ландшафтов целевых функций (LAND). Свидетельство Гос. Патента РФ об i официальной регистрации программы для ЭВМ №2003611016 от 28.04.2003 9. Коляда A.B., Курейчик В.М. Программа аппроксимации ландшафтов целевых функций при помощи нейронной сети (AproNN). Свидетельство Гос. Патента РФ об официальной регистрации программы для ЭВМ №2005610977 от 22.04.2005 10 Коляда A.B., Курейчик В.М. Программа анализа ландшафтов целевых функций по методу, основанному на спектральной теории (SPECTR). Свидетельство Гос. Патента РФ об официальной регистрации программы для ЭВМ №2005610979 от 22.04.2005

Личный вклад автора в работах, опубликованных в соавторстве: [2,4,8] - разработка алгоритма расчёта интегральных параметров ландшафтов целевых функций на основе барьерных деревьев; [5,6] - программная реализация алгоритма расчета спектра поверхности целевой функции, а также исследования связи спектра с характером галдшафта и сложностью ЦФ для ГА: [9] - разработка алгоритма аппроксимации при томотци нейронной сети, программная реализация, отладка программы, анализ результатов; [10] - разработка алгоритма расчёта собственных чисел, собственных секторов и спектра ландшафта ЦФ, программная реализация, отладка программы, анализ результатов.

Соискатель

Типография Таганрогского государственного радиотехнического университета.

Заказ № /36_

Тираж 100экз. 2005 г.

ВВЕДЕНИЕ.

1. ПРИМЕНЕНИЕ АНАЛИЗА ЛАНДШАФТОВ ДЛЯ ВЫБОРА ЭФФЕКТИВНОЙ ЦЕЛЕВОЙ ФУНКЦИИ.

1.1. Анализ методов решения оптимизационных задач.

1.2. Анализ целевых функций.

1.3. Постановка задачи диссертационной работы.

1.4. Использование ландшафта целевой функции для оценки её эффективности.

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

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

Задачами оптимизации являются задачи поиска оптимального решения в пространстве допустимых решений. Разработка новых методов и алгоритмов ^ для решения различных оптимизационных задачи по-прежнему продолжается.

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

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

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

Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда [3,4,5]. Де Йонг (De Jong) предложил идею анализа генетических алгоритмов. Суть его идеи заключается в том, что эффективность генетического алгоритма проверяется на задаче поиска минимума ряда тестовых целевых функций. Им же был предложен этот набор тестовых целевых функций.

Однако оставалась обратная проблема, заключающаяся в том, что для некоторой оптимизационной задачи требуется выбрать целевую функцию, обеспечивающую наибольшую эффективность генетического алгоритма для решения этой задачи. Сюда же относиться проблема определения целесообразности применения генетических алгоритмов для решения конкретной задачи. Поэтому требовались методы анализа целевых функций, позволяющие определять применимость целевой функции для генетических алгоритмов. К настоящему времени поиском методов анализа целевых функций занимается Питер Стадлер [6,7]. В его работах особое внимание уделяется ландшафтам целевых функций. Он указывает на возможность их использования для анализа целевых функций. Его методы анализа целевых функций базируются на анализе интегральных параметров их ландшафтов. Для получения этих параметров разработаны различные методы - метод барьерных деревьев и метод, основанный на спектральной теории. Однако для практического использования его методов необходимы алгоритмы, позволяющие быстро выделять локальные минимумы из выборки точек поверхности, алгоритмы, позволяющие находить пути из одного локального минимума в другой и алгоритмы, позволяющие быстро рассчитывать спектр поверхности. Кроме того, требует дальнейшего развития метод, основанный на спектральной теории, в частности необходимо определить взаимосвязь между спектром поверхности целевой функции и эффективностью генетических алгоритмов, которые её используют, а также разработать методы автоматического сравнения спектров. Таким образом, анализ ландшафтов целевых функций является новой и малоизученной стратегией выбора того или иного метода или целевой функции для решения оптимизационных задач.

Известно [8,9,10,11], что алгоритмы эволюционных вычислений хорошо находят решения для одномодальных целевых функций. В случае многомодальных целевых функций для них возможно возникновение эффекта преждевременной сходимости, когда результаты работы алгоритма не улучшаются, хотя оптимальное решение не найдено. Для преодоления эффекта преждевременной сходимости существует множество методов. Один из них состоит в выборе эффективной целевой функции. Операторы селекции и репродукции отбирают лучшие элементы популяции на основе сведений о желаемых свойствах проектируемых объектов, представленных в виде интегрированной совокупности как целевой функции. Для повышения эффективности эволюционного поиска целевая функция должна конструироваться таким образом, чтобы отражать все требуемые характеристики проектируемого объекта и в то же время минимизировать вероятность возникновения явления преждевременной сходимости.

Критерием оптимизации обычно является изменяемый параметр исследуемой системы или явления, для которого решается оптимизационная задача. Критерии оптимизации влияют на значение целевой функции, которая, в конечном счете, является их функцией. Решение, удовлетворяющее только части критериев и обладающее тем свойством, что при незначительном изменении значений критериев оно не улучшается, называется локальным оптимумом. С точки зрения их количества и величины различают одномодальные или гладкие, холмистые и многомодальные целевые функции. Одномодальные целевые функции имеют только глобальный оптимум. В отличие от них, многомодальные и холмистые целевые функции кроме глобального оптимума имеют также и локальные оптимумы, причем их величина для холмистых целевых функций сильно отличается от величины глобального оптимума. Чем ближе к одномодальной является целевая функция некоторой оптимизационной задачи, тем эффективнее работают многие методы её решения, например, основанные на эволюционных вычислениях. Хотя есть целевые функции такие как, например, "Иголка в стоге сена" (needle-in-the-haystack) (NIAH), для которых это не верно [4,13].

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

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

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

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

Расчёт значений целевой функции может занимать значительное время, а поскольку качество анализа её ландшафта зависит от размера выборки, необходимы методы, позволяющие получить дополнительные значения целевой функции без необходимости её пересчёта. Существуют различные методы аппроксимации. В диссертационной работе для этой цели решено использовать метод, использующий для аппроксимации нейронную сеть, как метод, позволяющий эффективно распараллеливать процесс аппроксимации. В качестве аппроксимирующей сети, была выбрана конструируемая RBF-сеть [14].

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

Подводя итог, необходимо обратить внимание на следующие моменты:

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

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

• Существующие способы представления ландшафтов, а также методы их анализа не охватывают всего разнообразия целевых функций [6,7,12].

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

Учитывая вышеизложенное, можно утверждать, что тема диссертационного исследования, связанная с анализом ландшафтов целевых функций и разработкой программных комплексов, позволяющих автоматизировать процесс анализа, является АКТУАЛЬНОЙ.

ЦЕЛЬ диссертационной работы заключается в разработке и исследовании методов позволяющих повысить скорость и качество решения оптимизационных задач, а также сократить время тестирования алгоритмов за счёт предварительного анализа целевых функций, сводящегося к анализу ландшафтов целевых функций. Для достижения поставленной цели были решены следующие задачи:

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

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

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

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

4. Проведены вычислительные эксперименты, в ходе которых определены области применения метода барьерных деревьев и метода основанного на спектральной теории.

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

6. Осуществлена проверка разработанного комплекса программ на предмет правильности принимаемых при помощи него решений относительно целесообразности применения той или иной целевой функции для решения некоторой задачи генетическими алгоритмами. В качестве тестовых задач использовались задача о рюкзаке и задача выбора оптимальных параметров вибраторных антенн. При этом для задачи о рюкзаке: a. Сформирован набор различных целевых функций для решения задачи о рюкзаке. b. При помощи разработанного комплекса априорно выбрана эффективная целевая функция. c. Разработан генетический алгоритм, при помощи которого проведены статистические исследования всех разработанных целевых функций. Используя результаты исследований, выбрана наилучшая целевая функция. d. Осуществлено сопоставление результатов априорных и статистических исследований. Для задачи выбора оптимальных параметров вибраторных антенн проводились аналогичные исследования за тем исключением, что в них подбирался эффективный набор штрафных коэффициентов.

МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на использовании элементов теории множеств, теории графов, теории алгоритмов, теории комбинаторной оптимизации, элементов теории статистических вычислений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:

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

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

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

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

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

6. Разработан алгоритм аппроксимации многомерной поверхности при помощи нейронной сети.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют: Разработанный комплекс программ и алгоритмов, который включает в себя:

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

14 деревьев,

2. алгоритм и программу оценки целевой функции по методу, основанному на спектральной теории,

3. алгоритм и программу аппроксимации ландшафта целевой функции при помощи нейронной сети,

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

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

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

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

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе №12353 «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений», а также в научно-исследовательских работах, выполненных по гранту РФФИ №12380 (№04-01-00174) «Многоальтернативные алгоритмы эволюционных вычислений».

Материалы диссертации были использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций по курсам «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Лингвистическое и программное обеспечение».

АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на Всероссийской научной конференции с международным участием молодых учёных и аспирантов, "Новые информационные технологии. Разработка и аспекты применения" (г. Таганрог 2002г.), на Международном научно-практическом семинаре, "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна 2003г.), на Научной сессии МИФИ-2003 "Интеллектуальные системы и технологии" (Москва 2003г.), на Всероссийских научных конференциях студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог 2000г., 2002г., 2004г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 12-ти печатных работах. Запатентовано 1 авторское свидетельство для программ ЭВМ «Программа расчёта параметров ландшафтов целевых функций (LAND)»

СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и приложения. Работа содержит 164 стр., а также 46 рис., список

3.7. Выводы и рекомендации

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

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

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

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

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

3.8. Практическое использование разработанного метода на примере задачи о рюкзаке

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

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

Для выбранной задачи о рюкзаке были придуманы несколько целевых функций.

Традиционная: (1) к

Несколько модифицированных функций: м=Хл2 (2) к

М = Хл3 (3) к

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

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

1. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificialpi Intelligence. USA: University of Michigan, 1975.

2. Holland J.H. "Genetic Algorithm, Scientific American, July 1992.

3. Goldberd D. E. Genetic Algorithms in Search, Optimization and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989, 412 p.

4. J. Horn and D.E. Goldberg, "Genetic algorithm difficulty and the modality of fitness landscapes", in FOGA 3, D. Whitley and M.D. Vose (ed.), Morgan Kaufmann: San Francisco, 1995, pp. 243-271.

5. Goldberg D.E. Genetic algorithms in search, optimization & machine learning.

6. University of Alabama. Addison-Wesley, 1989.

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

8. Christian M. Redys and Peter F. Stadler "Combinatorial landscapes". SIAM Review, 44, p.3-54, 2002.

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

10. Зинченко JI.A. «Алгоритмы численно-аналитического моделирования и средства программной поддержки САПР элементов автогенераторных датчиков». Таганрог, ТРТУ, 1999г. 194с.

11. P. Bentley (ed.): Evolutionary Design by Computers. Morgan Kaufmann, 1999.

12. JI.A. Гладков, JI.A. Зинченко, B.B. Курейчик, B.M. Курейчик, Б.К. Лебедев, E.B. Нужнов, C.H. Сорокин. «Методы генетического поиска».

13. Под ред. В.М. Курейчика. Таганрог, изд-во ТРТУ, 2002, 147с.

14. P.F. Stadler, Ch. Flamm. Barrier Trees on Poset-Valued Landscapes. Genet. Prog, and Evolv. Mach., 4: 7-20 (2003)

15. Вороновский Г.К. и др. «Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности». Харьков 1997

16. КурейчикВ.М. Математическое описание конструкторского и технологического проектирования с применением САПР. Москва: Радио и связь, 1990.

17. Никифоров A.M. Диссертационная работа. Разработка параллельного генетического алгоритма размещения блоков ЭВА. Таганрог 2002.

18. S.Wright, The roles of mutation, inbreeding, crossbreeding and selection in evolution, in Proceedings of the Sixth International Congress on Genetics, D.F. Jones, ed., vol. 1, 1932, pp. 356-366.

19. S.Wright, "surfaces" of selective value, Proc. Nat. Acad. Sci. USA. 58 (1967), pp. 165-172

20. M. Garey, D. Johnson. Computers and Intractability. A Guide to the Theory of NP Completeness (Freeman, San Francisco, 1979)

21. В.В. Курейчик. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

22. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ.- М.: Мир, 1984.

23. Методы генетического поиска. Под редакцией В.М. Курейчика. Изд-во ТРТУ, Таганрог, 2002, 145с.

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

25. А.В. Коляда "Выбор целевых функций в системах эволюционного проектирования". Сборник научных трудов. Научная сессия МИФИ-2003, Том 3 "Интеллектуальные системы и технологии", Москва 2003.

26. R. Merris. Lin Alg. Appl. 39, 19-31 (1995)

27. J.C.Culberson, Mutation-crossover isomorphism and the construction of discriminating functions, Evol. Сотр., 2 (1995), pp,279-311.

28. J.H. Gillespie. Molecular evolution over the mutation landscape, Evolution, 38 (1984), pp.1116-1129.

29. КурейчикВ.В. Концепция оптимизации на основе моделирования эволюции // Новые информационные технологии. Разработка и аспекты применения. Таганрог: изд-во ТРТУ, 2000; стр.49-51.

30. Курейчик В.В. Эволюционное моделирование. Учебное пособие. Таганрог, 2003.

31. Т. Jones, One operator, one landscape, Tech. Report #95-02-025, Santa Fe Institute, 1995.

32. P. Gitchoff and G.P. Wagner, Recombination induced hypergraphs: A new approach to mutation-recombination isomorphism, Complexity, 2 (1996), pp. 47-43.34