автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эффективные алгоритмы решения комбинаторных задач управления космическими аппаратами

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РФ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ сибирская аэрокосмическля академия

На правах рукописи

КОШКИН Юрий Геннадьевич

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ УПРАВЛЕНИЯ КОСМИЧЕСКИМИ АППАРАТАМИ

05.13 01 - Управление в технических системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Красноярск, 1994

Работа выполнена в Сибирской аэрокосыической академии.

Научный руководитель - кандидат технических наук,

профессор Антпношкин А.Н.

Официальные оппоненты: доктор технических наук,

профессор Ильин 0.А.

кандидат технических наук, доцент Воловик Ы.А.

Ведущая организация - НИК информатики и кибернетики Сибирского

отделения инженерной академии Российской Федерации

заседании специализированного Совета К 064.46.01 по присуждению ученой степени кандидата наук в Сибирской азрокосмической академии по адресу: 660014, Красноярск, проспект имени газеты "Красноярский рабочий", 31.

Вьи отзыв, заверенный печатью, просьСт. высылать по адресу: 660014, Красноярск, а/я 486, ученому секретарю специализированного Совета Ловчпкову А.Н.

г~

Автореферат разослан 1994 г.

Запита состоится

года в

Ученый секретарь специализированного Совета, к т н., доцент Ловчиков А.Н.

- з -

Актуальность проблемы. В настоящее время создавшаяся экономико-политическая ситуация з стране существенно отразилась на развитии космической техники и объемах космических исследований Росси. Значительное сокращение финансирования исследований космоса в короткий срок может привести к потере приоритета страны в этой области науки, снижению темпов развития и совершенствования космической техники, что объясняется, прежде всего, высокими темпами развития космической отрасли в ряде стран, епн недавно не числящихся в рейтинговом списке космических держав, а ¡акже быстрой сменой поколений космотехники, ее новыми функциями и, как следствие, качественно новыми заказами на производство и научные исследования.

В связи с этим одними из главных зад;. I, стоящих перед российскими специалистами сегодня, является задача эффективно;-': использования и расширения возможностей имеющегося космического ■парка и задача совершенствования программно-технического обеспечения управления его объектами - космическими аппартами (КЛ). Указанные задачи требует системного подхода при их решении. Естественно, при этом происходит значительное усложнение исследуемых моделей, что приводит к необходимости быстрого и эффективного их решения. Число таких задач велико и продолжает расти с каждым днем.

Разработка эффективного программного обеспечения управления космическими аппаратами приобретает в настоящий момент особую важность в связи с развитием электронно-вычислительной техники и появлением новых возможностей в решении задач управлзния слот-тип системами. Естественно, что программное обеспечение должно базироваться на надежной основе современного математического аппарата. Связующим звеном между математическим и программным обеспечением является так называемое алгоритмическое обеспечение, 'чачимость которого сейчас становится очевидной. Одновременно развитие и массовое применение ЭВМ делает возможным переход к многовариантным моделям управления в экономике, науке и технике, исследование которых сдерживается большой сложностью расчета каждого варианта, не говоря уже о каком-либо выборе вариантов.

Для чноговариантных задач управления (в частности, комбинаторных задач управления космическими аппа"атами) характерна буле-вость множества управляемых переменных, и они естественным обра-

зом сводятся к задачам псевдобулевой оптимизации - задачам оптимизации функций, заданных на множестве булевых переменных и принимающих вещественные значения. Кроме того, с помощь» булевых переменных могут бить описаны самые разнообразные объекты практически любой сложности. А появление в последнее время многочисленных методов бинаризации, сводящих задачу оптимизации на любом множестве переменных (.непрерывных, дискретных, смешанных) к задаче оптимизации с булевыми переменными, позволяет применять для решения задач с любым типом переменных методы, предназначенные для решения задач с булевыми переменными. Все это псзволяет говорить о необходимости разработки эффективных методов оптимизации псевдобулевых функций.

В настоящее время эффективные летоды оптимизации для задач лсевдобулевой оптимизации существуют только для случая задания критерия качества в явном линейном или линеаризуемом взде, что не реализуется в большинстве случаев для реальных практических задач. Для задач оптимизации с булевыми переменными с критерием качества, заданным в неявном (являющимся выходом некоторой технической системы) или алгоритмическом виде (характерном для задач управления космическими аппаратами), в настоящее время не существует эффективных алгоритмов решения и соответствующего программного обеспечения, за исключением методов случайного поиска, позволяющих получать субоптимальное решение. Получение же точного решения гарантирует только полный перебор, который для реальных задач зачастую невозможно осуществить за разумное время.

Однако имеющиеся алгоритмы случайного поиска решают задачи, заданные лишь на определенных множествах пространства булевых переменных. А разработанные ранее регулярные алгоритмы позволяют находить решение за приемлемое время лишь для узких классов функций, к тому же установление принадлежности той или иной функции к какому-либо из них есть трудная, а порой к неразрешимая задача.

В связи с изложенным появилась настоятельная потребность в разработке эффективного алгоритмического и программного обеспечения, позволяющего решать произвольные прикладные задачи псевдобулевой оптимизации.

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

Целью диссертационной работы является создание эффективного алгоритмического и программного обеспечения решения комбинаторных задач упр-зленип космическими аппаратами, сводимых к задачам псевчобулевой оптимизации.

Для достижения этой цели ставились задачи:

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

- разработать алгоритмическое и программное обеспечение для эффективного решения поставленных задач; ■

- реализовать разработанное алгоритмическое обеспечение з виде типовых программных средств в соответствии с требованиями Государственного фонда алгоритмов и програм. СССР;

- решить с помоиьв разработанных программных средств задачи: оптимизации программного обеспечения систем управления зосмгчес-■ними аппаратами и оптимального распределения функций между Остовым (БКУ)к казенным комплексами (НЮ') при восстановлении управления КА.

Методы исследования. Для решения поставленных задач использовался аппарат теор ш множеств, дискретной оптимизации (комбинаторная теория), теории вероятностей и теории оптимизации. Программная реализация алгоритмов осуществлялась в соответствии с ГОСТами и требованиями к программным средствам Государственного фонда алгоритмов и программ СССР (ГФАП СССР).

Научная новизна результатов, получен; лх в диссертации, состоит в следующем:

Г. Показано, что основные комбинаторные задачи управления космическими аппаратами являются задачами поисковой псевдобулевой оптимизации.

2. Разработаны регулярные поисковые алгоритмы оптимизации унимодальных псевдобулевых функций. Аналитически показано преимущество по быстродействию построенных алгоритмов перед методами локальной оптимизации и их неулучшаемость по трудоемкости в смысле верхней опенки числа вычислений.

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

4. Теоретически определена области эффективного применения построенных алгоритмов.

-б -

Практическое значение. Предложенные в работе алгоритмы реализованы программно в виде типовых программных средств и сданы в Государственный фонд алгоритмов и программ СССР.

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

Основные защищаемые положения.

1. Предлагаемые регулярные поис ;овые алгоритмы обеспечиваю! определение точного положения безусловного экстремума унимодальных и локального минимума полимодальных псевдобулевых функций не зависимо от того, как они заданы - аналитически или алгоритмически. Для разнозначных псевдобулевых функций затраты на поиск в несколько раз меньше затрат на организацию полного перебора.

2. Построенные алгоритмы случайного поиска позволяют находить субоптимальные решения задачи безусловной оптимизации псевдобулевых функций без ограничений на вид функционала.

3. Разработанные программные средства отвечай? современным требованиям, предъявляемым к программному обеспечению, и предназначены для решения задач поисковой псевдобулевой оптимизации.

4. Разработанное алгоритмическое и программное обеспечение позволяет эффективно решать большой круг комбинаторных задач управления космическими аппаратами.

Публикации. По теме диссертационной работы опубликовано одиннадцать печатных работ.

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на:

- X Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Нарва-Йыэссу, Эстония, 1988);

- VI Международной летней школе по теории вероятностей и математической статистике (София, Болгария, 1988);

- IV Всесоюзной конференции "Математические методы распознавания образов" (Рига, Латвия, 1939);

- III Всесоюзном симпозиуме "Перспективы развития вычисли-

тель.:ых систем" (Рига, Латвия. 1989);

.- Международном координационном совещании по случайному поиску (Красноярск, 1991);

- Международной конференции "Параметрическая оптимизация и близкие к ней разделы математики" (Берлин, Германия, 1991);

- Учредительной конференции Международной ассоциации по нетрадиционным методам оптимизации (Красноярск, 1992).

Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и двух приложений. Основной текст диссертации содержит ISO страниц машинописного текста. Библиографический список включает 114 наименований литературных источников. В приложении 2 приведены доку-ме: гы, подтверждающие внедрение результатов работы, В приложение 1 вынесены таблицы данных и решений практических задач, рассматриваемых в четвертой главе диссертации.

СОДЕРЖАНИЕ РАБОТЫ

. Во введении дана общая характеристика проблемы, обоснована актуальность выбранной темы, определены цель и задачи исследования. С;ормулировань. основные положения, выносимые на защиту, научная новизна и практическая значимость полученных результатов. Приводится обзор существующих методов решения дискретных задач оптимизации и соответствующего программного обеспечения. Дано краткое описание содержания диссертации.

В первой главе приводится гяд комбина-орных задач управления сложными техническими системами, сводимых к задачам псевдобулевой оптимизации. Особо выделяется класс задач упрсьл-шгг. u-i-y:-. ческими аппаратами, специфика которых не позволяет эффективно использовать при их решении имеющийся арсенал методов псевдобулевой оптимизации.

Вначале рассматриваются примеры прикладных задач псевдобулевой оптимизации; стуктурной адаптации сложных систем управления, задачи планирования экспериментов и другие. Дается общая постанов!,а задач условной и безусловной оптимизации псевдобулевых функций.

Формально задача безусловной псевдобулевой оптимизации ставится следующим образом:

где

£(Х) —> extr,

ЪП2 -> Я1,

впг = (X: х^ £ в2, = 17Й в2 = {0,1}.

(1)

Задаче условной псевдобулевой оптимизации соответствует постановка:

а 3 с В" - некоторая подобласть пространства булевых переменных, определяемая заданной системой ограничений.

Для определенности предполагается, что решается задача минимизации.

Далее рассматриваются комбинаторные задачи управления космическими аппаратами. Исследуется космический аппарат как сложная техническая система, которой присущи все приведенные в разделе этапы управления. Приводятся модели практических задач:

- выбора оптимального программного обеспечения систем управления КА при многоэтапном процессе выполнения задач, регламентированном технологическим циклом управления (1ЦУ);

- проектирования оптимальной бортовой структуры КА; эффективного распределения функций между бортовык (БКУ) и

наземным комплексами управления (НКУ) космического аппарата.

Все задачи формализованы в виде задач условной и безусловной псевдобулевой оптимизации с различными видами критериев.

В заключительной части главы дается формальная постановка задачи. исследования, обосновывается актуальность разработки и рассматривайте« подходы к построению алгоритмического и программного обеспечения решения задач управления КА, сводимых к задачам псевдобулевой оптимизации. На основании приведенного во введении обзора существующих в настоящее время точных и приближенных методов псевдобулевой оптимизации и соответствующего им программного обеспечения делается заключение о необходимости разработки новых алгоритмов псевдобулевой оптимизации (приближенных и точных) , которые позволили бы решить широкий круг рассмотренных в настоящей работе задач.управления космическими аппаратами.

Отмечается, что наиболее популярные среди точных (регуляр-

Г(х) —> ехсг,

где

(2)

Г: а -> Я1,

ных) алгоритмов методы локальной оптимизации, а сред;, приближенных методы случайного поиска имеют ряд существенных недостатков. Первые при своей работе не гарантируют исключение полного перебора (оценка сверху - card Б1;,), что создает неопределенные ситуации в кавдом конкретном случае их использования, и допускают повторные вычисления в точках, что при сложном виде оптимизируемой функции ведет к большим затратам машинного времен;; и памяти. Имег аиэся же алгоритмы случайного поиска решают лишь определенный класс задач условной псевдобулевой оптимизации, что к- -оотзетст-вует в большинстве случаев постановкам практических задач управления техническими системами

Вторая глава посвящена разработке группы регулярных алгорит-мог псевдобулевой оптимизации (названных "с.секающими"), проводится аналитическое исследование трудоемкости построенных алгоритмов и их сравнение с другими точными методами на классе "ни-•уодальных псездсбулевых функций.

Ti начале главы з виде определений и лемм приведен необходимый математический аппарат.

Определение. Точки X1, У2 с называются ¿-соседними, если они отличаются значением к координат, к ~ Т7Н.

Определенна. Множество O^iX), к = 37п, всех точек Б", к-сс-ездккх к точке X е В д.. называется к-п уровнем точки X.

Лемма. v X е В": В" - U 0,гСХ).

^ ^ к-о "

Далее приводятся естественные определения кратчайшего п;'т-л Bg, пута невозрастания, связанности мнокес*. -а, локального киккку-на, унимодальной и поликодальной функций, разнозначной унимодальной функции, множества постоянства и несколько полутени?:-; ранее утверждений. Доказывается следующая лемма.

Лемма. Если f(X) - унимодальная на функция и для гокоторого л « O.(Xl), к = 1.П-1 выполняется f(X') < f(X,J, Х,г й 0;.(л°), то точки X и X (точка минимума) погнадлсяат одноуу

Л J._1 - п

подпростанству В": V, или V„ , где V. - и ОЛХ°), \> = U ОЛХ°), i ^ 2 i=o 1 " i-k+l

о •

а А",, определяется из условия f(Xv) = win f(X).

К ХеО (X*J)

'Из лежы и се следствий непосредствено следует, что для разнозначных унш',сдельных псездобулевкх функций, чросмотрев точки кг.кого-либо уровня Х°, всегда можно определить в каком из подпро-

странств {Vх или V2) расположен минимум. Это позволяет строить "отсекающие" алгоритмы оптимизации унимодальных разнозначных псевдобулевых функций со следующей схемой работы:

1. Выбирается произвольно точка Х° «, Б^ и некоторый ее уровень 0к(Х°), к-1,п-1. Полагаем 1-0, L - п.

2. Определяются Кк и Хк из условий:

f(Xj - win f(X), К XeO.JX") •

rak) < ttx'k). xk e Oj(X'k) Если Xk не существует, то X - Xk и переход к п. 5.

3. Если Хк*Ок_1аю), то L-k k-k~i Сi-'i'.'k-J-I).

Если Хк е 0к+1(Х°), то l-k, k-l:+i (i-l.L-k-1).

4. Если L - I = 2, то из условия

f(X') - rain i f(XL),f(Xj) I определяем X . Иначе - переход к п. 2.

5. Останов.

Здесь 1 и L - номера соответственно первого и последнего уровней рассматриваемого на каждом этапе подпространства.

Свобода выбора "отсекающего" урогня 0к(Х°) на каждом этапе позволяет строить целое семейство алгоритмов, отличающихся правилом определения к в первом и третьем пунктах схемы. При отсутствии априорных сведений о функции естественно рассматривать "средние" уровни на каждом этапе алгоритма, а в качестве Х° - нулевую точку. Под "средним" уровнем на этапе можно понимать уровень с номером, равным среднему арифметическому (целую часть) номеров 1 и L, или же уровень, разбивающий исследуемое на этапе подпространство на два равноыощных (максимально близких по мощностям) подпространства. Необходимость рассмотрения второго варианта обусловлена биноминальным распределением точек В^ на уровнях. D работе рассматриваются оба варианта выбора среднего уровня, которым соответствуют алгоритм 1 и алгоритм 2.

Построенные алгоритмы позволяют оценить их эффективность на классе унимодальных разнозначных псевдобулевых функций. Доказывается, что в наихудшем случае алгоритм 1 требует построения |_Iog2(rj-l)j (л>1) "отсекающих" уровней и вычисления значений фун-

кции не более чем в Т^п) точках В" (п>4). где Т}(п) есть ^уыма всех просматриваемых точек "отсекающих" уровней.

LJoga(íbi>j

Т1(п) - 1 Cí' + n l^lHij, i-l

где jQ- О, jr ln/2j. jr LUi-!* V/2-b i - 2.llog2(r.-l~j.

Из полученного равенства следует, что -ценна при п>13

не превосходит 2п~1 вычислений, то есть алгоритм 1 предпочтительнее полного перебора более чем в два раза, при чем при росте и разница эта заметно возрастает.

Дл" алгоритма 2 показывается, что верхние оценки его эффективности численно не превосходят соответствующих опенок первого.

При оптимизации произвольных унимодальных псевдооулчзых функций в рассмотренную схему "отсекав®. гс~ алгоритма оптимизации унимодальных разнозначных псевдобулееых сикций необходимо добавить стратеги- выхода из множества посго/шства, при этом сцел.-л эффективности алгоритмов на этом классэ функций будет определяться оценками, полученными для разнозначных функций плюс число вычислений з точках множества постоянства.

"Отсекающие" алгоритмы ¡.с-расначально строились для решения задач безусловной псе.чдсбулевой оптимизации. Однако, как показано в работе, их i.jhho применять и при решении задач условной оптимизации с определенными видами ограничений. 3 частности, рассматриваются задачи с пространством решений, состоящим из неско. ^ких уровней Xo Особо рассмотрен случай, когда S в (2) определяется следующим образом:

S = (К s В'?,: £ x~ml, (3)

" i-l J

то есть состоит из одного уровня нулевой точки. Такой пос^.озка отвечает большой круг прикладных задач псездобулвиой оптимизации. Представление уровня в виде объединения непересекающихся подпро-странстi и справедливость аналогичных доказанным для утверждений позволяет строить "отсекающие" алгоритмы для задач поиска экстремума на уровне, подобн е "отсекающим" алгоритмам безусловной псевдобулевой оптимизации.

Не исключается возможность использования "отсекающих" схем при оптимизации полимодальных псевдобулсвых функций. Однако де-

талый) этот вопрос автором Sie исследовался и в работе сформулированы лишь общие выводы по нему.

Заключительны; часть главы посвящена сравнению "отсекающих" алгорнтмов с другими per;, мирными г тодзми псевдсоулевой оптимизации. На основании проведенных аналитических исследований, имеющемся оценках эффективности алгоритмов, а также практических результатов дела. выводы о преимуществах "отсекающих" алгоритмов порея методами ..окольной оптимизации и перебора. Главным из них являете.«: б j3»ioai;ioctb получения точной верхней оценки и верхней or^Ksn в сред:шг числа вычислений оптимизируемой функции, что невозможно для методов локальной оптимизации. А имеющаяся для одного из алгоритмов лекального поиска верхняя с енка в среднем очень гру'ая и значительно уступает даяе верхним оценкам "отсекающих" алгоритмов При этом для унимодальных разнозначных псег^о-•булевых функций верхняя оценка "отсекающих" алгоритмов а несколько раз меньше оценки полного перебора. К достоинствам "отсекающих" алгоритмов откосится такие исключение возможности повторного вычисления в точках B'i, что в общем случае является невозможным для алгоритмов локальной оптимизации

Основным недостатком "отсекающих" алгоритмов является относительно большая оценка снизу, которая определяется мощностью первого из просматриваемых уровней.

Третьи глава посвящена построения методов случайного поиска для решения задач безусловной псевдобулевой оптимизации, аналитическому исследованию их сравнительной эффективности и определению области возможного применения.

Рассматривается известная группа алгоритмов случайного поиска: случайный поиск о адаптацией (СПА), модифицированный случайна поиск с адаптацией (КСПА), случайный поиск с возвратом (СПВ), - объединенных общей схемо* их организации - схемой метода изменяющихся вероятностей (МИВЕР) - и решающих задачу условной оптимизации псевдобулевых функций.

В самом общем виде схема алгоритмов МИВЕРа применительно к задаче (1) выглядит следующим образом.

1. Задаются начальные значения компонент вектора вероятностей Р° = { Р° ..... Р° }, так чтобы £ Р° = J. Здесь

Р° = Р lXj = 1} - вероятность присвоения единичного значения j-й

(j = Т7л) компоненте вектора X е ■

- lo -

2. Случайным образом (в соответствии с распределением вероятностей Р*, к = 4J, я-1, где Я - параметр метода, задаваемый заранее) независимо выбиваются г точек Xi « Б", i = TT? (' - т»к*е параметр метода, задаваемый заранее)

3. Вычисляются соответствующие значения функции - f/vl), i = TTr.

4. Выбираются требуемые (по кс шретному алгоритму) значения функции из совокупности fix1), i « T7F, и соответсвующие этим значениям точки.

5. Полагается Je - к + 1. По результатам п.4 формируются (а соответствии с празилом конкретного алгоритма) компоненты вектора вероятностей Р^.

6. П. 2-5 повторяются Я раз.

7. За решение задачи оптимизации принимается вектор У , определяемый из условия: f(X J = min f^ , где I* п = nin fix1).

k-l ,r "" ' * д~ '. г

Начальное распределение вероятности"'' единичных ?начен.1Й компонент точ.чи X - Р° задается на основе алриорг-й информации о свойствах решаемой чадачи оптимизации, При отсутствии такой информации используется равновероятное распределение, то есть P°j - 1/п , j -Тп.

Конкретные алгоритмы ЫИЬ£Ра в оснознон отличаются правилом организации адаптации по получаемо;, на каждом этапе поиска апостериорной информации (п.п. 4, 5 общей схемы), программная реализация пункта 2 схемы МйВЕР оказалась возможной лишь при специфичном виде исследуемого пространства решений - (3), ..'о и предопределило использовани« алгоритмов СПА, МСПА, СПВ на класса задач условной псевдобулевой оптимизации. Однако, как показывается в работе, возможно сь.дение задачи условной оптимизации (2), (3) к задаче (1) и, как следствие, использование указанны.-, алгоритмов на классе задач безусловной псевдоб>левой оптимизации (названы соответственно СПАБО, МСПАБО, СПВБО). ..о при этом размерность пространства решений возрастав' вдвое. Это значительно ограничивает область эффективное применения алгоритмов (п<25), так как величина шагов изменения вектора вероятностей в них обратно пропорциональна л и при большой размерности задач по.чск мосет вырождаться в случайный перебор. Поэтому с црлью расширения зэзнозксстей применения методов случайного поиска при решении задачи (1) были разработаны алгоритмы СПАНВ и МСПАНВ, которые

отличается от своих ■'налогов 1 у 5 пунктами своих схем. На первом этапе алгоритмов компоненты исходного вектора вероятностей Р° -- полагаются равными 1/2, что соответствует заданию л независимых распределен;:;"! вероятностей ..рнсвоения единичного значения каждой компоненте л с В^. Выбор конкретного вектора определяется п Лезавнсимыми испытаниями, каждое из которых дает ответ на вопрос - текущая к^лсн^нта выбирае; ^го вектора нулевая ил;, единичная. Па последующих -.-тапах компоненты вектора вероятностей Р^ изменяется не.зависимо друг от друга на шаг Ъ=1/(2Ю. Отсутствие явной зависимости длины сага адаптации от а делает возможным использование алгоритмов СПАКБ, МСПАНЗ при решении задач большой размерности.

Взед чио в алгоритмы схемы МИВЕР при безусловной псевдобулевой оптимизации переменной величины шагов адаптации увеличи:. нет возможности алгоритмов. В настоящей главе обосновывается необходимость введения переменного сага, рассматриваются конкретные правила его изменения, показывается преимущество перед постоянным .

Одним из главных вопросов, р-зникающий при испол!.зовании алгоритмов случайного поиска, является вопрос адптации алгоритмов "под задачу", которая включает в себя понятия структурной и параметрической адаптации. Под параметрической адаптацией алгоритмов понимается определение таких значений параметров г и Л, при которых алгоритм решает задачу заданной размерности с наибольшей точностью при минимальных затратах на поиск. Структурьая адаптация - это выбор наиболее эффективного алгоритма на классе задач, при условии, что все рассматриваемые алгоритмы имеют оптимальные значения параметрог. Таким образом цель адаптации - получение с наименьшими затратами субоптимального решениг X* , максимально близкого к истинному X .

Методику параметрической адаптации алгоритмов случайного 'поиска, разработанную ранее для алгоритмов СПА и ЫСПА, предлагается использовать и для определения оптимальных значений параметров г и Я алгоритмов схемы МИВЕР при безусловной оптимизации. При этом усложняется вид реккурентных формул и, соответственно, увеличивается число вычислений.

В заключительной части главы проводится аналитическое сравнение разработанных алгоритмов безусловной оптимизации. ПоказЙ'ва-

ется преимущество алгоритмов СПАНЗ, ИСПАНЗ перед СЛАБО, НСПЛ,,0 па задачах большой пазмеркости, дается заключение об областях элективного применения алгоритмов.

Четвертая глава посвящена описки» программной и практической реализации построенных алгоритмов.

Предварительно рассматривается проблема генерации случайных векторов в алгоритмах СНА, ЫСПА. С1.АБ0. КСПАБО при их практической реализации. Показывается, что при обь'»нсй схеме генерации векторов уже на первых этапах работы алгоритмов возможен повторный выбор отдельных единичных компонент, что в конечном счете может привести к большим затратам ма: инного времени и даже зацикливанию. Для избежания подобных ситуаций предлагается использовать иную схему выбора единичных компонент случайного вектора I з В^. При незначительном усложнении предлагаемая процедура в среднем не менее чем в 1п(п) раз экономичнее первой и нсклк ¡ает возможность позторного выбора компонент.

Далзе приводится описание программ!' :х средств, реализующих рассмотренные з диссертации алгоритмы Ш1АБ0, МСПАНЬ, "отсекающий" алгоритм 2, и использоьлнные автором при решении практических задач. Все программные средства оформлены в виде подпрограмм на языке ФОРТРАН, полностью самодчкументкрованы и соответствуют требованиям, предъявляем"« ГФАП СССР к программному обеспечения.

Разработанные алгоритмы и соответствующее им грограммное обеспечение были апробированы на задачах:

- оптимизации состава комплекса программных средств космического аппарата при многоэтапной процессе выполнения задач, регламентированном ТЦУ;

- оптимального распределения функций восстановления управления космическим ппаратом между БКУ и ¡1КУ.

В качестве оптимизируемой функции для первой задач:: Еисгу::-ит суммарные затраты на выбор комплекса, для второй - коэффициент готовности космического аппарата. Д_нные для задач были представлены НПО пи.

Указанные задачи решались предложенными в работе алгоритмами и некоторыми известными ранее методами. Сравнительные результаты их решений вместе с данными задач вынесены в приложение I и обсуждаются в заключительно! части главы.

В заключении ."формулированы основные результаты и сделаны выводы по диссертации.

В приложении ?. приведены акты о внедг'шии результатов дис-сертг юнной работы.

ССНОВНКГ РЕЗУЛЬТАТЫ и выводы

1. Прсзеден анализ и формализация комбинаторных задач управления косми ¡ескрми аппаратами в виде задач псевдобулевой оптимизации. Показана (.стгч'твенности их сведения к задачам условной и безусловной спт/.мизацпн псевдобулевых функций. Выявлены особенности , не позволяют.'.'' аффективно применять для .ос решения имевшийся арпн.гл методов псоздобулевой оптимизации.

2. Разработано алгоритмическое и программное обеспечение'для решения кокОинаторных задач управления в технических системах (в частности КА.). Созданы две группы алгеритмон - случайного поиска и регулярные, - решзк-а;ие задачи, сводимые к задачам безусловной и некоторым втам условной псевдобулевой оптимизации. Аналитически показано преимущество по быстродействию построенных регулярных алгоритмов перед м> годами локальной оптимизации на классе унимодальных псевдобул' -,ых функций и их неулучшаемость по трудоемкости в смысле вер-кей оценки числа вычислений.

Теоретически определены области эффективного применения алгоритмов .

3. Разрабо-анное алгоритмическое обеспечение реализовано в веде типе их программных средств в соответствии с. требованием Государственного фонда алгорг-мов и программ СССР.

. С помощью созданных программных средств решен ряд практических задач, в том числе: оптимизации программного обеспечения систем управления космическими аппаратами и оптимального распределения функций меж„у БКУ и НКУ при восстановлении управления КА.

5. Разработанное в диссертации алгоритмическое и программное обеспечение применимо п^и решении большого круга технических, экономических и математических оптимизационнных задач, сводящихся к задачам условной и безусловной псевдобулевой оптимизации.

Основные ' сложения и результаты диссертационной работы публикованы в следующих работах:

1. Антамошкин А.Н., Конкин Ю.Г. "од;'.ф-.'."чроЕ(лниый 1учл1'к:ий поиск с адаптацией п^п безусловной оптимизации функционалов с булевыми переменными. - М: ГФАП СССР, инв N 50Ь^000079° 1935, 57с.

2. Антамошкин А.П., Ножкин Ю.Г 0 двух ехемах случайного поиска при безусловной оптимизации. // Тез. дскл. X Всес. симп. "Системы программного обеспечения рещркия задач оптимального планирования". М. : ЦЭМ11 АН СССР, 1983, с. 12,13.

3. Антамошкин А.Н., Кошкин Ю.Г. поисковый алге -итм безусловной оптимизации псевдобулевых функций. - М.: ГФАП СССР, инв. N 508В0001326, 1938, 43 с.

4. Антамошкин А.Н., Кошкин Ю.Г. Практические результаты использования одного алгоритма группировки // Тез. докл. iv Всес. конф. "Математические методы распознавания образов" -Рига: ЫИаКРРиС при СМ ЛатССР, 1969, с.,2 -13.

5. Антамошкин А.Н. Антамошкина О.И., Кошкин Ю.Г. Эффективность методоз псевдобулевой оптимизации при адаптации вычислительных систем // Тез. докл. III Всес. симп. "Перспективы развития вычислительных систем" - Рига: РШ5, 1969, с.19-20.

6. Кошкин Ю.Г, Корсакова О.Н. Линейная тактика в гторитмах псевдобулевой оптимизации. // Тез. докл. краевой конф. "Применение вычислительной техники в народном хозяйстве". - Красноярг-: НТО, 1989, с.25.

7. Кошкин 3. Переменный шаг адаптации з алгоритмах ЕДОВЕРа // Тез. докл. координационного совещания по случайному поиску -Красноярск: КИКТ, 1991, с.61-62.

8. Кошкин Ю., Кузьмин А., Лыткина Л. Расширение пакета ЕМР // Тез. докл. координационного совещания по случайном/ поиску. -Красноярск: КИКТ', 1991, с.63-65. -

9. Antanoshkin A.N., Koshkin Y.G. The variable .metric algorithms // Abs. of the Sixth international summer scnool on probability theory and mathematical statistics. - Sofia: Academy of Sciences, 1988.

10. Antarcoshkin A.N., Koshkin Y.G. The total examination eliminating when optimizing the uniniodal pseudoboolean functions // Int.Conf. "Parametric Opt. and Related Topics III" - Berlin, 1991.

11. Antaraoshkin A.h., Koshkin Y.G. The cutting off algo-ithns for pseudoboolean optimization // Infornatika, N A (2), 19*1, p.539-551.

Подписано в печать: 10.Сб.94 г. Заказ 361.Тираж 100. Отпечатано на ротапринте КГТУ.