ЛЕКЦИЯ 16. Курс: Проектирование систем: Структурный подход Каф. Коммуникационные сети и системы, Факультет радиотехники и кибернетики Московский физико-технический институт (университет) / Марк Ш. ЛЕВИН Институт проблем передачи информации, РАН Oct. 8, 2004 ПЛАН: 1.Техническая документация (опыт в России) 2.Типы перестановочного приема 3.Генетические алгоритмы 4.Многокритериальная эволюционная оптимизация 5.Multidisciplinary optimization 6.Смешанное целочисленное нелинейное программирование

Техническая документация (опят в России) 1.Предварительный аван-проект 2.Аван-проект 3.Техническое предложение 4.Техническое задание 5.Технический проект 6.Рабочий проект 7.Отчет об 1-ом этапе опытной эксплуатации (включая предложения по улучшению) 8.Итоговый отчет об эксплуатации (включая предложения по улучшению) БАЗОВАЯ ВЕРСИЯN 1.Техническое предложение 2.Техно-рабочий проект 3.Отчет об эксплуатации «СОКРАЩЕННАЯ» ВЕРСИЯ

Типы перестановочного приема (иллюстрация) jk Последовательность... jj+1 Последовательность... j n Последовательность... БАЗОВАЯ ВЕРСИЯ ВЕРСИЯ ДЛЯ СОСЕДНИХ ЭЛЕМЕНТОВ ВЕРСИЯ ДЛЯ ПОСЛЕДНЕГО (ИЛИ ПЕРВОГО) ЭЛЕМЕНТА

Перестановочный прием с 3-мя и 4-мя элементами (иллюстрация) j-2 j-1j Последовательность... j+1 ВЕРСИЯ ДЛЯ ПЕРЕСТАНОВОЧНОГО ПРИЕМА С 3-МЯ ЭЛЕМЕНТАМИ j-1j Последовательность... j+1 ВЕРСИЯ ПЕРЕСТАНОВОЧНОГО ПРИЕМА С 4-МЯ ЭЛЕМЕНТАМИ

Перестановочный прием: случай размерности 2 (иллюстрация) «Площадь»... 2-ЭЛЕМЕНТ ПЕРЕСТАНОВОЧНЫЙ СЛУЧАЙ... «Площадь»... 4-ЭЛЕМЕНТ ПЕРЕСТАНОВОЧНЫЙ СЛУЧАЙ...

Генетические алгоритмы (иллюстрация для задачи о рюкзаке) Решение x 0 = ( x 1, …, x i, …, x m ) Базовая задача о рюкзаке: max m i=1 c i x i s.t. m i=1 a i x i b x i {0, 1}, i = 1, …, m

Генетические алгоритмы (иллюстрация для задачи о рюкзаке) ШАГ 1. ИСХОДНОЕ РЕШЕНИЕ x 0 ШАГ 2. РАЗБИЕНИЕ x 0 НА 2 ЧАСТИ ШАГ 3. МУТАЦИЯ (ГЕНЕРАЦИЯ ВЕРСИЙ): *перестановка элементов, *изменение элементов и др..... a 1 a 2 a 3 a 4... b 1 b 2 b 3 b 4... ШАГ 4. ГЕНЕРАЦИЯ НОВЫХ РЕШЕНИЯ НА ОСНОВЕ ПАР ( a i, b j )... c 1 c 2 c 3 c 4... a b

Генетические алгоритмы (иллюстрация для задачи о рюкзаке) ШАГ 5. Исключение некоторых решений по ресурсным ограничениям( b )... c 1 c 2 c 3 c 4... ШАГ 6. Отбор наилучших решений... c 1 c 2 c 3... Отбор на основе двух подходов: 1.Отбор на основе функции полезности 2.Отбор на основе правила Парето ЭТО - Многокритериальная эволюционная оптимизация ШАГ 7.Повторение шагов 2, 3, 4, 5 и 6 для отобранных решений

Multidisciplinary optimization (проектирование систем для космоса, авиации, строительства, кораблестроения) max f (x) ( or extr f(x) ) subject to 1 (x) W вес B 1 2 (x) B 2 высота C 1 3 (x) C 2 температура D 1 4 (x) D 2 надежность... k (x) 0 Общая модель оптимизации с ограничениями Соответствующими определенным дисциплинам (в частности, вес, длина, надежность и др.): j (x) - функция ограничения (1 j k) Int. Society for Structural and Multidisciplinary Optimization (civil engineering, ship engineering, marine engineering, aerospace engineering) // Optimal design of structures (including issues of fluids)

Смешанное целочисленное нелинейное программирование (process systems engineering & chemical engineering) min F ( x, y ) subject to h (x, y) = 0 g (x, y) 0 где x - вектор бинарных переменных (выбор подсистем) y - вектор непрерывных переменных / параметров (например, размер) Общая модель оптимизации включающая целые и непрерывные переменные: *Global optimization *Process Systems Engineering (chemical engineering, etc.) *Prof. C.A. Floudas (Princeton Univ, Chemical Engineering) *Prof. I.E. Grossmann (Carnegie Mellon Univ., Chemical Engineering)

Основные методы для смешанного целочисленного нелинейного программирования 1.Метод ветвей и границ 2.Комбинаторные гибридные методы 3.Метод градиента 4.Метод внутренней точки (Interior point method)