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

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

КУЗНЕЦОВ Алексей Владимирович

АЛГОРИТМЫ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ ФУНКЦИЙ В ПРОСТРАНСТВЕ НЕПРЕРЫВНЫХ ПЕРЕМЕННЫХ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ-НЕРАВЕНСТВ

05.13.01 - системный аналич, управление и обработка информации (по отраслям: информатика, вычислительная техника и управление)

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

Красноярск — 2006

Работа выполнена

в ГОУ ВПО «Красноярский государственный технический университет»

Научный руководитель: док юр технических наук, профессор,

заслуженный деятель науки РФ Рубан Анатолий Иванович

Официальные оппоненты: доктор технических наук, профессор

Доррер Георгий Алексеевич

доктор технических наук, профессор Терсков Виталий Анатольевич

Ведущая организация: ГОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Рсшетнева» (г. Красноярск)

Защита состоится 26 мая 2006 года в 14:00 на заседании диссертационного совета Д 212.098.04 при Красноярском государшвенном техническом университете по адресу: ул. академика Киренского, 26, Красноярск, 660074, ауд. Д

Н-та11: sovet@front.ru

Телефон: (391-2) 912-295 (Ю ГУ, каф. САПР)

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

501.

Факс: (3912) 43-06-92 (КГТУ, для каф. САПР)

Автореферат разослан ¿Л апреля 2006 года.

Учёный секретарь диссертационного совета д.т.н.

2.006&

Ь Общая характеристика рабо! ы

Актуальность. Методы оптимизации присутствуют практически на всех этапах системного анализа, а так же в системах поддержки принятия решений. Оптимизация находит широкое применение в науке, технике, бизнесе и во многих других практических областях деятельности человека. Это мо1ух бьпь задачи: проекшрования. распределения ограниченных ресурсов, расчета траектории движения объекта, идентификации параметров и т. д. Словом, такие задачи возникают везде, где необходимо получить наилучший результат целевой функции в допустимой области, задаваемой множеством некоторых ограничений-неравенств. Целевая функция может быть многоэкстремальной, разрывной, не дифференцируемой, искаженной помехами.

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

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

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

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

Объектом исследований являются программные алгоритмы глобальной оптимизации при наличии ограничений-неравенств.

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

Цель исследований. Целью данной дитеертащюншж-ра&эты является синтез и анализ новых алгоритмов глобальГюй^гп^^^^^ ^ун! ций непре-

С.-Петербург ^

ОЭ I,

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

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

• Разработать профаммные алгоритмы глобальной оптимизации при наличии ограничений-неравенств.

• Разработать программный пакет, который позволит эффекшвно исследовать разработанные алгоритмы, а также решать различные задачи оптимизации.

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

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

• Получить различные статистические характеристики, описывающие свойства алгоритмов.

• Разработать методики подбора параметров аш ори шов для эффективного решения различных задач оптимизации.

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

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

Новые научные результаты диссертации. Разработаны и исследованы новые профаммные алюритмы глобальной оптимизации (основанные на методе усреднения координат) при наличии ограничений-неравенств:

1. Алгоритм на допустимых пробных точках [1, 2, 4].

2. Алгоритм поиска 1лавных экстремумов (глобальный экстремум и близкие к нему по функции качества) [10].

3. Алгоритм с использованием двух видов свертки ограничений в штрафную функцию: прямая свертка и свертка в относительных величинах [3, 5].

4. Алгоритм прямого учета ограничений в ядрах процедуры усреднения координат [2, 4].

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

Значение для практики. Разработан исследовательский профаммный пакет «Global Optimizer vl.O» [12]. Создана методология конструирования программных алгоритмов глобальной оптимизации, разработаны способы исследования влияния параметров алгоритмов на качество их работы. Полученные в

диссертационной работе рекомендации по выбору типа алгоритма и подбору его параметров позволяют конечным пользователям, не владеющим теорией глобальной оптимизации, решать с помощью разработанного программного пакета «Global Optimizer vl .0» различные сложные задачи, возникающие в реальной практике. В рамках диссертационной рабо i ы решено две практические задачи (подбор оптимальных параметров эллипсов аппроксимирующих произвольный контур и поиск оптимального решения задачи распределения штатов), которые подробно описаны в пятом разделе.

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

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

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

Личный вклад автора. Лично автором получены основные результаты диссертации: программные алгоритмы глобальной оптимизации и методы исследования их свойств, которые являются ставной частью разработанного автором программного пакета «Global Optimizer vl .0»; разработана методика конструирования специальных программных стендов для ошимизации задач, у которых целевая функция задается алгоритмически; решено две пракшческие задачи (разработаны специальные программные стенды). Часть результатов, полученных автором в диссертации, вошли в моно1рафию А. И. Рубана «Глобальная оптимизация методом усреднения координат» 2004 г., в которой содержатся ссылки на публикации автора.

Апробация результатов диссертации. Основные положения и результаты диссертационных исследований публиковались, докладывались и обсуждались на следующих научно-практических конференциях: The Third Russian-Korean International Symposium on Science and Technology, Новосибирск, 1999; Межвузовская научная конференция «Информатика и информационные технологии», КГТУ, Красноярск, 2003 и 2004; IV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям, Красноярск, Академгородок, 2003.

Кроме того, отдельные результаты работы и диссершция в целом обсуждались на научном семинаре кафедры «Информатика» KI I У.

Публикации. По теме диссертации опубликовано 12 научных работ, из которых: 7 статей в сборниках научных грудов, 2 работы в грудах международных и всероссийских научно-технических конференций, 2 работы размещено в Интернете, получено авторское свидетельство из отраслевого фонда алгоритмов и программ.

Общая характеристика диссертации. Диссертация состоит из введения, пяти глав, заключения, 2 приложений и списка использованных источников из 69 наименования, содержит 150 рисунков и 2 таблицы. Общий объем диссертации (с учетом приложений) составляет 138 страниц.

Содержание работы

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

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

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

Постановка задачи. Необходимо отыскать условный глобальный минимум функции качества 1(х) многих непрерывных переменных х-{х.,---,хт) с

учетом ограничений-неравенств срДх) < 0, 7 = 1, т] . Функция 1(х) может быть многоэкстремальной, разрывной, недифференцируемой, а также может быть искажена помехой. Ограничения сужают область поиска экстремума. Функции ограничений также могут быть невыпуклыми и недифференцируемыми. Поиск глобального минимума осуществляется только на основе измерений или вычислений функции качества 1{х) и функций срДх), определяющих ограничения.

Описание базового алгоритма безусловной оптимизации:

1. Равномерно разместить пробные точки х(1), / = 1 ,п в прямоугольной области с центром в точке х' и интервалами варьирования Ах':

Ху^ + Дх1~Ыу \ е[-1; 1], V = 1,от, г = 1, 2,..., и, (1)

где - равномерно распределённые (случайные или детерминированные) в интервале [-1;1] числа

2. Вычислить значение функции /0> = /(*'") в этих точках.

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

X1;' = x'v + A• i/v, Mv = ¿«^Г , р[" = /'(g(,1)

j-1

(0 _ „(.) _ ШШ

При минимизации: gu' = g[ I -I0)

7(0

I шах

(2)

при максимизации:

„(О _ _(0 =

О о max

4. Вычислить новое значение интервалов варьирования Ах'

Ax'J'=y,-Axl- ХК'ГЙ'Ч , v = l,т, q = 1,2,....

1/9

(3)

5. Проверить условие останова алгоритма, если оно выполняется, то завершить вычисления, иначе перейти к шагу 1. Остановка движения в программной реализации происходит при выполнении одного из критериев ocia-нова (задается исследователем перед запуском алгоритма):

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

б) Область варьирования уменьшилась до заданного малого размера.

в) Значение функции качества на текущей итерации мало отличается от значения на предыдущей итерации.

г) Значение вектора искомых переменных на текущей итерации мало отличается от предыдущего значения.

Примечания: 7m„ = max{7'", i = 1, п}, /тл = min{/'", / = 1, п]; в переменных и'", pi" для упрощения записи опущен номер итерации / = 0,1, 2,.... Коэффициент растяжения области варьирования уц > 0, он определяет скорость сжатия области варьирования. Коэффициент метрики пространства q = 1,2, • .В дальнейшем ps будем называть ядрами, a ps - нормированными ядрами. Весовые коэффициенты р{* всегда нормированы на системе п пробных точек:

п

Коэффициент s>0 характеризует степень селективности ядра. Для

i=(

решения различных задач оптимизации можно использовать следующий набор ядер pjg):

1. Степенное: p,(g) = Q-gr)', >" = 1,2, 3...;

2. Экспоненциальное: ps(g) = exp{-sg'}, г = 1, 2, 3...;

3. Регуляризованное гиперболическое: р,(g) = (sgr +1)"', г = 1, 2, 3...;

4. Гиперболическое: ps(g) = g~'.

Приведенного набора ядер вполне достаточно для решения большинства задач глобальной оптимизации. При увеличении коэффициента s растет «се-

лективность» (способность к локализации положения глобального экстремума) ядра.

Параметр ядра г> 1 определяет «выпуклость» ядра и обычно принимает значения от 1 до 5. Значения больше 5 могут применяться при оптимизации многоэкстремальных функций, сильно искаженных помехами.

Генераторы последовательностей равномерно распределенных точек

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

Требуется равномерно разместить п точек внутри прямоугольной области П' с центром в точке х', при этом каждое значение х можно преде 1авитт> в следующем виде: ху = х[ иг е[-1; 1], у = \,т . Что эквивалентно их

размещению внутри гиперкуба с единичными координатами из [-1; 1] и центром в начале координат.

Для генерирования последовательностей точек в пространстве координат использовались:

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

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

Генератор ЛПт последовательностей. Размещение точек детерминированное (как у регулярной сетки) и оптимальное: точки равномерно распределены в пространстве и по каждой координате (упорядоченные координаты точек находятся на равномерном расстоянии друг от друга). Регулярность ЛПт последовательности также не позволяет проводить статистические исследования.

Новый генераюр (автор идеи Рубан А.И.) псевдослучайных равномерно распределённых точек с реализацией дополнительного условия (второго условия оптимальности в ЛПт генераторе): упорядоченные значения для каждой координаты всех генерируемых точек находятся на равном расстоянии друг от друга. Случайное размещение точек позволяет проводить статистический анализ свойств изучаемых функций и рассматриваемых алгоритмов.

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

статистических характеристик перечисленных генераторов) и было показано, что наилучшими свойствами обладает новый генератор. Он позволяет проводить статистические исследования и генерирует последовательности с меньшими неоднородностями, чем обычный генератор, что позволяет в задачах глобальной поисковой оптимизации алгоритмам поиска совершать на 1-2 итерации меньше.

Оценка сложности представленных алгоритмов. Можно примерно оценить временную и емкостную сложность представленных алгоритмов. Временной сложностью алгоритма называется время, затрачиваемое на решение, как функция размеров задачи. Это характеристика пары <тип ЭВМ, алгоригм>. Временная сложность представленных в диссертации алгоритмов растет линейно с ростом числа пробных точек п на каждой итерации и можег быть примерно оценена как О(Ы).

Затраты памяти (обычно в байтах) как функция размеров задачи - емкостная сложность. Емкостная сложность задачи зависит от количества пробных точек на каждой итерации п, размерности задачи т и количества ограничений т1. Представленные алгоритмы требуют память только для выполнения одной итерации и в процессе работы, объем используемой памяти практически не растет. В отличие от временной сложности, емкостная стоимость может быть точно рассчитана для любой отдельно взятой конкретной задачи, до ее запуска, так как размерность задачи и количество ограничений - константы входящие в постановку задачи, а количество пробных точек задается как параметр алгоритма.

Алгоритм на допустимых точках

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

Следует отметить, что этот алгоритм должен стартовать из такой точки и с такой начальной областью варьирования, чтобы хотя бы часть прямоугольной области варьирования пересекалась с допустимой областью, задаваемой ограничениями. Иначе алгоритм не сможет разместить ни одной пробной точки, и через некоторое количество попыток, (этот параметр определяется пользователем) выдаст сообщение о невозможности разместить п пробных точек в допустимой области и прекратит работу.

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

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

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

При исследовании свойств этого алгоритма были выявлены следующие закономерности.

С ростом количества пробных точек п улучшается точность оценивания положения условного глобального экстремума, но при достижении некоторого порогового значения п = п качество работы алгоритма перестает улучшаться. На рисунке 1 показано изменение точности с ростом количества пробных точек п для случая без помехи и при ее наличии.

шах(|х* - х I, V = 1 ,т) тах(|д:' - хг\, V 1 ,т)

Рисунок 1. Максимальное отклонение модуля невязки координат и истинного решения с ростом количества пробных движений п, а) без помехи, б) при наличии 100% помехи

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

Параметр у в формуле (3) оказывает сильное влияние на работу алгоритма. Этот параметр регулирует степень растяжения области варьирования. При ус < 1 алгоритм начинает быстрее сжимать область варьирования и тем самым быстрее завершает свою работу, совершая при этом меньше итераций. При

у >1 алгоритм наоборот, уменьшает скорость сжатия, увеличивая количество итераций алгоритма.

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

Обычно у9 не выходит за интервал [1.0; 1.7].

тах(|х^ - ху |, V = 1, т) тах(|л:* - |, V = 1, т)

Рисунок 2. Максимальное отклонение модуля невязки координат и истинного решения с ростом у?, а) без помехи, б) при наличии 200% помехи

Разработанные программные алгоритмы показали очень хорошую помехоустойчивость, уровень помехи в отдельных примерах достигал 500% от амплитуды функции качества в области поиска. С ростом уровня помехи точность поиска и вероятность отыскания глобального минимума уменьшаются, но не настолько, как можно было бы ожидать при таком высоком уровне помехи. Также следует отметить, что наличие помехи требует большего количество пробных точек п :оно должно быть в 2 - 10 раз больше, чем без помехи (это зависит от уровня помехи и топологии оптимизируемой функции).

Наибольшее влияние на работу алгоритма оказывает ядро. При этом ядро сложно в настройке, так как фактически приходная настраивать три параметра: вид ядра, параметр г и степень селекгивности ядра л1. Параметр г > 1 определяет степень выпуклости ядра и обычно применяется г- 2. Большие значения параметра г берутся, если необходимо усилить сглаживание, например, для задач с помехой, так как с ростом г ядро становится более выпуклым и менее селективным. При возрастании степени селективности ядра .у (где .у > 0) нормированные неотрицательные ядра р.тш(х), рм{х) становятся все более узкими и приближаются к дельта-функции с особой точкой, соответствующей глобальному экстремуму функции 1{х). Так обстоит дело в идеальном случае для теоретического алгоритма, а для программной реализации высокая степень селективности ядра может привести к тому, что алгоритм вместо глобального

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

Опишем еще одну эвристическую надстройку, но уже над алгоритмом на допустимых точках - эю алгоритм поиска главных экстремумов.

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

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

Рассмотрим алюритм разбиения на подобласти, при условии отыскания главных минимумов (для главных максимумов алгоритм аналогичный, но отбираются не минимальные, а максимальные величины). В гиперпрямоугольной области поиска экстремумов (с центром в х° и интервалами Ах°) точек х<0,1 = 1, п°, попадающих в допустимую область. В них вычисляется минимизируемая функция 1(х{") = /(,), г = 1 ,п°. Пробные точки х"\ г = 1, п° разбиваются на группы точек, тяготеющих к главным экстремумам. Для этого находится такая точка х^, которая соответствует наименьшей величине

/„, =пип{/(", /-1, и0} функции 1(х) на множестве всех пробных значений. Затем просматриваются все остальные пробные точки (кроме х„т) и из них отбираются те, которые расположены в окрестности х|ш, например, в соошетствии с условием: \х'в -*>1ПП1| < Дх°/с для всех v = \,m. Найденные точки из выборки

изымаются и образуют множество точек Мп, 1де и, - мощность множества М<

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

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

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

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

Рисунок 3. Линии равных уровней од- Рисунок 4. Процесс отыскания двух

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

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

ной из тестовых функций

главных минимумов

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

Штрафная функция часто имеет вид:

7(х) = /(*) + £а,(р;(х), ср;(х) = тах{0, фу(х)}, а, >0;

либо

7{х) = 1(х) + а^{х), ф+(х) = шах{0, ф,(х),..., Ф„,(х)}, а>0. (6)

Достоинством последней является наличие только одного штрафного коэффициента а > 0. Этот способ формирования штрафной функции (в виду его простоты) будет использоваться в дальнейшем.

За!ем по базовому алгоритму безусловной глобальной оптимизации отыскивается безусловный глобальный экстремум штрафной функции /(х), который совпадает с условным глобальным экстремумом исходной функции 1{х).

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

На этапе пробных движений (перед совершением каждого рабочего шага) после выполнения п пробных шагов и вычисления в каждой пробной точке значений всех функций (минимизируемой 7(х(") и всех функций ф,(■*'"), •••, фт (х("), 1 = 1, п, входящих в левую часть ограничений-неравенств) при каждом фиксированном значении г в расчетах итоговой штрафной функции 7(х{") для пробной точки х'" участвуют только те функции ф( (х!0), которые больше нуля (т. е. те функции, для которых ограничения нарушены): ф_) (х(0) > 0 при _/' е J(') е 1, от,.

Итоювая функция /(х10) для каждой пробной точки х'" находится аддитивным наложением на относительную величину основной функции I штрафной добавки в относительных величинах:

/ (х<") = > ~ 1т- + а • тах \ ф/) ~ , ейт,\, а>0. (7)

II Ф -ф

та? тт ^ > ;тях Т/паи )

3Десь: Футп = пип{фу(*(,)), г :0 <ф,(*'")}, Ф,гах = тах{ф/х("), г :0 < (р/х">)} для каждого фиксированного ]; /ш = тт{/(х("), i = \,n}, /„а1=шах{/(х<"), / =

Если при некотором у = I множество {/: <р((х"') > 0} пустое, то этот номер / не входит во множество присутствующее в формуле (7) (для каждого фиксированного /').

Для пробных точек, в которых ни одно неравенство не нарушено (множество ./'" пусюе) хшрафная добавка берётся равная нулю.

Рхли при некотором _/' = / множество {/ :ф;(х'") > 0} состоит из одною элемента, то соответствующий элемент в (7) (входящий под опера-юр тах{])

полагаем равным единице:

= 1.

Ф/тах Ф/плп

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

В "хорошо организованных" задачах условной оптимизации в отличие от прямого формирования штрафной функции в виде (6), где параметр усиления штрафной добавки может быть достаточно велик (например, а =100), использование в штрафных функциях относительных величин (7) приводит к тому, что коэффициент штрафа а не может принимать больших значений. Рассмотрение различных примеров показало, что целесообразно ос выбирать из интервала [2; 10]. Для этих "хорошо организованных" задач оба подхода дают примерно одинаковые итоговые результаты.

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

Проведено исследование влияния параметра а на качесч во работы алгоритма.

шах

шах

¡, v -1 ,т)

а) б)

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

На рисунке 5 показано поведение алгоритма с ростом а от 1 до 1000 для обоих способов формирования штрафной функции и хорошо видно, что оптимальные диапазоны параметра а разные для каждого способа свертки. Для прямого способа это широкий диапазон от 100 до 600, а для свертки в относительных величинах от 5 до 50.

Третий раздел посвящен описанию и исследованию прямого алгоритма глобальной ошимизации при ограничениях-неравенствах.

Как и все предыдущие алгоритмы, этот алгоритм является модификацией базового алгоритма (см. раздел 1.1). Основная модификация заключается в учете влияния ограничений при расчете значений нормированных ядер р , теперь весовые коэффициенты ps рассчитываются следующим образом:

p»(gMmp,.(g?)

РТ = ---• (8)

2>,,0?(Ю)П р,МТ)

И-1 /б/"

Здесь: = ^ ^ ^'"" ;/>,,- ядро по функции и р2, - ядро по ограни-

ФI шах Ф j rmn

чениям; фугах = max {ф(;с("), г: ф,(х(") > 0}, флтш = тт{ф(х1'1),/:фДл:(',)>0} .для каждого фиксированного j; остальные обозначения те же.

При каждом фиксированном значении i для пробной точки х"' в расчетах участвуют только те функции фДх<0), которые больше нуля (т. е. те функции,

для которых ограничение нарушены): фу(х<0) > 0 при j в J'" el ,m.

Если при некотором j - к множество {г: ф (х(,)) > 0} пустое, то этот номер

к не входит во множества Jm, присутствующие в формуле (8) (для каждого фиксированного i).

Если при некотором j = k множество {/: фДх(") > 0} состоит из одного элемента, то соответствующий элемент в формуле (8) (аргумент ядра p2s) полагаем равным 0.75. Это значение было получено экспертным путем.

Для пробных точек с номерами (г), в которых ни одно неравенство не нарушено (множество Jl,) пустое) величина ]~[р, .(g'f) берется равной 1. Если

jmS"

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

Этот алгоритм работает «более мягко» чем другие представленные в диссертации алгоритмы. Так как неравенства учитываются напрямую, то не происходит «ухудшения» свойств алгоритмов за счет оврагов, как это имеет место для алгоритмов со штрафными функциями (см. второй раздел) - это является его существенным преимуществом.

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

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

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

В процессе исследования было выявлено, чю ядро по ограничениям должно быть более селективным, чем ядро по оптимизируемой функции, иначе алгоритм будет отыскивать глобальный безусловный экстремум, в то время как требуется отыскивать глобальный условный экстремум. На рисунке 6 показано поведение алгоритма при фиксированной селективности ядра по функциям ограничений (5 = 100) и изменении селективности ядра по оптимизируемой функции от 1 до 100 для случая без помехи и при ее наличии.

0 20 40 60 80 100 о л « ш 00 100

а) б)

Рисунок 6. Максимальное отклонение модуля невязки координат и исшнного решения с ростом степени селективности s; а) без помехи, б) с помехой

Четвертый раздел диссертации посвящен описанию разработанною программного пакета «Global Optimizer v 1.0».

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

Пакет реализован на языке Object Pascal с использованием среды визуального программирования Borland Delphi 7.0 фирмы Borland International Inc. База данных разработана в среде IBLxpert 2005, в качестве СУБД используется Yaffil SQL Server. Программный пакет «Global Optimizer vl.0» функционирует в операционной системе из семейства Windows 9x/NT/2000/XP.

Программный пакет «Global Optimizer vl.0» прошел экспертизу и зарегистрирован в отраслевом фонде алгоритмов и программ (номер государственной регистрации - 50200500390 oi 01.04.2005).

тах(|х' -х I, v = 1 ,т)

тахф:' -x,\,v = 1 ,т)

Концептуальная схема архитектуры программного пакета представлена на рис. 7.

Рисунок 7. Архитектура программного пакета

База данных используется для хранения объектов, создаваемых пользователем в процессе работы. Доступ к базе данных осуществляется через специально разработанное DB API, что позволяет с минимальными затратами в дальнейшем перенести проект на любой сервер баз данных.

Математическое ядро - программная реализация алгоритмов глобальной ошимизации. Ядро разрабатывалось с применением объектно-ориентированного подхода, который позволяв i легко дополнять ядро новыми возможностями, а также максимизирует повторное использование кода за счет наследования.

Модуль исследования - программная реализация различных методов исследования свойств алгоритмов. Этот модуль позволяет получить оценки- вероятности отыскания глобального экстремума, математического ожидания (с доверительным двухсторонним 95% интервалом) и медианы, с помощью следующих трех видов исследований:

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

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

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

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

Модуль управления является связующим звеном для всех остальных частей системы.

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

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

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

Функция качества 1(§,а,Ь,х0,у0) рассчитывается следующим образом: исходный контур центрируется относительно начала координат, затем все точки контура смещаются относи!ельно начала координат на -х0 и - у,., поворачиваются на угол - ф, после чего, вычисляются координа-

Рисунок 8. Графическое описание задачи по подбору параметров оптимальных эллипсов

гы хе,уе:

21.' '■> а о х,

х.г+уУ

= 4;

X.

й, =у1(х. ~х,)-+(уе -у)1 , /(ф,й,М0,}>0) = 15, .

(9)

На рисунках 9 и 10 показаны срезы функции (9) демонстрирующие ее мно-гоэкстремальность.

л /(ф, а, Ь)

' \ - ^.......... v • ....... v,

..........утл

Рисунок 9. Срез по функции (9) при Рисунок 10. Линии равных уровней фиксированных а, Ь, х0, уд функции (9) при фиксированных Ь,х0,у0

При наличии ограничений:

Ф, =-а, ф2 =-Ь, ф3 --ф, ф4 =ф-тс; ф, <0, г = 1, 4,

для отыскания оптимальных параметров минимального эллипса, охватывающего весь контур необходимо к ограничениям (10) добавить ограничение (11), а для отыскания параметров максимального эллипса, содержащегося в контуре, соответственно, необходимо добавить ограничение (12):

М

С 2

ь2

\

а

Ф5 < 0, где г(и)=

х, а1

К. Ъ2

и, и> 0, 0, и< 0,

, Ф.^0.

(12)

Результаты оптимизации эллипсов для произвольного контура алгоритмом с использованием штрафной функции в относительных величинах при различных значениях параметра а приведены на рисунках 11 и 12.

-г Ж $

и

Рисунок 11. Результаты оптимизации Рисунок 12. Результаты оптимизации при а = 1 при а = 2

Вторая задача заключается в отыскании оптимальных нормирующих коэффициентов х[к в задаче распределения штатов в вузе (на примере КГТУ). Эта задача характерна тем, что имеет очень большую размерность (порядка 170 переменных) и большое число ограничений (более 300).

5 Г I

! \ 5 г Функция качества: 1{хп)= ■ Кг

*-1 /-1

Ограничения: х"""к <хГк <х""*,к = 1,5,/ = 1,/'';

1

5 Р 1

»-1 /-1 X

_ на,

<-] Т■ _»-'

<0"

(13)

(14)

(15)

/-1 х

и с, = + ^Г" -1).

1а,,-Ее,

<1-1

*Л

Пояснения к обозначениям задачи: К/к - количество студентов / -ой категории (типы обучаемых и формы обучения), обучающихся на к-ом факультете.

- учебная нагрузка, поручаемая к-ым подразделением у -ой кафедре, х^ -число обучающихся / -ой категории на к -ом подразделении, приходящихся на одного преподавателя университета. и gk"y, - коэффициенты, позволяющие рассчитать доли от общего числа ставок в вузе бюджетных и контрактных соответственно, используемые на нужды вуза (например, на содержание административного аппарата, обслуживающего персонала и т.п.). и - коэффициенты, позволяющие рассчитать резервное число бюджетных и контрактных ставок к -ого подразделения (резерв декана). каф и £ ""*' - коэффициенты, позволяющие рассчитать резервное число бюджетных и контрактных ставок у -ой кафедры (резерв заведующего кафедрой). Резервный коэффициент имеет область определения [0,1]. Например, если резервный фонд вуза составляет 15% от общего числа бюджетных ставок, то коэффициент примет значение 0,85.

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

Рисунок 13. График срезов трех функций офаничений по трем переменным

Задача была успешно решена, специализированный программный стенд был внедрен как часть системы принятия решений «Ресурсы образовательного процесса» в КГТУ

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

дуль исследования и элементы пользовательского интерфейса из программного пакета глобальной оптимизации «Global Optimizer vi .0».

Заключение

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

Разработан программный пакет «Global Optimizer vl.O», позволяющий детально исследовать свойства алгоритмов оптимизации и решать задачи услов- « ной глобальной оптимизации.

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

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

Решено две достаточно сложных практических задачи.

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

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

Публикации автора по теме диссертации

1. Kuznetsov, А. V. Nonparametric retrieval global optimization with presence of restrictions-inequalities / A. V. Kuznetsov // Abstracts The Third Russian-Korean International Symposium on Science and Technology. June 22-25. Novosibirsk State Technical University. 1999. P. 222. *

2. Кузнецов, А. В. Алгоритмы прямой непараметрической поисковой глобальной ошимизации при ограничениях-неравенствах / А. В. Кузнецов, А. И. Рубан // Информатика и системы управления: Межвуз. Сб. научных трудов. Вып. 4. Красноярск: НИИ ИПУ, 1999. С. 134-139.

3. Кузнецов, А. В. Непараметрическая поисковая глобальная минимизация штрафных функций / П. Е Константинов, А. В. Кузнецов, А. И. Рубан // Информатика и системы управления: Межвузовский сборник научных трудов. Вып. 4. Красноярск: НИИ ИПУ, 1999. С. 88-98.

4. Кузнецов, А. В. Алгоритм непараметрической поисковой оптимизации при наличии ограничений-неравенств / А. В. Кузнецов, А.И. Рубан // Вестник Красноярского государственного технического университета. Информатика, вычислительная техника, управление. Вып. 26. Красноярск: Изд-во КГТУ, 2001. С.195-206.

5. Кузнецов, А. В. Алгоритмы непараметрической поисковой глобальной оптимизации при ограничениях-неравенствах / А. В. Кузнецов // Тезисы IV Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, Красноярск 2003, С.78. Режим доступа

f к полному тексту статьи: http://www.ict.nsc.ru/ws/YM2003/6319/.

6. Кузнецов, А. В. Программный комплекс непараметрической поисковой глобальной оптимизации / А. В. Кузнецов // Информатика и информационные технологии: Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2003. С. 144-147.

7. Кузнецов, А. В. Разбор и трансляция математических формул / А. В. Кузнецов // Режим доступа к тексту статьи: http://www.delphikingdom.com/ asp/viewitem.asp ?catalogid=1019

8. Кузнецов, А. В. Генераторы последовательностей равномерно распределенных точек / А. В. Кузнецов // Информатика и информационные технологии: Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2004. С. 39-47.

9. Кузнецов, А. В. Новый генератор случайных равномерно распределенных точек / А. В. Кузнецов, А. И. Рубан // Информатика и системы управления. Вып. 10: Межвуз. сб. науч. тр. Красноярск: ГУ НИИ информатики и процессов управления, 2004. С. 5-12.

10. Кузнецов, А. В. Программный алгоритм поиска главных экстремумов / А. В. Кузнецов // Информатика и системы управления. Вып. 10: Межвуз. сб. науч. тр. Красноярск: ГУ НИИ информатики и процессов управления, 2004. С. 35-44.

11. Кузнецов, А. В. Разбор и трансляция математических формул / А. В. Кузнецов // Информатика и информационные технологии: Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2004. С. 31-38.

12. Кузнецов, А. В. Программный пакет глобальной оптимизации «Global Optimizer vl.0» / А. В. Кузнецов, А. И. Рубан // М.Ж ВНТИЦ (№ гос. регистрации 50200500390 от 01.04.2005).

Отпечатано в ИПЦ КГТУ. Тираж 100 экз. Заказ 699/2 660074, Красноярск, ул. Киренского, 28

гоо& л

1-9855

Содержание.

Введение.

Общие сведения о диссертации.

Краткий анализ подходов к решению задачи глобальной оптимизации.

Выводы.

1 Алгоритмы на допустимых пробных точках.

1.1 Базовый алгоритм безусловной глобальной оптимизации методом усреднения координат.

1.2 Генераторы последовательностей равномерно распределенных точек

1.3 Алгоритм глобальной оптимизации при ограничениях-неравенствах.

1.4 Примеры.

1.5 Свойства алгоритма и влияние параметров на качество его работы.

1.6 Алгоритм поиска главных экстремумов.

Выводы.

2 Алгоритмы глобальной оптимизации при ограничениях-неравенствах с использованием штрафных функций.

2.1 Прямая свертка ограничений в штрафную функцию.

2.2 Формирование штрафной функции с использованием относительных значений оптимизируемой функции и ограничений.

2.3 Примеры.

2.4 Свойства алгоритма и влияние параметров на качество его работы.

Выводы.

3 Прямой алгоритм глобальной оптимизации при ограничениях-неравенствах

3.1 Прямой алгоритм учета ограничений.

3.2 Примеры.

3.3 Свойства алгоритма и влияние параметров на качество его работы.

Выводы.

4 Программный пакет глобальной оптимизации «Global Optimizer vl.O».

4.1 Общее описание.

4.2 Требования к ресурсам.

4.3 Математическое ядро и модуль исследования. ф 4.4 Методика проведения интерактивных исследований.

4.5 Методика проведения пакетных исследований.

4.6 Методика конструирования специальных программных стендов.

Выводы.

5 Решение практических задач.

5.1 Поиск оптимальных параметров эллипсов, аппроксимирующих произвольный контур.

5.2 Поиск оптимального решения задачи распределения штатов.

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

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

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

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

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

Устойчивый рост интереса исследователей - практиков к методам глобальной оптимизации в последние годы показан в работе [8], объясняемый тем, что классические методы поиска оптимума оказываются неэффективными при решении сложных многокритериальных задач (например, для оптимизации химико-технологических систем). На рисунке 1 представлен рост числа публикаций в базе данных INSPEC содержащих слова «global optimization» в заголовке с 1967 по 2000 года. Сеть STN International (The Scientific and Technical Information Network) представляет собой международную негосударственную форму сотрудничества трех крупнейших производителей вторичной научно-технической информации и образована ведущими производителями: Chemical Abstracts Service (США), Fachinformationszentrum Karlsruhe (Германия) и JST (Япония). INSPEC - крупнейшая база данных научной сети STN International с информацией по физике, электротехнике, техническим наукам, компьютеризации управления, ведущаяся с 1969 г. Приводимые данные показывают динамику роста интереса исследователей-практиков к теме глобальной оптимизации. Таким образом, новые, эффективные, универсальные и простые в эксплуатации алгоритмы глобальной оптимизации будут востребованы в индустрии.

Рисунок 1. Количество публикаций, содержащих словосочетание «global optimization» в заголовке, по годам ш Публикаций

1967

1970

1998

2000

Проблема глобальной оптимизации относится к классу сложных и до сих пор полностью не разрешенных проблем. Хотя уже и существуют определенные результаты в этой области, но высокоэффективных, быстро сходящихся, простых по своей структуре, помехоустойчивых, не требующих сложной настройки параметров и понятных конечному пользователю алгоритмов очень мало. Как отмечает в своей работе [24] А. А. Красовский «.вполне удовлетворительные методы решения многоэкстремальных многомерных задач с неизвестной априори топологией целевых функций до настоящего времени отсутствуют.».

В статье А. И. Каплинского и А. И. Пропоя [20, с. 55] написано: «Методы решения экстремальных задач к настоящему времени достаточно хорошо разработаны. Однако эти методы в основном ориентированы на решение "хороших" задач (выпуклых, гладких, детерминированных) и основаны на использовании локальной информации (типа "градиент в точке"). Принципиальная черта "плохих" экстремальных задач (невыпуклых, негладких, недетерминированных) состоит в том, что они требуют нелокальной информации в процессе их решения. Общим путем введения нелокальности является рандомизация исходной задачи».

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

Цель работы

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

Новые научные результаты диссертации

Разработаны и исследованы новые программные алгоритмы глобальной оптимизации (основанные на методе усреднения координат) при наличии ограничений-неравенств:

1. Алгоритм на допустимых пробных точках [3, 25].

2. Алгоритм поиска главных экстремумов [30].

3. Алгоритм с использованием двух видов свертки ограничений в штрафную функцию: прямая свертка и свертка в относительных величинах [26].

4. Алгоритм прямого учета ограничений в ядрах процедуры усреднения координат [27].

Часть результатов, полученных автором в диссертации, вошли в монографию А. И. Рубана [45], в которой содержатся ссылки на публикации автора.

Теоретическая значимость

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

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

Практическая значимость

На основе предложенных в диссертации алгоритмов, а также серии алгоритмов, представленных в работе [45] для других классов задач глобальной оптимизации, разработан исследовательский программный пакет «Global Optimizer vl.O». При этом создана методология конструирования программных алгоритмов глобальной оптимизации, разработаны способы исследования влияния параметров алгоритмов на качество их работы.

Полученные в диссертационной работе рекомендации по выбору типа алгоритма и подбору его параметров позволяют обычным пользователям, не владеющим теорией глобальной оптимизации, решать с помощью разработанного программного пакета «Global Optimizer vl.O» различные сложные задачи, возникающие в реальной практике. В рамках диссертационной работы решено две практические задачи (подбор оптимальных параметров эллипсов аппроксимирующих произвольный контур и поиск оптимального решения задачи распределения штатов), которые подробно описаны в пятом разделе.

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

Структура диссертации

Диссертация состоит из введения, пяти глав, заключения, 2 приложений и

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

320

310-1

I Д'-f )

1 ч ^ ч.

345 340 335 330

325-■

320

315 Г 1 )

I--M-MH >ш

0 5 10 15 20 25

Рисунок 5.2.6. Изменение по итерациям функции (5.2.1) при оптимизации алгоритмом с использованием свертки (2.2.4)

0 5 10 15 20

Рисунок 5.2.7. Изменение по итерациям функции (5.2.1) при оптимизации прямым алгоритмом (3.1.1)

Время работы обоих алгоритмов при указанных выше настройках на компьютере класса Pentium III 1000 MHz примерно 5 секунд.

Заключение

Разработаны и исследованы новые программные алгоритмы глобальной оптимизации (основанные на методе усреднения координат) при наличии ограничений-неравенств:

1. Алгоритм на допустимых пробных точках [3, 25].

2. Алгоритм поиска главных экстремумов [30].

3. Алгоритм с использованием двух видов свертки ограничений в штрафную функцию: прямая свертка и свертка в относительных величинах [26].

4. Алгоритм прямого учета ограничений в ядрах процедуры усреднения координат [27].

Разработан программный пакет «Global Optimizer vl.O» [33], позволяющий детально исследовать свойства алгоритмов оптимизации и решать задачи:

• Безусловной глобальной оптимизации. ф • Условной глобальной оптимизации при наличии ограниченийнеравенств.

• Условной глобальной оптимизации при наличии ограничений равенств.

• Условной глобальной оптимизации при наличии ограничений-неравенств и равенств одновременно.

• Решения систем уравнений, с возможностью добавления ограничений-неравенств.

• Минимаксной глобальной оптимизации, с возможностью добавления ограничений-неравенств.

Ш • Глобальной многокритериальной оптимизации, с возможностью добавления ограничений-неравенств.

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

Проведены исследования влияния параметров предложенных алгоритмов на качество их работы.

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

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

По результатам проделанной работы намечены пути дальнейшего развития разработанного программного пакета «Global Optimizer vl.O». Разработка алгоритмов более экономно использующих пробные точки (путем сохранения точек с предыдущих итераций). Разработка новых стратегий учета ограничений (перемещение по кратчайшему пути в допустимую область точек попавших в недопустимую область). Разработка кластерных версий алгоритмов для эффективной оптимизации задач большой размерности. Обобщение накопленного опыта оптимизации различных классов задач в виде добавления элементов экспертной системы, которая будет позволять пользователям, не владеющим высокой квалификацией в оптимизации, эффективно решать свои прикладные задачи.

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

1. Goldberg, D. Е. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading. / D. E. Goldberg. Massachusetts: Addison-Wesley, 1989.

2. Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. / J. H. Holland. Cambridge, MA: MIT Press, 1992 (2nd edition).

3. Rouban, A. I. Simulation Methods of Test Multiextreme Functions of Continuous Arguments / A. I. Rouban // Advances in Modeling & Analysis: Series C. System Analysis; Control & Design; Simulation; CAD. France: A.M.S.E. 2002. Vol. 57. № 6. P. 11-30.

4. Schwefel, H. Parallel Problem Solving from Nature / H. Schwefel, R. Maenner // Proc. 1st Workshop PPSN, Berlin: Springer.

5. Алексеев, В. И. Субоптимальные рекуррентные алгоритмы оценивания в системах навигации / В. И. Алексеев // Изв. вузов СССР. Радиоэлектроника. 1987. Т. 30. № 3. С. 34-39.

6. Алексеев, В. И. Экстремальная радионавигация / В. И. Алексеев, А. М. Ко-риков, Р. И. Полонников, В. П. Тарасенко. М.: Наука, 1978. 280 с.

7. Букатова, И. JI. Эволюционное моделирование и его приложения. / И. JL Букатова. М.: Наука, 1979.

8. Букатова, И. JI. Эвроинформатика: теория и практика эволюционного моделирования. /И. JI. Букатова, 10. И. Михасев, А. М. Шаров. М.: Наука, 1991.

9. Волин, Ю. М. Оптимизация технологических процессов в условиях недостаточной экспериментальной информации на этапе функционирования / Ю. М. Волин, Г. М. Островский // Автоматика и телемеханика. 2005. №8.ф С. 3-21.

10. Гергель, В. П. АБСОЛЮТ. Программная система для исследований и изучения методов глобальной оптимизации. Учеб. пособие / В. П. Гергель, Р. Г. Стронгин. Изд-во Нижегородского университета, 1998. 141 с.

11. Гради, Б. Объектно-ориентированный анализ и проектирование с примерами на С++ / Б. Гради. 2-е изд. Пер. с англ. М.: «Издательство Бином», СПб: «Невский диалект», 1998.

12. Дивногорцев, Д. И. Поиск главных минимумов многоэкстремальных функ-# ций / Д. И. Дивногорцев // Вестник Красноярского гос. техн. ун-та. Информатика, вычислительная техника, управление. Вып. 10. Красноярск: Изд-во КГТУ, 1997. С. 19-22.

13. Еремин, И. И. Современные проблемы теории оптимизации / И. И. Еремин, А. И. Кибзун // Автоматика и телемеханика. 2004. №8. С. 3.

14. Живоглядов, В. П. Непараметрические алгоритмы адаптации. / В. П. Живо-глядов, А. В. Медведев. Фрунзе: Илим, 1974. 134 с.

15. Жилинскас, А. Поиск оптимума: компьютер расширяет возможности /

16. A. Жилинскас, В. Шалтянис. М.: Наука, 1989. 128 с.

17. Ш 19. Иванов, М.В. Программная реализация алгоритма генерации ЛПт последовательностей / М.В. Иванов // Информатика и процессы управления: Межвузовский сб. науч. ст. Красноярск: КГТУ, 1995. С. 125-130.

18. Каплинский, А. И. Методы нелокальной оптимизации, использующие теорию потенциала / А. И. Каплинский, А. И. Пропой // Автоматика и телемеханика. 1993. № 7. С. 55-65.

19. Катковник, В.Я. Линейные оценки и стохастические задачи оптимизации /

20. B. Я. Катковник // Изв. вузов. Физика. 1995. Т.38. №9. С.65-73.

21. Кнут, Д. Э. Искусство программирования, том 2. Получисленные алгоритмы129

22. Д. Э. Кнут. М. Изд. Дом «Вильяме», 2000.

23. Краеовекий, А. А. Непрерывные алгоритмы и стохастическая динамика поиска экстремума / А. А. Красовский // Автоматика и телемеханика. 1991. № 4. С. 55-65.

24. Красовский, А. А. Селективно-усреднительный метод решения многоэкс-ф тремальных задач / А. А. Красовский // Автоматика и телемеханика. 1992. №9. С. 117-128.

25. Кузнецов, А. В. Алгоритмы непараметрической поисковой глобальной оптимизации при ограничениях-неравенствах / А. В. Кузнецов // Тезисы IV

26. Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, Красноярск 2003, С.78. Режим доступа к полному тексту статьи: http://www.ict.nsc.ru/ws/YM2003/6319/.

27. Кузнецов, А. В. Алгоритмы прямой непараметрической поисковой глобальной оптимизации при ограничениях-неравенствах / А. В. Кузнецов, А. И. Рубан // Информатика и системы управления: Межвуз. сб. науч. тр. Вып. 4. Красноярск: НИИ ИПУ, 1999. С. 134-139.

28. Кузнецов, А. В. Генераторы последовательностей равномерно распределенных точек / А. В. Кузнецов // Информатика и информационные технологии:• Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2004. С. 39-47.

29. Кузнецов, А. В. Новый генератор случайных равномерно распределенных точек / А. В. Кузнецов, А. И. Рубан // Информатика и системы управления. Вып. 10: Межвуз. сб. науч. тр. Красноярск: ГУ НИИ информатики и процессов управления, 2004. С. 5-12.

30. Кузнецов, А. В. Программный алгоритм поиска главных экстремумов / А. В. Кузнецов // Информатика и системы управления. Вып. 10: Межвуз. сб. науч. тр. Красноярск: ГУ НИИ информатики и процессов управления, 2004. С. 3544.

31. Кузнецов, А. В. Программный комплекс непараметрической поисковой гло-ф бальной оптимизации / А. В. Кузнецов // Информатика и информационныетехнологии: Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2003. С. 144-147.

32. Кузнецов, А. В. Программный пакет глобальной оптимизации «Global Optimizer vl.O» / А. В. Кузнецов, А. И. Рубан // М.Ж ВНТИЦ (№ гос. регистрации 50200500390 от 01.04.2005).

33. Кузнецов, А. В. Разбор и трансляция математических формул / А. В. Кузнецов // Информатика и информационные технологии: Межвуз. сб. науч. тр. Красноярск: ИПЦ КГТУ, 2004. С. 31-38.

34. Кузнецов, А. В. Разбор и трансляция математических формул / А. В. Кузнецов // http://www.delphikingdom.com/asp/viewi tem.asp?catalogid=l 019

35. Медведев, А. В. Об алгоритмах случайного поиска / А. В. Медведев, И. М. Цикунова // Применение вычислительных машин в системах управления непрерывными производствами / Сб. статей. Фрунзе: Изд. «Илим», 1976. С. 81-92.

36. Наумов, А. И. Селективно-усреднительный метод поиска глобального экстремума в задачах оптимизации движения динамических объектов / А. И. Наумов, И. Е. Шелковенков // Изв. РАН. Теория и системы управления.• 1996. №6.

37. Пачеко, К. Delphi 5. Руководство разработчика в 2-х томах. / К. Пачеко, С. Тейксейра. СПб.: Издательский дом «Вильяме», 2000.

38. Поляк, Б. Т. Введение в оптимизацию / Б. Т. Поляк. М.: Наука, 1983.

39. Пропой, А. И. Возбудимые среды и нелокальный поиск / А. И. Пропой // Автоматика и телемеханика. 1995. №7. С. 162-171.

40. Пропой, А. И. Задачи оптимизации и обучения для нелокального поиска в возбудимых средах / А. И. Пропой // Автоматика и телемеханика. I: 1996. № 1. С. 57-66. II: 1996. № 3. С. 68-81. III: 1997. № 4. С. 54-64.131

41. Пропой, А. И. К теории нелокального поиска. 1. Задачи обучения и оптимизации / А. И. Пропой // Автоматика и телемеханика. 1995. № 2. С. 44-52.

42. Растригин, Л. А. Адаптация сложных систем: Монография / Л. А. Растригин. Рига.: Зинатне, 1981. 375 с.

43. Растригин, Л. А. Статистические методы поиска / J1. А. Растригин. М.: Нау-ф ка, 1968. 376 с.

44. Рубан, А. И. Глобальная оптимизация методом усреднения координат: Монография / А. И. Рубан. Красноярск: ИПЦ КГТУ, 2004. 302 с.

45. Рубан, А. И. Метод непараметрической оптимизации стохастических объектов / А. И. Рубан // Системы управления: Сб. научных работ. Вып. 1. Томск: Изд-воТГУ, 1975. С. 101-107.

46. Рубан, А. И. Метод непараметрической поисковой глобальной оптимизации / А. И. Рубан // Кибернетика и вуз: Сб. научных работ. Вып. 28. Томск: ТПУ,1994. С. 107-114.

47. Рубан, А. И. Метод непараметрической поисковой оптимизации / А. И. Рубан // Изв. вузов. Физика. 1995. Т. 38. № 9. С. 65-73.

48. Рубан, А. И. Методы анализа данных. Учеб. пособие. 2-е изд. / А. И. Рубан. Красноярск: КГТУ, 2004. 319 с. (С.209-223).

49. Рубан, А. И. Методы оптимизации. Учеб. пособие. 3-е изд. / А. И. Рубан. Красноярск: ИПЦ КГТУ, 2004. 528 с.

50. Рубан, А. И. Общие схемы построения тестовых многоэкстремальных функций непрерывных переменных. / А. И. Рубан // Информатика и системы

51. Ф управления: Межвуз. сб. науч. тр. Вып. 4. Красноярск: НИИ ИПУ, 1999. С.12.25.

52. Семёнкин, Е. С. Адаптивные поисковые методы оптимизации сложных систем / С. П. Коробейников, Е. С. Семёнкин, О. Э. Семёнкина. Красноярск: СИБУП, 1997. 355 с.

53. Семёнкин, Е. С. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами. / Е. С. Семёнкин, В. А. Лебедев. М.: МАКС Пресс, 2002. 320 с.

54. Семёнкин, Е. С. Модели и методы оптимизации систем управления сложны132ми объектами./ Е. С. Семёнкин, В. А. Терсков. Красноярск: СЮИ МВД РФ, 2000.211 с.

55. Стрекаловский, А. С. О локальном и глобальном поиске в невыпуклых задачах оптимизации / А. С. Стрекаловский, Т. В. Яковлева // Автоматика и телемеханика 2004 №3. С. 23-34.

56. Стронгин, Р. Г. Численные методы в многоэкстремальных задачах / Р. Г. Стронгин. М., Наука, 1978. 240 с.

57. Федоров, П. Е. Применение метода эллиптических оценок при построении географических информационных систем экологического назначения» / П. Е. Федоров. Диссертационная работа на соискание степени кандидата техн. наук. Красноярск 1998. 144 с.

58. Фогель, JI. Искусственный интеллект и эволюционное моделирование. / Л. Фогель, А. Оунэнс, М. Уолш // М.: Мир, 1969.

59. Черноусько, Ф. Л. Оценивание фазового состояния динамических систем. / Ф. Л. Черноусько. М.: Наука, 1988. 319 с.

60. Якунин, 10. Ю. Оптимальное управление формированием штатов профессорско-преподавательского состава вуза, / 10.10. Якунин. Диссертационная работа на соискание степени кандидата техн. наук. Красноярск, 2005.

61. Якунин, Ю. Ю. Модель распределения бюджетных и внебюджетных ресурсов по кафедрам в вузе / М. А. Воловик, В. М. Журавлёв, Ю. Ю. Якунин // Информатика и системы управления: Межвуз. сб. науч. тр. Вып. 9, НИИ ИПУ, Красноярск, 2003. С. 260-266.

62. Якунин, Ю. Ю. Модель распределения ресурсов в вузе / 10.10. Якунин, М. А. Воловик // Информатика и системы управления: Межвузовский сборник научных трудов. Вып. 10, НИИ ИПУ, Красноярск, 2004. С. 101-104.

63. Якунин, Ю. Ю. Показатели эффективности распределения штатов и нагруз133ки на кафедры / Ю. 10. Якунин, М.А. Воловик, A.M. Даничев // Информатика и системы управления: Межвуз. сб. науч. тр. Вып. 10, НИИ ИПУ, Красноярск, 2004. С. 105-113.

64. Якунин, 10. Ю. Показатели эффективности распределения штатов и нагрузки на кафедры электронный ресурс.: тезисы 8-й Московской международф ной телекоммуникационной конференции студентов и молодых ученых /

65. Ю. Ю. Якунин // МИФИ, 2004. Режим доступа к тезисам: http://www.molod.mephi.ru/dir2.asp?rid=23&grid=6

66. Якунин, 10. Ю. Распределение ресурсов с учетом ограничений средней на-# грузки преподавателей на кафедрах / 10. Ю. Якунин, М. А. Воловик // Информатика и системы управления: Межвуз. сб. науч. тр. Вып. 10, НИИ ИПУ, Красноярск, 2004. С. 124-132.