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

• Автор: Нгуен Минь Ханг
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 116 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

1. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ

РЕШЕНИЯ БОЛЬШИХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

1.1. Генетический алгоритм как метод нахождения

оптимальных решений

1.2. Метод решения задачи одномерного раскроя на основе генетического алгоритма

1.2.1. Общее описание задачи одномерного раскроя материалов

1.2.2.Метод генерации столбцов

1.2.3.Математическая постановка задачи раскроя стальных листов разных размеров

1.2.4.Генетический алгоритм для решения задачи раскроя стальных листов

1.2.5.Практические результаты применения алгоритма СА-СС для задачи раскроя
1.3. Использования генетического алгоритма для решения задачи покрытия множества
1.3.1.Постановка задачи о покрытии множества
1.3.2.Подход, основанный на генетическом алгоритме, для нахождения минимального покрытия
1.3.3.Результаты использования ГА для решения задачи покрытия множества
1.4. Оптимизация структуры атомного кластера с помощью генетического алгоритма
1.4.1.Задача конфигурационной оптимизации атомного кластера
1.4.2.Обзор предложенных методов

1.4.3.Генетический алгоритм оптимизации структуры атомного кластера
1.4.4. Параллельная реализация
1.4.5.Результаты численных экспериментов нахождения оптимальной структуры атомного кластера
2. МЕТОД НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ
2.1. Нахождение проекции точки на множество решений
двойственной задачи линейного программирования
2.2. Программная реализация и результаты вычислений
метода Ньютона для решения двойственной задачи ЛП
3. ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ОБОБЩЕННОГО
МЕТОДА НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ БОЛЬШОЙ РАЗМЕРНОСТИ
3.1. Параллельный итерационный алгоритм
3.2. Основные операции параллельного алгоритма
3.3. Схемы разбиения данных
3.3.1.Столбцовая схема
3.3.2.Строчная схема
3.3.3.Клеточная схема
3.3.4.Безматричная схема
3.4. Результаты численных экспериментов
ВЫВОДЫ
ЦИТИРОВАННАЯ ЛИТЕРАТУРА

ВВЕДЕНИЕ
Объект исследования и актуальность темы.
С развитием человечества растет и объем обрабатываемой информации, что приводит к необходимости решать оптимизационные задачи все больших размерностей. Эта тенденция особенно заметна в таких областях как биоинженерия и экономика. Для решения задач большой размерности наряду со увеличением вычислительной мощности компьютеров необходима разработка новых алгоритмов и методов, эффективно использующих вычислительные ресурсы и позволяющих получить решения для ранее нерешаемых задач.
Было разработано множество алгоритмов и методов решения различных оптимизационных задач. Многие практические задачи характеризуются высокой размерностью, наличием трудно формализуемых ограничений, нечисловым характером части переменных. При этом как формализация, так и численное решение задач принятия решений при планировании, распределении ресурсов, оптимизации сложных процессов в различных приложениях вызывает известные трудности.
В частности, существенные затруднения связаны с высокой размерностью решаемых задач. Многие прикладные задачи экономики и управления могут быть представлены в виде задач линейного программирования (ЛП), для решения которых давно существуют численные методы и программное обеспечение, и, как могло бы показаться, не представляет никакой трудности найти оптимальное решение [1], [2]. Однако размерности современных задач порою не позволяют решить их традиционными способами, поэтому требуется разработка новых подходов решения с привлечением мощных вычислительных ресурсов. Наличие больших, более мощных и доступных мультипроцессорных компьютеров означает, что

вероятностью:
№ = <127>
Оператор мутации воздействует на особи 5 = (61
образом:
Ь = 6® при I и г д г = 1,М (1-28)
Щ[з] = ВД] = ИЛ при jrиj = l
6[г] = №[г — 1, 6[г] = Ьч[г] + 1 если 1?[г] > 0. (1.30)
Щ_г = ЬР[г], Ь[г — Ьч[г если Pr — 0. (1-31)
Оператор отбора. Вероятность отбора определяется
пропорционально степени приспособленности:
Л=УШШ7) <1Ж)
V/(5г)
где 5 есть особь из рассматриваемой популяции С
Заметим, что операторы скрещивания и мутации, определенные выше, гарантируют того, что особи потомки и родители всегда являются разбиением одного и того же вектора.
Алгоритм вА-СС
Вход: то, М, I, Ь, 6, с
Выход: оптимальное решение задачи ж* вместе с соответствующей картой раскроя А.
Шаг 0. Создать популяцию из Н особей Со = {яю

т = ]Гб?0 = б,г = 1