Введение к работе
Актуальность проблемы. В настоящее время создавшаяся экономико-политическая ситуация з стране существенно отразилась на развитии космической техники и объемах космических исследований Росси. Значительное сокращение финансирования исследований космоса в короткий срок может привести к потере приоритета страны в этой области науки, снижению темпов развития и совершенствования космической техники, что объясняется, прежде всего, высокими темпами развития космической отрасли в ряде стран, епн недавно не числящихся в рейтинговом списке космических держав, а іакже быстрой сменой поколений космотехники, ее новыми Функциями и, как следствие, качественно новыми заказами на производство и научные исследования.
В связи с этим одними из главных зад;, і, стоящих перед российскими специалистами сегодня, является задача эффективного использования и расширения возможностей имеющегося космического парка и задача совершенствования программно-технического обеспечения управления его объектами - космическими аппартами (КЛ). Указанные задачи требует системного подхода при их решении. Естественно, при этом происходит значительное усложнение исследуемых моделей, что приводит к необходимости быстрого и эффективного их решения. Число таких задач велико и продолжает расти с каждым днем.
Разработка эффективного программного обеспечения управления космическими аппаратами приобретает в настоящий момент особую важность в связи с развитием электронно-вычислительной техники и появлением новых возможностей в решении задач управлзния сложными системами. Естественно, что программное обеспечение должно базироваться на надежной основе современного математического аппарата. Связующим звеном между математическим и программным обеспечением является так называемое алгоритмическое обеспечение, 'чачимость которого сейчас становится очевидной. Одновременно развитие и массовое применение ЭВМ делает возможным переход к многовариантным моделям управления в экономике, науке и технике, исследование которых сдерживается большой сложностью расчета каждого варианта, не говоря уже о каком-либо выборе вариантов.
Для чноговариантных задач управления (в частности, комбинаторных задач управления космическими аппаратами) характерна буле-ность множества управляемых переменных, и они естественным обра-
зом сиодятсн к задачам псевдобулевой оптимизации - задачам оптимизации функций, заданных на множестве булевых переменных и принимающих вещественные значения. Кроме того, с помощь» булевых переменных могут бить описаны самые разнообразные объекты практически любой сложности. А появление в последнее время многочисленных методов бинаризации, сводящих задачу оптимизации на любом множестве переменных (.непрерывных, дискретных, смешанных) к задаче оптимизации с булевыми переменными, позволяет применять для решения задач с любым типом переі:~нньіх методы, предназначенные для решения задач с булевыми переменными. Все это псзволяет говорить о необходимости разработки эффективных методов оптимизации псевдобулевых функций.
В настоящее время эффективные летоды оптимизации для задач лсевдобулевой оптимизации существуют только для случая задания критерия качества в явном линейном или линеаризуемом виде, что не реализуется в большинстве случаев для реальных практических задач. Для задач оптимизации о булевыми переменными с критерием качества, заданным в неявном (яеляющимся выходом некоторой технической системы) или алгоритмическом виде (характерном для задач управления космическими аппаратами), в настоящее время не существует эффективных алгоритмов решения и соответствующего программного обеспечения, за исключением методов случайного поиска, позволяющих получать субоптимальиое решение. Получение же точного решения гарантирует только полный перебор, который для реалышх задач зачастую невозможно осуществить за разумное время.
Однако имеющиеся алгоритмы случайного поиска решают задачи, заданные лишь на определенных множествах пространства булевых переменных. А разработанные ранее регулярные алгоритмы позволяют находить решение за приемлемое время лишь для узких классоз функций, к тому же установление принадлежности той или иной функции к какому-либо из них есть трудная, а порой и неразрешимая задача.
В связи с изложенным появилась настоятельная потребность в разработке эффективного алгоритмического и программного обеспечения, позволяющего решать произвольные прикладные задачи псевдобулевой оптимизации.
Настоящая работа посвящена разработке регулярных и рандомизированных алгоритмов оптимизации псевдобулевих функций для решения комбинаторных задач оптимизации управления космическими аппаратами.
Целью диссертационной работы является создание эффективного алгоритмического и программного обеспечения решения комбинаторных задач упр-зленип космическими аппаратами, сводимых к задачам псевдобулевои оптимизации.
Для достижения этой цели ставились задачи:
провести анализ и формализацию оптимизационных задач управления космическими аппаратами в виде задач псевдобулевой оптимизации;
разработать алгоритмическое и программное обеспечение для эффективного решения поставленных задач;
реализовать разработанное алгоритмическое обеспечение з виде типовых программных средств в соответствии с требованиями Государственного фонда алгоритмов и програм. СССР;
решить с помощь» разработанных программных средств задачи: оптимизации программного обеспечения систем управления зоемгчес-ними аппаратами и оптимального распределения функций между Остевым (БКУ)к казенным комплексами (НКУ) при восстановлении управления КА.
Методы исследования. Для решения поставленных задач использовался аппарат теор ш множеств, дискретной оптимизации (комбинаторная теория), теории вероятностен и теории оптимизации. Программная реализация алгоритмов осуществлялась в соответствии с ГОСТами и требованиями к программным средствам Государственного фонда алгоритмов и программ СССР (ГФАП СССР).
Научная новизна результатов, получен; jx в диссертации, состоит в следующем:
1'. Показано, что основные комбинаторные задачи управления космическими аппаратами являются задачами поисковой псевдобулевой оптимизации.
-
Разработаны регулярные поисковые алгоритмы оптимизации унимодальных псевдобулевых функций. Аналитически показано преимущество по быстродействию построенных алгоритмов перед методами локальной оптимизации и их неулучшаемость по трудоемкости в смысле верхней опенки числа вычислений.
-
Разработаны универсальные алгоритмы случайного поиска для задач безусловной оптимизации псевдобулевых функций.
-
Теоретически определены области эффективного применения построенных алгоритмов.
-б -
Практическое значение. Предложенные в работе алгоритмы реализованы программно в виде типовых программных средств и сданы в Государственный фонд алгоритмов и программ СССР.
Разработанные программные средства использовались при решении практических задач оптимизации программного обеспечения систем управления космич скимк аппаратами и проектирования оптимальной структуры бортового комплекса управления космическими аппаратами, а также широкого круга других прикладных за/чч псевдобулевой оптимизации, что подтверждается актами о внедрении, приведенными в приложении диссертационной работы.
Основные защищаемые положения.
-
Предлагаемые регулярные поис ;овые алгоритмы обеспечиваю! определение точного положения безусловного экстремума унимодальных и локального минимума полимодальных псевдобулевых функций не зависимо от того, как они заданы - аналитически или алгоритмически, ^ля паэнозначных псевпоб*'леБЫУ ,*іігннмиі! затпаты на поиск в несколько раз меньше затрат на организацию полного перебора.
-
Построенные алгоритмы случайного поиска позволяют находить субоптимальные решения задачи безусловной оптимизации псевдобулевых функций без ограничений на вид функционала.
-
Разработанные программные средства отвечают современным требованиям, предъявляемым к программному обеспечению, и предназначены для решения задач поисковой псевдобулевой оптимизации.
-
Разработанное алгоритмическое и программное обеспечение позволяет эффективно решать большой круг комбинаторных задач управления космическими аппаратами.
Публикации. По теме диссертационной работы опубликовано одиннадцать печатных работ.
Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на:
X Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Нарва-Йыэссу, Эстония, 1988);
VI Международной летней школе по теории вероятностей и математической статистике (София, Болгария, 1988);
IV Всесоюзной конференции "Математические методы распознавания образов" (Рига, Латвия, 1989);
III Всесоюзном симпозиуме "Перспективы развития вычисли-
тель.:ых систем" (Рига, Латвия. 1989);
-- Международном координационном совещании по случайному поиску (Красноярск, 1991);
Международной конференции "Параметрическая оптимизация и близкие к ней разделы математики" (Берлин, Германия, 1991);
Учредительной конференции Международной ассоциации по нетрадиционным методам оптимизации (Красноярск, 1992).
Структура работы. Диссертационная работа состоит из введения, четирех глав, заключения, списка использованной литературы и двух приложений. Основной текст диссертации содержит ISO страниц машинописного текста. Библиографический список включает 114 наименований литературных источников. В приложении 2 приведены доку-ме: гы, подтверждающие внедрение результатов работы, В приложение 1 вынесены таблицы данных и решений практических задач, рассматриваемы): в четвертой главе диссертации.
