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

• Коляда, Александр Владимирович
• кандидат технических наук
• 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) действительно является наиболее пригодной для решения задачи о рюкзаке при помощи генетических алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Коляда, Александр Владимирович, 2005 год

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