М.М. ГОРБУНОВ-ПОСАДОВ - Системное обеспечение пакетов прикладных программ (1184225), страница 31
Текст из файла (страница 31)
В качестве пробныхточек пространства параметров берутся точки равномерно распределенныхпоследовательностей.Особенность метода состоит в том, что диалог конструктора с ЭВМпротекает в очень благоприятных для конструктора условиях: он оперируетпривычными для него величинами - значениями критериев - и не должен«комбиниро-вать», т.е. гадать, какой выигрыш по одним критериям могут дать уступкипо другим критериям; это выясняется в процессе диалога.6.1.2. Организация исследования. Введем некоторые понятия,используемые в дальнейшем изложении. Параметрами αi (1 ≤ i ≤ N) будемназывать те величины, которые конструктор может варьировать дляполучения оптимального решения.
Пространством параметров будемназывать N-мерное пространство, состоящее из точек A с координатами(α1,…,αN).Как правило, конструктор может указать разумные пределы изменениякаждого из параметров, которые мы будем называть параметрическимиограничениями:В результате получается N-мерный прямоугольный параллелепипед впространстве параметров.
Объем этого параллелепипеда обозначим через V.Программа, моделирующая исследуемый объект, должна по заданнойсовокупности значений параметров модели рассчитать значения рядафункционалов φj (1 ≤ j ≤ M). Каждый из функционалов имеет очевидный дляконструктора физический смысл (мощность, стоимость, вес и т.д.).Конструктор должен указать, какие функционалы будут выступать вкачестве критериев оптимизации. Остальные вычисляемые функционалыстанут рассматриваться как псевдокритерии - их значения интересуютконструктора, но в процессе определения оптимальных значений параметровони не участвуют.
Написав моделирующую программу и определивкритерии оптимизации, можно переходить к вычислению допустимых точекв пространстве параметров, которое включает в себя этапы расчета, выборакритериальных ограничений и обработки.На этапе расчета программы пакета КРИТ выбирают К пробных точекA1,...,AK , равномерно распределенных в области, заданной ограничениями(1). В каждой из пробных точек посредством обращения к моделирующейпрограмме вычисляются значения функционалов φj (1 ≤ j ≤ M). Для каждогофункционала составляется так называемая таблица испытаний, в которойзначения φj(A1), … ,φj(AK) расположены в порядке возрастания (убывания) иуказаны номера соответствующих пробных точек. Таблица испытанийпозволяет увидеть максимум и минимум функционала,155получить представление о частоте тех или иных значений φj(A).На этапе выбора конструктор, просматривая таблицы испытаний, должендля каждого критерия из числа функционалов у, назначить критериальныеограничения (односторонние или двухсторонние), т.е.
указать диапазонзначений критерия, который он считает приемлемым. При первоначальныхрасчетах рекомендуется задавать относительно слабые ограничения, с темчтобы в таблицах испытаний осталось больше допустимых точек.На этапе обработки программы пакета КРИТ отбирают те пробныеточки, для которых значения всех критериев попадают в диапазон, указанныйконструктором. Если множество отобранных таким образом допустимыхточек пусто, то следует вернуть конструктора на этап выбора критериальныхограничений и потребовать от него уступок, т.е.
расширения границдиапазонов. Если конструктор продолжает настаивать на своих ограничениях,можно попытаться повторить этап расчета, увеличив число исследуемыхпробных точек.Если и это не помогло, т.е. при большом числе испытаний допустимыеточки не обнаруживаются, то имеются серьезные основания считать, чтовыбранные критериальные ограничения несовместны. Конечно, нельзякатегорически исключить возможность того, что в некоторой точке А',отличной от A1,...,AK , получаются удовлетворяющие конструктора значениякритериев. Однако, даже если такая точка А' существует, то из-заравномерности распределения пробных точек ее окрестность, в которойсохраняется «замечательное» свойство, очень мала (объем ее порядка V/K) ипрактически система, соответствующая А', будет неустойчивой (неконструктивной).Если же множество допустимых точек не пусто, то можно переходить кболее подробному анализу этих точек, на основе которого и решаетсяисходная задача оптимизации машины.Здесь может сложиться впечатление, что при проведении расчетов порассмотренной методике средства пакета КРИТ играют весьма скромнуюроль.
На самом деле это далеко не так.Прежде всего отметим, что узловым моментом в данной методикеявляется равномерность распределения пробных точек в N-мерномпространстве параметров. Выяснилось, что большинство существующихдатчиков случайных чисел не удовлетворяют в полной мере требованиюравномерности инеобходим специальный алгоритм генерации пробных точек. Программа,реализующая этот алгоритм, разумеется, включена в пакет КРИТ, как имногие другие общие для оптимизационных расчетов программы. Тем самымне только экономятся усилия по программированию конкретных оптимизационных задач, но и, что не менее важно, у пользователя пакета появляетсявполне обоснованная уверенность в том, что он ничего не упустил иправильно интерпретирует предписания данной методики.Кроме того, используемый пакетом общий каркас оптимизационнойпрограммы содержит в себе удобные гнезда для конкретных фрагментовпрограмм моделирования. Располагая вновь создаваемые программы в этихгнездах, пользователь получает в свое распоряжение богатый арсеналалгоритмических находок, собранных разработчиками пакета из различныхрешавшихся ранее оптимизационных задач.6.1.3.
Каркас оптимизационной программы. Предписываемый пакетомКРИТ каркас оптимизационной программы изображен на рис.6.1. В каркасеможно выделить две части: ядро пакета, недоступное пользователю длямодификации, и оболочку, в гнездах которой располагаются программыпользователя, реализующие конкретную оптимизируемую модель.Рассмотрим назначение отдельных гнезд каркаса.Расчет начинается с главной программы (MAIN). Здесь задаютсяпараметры расчета, значения границ изменения параметров модели,ограничения на критерии, распределяется память для рабочих массивов и др.Программа ядра - COTROL - осуществляет организацию основногоцикла работы пакета.Вначале выполняется программа оболочки INITAL, инициализирующаярасчет. Инициализация может включать в себя ввод начальных данных,вычисление констант, очистку массивов, открытие файлов и др.Предполагается, что программа INITAL работает один раз на расчет.Дальнейшая работа пакета производится в рамках цикла, числоповторений которого определяется числом требуемых испытаний.
Прикаждом выполнении тела цикла производится вычисление значенийкоординат очередной пробной точки по значениям стандартной равномернораспределеннойвединичномкубеквазислучайнойN-мерномпоследовательности. В простейшем случае вычисление сводится к отображению множества точек единичного N-мерного куба в точки N-мерногопараллелепипеда, границы которого были заданыв виде параметрических ограничений.
Вычисление значений координатпробных точек производится в программе, размещаемой в гнезде оболочкиREFLEX.После того, как очередная пробная точка получена, нужно проверить,удовлетворяет ли она простым функциональным ограничениям на параметры.Дело в том, что в конкретных приложениях форма области определения задачикак правило отличается от N-мерного параллелепипеда - в области могут быть«вырезаны» L-мерные полосы, выколоты точки и т.д. В этом случае формаобласти может быть задана в виде алгебраических неравенств и соотношений,называемых в дальнейшем простыми функциональными ограничениями. Дляполучения координат пробной N-мерной точки сначала получают значениякоординат в объемлющем область определения N-мерном параллелепипеде, азатем проверяют функциональные ограничения.
Если точка попала в областьопределения, то она пригодна для дальнейших расчетов. Программа оболочки,осуществляющая проверку пригодности пробной точки, размещается в гнездеSIMPLE.Если точка признается непригодной, то пакет переходит к выборуследующей пробной точки. Если точка признана пригодной (т.е. онапринадлежит области определения задачи), то выполняется программа расчетазначений функционалов в полученной пробной точке.Программа расчета - MODELE - должна быть организована так, чтобы онадопускала многократное обращение.
Если вычисление значений в одной точкезанимает много времени, то, чтобы сократить возможный ущерб от повторногосчета при сбоях, рекомендуется использовать возможности пакета по созданиюконтрольных точек через любое заданное число шагов.Полученные значения функционалов могут быть дополнительноисследованы. В некоторых задачах существуют требования, налагаемые накомбинации значений функционалов.
Например, два функционала не должнысильно отличаться друг от друга, сумма значений других функционалов недолжна превышать значения некоторой константы и др. По существу,введениетакоготребованияэквивалентновведениюнового«псевдокритерия», для которого заданы ограничения. Однако конструкторуможет быть неудобно вводить новый псевдокритерий - в этом случае болееестественно иметь средство проверки значений самих функционалов.Проверка осуществляется в программе COMPLX. Если значенияфункционалов в пробной точке подходят, то эти значения запоминаютсяпакетом и подлежат дальнейшейобработке.
Заметим, что в отличие от программы проверки простыхфункциональных ограничений (SIMPLE), программа проверки «сложных»функциональных ограничений на критерии (COMPLX) выполняется послевычисления значений функционалов. И простые, и сложные ограничениямогут отсутствовать.Выполнив рассмотренные выше действия, пакет переходит квычислению следующей точки.После того, как проведено требуемое число испытаний, пакет выполняетпрограмму оболочки POST, завершающую расчет модели. Завершающиедействия могут включать закрытие файлов пользователя, сбор статистики,печать сообщений и др.Если конструктор желает совместить расчет с обработкой, то он задаетэто с помощью определенной комбинации значений управляющихпараметров.
Обработка результатов испытаний производится программойRESUME и завершается выдачей на печать разнообразных таблиц играфиков. В частности, можно напечатать таблицы испытаний для каждогоиз функционалов, таблицы значений параметров, таблицы коэффициентовкорреляциикритериев,значениякритериев,удовлетворяющиекритериальным ограничениям, сводную таблицу испытаний.
Кроме того,можно получить графическое изображение зависимости пар критериев, атакже напечатать множество решений, оптимальных по Парето.Понятие оптимальности по Парето требует некоторых пояснений. Есликонструктор желает осуществить выбор параметров, принимая во вниманиенесколько важнейших критериев φjl (1 ≤ l ≤ M1), то можно облегчить ему этотвыбор, исключив из числа пробных точек такие, которые заведомо не могутоказаться наилучшими. Пробная точка А может быть отброшена, еслисуществует пробная точка А' такая, что φjl (А')≥ φjl (А) для всех значений l изотрезка [l,M1] и хотя бы для одного значения l имеет место строгоенеравенство. (Предполагается, что критерий φjl максимизируется. Если же онминимизируется, то вместо отношения ≥ берется отношение ≤.)Паретовскими называются пробные точки, которые остаются после отбрасывания всех таких «бесперспективных» точек.Иногда полезно ограничить обработку определенным подмножествомуспешных испытаний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
