Адаптивные многошаговые методы и программные средства параллельной глобальной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Гергель, Александр Викторович

• Гергель, Александр Викторович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Гергель, Александр Викторович

Введение.-.

1. Модели и методы многомерной многоэкстремальной оптимизации.

1.1. Постановка задачи многомерной многоэкстремальной оптимизации.

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

1.3. Информационно-статистические алгоритмы глобального поиска.

2. Методы многоэкстремальной оптимизации с адаптивными решающими правилами.

2.1. Методы многоэкстремальной оптимизации с использованием производных.

2.2. Методы многоэкстремальной оптимизации с адаптивными оценками константами Липшица.

2.2.1. Локальная настройка оценок константы Липшица.

2.2.2. Локальная настройка с аддитивной сверткой оценок константы Липшица.

2.2.3. Локальная настройка с интервальной схемой построения оценок константы Липшица.

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

3. Многомерная многоэкстремальная оптимизации на основе многошаговой редукции размерности.

3.1. Многошаговая схема редукции размерности.

3.2. Адаптивная многошаговая схема редукции размерности.

3.2.1. Общее описание подхода.

3.2.2. Алгоритмическое описание.

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

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

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

3.6. Операционные характеристики алгоритмов глобального поиска.

4. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации.

4.1. Централизованная схема параллельного глобального поиска.

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

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

4.3.1. Общая схема распределенных вычислений.

4.3.2. Структурная схема распределенных вычислений.

4.3.3. Балансировка вычислительной нагрузки в структурной схеме распределенных вычислений.

5. Программные средства параллельной глобальной оптимизации.

5.1. Общая характеристика комплекса глобальной оптимизации 01орйСот.

5.2. Система одномерной многоэкстремальной оптимизации С1ор^Сот-1.

5.3. Система двухмерной многоэкстремальной оптимизации С1орйСот

5.4. Система многомерной многоэкстремальной оптимизации 01орйСот+

Введение диссертации (часть автореферата) на тему «Адаптивные многошаговые методы и программные средства параллельной глобальной оптимизации»

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

Проблематика моделей, методов и программных средств решения задач оптимизации является областью активных научных исследований, в которой результаты советских и российских ученых имеют широкое признание в стране и за рубежом. Можно выделить работы Д.И. Батищева, Ф.П.Васильева, В.П. Гергеля, В.А. Гришагина, Ю.Г. Евтушенко, А.Г. Жилинскаса, В.Г. Карманова, А.Г. Коротченко, Ю.И. Неймарка, С.А. Пиявского, Я Д. Сергеева, Р.Г. Стронгина, Ю.А. Флерова и др. Среди зарубежных ученых можно выделить Р. Брента, П. Пардалоса, Я. Пинтера, X. Туя, П. Хансена, Р. Хорста и др.

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

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

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

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

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

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

Научная новизна. При выполнении работы получены следующие основные новые результаты:

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

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

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

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

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

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

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

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

- Программная система 01орйСот+ для параллельного решения сложных вычислительно-трудоемких задач многомерной многоэкстремальной оптимизации.

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

Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов, выполняемых на факультете ВМК при поддержке Российского фонда фундаментальных исследований (проекты № 04-01-00455, № 07-01-00467-а) и Совета по грантам Президента Российской Федерации по государственной поддержке ведущих научных школ РФ (грант № НШ — 4694.2008.9), совместного научно-исследовательского проекта РФФИ и Нидерландской организации по научным исследованиям NOW 047.016.014. Результаты работы используются также в учебном процессе факультета ВМК ННГУ при чтении курсов "Модели и методы многоэкстремальной оптимизации", "Системы поддержки принятия решений".

Апробация работы. Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.

Диссертационная работа состоит из пяти глав.

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

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

- локальная настройка с интервальной схемой построения оценок константы Липшица,

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

- локальная настройка с аддитивной сверткой оценок константы Липшица

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

В третьей главе осуществляется развитие многошаговой схемы редукции размерности. В рамках новой адаптивной схемы предлагается одновременное решение всех порождаемых в ходе редукции одномерных задач оптимизации, обобщается характеристическая форма представимости алгоритмов многоэкстремальной оптимизации, выполняется теоретическое обоснование для информационно-статистических методов глобального поиска. В § 3.1 изложена схема многошаговой схемы редукции размерности, согласно которой решение многомерной задачи оптимизации может быть получено посредством решения последовательности «вложенных» одномерных задач. В § 3.2 рассматривается новая адаптивная многошаговая схема редукции размерности, согласно которой устраняется принцип строгого соподчинения решения порождаемых в рамках многошаговой схемы одномерных функций - все эти задачи предлагается решать одновременно.

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

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

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

В пятой главе представлено описание программного комплекса глобальной оптимизации в1ор1:1Сот, в котором реализованы разработанные в рамках диссертационной работы методы многоэкстремальной оптимизации. В § 5.1 приводится общая характеристика комплекса глобальной оптимизации 01орйСот. В § 5.2 представлено описание системы С1ор1лСот-1, ориентированной на решение задач одномерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью оценки эффективности одномерных алгоритмов глобального поиска. В § 5.3 представлено описание системы С1орйСот-2, ориентированной на решение задач двухмерной многоэкстремальной оптимизации. Данная система предназначена для проведения вычислительных экспериментов с целью исследования адаптивной многошаговой схемы редукции размерности. В § 5.4 представлено описание системы многомерной многоэкстремальной оптимизации С1ориСоггН-, которая является основной в комплексе и ориентирована на параллельное решение задач многомерной многоэкстремальной оптимизации. В § 5.5 приведены результаты вычислительных экспериментов для системы 01орйСот+.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Гергель, Александр Викторович

Результаты работы докладывались на Международных конференциях "Высокопроизводительные вычисления на кластерных системах" (Нижний Новгород, 2007, Казань, 2008, Владимир, 2009), Всероссийской конференции "Научный сервис в сети Интернет" (Новороссийск, 2009), научно-технических конференциях "Технологии Майкрософт в теории и практике программирования" (Нижний Новгород, 2007-2008, 2010), на научных конференциях и семинарах Нижегородского государственного университета.

Основное содержание диссертации отражено в девяти работах [12-19,23].

120

Заключение

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

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

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

1. Анциферов Е.Г., Ащепков J1.T., Булатов В.П. Методы оптимизации и их приложений. 4.1. Математическое программирование. - Новосибирск: Наука, 1990.

2. Ашманов С.А., Тимохов А. В. Теория оптимизации в задачах и упражнениях. — М.: Наука, 1991.

3. Базара М, ILlemmu К. Нелинейное программирование. Теория и алгоритмы. -М.: Мир, 1982.

4. Батищев Д. И. Методы оптимального проектирования. — М.: Радио и связь, 1984.

5. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации — Н. Новгород: Изд-во ННГУ, 2006.

6. Богачев К.Ю. Основы параллельного программирования. М.: Бином. Лаборатория знаний,2003.

7. Васильев Ф.П. Численные методы решения экстремальных задач.М.: Наука, 1980.

8. Воеводин В.В. Математические основы параллельных вычислений. М.: МГУ 1991.

9. Воеводин В.В. Модели и методы в параллельных процессах. М.: Наука 1986.

10. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХВ-Петербург, 2002.

11. Габасов Н.С., Кириллова Ф.М. Методы оптимизации. Минск: Изд-во

12. Гергелъ А.В, Гнатюк Д.В. Модификация адаптивных параллельных алгоритмов для многомерной многоэкстремальной оптимизации Труды Всероссийской суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). М.: Изд-во МГУ, 2010. С.352-362.

13. Гергелъ A.B. О новом методе решения многоэкстремальныхмногомерных задач оптимизации //Шестая нижегородская сессия молодых ученых, тез. докл., Нижний Новгород. 2001. С 87-92.

14. Гергель A.B. Применение централизованной схемы параллельного глобального поиска для адаптивной многошаговой схемы редукции размерности //материалы конференции «Технологии Microsoft в теории и практике программирования», Нижний Новгород. 2010. С 64-66.

15. Гергель А. В. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации. Приборостроение, Изд СПГУ, 2009. Т. 52, № 10, С. 74-80.

16. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации. // "Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2009), Изд ВТУ, 2009. С. 92-96.

17. Гергель А.В, Гнатюк Д.В. Адаптивные параллельные алгоритмы для многомерной многоэкстремальной оптимизации. // Материалы конференции Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010), Изд. ПГТУ, 2010. С. 160-165.

18. Гергель A.B. Параллельные методы многоэкстремальной оптимизации с адаптивными решающими правилами. // Материалы конференции Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2010), Изд. ПГТУ, 2010. С. 152-159.

19. Гергель В.П. Алгоритм глобального поиска с использованием производных // Динамика систем: Межвуз. тематич. сб. науч. тр. / Под ред. Ю.И. Неймарка. Горький: ГТУ, 1992.- С. 161 - 178.

20. Гергелъ B.II. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Ж. вычисл. матем и матем. физ. 1996.-Т.36, № 6. - С. 51-67.

21. Гергелъ В.П. Теория и практика параллельных вычислений: учебное пособие. М., Интернет-Университет Информационных Технологий, Бином, 2007.

22. Гергелъ В.П., Гришагин В.А., Гергелъ A.B. Адаптивные параллельные вычисления для многомерной многоэкстремальной оптимизации. Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009 г., г.Новороссийск). М.: Изд-во МГУ, 2009. С.417-421.

23. Гергелъ В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н. Новгород: Изд-во ННГУ, 2001.

24. Гермейр Ю. Б. Введение в теорию исследования операций.- М.:наука, 1971.

25. Гит Ф., Мюррей У.,Райт М. Практическая оптимизация. -М.: Мир, 1985.

26. Голиков А. И., Евтушенко Ю.Г. Теоремы об альтернативах и их применении в численных методах // Ж. вычисл. матем. и матем. физ. -2003. Т.43, №3. - С. 354-375.

27. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация. — Н.Новгород: Изд-во ННГУ, 2007.

28. Гришагин В.А. Об условиях сходимости для одного класса алгоритмов глобального поиска. В сб.: Тезисы докл. III Всес. Семинара «Численные методы нелинейного программирования». Харьков: ХГУ, 1979. С. 8284.

29. Гришагин В.А. Операционные характеристики некоторых алгоритмов глобального поиска // Проблемы случайного поиска. Рига: Зинатне, 1978. №7. С. 198-206.

30. Гришагин В.А., Сергеев Я.Д. Асинхронные параллельныехарактеристические алгоритмы в многомерной рекурсивной глобальной оптимизации // 8-я Международная Конференция

31. Высокопроизводительные параллельные вычисления на кластерных системах" (НРС-2008), Изд КГТУ, 2008. С. 143-150.

32. Даугавет В. А. Численные методы квадратичного программирования.-СПб.: Изд-во СПбГУ, 2004.

33. Демиденко Е.З. Оптимизация и регрессия. М.: Наука, 1989.

34. Евтушенко Ю.Г Методы поиска глобального экстремума // Исследование операций. -М.: ВЦ АН СССР, 1974. Т.4. - С.39-68.

35. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизаций. -М.: Наука, 1982.

36. Евтушенко Ю.Г Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Ж. вычисл. матем. и матем. физ. 1971.-T.il, № 6. - С. 1390-1403.

37. Евтушенко Ю.Г., Малкова В.У., Станевичюс A.A. Распараллеливание процесса поиска глобального экстремума // Автоматика и телемеханика. 2007. - №5. - С.45-58.

38. Евтушенко Ю.Г, Потапов М.А. Методы численного решения многокритериальных задач.// ДАН, 1986. Т.2.№ 11.

39. Ермаков С.М., Жиглявский A.A. Математическая теория оптимального эксперимента. М.: Наука, 1987

40. Ермольев Ю.М., Норкин В.И. Методы решения невыпуклых негладких задач стохастической оптимизации // Кибернетика и системый анализ.-2003. Т.5. - С.89-106.

41. Жиглявский A.A. Математическая теория глобального случайного поиска.-Л.: Изд-во ЛГУ, 1985.

42. Жиглявский A.A., Жилинскас А.Г. Методы глобального экстремума.-М.: Наука, 1991.

43. Жилинскас А.Г.Глобальная оптимизация. Аксиоматика статическихмоделей, алгоритмы, применение.- Вильнюс: Мокслас,1986

44. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

45. Карманов В.Г. Математическое программирование. М.: Наука, 1986.

46. Kapp Ч, Хоув Ч. Количественные методы принятия решений в управлении и экономике.-М.: Мир, 1964.

47. Кнут Д. Искусство программирования. Т.2: Получисленные алгоритмы.-3-е изд.- М.: Вильяме, 2000.

48. Корнеев В.В. Параллельное программирование в MPI. М.-Ижевск: Институт компьютерных исследований, 2003.

49. Лузин H.H. Теория функций действительного переменного. Учпедгиз, М, 1948.

50. Малоземов В.Н. Линейная алгебра без определителей. Квадратичная функция. СПб.: Изд-во СПбГУ, 1997.

51. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.:Наука, 1978.

52. Немировский A.C., Юдин Д.Б. Сложность зада и эффективность методов оптимизации. — М.: Наука, 1979.

53. Немнюгин С.,Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. Спб.: БХВ-Петербург, 2002.

54. Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функции //Ж. вычисл. матем. и матем. физ. 1972. Т. 12. №4. С. 888-896.

55. Пшеничный Б.Н, Данилин Ю.М. Численные методы в экстремальных задачах. М.:Наука, 1975.

56. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.:Наука, 1980.

57. Растригин JI.A. Адаптация сложных систем. Методы и приложения. -Рига: Зинатне, 1981.

58. Растригин JI.A. Статистические методы поиска. -М.: Наука, 1968.

59. Сергеев ЯД. Одномерный детерминированный алгоритм глобальной оптимизации // Ж. вычисл. матем и матем. физ. — 1995. Т.35, № 5. — С. 705-717.

60. Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. -М.: ФИЗМАТЛИТ, 2008. 252 с.

61. Сергеев ЯД., Стронгин Р.Г., Алгоритм глобальной оптимизации с параллельными итерациями // Ж. вычисл. матем и матем. физ. 1989. -Т. 29, №3.-С. 332-345.

62. Стрекаловский A.C. К проблеме глобального экстремума //Докл. АН СССР. 1987. - Т.282, №5. - С. 1062-1066.

63. Стронгин Р.Г. О сходимости одного алгоритма поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. -1973.-Т.4-С.10-16.

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

65. Стронгин Р.Г., Маркин Д. JI. Минимизация многоэкстремальных функций при невыпуклых ограничениях // Кибернетика. — 1986.-Т.4. -С.63-69.

66. Стронгин Р.Г., Гергелъ В.П., Городецкий С.Ю., Гришагин В.А., Маркина М.В. Современные методы принятия оптимальных решений. -Н.Новгород: Изд-во ННГУ, 2002.

67. Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа.-М.: Наука, 1989.

68. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986.

69. Тимонов J1.H. Алгоритм поиска глобального экстремума // Изв. АН СССР. Техническая кибернетика. 1977.-T.3.-C.53-60.

70. Туй X. Вогнутое программирование при линейных ограничениях. //Докл. АН СССР. 1964. - Т. 159, №9. - С. 32-35.

71. Уайлд Д.Дою. Методы поиска экстремума, 1967

72. Якобовский М.В. Распределенные системы и сети. М.: МГТУ «Стакин», 2000.

73. A user's guide to tabu search/isaf. By F. Glover, E. Taillard, D. De. Werra. — The Netherlands: Baltzer Scince Publishers, 1993. Vol. 41 of Special Issue of Annals of Operations Research.

74. Addis В., Locatelli M. A new class of test function for global optimization // J. Global Optim. 2007.- Vol.38, № 3.-P.479-501.

75. Agent Modeling, Papers from the 1996 AAAI Workshop, 1996. AAAI Press. ISBN: 1-5773-5008-1.

76. Andrews G.R. Foundations of Multithreading, Parallel and Distributed Programming. Addison-Wesley,2000 (русский перевод Эндрюс Г.Р.Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом «Вильяме», 2003)

77. Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems / Ed. by P. M. Pardalos.- Dordrecht: Kluwer Academic Publishers, 2000.

78. Archetti F., Schoen F. A survey on the global optimization problem: Generaltheory and computational approaches // Ann. Oper. Res. — 1984. — Vol.1, №2. — P.87-110.

79. Baritompa W. Customizing methods for global optimization — A geometric viewpoint //J. Global Optim. 1993.- Vol. 3, № 2. - P. 193-212.

80. Bayesian Heuristic Approach to Discrete and Global Optimization/ J. Mockus, W.Eddy, A.Mockus et al. Dordrecht: Kluwer Academic Publishers, 1996.

81. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods. Prentice Hall, Englewood Cliffs, New Jersey, 1989.

82. Breiman L., Citler A. A deterministic algorithm for global optimization // Math. Program. 1993. - Vol.58, № 58, № 1 - 3. -P.179-199.

83. Casado L.G., Garcia I., Csendes T. A new multisection technique in interval methods for global optimization computing // Computing. — 2000. — Vol. 65, № 3. -P.263-269.

84. Cvijovic D., Klinowski J. Taboo search an approach to the multiple minima problem // Science.-1995.-Vo;.267, №5198.-P.664-666.

85. Deep Blue Versus Kasparov: The Significance for Artificial Intelligence, Collected Papers from the 1997 AAA! Workshop, 1997. AAA! Press. ISBN: 1-5773-5031-6.

86. Dekkers A., Aarts E. H. L. Global optimization and simulated annealing // Math. Program. 1991. - Vol. 50, № 1 - 3.- P. 367-393.

87. Developments in Global Optimization / Ed. by I. M. Bomze, T. Csendes, R. Horst, P. M. Parlalosc

88. Encyclopedia of Optimization (6 volumes) / Ed. by C A. Floudas, P. M. Parialos.- Kluwer Academic Publishers, 2001.

89. Essays and Surveys in Global Optimization / Ed. by C. Audet, P. Hansen, G. Savard. GERAD 25th Anniversary. N. Y.: Springer-Verlag, 2005.

90. Evtushenko Y.G. Numerical Optimization Techniques. Berlin: SpringerVerlag, 1985.

91. Floudas C. A. Deterministic Global Optimization: Theory, Algoritms, and Applications. Dordrecht: Kluwer Academic Publishers, 2000

92. Flynn M.J. Very high-speed computing systems //Proceedings of the IEEE 1966. 54(12):P. 1901-1909.

93. Fogel D. B. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Piscataway, NJ, USA: Wiley-IEEE Press 2000.

94. Foster I. Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley, 1995.

95. Galperin E. A. The cubic algorithms // J. Math. Analys. And Appl. 1985. V.112. P. 635-640.

96. Gergel V.P. A global optimization algorithm for multivariate function with Lipschitzian first derivatives // J. Global Optim. 1997. - Vol.10, № 3,-P.257-281.

97. Gergel V.P. A software system for multiextremal optimization // European J. Oper. Res. 1993. - Vol.65, № 3. - P. 305-313.

98. Global Optimization in Engineering Design / Ed. by I.E. Grossman -Dordrecht: Kluwer Academic Publishers, 1996.

99. Global Optimization Using Inerval Analysis / Ed. by E.R. Hansen-N.Y.: M.Dekker, 1992.

100. Global Optimization: From Theory to Impementation /Ed. by I. E. Liberti, N. Maculan. Berlin: Springer-Verlag, 2006.

101. Global Optimization: Scientific and Engineering Case Studies/ Ed. by J.D. Pmfer.-Berlin:Springer Verlag, 2006.

102. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley,1989.

103. Grama A.Y., Gupta A. and Kumar V. Isoefficiency: Measuring the scalability of parallel algorithms and architectures // IEEE Parallel and Distributed technology, 1993. 1(3).P.12-21.

104. Grishagin V.A., Sergeyev Y.D., Strongin R.G. Parallel characteristic algorithms for solving problems of global optimization // J.Global Optim. -1997.- Vol. 10, № 2. — P. 185-206.

105. Group W., Lusk E., Thakur R. Using MPI-2: Advanced Features of the Message Passing Interface (Scientific and Engineering Computation).- MIT Press, 1999.

106. Hal Abelson, editor. Workshop on Amorphous Computing, September 13-14, 1999, DARPA ITO, MIT Artificial Intelligence Laboratory, Cambridge, MA, USA. MIT AI Lab.

107. Handbook of Global Optimization / Ed, by P.M.Pardalos, H.E. Romeijn. -Dordrecht: Kluwer Academic Publishers, 2002. Vol.2

108. Handbook of Global Optimization / Ed, by R. Horst, P.M.Pardalos. -Dordrecht: Kluwer Academic Publishers, 1995. — Vol.1

109. Handbook of Test Problems in Local and Global Optimization / C.A. Floudas, P.M. Pardalos, C. Adjiman et al. Dordrecht: Kluwer Academic Publishers, 1999.

110. Hansen P., Jaumard B., Lu S. H. Global optimization of univariate Lipschitz functions: 2. New algorithms and computational comparison // Math. Program. 1992. V.55. P. 273-293

111. Hansen P., Jaurmard B. Lipschitz optimization // Handbook of Global Optimization / Ed, by R. Horst, P.M.Pardalos. Dordrecht: Kluwer Academic Publishers, 1995. - Vol.1.- P.407-493.

112. Hartman J.K. Some experiments in global optimization // Nav. Res. Logist. -1973. Vol.20, № 3. — P.569-576.

113. Henri Elle Bal. Programming Distributed Systems. Silicon Press/Prentice Hall International, 1990/1991. ISBN: 0-9293-0605-8, 978-0-92930-605-6, 0-13722083-9.

114. Holland J. H. Adaptation in Natural and Artificial Systems.- Ann Arbor, MI, USA: The University of Michigan Press, 1975.

115. Horst R., Pardalos P. M., Thoai N.V. Introduction to Global Optimization.j

116. Dordrecht: Kluwer Academic Publishers, 1995.- (The 2 edition Kluwer Academic Publishers, 2001).

117. Horst R., Tuy H. Global Optimization Deterministic Approaches.- Berlin: Springer-Verlag, 1996.

118. Horst R., Tuy H. On the convergence of global methods in multiextremal optimization // J. Optim. Theory Appl. 1987. - Vol.54, № 2. -P.253-271.

119. James E. Baker. Adaptive selection methods for genetic algorithms. In Proceedings of the 1 st International Conference on Genetic Algorithms, pages 101-111, 1985.

120. James E. Baker. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the second International Conference on Genetic Algorithms, pages 14-21, 1987.

121. Kearfott R.B. Rogorous Global Search: Continuous Problems. Dordrecht: Kluwer Academic Publishers, 1996.

122. Kelley C.T. Iterative Methods for Optimization. Philadelphia: SIAM Publications, 1999.

123. Kirkpatrick S., Gellat C.D., Vecchi M.P. Optimization by simulated annealing

124. Science. 1983. - Vol. 220, № 4598. -P.671-680

125. Kumar V., Grama A., Gupta A, Karypis G. Introduction to Parallel Computing. The Benjamin / Cumming Publishing Company, Inc., 1994 (2nd edn.,2003).

126. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing.-The Benjamin/Cummings Publishing Company, Inc., 1994 (2nd edn.,2003).

127. Locatelli M. On the multilevel structure of global optimization problems // Comput. Optim. Appl. 2005.- Vol.30, № 1. - P.5-22.

128. MacLagan D., Sturge T., Baritompa W. Equivalent methods for global optimization // State of the Art in Global Optimization / Ed. By C.A. Floudas, P.M. Pardalos. — Dordrecht: Kluwer Academic Publishers, 1996. P.201-212.

129. Meewella C.C., Mayne D. Q. An algorithm for global optimization of Lipschitz continuous // J. Optim. Theory Appl. 1988. - Vol. 57, № 2. -P.307-322.

130. Michalewicz Z. Genetic Algoritms + Data Structures = Evolution Programs. -3 rd edition. Berlin: Springer-Verlag, 1996.

131. Mladineo R.H. Stochastic minimization of Lipschitz functions // Recent Advances in Global Optimization // Ed. by C. A. Floudas, P. M. Pardalos.-Princeton, NJ, USA: Princeton University Press, 1992.- P.369-383.

132. Mockus J. Bayesian approach to global optimization. Dordrecht: Kluwer Academic Publishers, 1989.

133. New Ideas in Optimization / Ed. By D.W. Corne, M. Dorigo, F. Glover.-Maidenhead, UK: McGraw-Hill, 1999

134. New Ideas in Optimization // Ed. by D.W. Corne, M. Dorigo, F. Glover.-Maidenhead, UK: McGraw-Hill, 1999.

135. Nimerical Techniques for Stochastic Optimization Problems / Ed. by Y. M. Ermoliev, R.J. -B.Wets. Berlin: SpringerOVerlag,1988.

136. Nocedal J., Wright S.J. Numerical Optimization. — Dordrecht: Springer-Verlag,1999.

137. Optimization and Industry: New Frontiers / Ed. by P.M. Pardalos, V.V. Korotkikh. Dordrecht: Kluwer Aademic Publishers, 2003.

138. Pacheco P. Parallel Programming with MPI. Morgan Kaufmann, 1996.

139. Pardalos P. M., Rosen J. B. Constrained Global Optimization: Algorithms and Applications.-N.Y.: Springer-Verlag, 1987.

140. Pardalos P.M. Romeijn H.E., Tuy H. Recent developments and trends in global optimization // J.Comput. Appl. Math. 2000. - Vol.124,№1 -2.-P.209-228.

141. Per Bak, Chao Tang, and Kurt Wiesenfeld. Self-organized criticality. Physical Review A, 38(l):364-374, July 1, 1988. doi:10.1103/PhysRevA.38.364.

142. Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: a new explanation for the effectiveness of voting methods. Annals of Statistics, 26(5): 1651—1686, 1998.

143. Peter J. Angeline and Kenneth E. Kinnear, Jr, editors. Advances in Genetic Programming,volume 2 of Complex Adaptive Systems. MIT Press, Cambridge, MA,USA, October 26, 1996. ISBN: 0-2620-1158-1, 978-026201-158-7.

144. Pinter J. D. Global optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementation and Applications). Dordrecht: Kluwer Academic Publishers, 1996.

145. Pinter J.D. Convergence qualification of adaptive partition algorithms in global optimization // Math. Program. 1992. - Vol. 56, № 1-3. - P.343-360.

146. Proceedings of the The Fifth Conference on Innovative Applications of Artificial Intelligence (IAAI 1993), July 11-15, 1993, Washington, DC, USA. AAAI. ISBN:0-9292-8046-6.

147. Quinn M.J. Parallel programming in C with MPI and OpenMP.- New York, NY: McGraw-Hill, 2004.

148. R. Battiti and G. Tecchiolli. The reactive tabu search. ORSA Journal on Computing, 6(2): 126-140, 1994.i

149. Ratschek H., Rockne J. New computer Methods for Global Optimization. -Chichester, England: Ellis Horwood Ltd, 1988.

150. Ratschek H., Rockne J. New Computer Methods for Global Optimization.-Chichester, England: Ellis Hordoow Ltd, 1988.

151. Recent advances in Global Optimization / Ed. by C.A. Floudas, P.M. Pardalos.- Princeton, NJ, USA: Princeton University Press, 1992.

152. Rinnooy Kan A.H.G., Timmers G.T. Global optimization // Handbook of Operations Research, Volume 1: Optimization / Ed. by.G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd. Amsterdam: North-Holland, 1989.-P.631-662.

153. Roosta S.H. Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-Verlag, NY,2000.

154. Schhwefel H.-P. Evolution and Optimum Seeking. — N.Y.: John Wiley &Sons, 1995.

155. Schneider J. J., Kirkpatrick S. Stochastic Optimization.-Berlin: Springer, 2006.

156. Schoen F. Stohasctic techniques for global optimization: A survey of recent advances //J. Global Optim.-1991.-Vol.1, № 1. -P.207-228.

157. Schwefel H.-P. Evolution and Optimum Seeking. -N.Y.: John Wiley & Sons, 1995.

158. Sergeyev Y. D. A global optimization algorithms using smooth auxiliary functions: Tech. Rep. 1. Institute of Systems and Informatics, Rende (CS), Italy: ISI-CNR, 1994.

159. Sergeyev Y. D. An efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms // J. Optim. Theory Appl.-2000.-Vol.l07№ 1. -P. 145-168.

160. Sergeyev Y. D. Global one-dimensional optimization using smooth auxiliaryfunctions //Math. Program. 1998.-Vol.81, № 1. -P. 127-146.

161. Sergeyev Y. D., Grishagin V.A. Parallel asynchronous global search and the nested optimization scheme // J. Comput. Anal. Appl. — 2001. — Vol. 3, № 2. — P. 123-145.

162. Sergeyev Y. D., Grishagin V.A. Parallel method for finding the global minimum of univariate function // J. Optimt. Theory. Appl. — 1994. Vol. 80, №3.-P. 513-536.

163. Sergeyev Y. D., Grishagin V.A. Parallel Method for Finding the Global Minimum of Univariate Functions // Journal of Optimization Theory and Applications, 1994. V. 80.№ 3.

164. Sergeyev Y. D., Grishagin V.A. Sequential and parallel global optimization algorithms // Optim. Methods Softw. 1994. - Vol. 3, № 1 -3. - P. 1111-124.

165. Sergeyev Y.D. A global optimization algorithm using derivatives and local tuning: Tech. Rep. 1. Institute of Systems and Informatics, Rende (CS), Italy: ISI-CNR, 1994.

166. Sergeyev Y.D. A one-dimensional global minimization algorithm using local estimation of Lipschitz constant: Tech. Rep.28. — University of Calabria, Rende (CS), Italy: DEIS, Department of Electronics, Computer Sience and Systems, 1992.

167. Sergeyev Y.D. An algorithm for finding the global minimum of multiextremal Lipschitz functions // Operations Researh 93 / Ed. by A. Bahem, U. Derigs, MJunger, R.Schrader.-Physica-Verlag, 1994.-P.463-465.

168. Sergeyev Y.D. An information global optimization algorithm with local tuning // SIAM J. Optim. 1995. - Vol.5, № 4.- P.858-870.

169. Sergeyev Y.D. Parallel information algorithm with local tuning for solving multidimensional GO problems // J. Global Optim. -1999. -Vol.15, № 2. -P. 157-167.

170. Shir M., Otto S., Huss-Lderman S., Walker D., Dongarra J. MPI: The Complete Reference. MIT Press, Boston, 1996.

171. Skillicorn D.B., Talia D. Models and languages for parallel computation // ACM Computing surveys, 1998, 30, 2.

172. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: The Complete Reference. — MIT Press, Boston, 1996.

173. State of The Art in Global Optimization: Computation Methods and Applications / Ed. by. C.A. Floudas, P.M. Pardalos.- Dordrecht: Kluwer Academic Publishers, 1996.

174. Stephanos Androutsellis-Theotokis and Diomidis Spinellis. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv., 36(4):335-371,2004. ISSN: 0360-0300.

175. Stephens C.P., Baritompa W. Global optimization requires global information // J. Optim. Theory Appl. 1998. - Vol. 96, № 3.- P.575-588.

176. Stochastic and Global Optimization / Ed. by G.Dzemyda, V. Saltenis, A. Zilinskas. Dordrecht: Kluwer Academic Publishers, 2002.

177. Stochastic and Global Optimization / Ed. by. G. Dzemyda, V. Saltenis, A. Zilinskas. Dordrecht: Kluwer Academic Publishers, 2002.

178. Storn R., Price K. Different evolution A simple and efficient heuristic for global optimization over continuous spaces // J. Global Optim. - 1997.-Vol.ll, №4. -P.341-259.

179. Strekalovsky A.S. Global optimality conditions for nonconvex optimization // J. Global Optim. 1998. - Vol.12, №4. -P.415-434.

180. Strongin R.G., Sergeev Ya.D. Global multidimensional optimization on parallel computer//Parallel Comput. 1992.- Vol. 18, № 11.-P.1259-1273.

181. Strongin R.G., Sergeev Ya.D. Global optimization with Non-Convex Constrains. Sequential and Parallel Algorithms.-Dordrecht: Kluver Academic Publishers. The Netherlands, 2000.

182. Sturua E.G., Zavriev S.K. A trajectory algorithm based on the gradient method. The search on the quasioptimal trajectories //J. Global Optim. 1991. -Vol. 1, №4.-P.375-388.

183. Tawarmalini M., Sahinidis N.V. Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory Algorithms, Software and Applicatios. Dordrecht: Kluwer Academic Publishers, 2002.

184. Torn A, Zilinskas A. Global optimization. Berlin: Springer-Verlag, 1989.

185. Torn A., Zilinskas A. Global Optimization. Berlin: Springer-Verlag, 1989.

186. Towards Global Optimization (Volumes 1 and 2) / Ed. by L.C.W. Dixon, G.P. Szego. — Amsterdam: North-Holland,1975,1978.

187. Van Laarhoven P. J. M., Aarts E. H. L. Simulated Annealing: Theory and Applications.- Dordrecht: Kluwer Academic Publishers, 1987.

188. Walster G., Hansen E., Sengupta S. Test results for global optimization algorithm // Numerical Optimization 1984 / Ed. by P.T. Boggs, R.H. Byrd, R. B. Schnabel. -Phuiladelphia: SIAM, 1985. -P.272-287.

189. Wilkinson B., Allen M. Parallel programming. Prentice Hall, 1999.

190. William Bateson. Mendel's Principles of Heredity. Cambridge University Press, Cambridge, 1909. ISBN: 978-1-42864-819-7.

191. Zavriev S.K. On the global optimization properties of finite-difference local descent algoritms // J. Global Optim. 1993.-Vol.3, №3.-P.337-358.

192. Zhigljavsky A. A. Theory of Global Random Search. Dordrecht: Kluwer Academic Publishers, 1991.

193. Zhigljavsky A. A., Zilinskas A. Stochastic Global Optimization. N. Y.: Springer, 2008.

194. Zomaya A.Y. Parallel and Distributed Computing Handbook. McGraw-Hill, 1996.