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

• Автор: Ленцевичюс, Раймондас Анатолиевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Каунас
• Количество страниц: 176 c. : ил

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

ГЛАВА I. СОСТОЯНИЕ ВОПРОСА.

1.1. Краткая классификация методов дискретной оптимизации и прикладные задачи.

1.2. Методы структурного представления и преобразования графа сети,

прикладные задачи

1.3. Приближенные методы решения невыпуклой транспортной задачи размещения

1.4. Методы решения задачи минимизации гамильтонова цикла и квадратичной

задачи о назначениях .

1.5. Методы случайного поиска и оценки точности приближенного решения задач ДО . .

1.6. Выеоды по главе I

ГЛАВА II. СТРУКТУРНО ТОПОЛОГИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ ГРАФА СЕТИ. ПРИМЕНЕНИЕ
ДЛЯ РАСЧЕТА НАДЕЖНОСТИ ЭЛЕКТРИЧЕСКИХ
2.1. Постановка задачи, структура
данных.
2.2. СТП для выделения и изменения прадерева
и циклов графа .
2.3. Вычислительная сложность и способы повышения эффективности методов и алгоритмов
2.4. Внедрение методики выделения леса для
расчета надежности электрических
2.5. Алгоритмы АРСС. Эффективный алгоритм
выделения леса прадеревьев
2.6. Тестовый пример, вычислительная эффективность, практические расчеты
2.7. Выводы по главе II.
ГЛАВА III. ГРАФОТОЮЛОГИЧЕСКИИ АЛГОРИТМ ПОКООРДИНАТНОГО МЕТОДА ДЛЯ РЕШЕНИЯ МНОГОЭКСТРЕ
МАЛЬНОИ СЕТЕВОЙ ТРАНСПОРТНОЙ ЗАДАЧИ
РАЗМЕЩЕНИЯ С РАЗРЫВНОЙ ФУНКЦИЕЙ ЦЕЛИ
3.1. Графотопологическая модель
3.2. Графотопологический алгоритм покоординатной оптимизации.
3.3. Представление данных, характеристика
программы, вычислительная сложность
3.4. Решение прикладных задач .
3.5. Выводы по главе III . .
ГЛАВА 1У. ГРАФОТОПОЛОГИЧЕСКИи АЛГОРИТМ ЗАМЕНЫ
ДУГ ДИСКРЕТНОЙ ПОКООРДИНАТНОЙ ОПТИМИЗАЦИИ ГАМИЛЬТОНОВА ЩКЛА БОЛЬШОЙ РАЗМЕРНОСТИ
4.1. Графотопологическая модель
4.2. Метод дискретной покоординатной
оптимизации
4.3. Графотопологические преобразования гамильтонова цикла и допустимость решения
4.4. Алгоритм и программа минимизации гамильтонова цикла.
4.5. Алгоритм ДПО для квадратичной задачи
о назначениях .
4.6. Внедрение модели и алгоритма ТЯ построение минимального маршрута
обхода сверления печатных плат .
4.7. Выводы по главе ТУ.
ГЛАВА У. КОМПЛЕКСНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМОВ
СЛУЧАЙНОГО ПОИСКА С ЛОКАЛЬНО, ОПТИМИЗАЦИЕЙ СЕТЕВЫХ ЗАДАЧ ДО.
5.1. Постановка задачи
5.2. Тестовые задачи гамильтоновой цепи
5.3. Вычислительная сложность .
5.4. Алгоритмы приемлемые в среднем .
5.5. Непараметрическое оценивание числа локальных минимумов алгоритмов случайного поиска с локальной оптимизацией .
5.6. Выводы по главе У
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Полученные вычислительные результаты эффективности алгоритма ДПО показывают о возможности его использования в качестве препроцессора получения решений в составных и гибридных схемах алгоритмов. В пятой главе приводится методика комплексного исследования вычислительной сложности по памяти, быстродействию и точности приближенных алгоритмов решения задач ДО, включая алгоритмы случайного поиска с локальной оптимизацией. Введено понятие и определение алгоритма приемлемого в среднем по отношению ручных методов решения и других алгоритмов, включая алгоритмы существующих стандартных САПР. Построены теоретические оценки числа локальных минимумов при заданной точности и доверительной вероятности. Оценки позволяют определить конец счета, что связано с экономией времени ЭВМ, проверить стабильность полученных решений от размера решаемых задач. Получено, что теоретические оценки хорошо совпадают с экспериментом (отличие в среднем на 5/9. Выявлено, что наиболее сбалансированными вычислительными характеристиками по отношению существующих обладает разработанный алгоритм. Установлено, что разработанный алгоритм является приемлемым в среднем по отношению ручных методов решений и решений существующих стандартных САПР. Выявлено хорошая стабильность точности полученных решений от размеров решаемых задач. При этом установленно, что достаточно малого количества локальных минимумов (2-3) для получения решений с точностью 0% - 3,9% на широкой шкале размерностей решаемых задач от до точек. Полученные результаты легли в основу обоснования экономии при серийном производстве печатных плат РЭА. Разработанный единый подход к построению УСД структурного дерева и решению других задач структурно-топологических преобразований графа - сети. Полученные оценки вычислительной сложности алгоритмов выделения дерева (леса) и структурного дерева (леса). Разработанные конструктивные графо-топологическая модель и алгоритм случайного поиска с локальной оптимизацией на УСД структурном дереве решения невыпуклой многоэкстремальной сетевой транспортной задачи размещения, реализующие метод покординатной оптимизации, позволяющие решать задачи больших размерностей без применения агрегирования. Разработанный метод дискретной покоординатной оптимизации (ДПО), конструктивные графо-топологическая модель и алгоритм случайного поиска с локальной оптимизацией на УСД структурном дереве решения задачи минимизации ГЦ большой размерности (до ЮОО-и точек на ’ байтовой по памяти ЭВМ), обобщающие метод С. Лина и решающие до сих пор нерешенную проблему организации памяти, что позволяет расширить диапазон размерностей решаемых прикладных задач маршрутизации до практических потребностей (автоматического проектирования маршрутов сверления печатных плат РЭА, запускаемых в серийное производство). Разработайте алгоритм ДПО решения КЗН и полученный вариант алгоритма парных перестановок для специального случая КЗН - задачи размещения. Разработанная методика комплексного исследования вычислительной сложности приближенных алгоритмов, включая алгоритмы случайного поиска с локальной оптимизацией, позволяющая исследовать вычислительные характеристики алгоритмов в минимаксном отношении, приемлемость в среднем по отношению ручных решений к решений существующих САПР. Полученные теоретические оценки числа локальных минимумов при заданной точности и доверительной вероятности, позволяющие определить конец счета, что связано с экономией времени ЭВМ. ГЦ по приведенной методике на десяти выбранных реальных (маршруты сверления печатных плат), известных и специально построенных тестовых задачах большой размерности (от до точек), позволивший установить пригодность алгоритма для решения прикладных задач большой размерности (например, автоматизации проектирования маршрута сверления печатных плат) и найти обоснование экономической эффективности в серийном производстве. Лит. Лит. Лит. ЧПУ печатных плат РЭА, запускаемых в серийное производство. Применение конструктивных графо-топологических методов и алгоритмов для решения этих задач позволяет получать экономически й эффект тыс. Связь с научной тематикой.