Isbn 978-5-7262-1377 нейроинформатика 2011
Вид материала | Документы |
- Isbn 978-5-7262-1377 нейроинформатика 2011, 107.92kb.
- Isbn 978-5-7262-1377 нейроинформатика 2011, 143.59kb.
- Isbn 978-5-7262-1377 нейроинформатика 2011, 97.16kb.
- Isbn 978-5-7262-1375 нейроинформатика 2011, 127.94kb.
- Isbn 978-5-7262-1375 нейроинформатика 2011, 25.66kb.
- Isbn 978-5-7262-1375 нейроинформатика 2011, 105.62kb.
- Isbn 978-5-7262-1226 нейроинформатика 2010, 142.85kb.
- Isbn 978-5-7262-1376 нейроинформатика 2011, 103.58kb.
- Isbn 978-5-7262-1375 нейроинформатика 2011, 79.42kb.
- Isbn 978-5-7262-1226 нейроинформатика 2010, 136.25kb.
ISBN 978-5-7262-1377-4. НЕЙРОИНФОРМАТИКА – 2011. Часть 3
А.П. КАРПЕНКО, З.О. СВИАНАДЗЕ
Московский государственный технический университет им. Н.Э.Баумана
apkarpenko@mail.ru
МЕТА-ОПТИМИЗАЦИЯ НА ОСНОВЕ
САМООРГАНИЗУЮЩИХСЯ КАРТ КОХОНЕНА
И ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Рассматривается задача параметрической оптимизации алгоритмов поисковой оптимизации (задача мета-оптимизации). Предложен метод мета-оптимизации, основная особенность которого заключается в отыскании оптимальной стратегии алгоритма в процессе нормальной эксплуатации реализующей его программы. Метод использует кластеризацию множества задач рассматриваемого класса с помощью самоорганизующихся карт Кохонена и решение собственно задачи мета-оптимизации с помощью непрерывного генетического алгоритма.
Ключевые слова: мета-оптимизация, самоорганизующаяся карта Кохонена (SOM), непрерывный генетический алгоритм
Введение
В современных алгоритмах поисковой оптимизации обычно имеется значительное число свободных параметров, вектор значений которых называется стратегией алгоритма. Стратегия алгоритма оптимизации в значительной степени определяет его эффективность. Поэтому возникает задача поиска оптимальной стратегии алгоритма. Эта задача называется задачей мета-оптимизации. Оптимизируемый алгоритм и соответствующая программа называются базовыми, а алгоритм и программа решения задачи мета-оптимизации – мета-алгоритмом и мета-программой.
Известен ряд работ, посвященных теоретическому анализу влияния различных стратегий на эффективность некоторых базовых алгоритмов. Однако исследования такого сорта основаны на сильных упрощениях базового алгоритма и имеют ограниченную практическую ценность. Обычно задачу мета-оптимизации решают численными методами, которые можно разделить на две группы – методы управление параметрами и методы настройки параметров [Michalewicz Z., Hinterding R., Eiben A.E. Parameter Selection. Evolutionary Optimization. New York: Springer. 2003. V. 48. № 11. P. 279–306.].
В методах настройки параметров задача мета-оптимизации решается для некоторого класса задач. Найденные оптимальные стратегии базового алгоритма фиксируются и используются для решения других задач данного класса. Методы настройки параметров разделяются на методы однократной настройки и методы перманентной настройки [1].
В методах управления параметрами задача мета-оптимизации решается в процессе решения исходной задачи оптимизации (с помощью базового алгоритма). Основная идея состоит в том, что поскольку для каждой задачи оптимизации оптимальной является, вообще говоря, своя стратегия, поиск этой стратегии необходимо производить в процессе каждого запуска базового алгоритма. Методы управления параметрами разделяются на методы адаптивного управления и методы само-адаптивного управления [1].
В данной работе предлагается вариант метода мета-оптимизации на основе перманентной настройки, основная особенность которого состоит в отыскании оптимальной стратегии базового алгоритма в процессе нормальной эксплуатации соответствующей базовой программы, т.е. в процессе решения не тестовых, а реальных задач оптимизации. При этом базовая программа перед началом вычислений посылает мета-программе априорную информацию об атрибутах решаемой задачи, а после завершения вычислений – апостериорную информацию о тех же атрибутах. Программная реализация метода приводит к распределенной мета-программной системе, центральная часть которой в процессе своего функционирования накапливает информацию об атрибутах задач, когда-либо решавшихся в системе. При предъявлении системе базовой программой априорных значений атрибутов новой задачи, система на основе накопленной информации возвращает базовой программе приближенно-оптимальную стратегию базового алгоритма.
Постановка задачи
Рассмотрим задачу глобальной безусловной оптимизации

где





Пусть








которое определяет множество алгоритмов

Задача 1. Для задачи








Можно предложить целый ряд критериев






Положим, что тем или иным способом, например, с помощью аддитивной скалярной сверки [Черноруцкий И.Г. Методы принятия решений. СПб.: БХВ-Петербург. 2005. 416 с.] векторный критерий оптимальности



Задача 2. Для класса задач









В данном случае также можно предложить вектор критериев оптимальности


Схема метода
Введем в рассмотрение вектор







Выделим среди атрибутов








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

- производится сначала кластеризация, а затем периодическая рекластеризация этого множества – выделяется кластеры


- каждому из кластеров


- для задачи




- соответствующая стратегия


Метод требует решения двух следующих основных задач:
- задача кластеризации множества

- задача оптимизации стратегий

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

- клиентская программа посылает серверной программе вектор

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




- клиентская программа, получив стратегию


- завершив решение задачи t, клиентская программа формирует вектор

- получив вектор

Вектор


-


-


-

В качестве критерия оптимальности








Здесь






Для решения задачи кластеризации множества



Решение задачи оптимизации стратегии


Исследование эффективности метода
В качестве базового алгоритма a рассмотрен алгоритм метода Нелдера-Мида (метода деформируемого многогранника), относящийся к классу прямых детерминированных методов оптимизации [Nelder J.A., Mead R. A simplex method for function minimization // The Computer Journal. 1965. V. 7. P. 308–313.]. В качестве свободных параметров алгоритма рассмотрены параметры










где









Класс задач

Приведенные ниже результаты получены на основе решения более 150 тысяч задач указанного класса T. Число кластеров


Динамику развития одного из кластеров


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



Спустя 30 поколений развития кластеров






Рис. 1. К динамике развития кластеров

Таблица 1
Результаты исследования оптимальных стратегий

Число испытаний | Стратегия ![]() | Стратегия ![]() |
Среднее | 161 | 130 |
Минимальное | 35 | 16 |
Максимальное | 600 | 600 |
Табл. 1 показывает, что средняя производительность алгоритма Нелдера-Мида при использовании стратегий


Кроме того, спустя то же число поколений развития кластеров


Таблица 2
Результаты исследования лучших стратегий

Число испытаний | Стратегия ![]() | Стратегия ![]() |
Среднее | 214 | 115 |
Минимальное | 24 | 13 |
Максимальное | 1000 | 350 |
Табл. 2 показывает, что стратегии, найденные мета-алгоритмом, обеспечивают по сравнению с рекомендованной стратегией





Выводы
В работе предложен метод мета-оптимизации базового алгоритма оптимизации в процессе нормальной эксплуатации соответствующей базовой программы. Выполнена программная реализация метода, имеющая трехзвенную клиент-серверную архитектуру. Экспериментальное исследование эффективности метода выполнено на примере мета-оптимизации алгоритма Нелдера-Мида, как базового алгоритма. Результаты исследования показывают перспективность предложенного метода, а также эффективность использования в нем самоорганизующихся карт Кохонена и непрерывного генетического алгоритма .
Клиент-серверная архитектура разработанного программного обеспечения метода вносит в систему накладные расходы, обусловленные коммуникациями между его клиентской и серверной частями. Для задач, имеющих невысокую вычислительную сложность, это обстоятельство может приводить к неэффективности мета-оптимизации, поскольку выигрыш в количестве испытаний может быть перевешен накладными расходами. Однако в задачах, представляющих практический интерес, типичной является высокая вычислительная сложность целевой функции, обеспечивающая малый удельный вес указанных коммуникационных расходов. Как следует из результатов исследования, в такой ситуации мета-оптимизация базового алгоритма оптимизации может обеспечить значительный положительный эффект.
В работе в качестве исходной задачи оптимизации рассмотрена задача многомерной глобальной безусловной оптимизации. Для решения задач условной оптимизации в вычислительной практике широко используются методы штрафных и барьерных функций, сводящие задачу условной оптимизации к совокупности задач безусловной оптимизации [Черноруцкий И.Г. Методы принятия решений. СПб.: БХВ-Петербург. 2005. 416 с.]. Таким образом, полученные в работе результаты могут быть использованы и при глобальной условной оптимизации.
С другой стороны, имеется большое число методов решения задач глобальной условной оптимизации, которые не используют сведение ее к задаче безусловной оптимизации. Это обстоятельство делает актуальной модификацию предложенного в работе метода и программного обеспечения для решения задач глобальной условной оптимизации, как самостоятельного класса задач.
Как отмечалось выше, задача мета-оптимизации представляет собой, по сути, задачу многокритериальной оптимизации. В работе для решения этой задачи использован простейший метод решения многокритериальных задач – метод сведения их с помощью аддитивной скалярной свертки к однокритериальным задачам. Представляется перспективной модификация предложенного в работе метода и программного обеспечения, использующая более тонкие методы решения задач многокритериальной оптимизации.
Список литературы
- Michalewicz Z., Hinterding R., Eiben A.E. Parameter Selection. Evolutionary Optimization. New York: Springer. 2003. V. 48. № 11. P. 279–306.
- Черноруцкий И.Г. Методы принятия решений. СПб.: БХВ-Петербург. 2005. 416 с.
- Уоссермен Ф. ссылка скрыта. М.: Мир. 1992. 240 с.
- Deb K., Kumar A. Real coded genetic algorithms with simulated binary crossover: Studies on multi modal and multi objective problems // Complex Systems. 1995. V. 6. № 9, P. 431–454.
- ссылка скрыта
- Nelder J.A., Mead R. A simplex method for function minimization // The Computer Journal. 1965. V. 7. P. 308–313.
- Tang K., Yao X., Suganthan P.N. et al. Benchmark functions for the cec’2008 special session and competition on large scale global optimization // Tech. rep. / Nature Inspired Computation and Applications Laboratory, USTC, China, 2007.
УДК 004.032.26(06) Нейронные сети