Метод обобщенного локального поиска для задач принятия решений в управлении сложными системами тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Семенкина, Ольга Эрнестовна

• Семенкина, Ольга Эрнестовна
• доктор технических наук
• 2002

Оглавление диссертации доктор технических наук Семенкина, Ольга Эрнестовна

ВВЕДЕНИЕ

ГЛАВА I. Формализация и исследования задач оптимизации загрузки ресурсов мелкосерийного производства при нерегулярном поступлении заказов

§1.1. Экономико-математическая модель задачи распределения производственной программы предприятия по плановым периодам

§ 1.2. Задачи формирования производственной программы при мелкосерийном производстве

§ 1.3. Задачи формирования оптимальной производственной программы Выводы

ГЛАВА П. Анализ и формализация задач синтеза систем управления сложными объектами

§ 2.1. Система управления космическими аппаратами

§ 2.2. Анализ и формализация задачи определения коэффициентов готовности по технологическому контуру

§ 2.3. Анализ и формализация задачи выбора эффективного варианта технологического контура системы управления

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

§ 2.5. Формализация задачи определения показателя эффективности работы системы управления по контуру целевого управления

§ 2.6. Формализация задач определения показателей эффективности работы и выбора эффективного варианта командно-программного контура системы управления

§ 2.7. Моделирование взаимодействия между контурами систем управления орбитальной группировкой космических аппаратов Выводы

ГЛАВА III. Математический аппарат регулярных поисковых алгоритмов оптимизации на дискретных структурах

§3.1. Свойства пространства булевых переменных

§ 3.2. Частичный порядок и Ф-множества в пространстве булевых переменных

§3.3. Свойства пространства целочисленных переменных Выводы

ГЛАВА IV. Оптимизация унимодальных функций

§4.1. Унимодальная монотонная псевдобулевая функция и ее свойства

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

§ 4.3. Алгоритм оптимизации монотонных унимодальных псевдобулевых функций с множествами постоянства

§ 4.4. Оценка эффективности работы алгоритма

§ 4.5. Алгоритм оптимизации унимодальных псевдобулевых функций общего вида

§ 4.6. Обобщенный алгоритм локального поиска для оптимизации псевдобулевых функций

§ 4.7. Обобщенный алгоритм смешанной оптимизации Выводы

ГЛАВА V. Оптимизация полимодальных функций на дискретных структурах

§5.1. Полимодальная локально Структурно монотонная функция булевых переменных и ее свойства

§ 5.2. Алгоритмы оптимизации полимодальной локально структурно монотонной псевдобулевой функции

§ 5.3. Эффективность алгоритмов глобальной оптимизации

§ 5.4. Эволюционные и генетические алгоритмы

§5.5. Методы интеллектуального поиска

§ 5.6. Гибридные адаптивные поисковые алгоритмы

§ 5.7. Обобщенный локальный поиск для решения задач глобальной оптимизации Выводы

ГЛАВА VI. Практическая реализация моделей и алгоритмов

§ 6.1. Система поддержки принятия решений при моделировании сложных систем с помощью Марковских процессов

§6.2. Программная система решения задач оптимизации с булевыми и целочисленными переменными

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

§ 6.4. Расширение типовых программных средств алгоритмами решения задач с булевыми и дискретными переменными

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

Введение диссертации (часть автореферата) на тему «Метод обобщенного локального поиска для задач принятия решений в управлении сложными системами»

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

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

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

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

Исследования, проведенные в ходе выполнения диссертации, поддерживались грантом научного фонда аэропорта Франкфурта на Майне (Flughafen Frankfurt Main Stiftung) и стипендией Немецкой службы академических обменов (DAAD). Работа над книгой [146] поддерживалась грантом Красноярского краевого фонда "Образование".

Состояние проблемы. Общая методология автоматизации процесса проектирования систем управления космическими аппаратами была разработана в рамках отраслевой программы "Салют-90", представлена руководителем программы Князькиным Ю.М. в [25] и опубликована в его монографии [17]. Различным аспектам рассматриваемой проблемы посвящены докторские [5, 16] и кандидатские [1, 14, 30, 32, 100] диссертации, в которых представлены как формальные модели, так и методы решения возникающих задач оптимизации.

В работе [5] рассматривались формальные модели процесса проектирования как такового и задачи верхнего уровня принятия решения - распределение функций, формирование технологических циклов управления и т.д. Данные модели сводились к задачам псевдобулевой оптимизации, для которой и предлагались алгоритмы локальной и глобальной оптимизации. Основной рабочей процедурой являлся алгоритм случайного поиска с возвратом [3, 36], характерной особенностью которого является необходимость настройки законов распределения, что является определяющим для организации эффективного поиска. 6

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

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

Данные работы оставляли в стороне задачи более низкого уровня принятия решения, в частности предполагалось, что показатели эффективности подсистем являются некоторым вычислимыми функциями своих параметров, без обсуждения способа получения процедуры таких вычислений. Некоторые подсистемы (например в составе НКУ) вообще не рассматривались, т.к. на предварительных этапах проектирования достаточно было иметь информацию об интегральных характеристиках системы в целом. Однако, при автоматизации проектирования систем управления космическими аппаратами на 7 стадии детальной проработки возникает необходимость рассмотрения структурных единиц более низкого уровня детализации и в данном случае возникают дополнительные аспекты в решаемых задачах оптимизации. Как указывалось в [17], при детализации проектирования систем управления возникают задачи оптимизации управления или выбора эффективных вариантов систем управления, которые обладают некоторыми дополнительными особенностями, рассмотрение которых еще не проводилось. Эти дополнительные особенности делают возникающие задачи оптимизации особенно трудными для t решения, т.к. все они в совокупности ранее не рассматривались. Такими особенностями являются:

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

- наличие большого количества критериев качества, когда каждая из подсистем имеет свои, а система в целом - свои показатели;

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

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

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

На преодоление отдельных проблем упомянутых задач были направлены работы [1, 14, 30]. Так в [1] предложен подход для решения многошкальных задач оптимизации алгоритмически заданных функций, причем много-критериальность предполагалась преодоленной за счет какой-либо свертки критериев. Разработана также программная система, реализующая данный подход. Предметом работы [30] являются методы решения многокритериальных задач описанного типа. При этом для преодоления многошкальности используется бинаризация переменных, т.к. в качестве основной оптимизационной процедуры задействован генетический алгоритм [151]. В работе [14] предлагается использовать нейросетевую аппроксимацию оптимизируемых функций и ограничений для ускорения проведения расчетов, что приводит к существенному ускорению процесса оптимизации. Подход инвариантен применяемому алгоритму оптимизации, т.к. нейросетевой аппроксиматор встраивается в такой алгоритм, какую бы процедуру оптимизации он не реализовал.

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

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

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

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

Поисковый метод для решения разношкальных задач предлагался в [53], но он использовал бинаризацию переменных, что в практических задачах может привести к возникновению дополнительных сложностей, когда бинаризованная задача оказывается значительно больше и сложнее исходной. Методы обработки разнотипных переменных, предложенные в [36], могут быть преобразованы в методы оптимизации {некоторые из них использовались в [5] для решения псевдобулевых задач оптимизации проектирования), однако эти методы тоже потребуют сведения разношкальных переменных к булево-му или непрерывному типу. Наиболее перспективными выглядят так называемые методы адаптивного поиска [118, 119], но они требуют серьезных модификаций, т.к. ориентированы главным образом на однокритериальные задачи одноуровневой оптимизации с переменными одного типа (за исключением генетического алгоритма, который выполняет бинаризацию).

10

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

Наличие значительных трудностей и специфических особенностей в решении целочисленных и комбинаторных задач оптимизации породило большое количество методов и алгоритмов. При их разработке привлекается весьма разнообразный математический аппарат от математической логики до теории динамических систем, что делает достаточно сложной задачу проведения классификации в данной области. Примем в качестве основного клас-сификационого признака принцип, положенный в основу выделения области поиска решения и организации поиска в этой области [54].

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

11.

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

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

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

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

12 задачи нелинейного программирования, является оптимальным или, по крайней мере, допустимым.

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

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

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

13

Первый класс охватывает разнообразные комбинаторные методы и алгоритмы дискретной оптимизации. К ним относятся все алгоритмы последовательного сужения конечного множества альтернатив, при реализации которых оптимальное решение определяется в результате полного или неполного (целенаправленного, неявного) перебора альтернатив или (и) элементов их составляющих. Большинство комбинаторных алгоритмов может применяться как на основе предварительного представления задачи моделью целочисленного программирования, так и непосредственно для решения задачи на комбинаторной структуре. Важнейшими видами комбинаторных алгоритмов являются: алгоритмы прямого перебора, алгоритмы метода ветвей и границ, фильтрующие алгоритмы (Балаша), алгоритмы динамического программирования. В литературе можно встретить несколько схем сужения множества альтернатив, охватывающих несколько видов комбинаторных алгоритмов. Оптимизационная схема академика B.C. Михалевича, введенная под названием метода последовательного анализа вариантов (последовательного исключения возможностей) [41, 62, 63], включает как частные случаи схемы методов динамического программирования и ветвей и границ. Для ряда комбинаторных алгоритмов общая оптимизационная схема вводится под названием поиска с возвращением [55].

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

14 жет быть вычислена вне точек целочисленной решетки, как это имеет место в нашем случае.

Ко второму классу отнесем методы и алгоритмы, реализующие идею предварительного расширения множества допустимых альтернатив, позволяющего представить его описание в удобном для нахождения экстремума виде, и последующего сужения этого множества с использованием последовательно определяемых на каждом шаге сужения решений. В данном классе в свою очередь можно выделить два основных метода. Первый метод, предложенный Р. Гомори в 1958 г. и рассчитанный в основном на решение задач линейного целочисленного программирования, предполагает введение континуального расширения за счет снятия ограничений на целочисленность и последующее сужение на основе использования получаемых решений для построения последовательно вводимых ограничений, интерпретируемых как введение отсекающих гиперплоскостей (этот метод часто называют методом отсекающих плоскостей) [29, 69]. Второй метод, предложенный В. А. Емели-чевым и В. И. Комликом (1965 г:), и развитый в последующие годы, предполагает осуществление конечного расширения (множество допустимых альтернатив остается конечным, но его описание существенно более просто, чем описание исходного множества) и последующего его сужения путем элиминации (исключения) получаемых решений. Как в первом, так и во втором методе в случае определения последовательности сужений с использованием исходной целевой функции сужение осуществляется до получения на некотором шаге решения, удовлетворяющего ограничениям точно или приближенно. Была также предложена модификация второго метода, связанная с введением миноранты минимизируемой (мажоранты максимизируемой) функции. Общая схема, охватывающая случаи как континуального, так и конечного расширения, вводится под названием метода построения последовательности планов [19].

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

15 строения миноранты (мажоранты). В случае неявных функций реализация подходов исключительно затруднена.

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

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

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

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

Значительную роль в развитии теории дискретной локальной оптимизации сыграли работы Ю.И. Журавлева в области общей теории локальных алгоритмов и их применения для построения минимальных дизъюнктивных форм [21], и И.В. Сергиенко в области исследования различных видов итеративных алгоритмов локальной оптимизации (алгоритмы метода вектора спада) [62, 63].

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

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

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

17 ного поиска, отличающиеся тем, что в процессе реализации поиска в "механизм" выбора вносятся те или иные изменения в соответствии с получаемыми в процессе поиска результатами [51, 52, 67]. Случайный поиск в общем виде применим к задачам оптимизации с неявными функциями, хотя и требует подчас чрезмерных затрат к тому же с сомнительными гарантиями сходимости к искомому решению.

Локально-стохастическая оптимизация. В связи с очевидными недостатками как локальных алгоритмов, так и алгоритмов случайного поиска, осуществляется их синтез с целью преодоления этих недостатков. При этом случайный поиск обеспечивает подбор исходных точек для проведения локальной оптимизации и решения постепенно улучшаются не только на каждом сеансе локальной оптимизации, но и от одного сеанса локальной оптимизации к другому. Исходную точку для реализации локально-стохастического поиска целесообразно подбирать с помощью весового алгоритма, обеспечи вающего "адаптацию" поиска к параметрам задачи. Локально-стохастические алгоритмы относятся к числу наиболее эффективных алгоритмов дискретного программирования [19, 62, 67].

Выделим в отдельную группу бурно развивающиеся в последние два десятилетия (в основном на Западе) так называемые адаптивные алгоритмы поиска, которые объединяют такие различные идеи как генетические и эволюционные алгоритмы, имитация отжига и поиск Табу. Объединяющей идеей является то, что все эти направления моделируют естественное поведение живых и неживых объектов природы. Генетические алгоритмы [102, 103, 84] моделируют генетический механизм биологических организмов и являются, по сути, управляемым случайным поиском, хотя и весьма специфическим. Эволюционные алгоритмы, в отличие от генетических, моделируют эволюционные процессы группы индивидов [122, 123, 128-131] и во многом похожи на генетические алгоритмы. Специальные исследования показали, что эволюционные алгоритмы имеют преимущество на унимодальных функциях, в то время как генетические алгоритмы заметно лучше ведут себя в полимо

18 дальном случае. Первые же попытки применить данный подход к NP-сложным задачам показали высокую работоспособность алгоритмов [99].

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

Табу поиск и примыкающие" к нему методы [90-98] имеют еще и другое название "интеллектуального" поиска и моделируют эвристическое принятие решения человеком типа запрета на "неудачные" направления и поощрения "удачных". Высокая эффективность поиска Табу принесла ему заслуженное внимание исследователей, что выразилось в том, что этому подходу был посвящен специальный выпуск известного журнала "Annual of Operations Research" в 1993 году.

Представляют большой интерес и примыкающие к указанным подходам идеи робастных методов комбинаторной оптимизации [111] и методика построения окрестностей в пространстве локальных минимумов исходной задачи [80].

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

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

19 дискретных пространств; методы, жестко ориентированные на структуру задачи.

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

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

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

20

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

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

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

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

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

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

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

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

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

Определенные эвристически соображения положены в основу собственно приближенных методов универсального характера. Однако, этим алгоритмам может быть дано определенное математическое обоснование. Подлинно эвристическими алгоритмами являются алгоритмы, при построении которых принимаются во внимание эвристические идеи, связанные с глубоким учетом специфики задачи. Наибольшее распространение получили эвристические алгоритмы при решении задач составления расписаний [27, 64]. Следует подчеркнуть, что применение эвристических алгоритмов является обоснованным только тогда, когда соответствующее исследование показывает, что решение в приемлемый срок не может быть получено на основе использования известных строгих методов и имеющихся в наличии вычислительных средств.

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

Диалоговые и бездиалоговые алгоритмы. Диалоговые алгоритмы предусматривают введение на определенных шагах алгоритма информации, полу

23 чаемой в результате использования эвристик человека и осуществления диалога "человек-ЭВМ".

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

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

Алгоритмы локального спуска и прямого случайного поиска использовались для решения некоторых задач оптимального проектирования частных функций системы управления космическими аппаратами [5, 26, 32, 107]. Недостатком указанных работ является то, что, во-первых, они решали только задачи оптимизации с булевыми переменными и не учитывали возможность появления дискретных, а во-вторых - при построении алгоритмов псевдобулевой оптимизации авторы имели дело только с одной системой окрестностей, причем самой слабой, что и давало верхние оценки эффективности на

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

Комплексный подход к решению таких задач представлен в [157, 165]. Примененный подход может быть определен как самонастраивающийся гибридный адаптивный поиск для решения задач условной оптимизации алгоритмически заданных функций смешанных переменных. В принципе, данный подход практически решает проблему эффективного выбора структур систем управления сложными объектами, в том числе космическими аппаратами. Однако, принципиальной трудностью является выбор гибридных алгоритмов, включаемых в состав конкурирующих популяций. Должны быть выбраны всего несколько алгоритмов из многих тысяч. Кроме того, анализ реализованного в [15.7, 165] подхода доказывает, что если задействуются гибридные алгоритмы, не включающие в свой состав локальный поиск, то получаемые решения не всегда эффективны, в частности они могут даже не быть локальными экстремумами, т.е. элементарно могут быть улучшены. В случае же включения локальных алгоритмов в гибридную схему, ее эффективность, судя по всему, именно ими и обеспечивается. Необходимость использования эволюционных алгоритмов поэтому оказывается под вопросом. Еще одним недостатком является невозможность использования "удобных" с точки зрения оптимизации свойств целевых функций, если таковые будут иметь место.

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

Для достижения этой цели решались следующие задачи:

25

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

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

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

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

- программная реализация разработанного математического и алгоритмического обеспечения,

- решение реальных практических задач выбора структуры систем управления сложными объектами и планирования их загрузки.

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

Научная новизна.

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

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

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

26 ными переменными, автоматически настраивающиеся на специфические свойства оптимизируемых функций в ходе процесса оптимизации.

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

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

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

Реализация результатов работы. Модели и алгоритмы выбора эффективных вариантов систем управления космическими аппаратами были переданы на НПО ПМ (г. Железногорск).

Формальные модели и алгоритмы синтеза эффективных структур распределенных информационных систем и модели планирования загрузки производственных ресурсов, формирования производственной программы и порядка запуска заказов на выполнение были переданы Горно-химическому комбинату (г. Железногорск).

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

27

Модели выбора вариантов распределенных систем управления и алгоритмы регулярной и стохастической оптимизации, предложенные в диссертации, используются на кафедре механики и процессов управления Красноярского госуниверситета и на кафедре системного анализа и исследования операций Сибирской аэрокосмической, академии (САА) при проведении занятий по дисциплинам "Системный анализ", "Теория оптимизации", "Управление сложными системами".

На защиту выносятся:

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

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

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

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

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

Публикации. По теме диссертации опубликовано более сорока печатных работ. Список основных публикаций автора по теме диссертации приведен в списке литературы [142-176].

28

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на Международных симпозиумах по исследованиям операций (Пассау, 1995, Брауншвайг, 1996, Йена, 1997), Международных конференциях "Адаптивные вычисления в инженерном проектировании" (Плимут, 1994, 1996), научном семинаре Омского института информационных технологий и прикладной математики (1995), Международной конференции "Дни оптимизации" (Ванкувер, 1996), Международной конференции по моделированию и имитации (Сантьяго де Компо-стела, 1999), Всероссийской конференции "Непараметрика'2000" (Красноярск, 2000), 11-й конференции рабочей группы "Теория и практика принятия решений" общества по исследованию операций (Клостер Банц, 2001), научно-технической конференции МИФИ "Научно-инновационное сотрудничество" (2002), научных семинарах кафедры системного анализа и исследования операций Сибирской аэрокосмической академии (1996-1999), научно-технических советах НИИ СУВПТ (2000-2002).

Структура работы. Диссертация состоит из введения, шести глав, заключения, библиографии из 176 источников и приложений.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Семенкина, Ольга Эрнестовна

ВЫВОДЫ

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

298

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Разработана система поддержки принятия решений при моделировании сложных систем Марковскими процессами.

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

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

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

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

299

9. Разработана программная система, реализующая построенные модели и алгоритмы.

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

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

300

Список литературы диссертационного исследования доктор технических наук Семенкина, Ольга Эрнестовна, 2002 год

1. Абрамович К.Ю. Методы решения специальных классов задач оптимизации при синтезе управления космическими аппаратами. - Дисс. на соиск. уч. степени канд. техн. наук. - Красноярск: САА, 1997. 156 с.

2. Автоматизация поискового конструирования // Под ред. Половинкина А.И. М.: Радио и связь, 1981. 344 с.

3. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. -Томск: Изд-во ТГУ, 1987. 104 с.

4. Антамошкин А.Н. Регулярная оптимизация псевдобулевых функций. -Красноярск: Изд-во КГУ, 19&9. 160'с.

5. Антамошкин А.Н. Оптимизация процессов автоматизированного синтеза систем управления космическими аппаратами. Дисс. на соиск. уч. степени доктора техн. наук. - Красноярск: САА, 1996. 265 с.

6. Антамошкин А.Н., Семенкина О.Э. и др. Разработка модельного и алгоритмического обеспечения сквозного проектирования систем управления космическими аппаратами. Отчет по х/т 14И92 НПО ПМ. - Красноярск: Сибирский филиал Инженерной Академии РФ, 1992. 245 с.

7. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их применение. М.: Наука, 19#9. 160 с.

8. Баринов К.Н., Бурдаев М.Н., Мамон П.А. Динамика и принципы построения орбитальных систем космических аппаратов. М.: Машиностроение, 1975. 270 с.

9. Ю.Бебенин Г.Г., Скрубушевский Б.С., Соколов Г.А. Системы управления полетом космических аппаратов. М.: Машиностроение, 1978. 272 с.

10. П.Береснев В.А., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.

11. Букатова И.Л., Ю.И.Михасев, А.М.Шаров. Эвоинформатика: Теория и практика эволюционного моделирования. -М.: Мир, 1991. 206 с.

12. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. М.: Наука, 1991.

13. Вишневская С.Р, Аппроксимация в задачах оптимизации управления космическими аппаратами. Дисс. на соиск. уч. степени канд. техн. наук. -Красноярск: САА, 1997. 167 с.

14. Воловик М.А. Коэффициент готовности прибора со встроенной системой контроля. Системный анализ и исследование операций. - Новосибирск: ВЦ АН СССР, 1977.

15. Воловик М.А. Методы и модели коллективного анализа и проектирования структур технологии управления космическими аппаратами. Дисс. на соиск. уч. степени доктора техн. наук. - Красноярск: КГТУ, 1997. 340 с.301

16. Жилинскас А.Г. Методы исследования глобального экстремума. М.: Наука, 1991.

17. Журавлев Ю.И., Финкелыптейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. Проблемы кибернетики. -М.: Наука, 1965. Вып. 14. С. 289-295.

18. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979. -432 с.

19. Конвей Р.В., Максвелл В.Л., Миллер П.В. Теория расписаний. М.: Наука, 1975.

20. Корбут А.А., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

21. Корбут А.А., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования. Известия АН СССР. Техническая кибернетика, 1983, №1. Сс. 165-176.

22. Коробейников С.П. Методы многокритериальной оптимизации для задач синтеза управления сложными объектами. Дисс. на соиск. уч. степ. канд. техн. наук. - Красноярск: ГХК, 1997. 174 с.

23. Королюк В. С., Турбин А. Ф. Процессы марковского восстановления в задачах надежности систем. Киев: Наукова думка, 1982.

24. Кошкин Ю.Г. Эффективные алгоритмы решения комбинаторных задач управления космическими аппаратами. Дисс. на соиск. уч. степ. канд. техн. наук. - Красноярск: САА, 1994. 154 с.302

25. ЗЗ.Лапко А.В. Непараметрические методы оптимизации и их применение. -Новосибирск: Наука, 1993. 152 с.

26. Ларичев О.И., Моргоев В:К. Проблемы, методы и системы извлечения экспертных знаний. Автоматика и телемеханика, №6, 1991. Сс. 3-27.

27. Ларичев О.И., Мовшевич Е.Н. Качественные методы принятия решения. -М: Наука, 1996. 286 с.

28. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. -Новосибирск: ИМ СО АН СССР, 1981. 160 с.

29. Лебедев В.А., Терсков В.А. Моделировние и оптимизация многопроцессорных систем оперативного управления. М.: МАКС Пресс, 2002. - 330 с.

30. Машунин Ю.К. Модели и методы многокритериальной оптимизации. М: Наука, 1982. 128 с.6 39. Me две дев А.В. Непараметрические системы адаптации. Новосибирск: Наука, 1983. 174 с.

31. Медведев А.В. Непараметрические методы в кибернетике. Известия ВУЗов. Физика, 1995, № 9. Сс. 46-54. ■

32. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика, №12, 1975.

33. Можаев Г.В. Синтез орбитальных структур спутниковых систем. М.: Машиностроение, 1989. 304 с.

34. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975.

35. Озерной В.М. Принципы построения и использования многокритериальных моделей задач принятия решений // Проблемы принятия решений. Вып. 5. М.: ИПУ, 1974. Сс. 3-15.

36. Озерной В.М., Гафт М.Г. Методология решения дискретных многокритериальных задач // Проблемы принятия решений. Вып. 5. М.: ИПУ, 1974. Сс. 30-44.

37. Основы теории полета и элементы проектирования искусственных спутников Земли / М.К.Тихонравов; И.М.Яцункский, Г.Ю.Максимов, О.В.Гурко. -М.: Машиностроение, 1967. 296 с.

38. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1979.

39. Подиновский В.В. Многокритериальные задачи с однородными равноценными критериями ЖВМ и МФ, 1975. Т. 15. Сс. 330-344.

40. Подиновский В.В. Многокритериальные задачи с упорядоченными по важности однородными критериями // Автоматика и телемеханики, 1976. №11. Сс. 118-127.

41. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений // Многокритериальные задачи принятия решений. М.: Машиностроение, 1978. Сс. 48-82.

42. Растригин Л .А. Статистические методы поиска. М.: Наука, 1968.

43. Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981.303

44. Растригин JI.А., Фрейманис Э.Э. Решение задач разношкальной оптимизации методом бинаризации. Вопросы разработки ТАСУ. Кемерово: НТО, 1984. Вып. 3. Сс.39-48.

45. Резников Б.А. Методы и алгоритмы оптимизации на дискретных моделях сложных систем. Л.: ВИКИ им. Можайского, 1983. 250 с.

46. Рейнгольд Э., Нивергельт Ю-, Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

47. Рубан А.И. Метод непараметрической поисковой оптимизации. Известия ВУЗов. Физика, №9, 1995. Сс. 65-73.

48. Рубан А.И. Поисковая оптимизация на основе использования инверсных непараметрических характеристик // Информатика и процессы управления: Сб. науч. работ. Красноярск: КГТУ, 1995. Сс. 94-104.

49. Рыбников К. А. Введение в комбинаторный анализ. М.: Изд-во Моск. унта, 1985.- 308 с.

50. Саати Т. Целочисленные методы оптимизации и связанные с ними проблемы. М.: Мир, 1973.

51. Семенкин Е.С., Лебедев В.А. Метод обобщенного адаптивного поиска для синтеза систем управлени сложными объектами. М.: МАКС Пресс, 2002. - 320.с. ,

52. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука,1975.

53. Тихонов В. И., Миронов Н. А. Марковские процессы. М.: Советское радио, 1977.-488 с.

54. Ушаков И. А. О вычислении среднего стационарного времени пребывания полумарковского процесса р подмножестве состояний // Извещение АН СССР. Техническая кибернетика. 1990. - № 4.

55. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с. 68.Химмельблау Д. Прикладное нелинейное программирование. - М.: Мир, 1975.534 с.

56. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

57. Шойер Э. Теория надежности. Исследование операций. М.: Мир, 1981. Т. 2. Сс. 314-343.70'. Экономико-математические модели и методы. Под общ. ред. А.В. Кузнецова. Мн.: БГЭУ, 2000. - 412 с.304

58. Юдин Д.Б. Задачи и методы стохастического программирования. М.: Сов. радио, 1979. 392 с.

59. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации алгоритмов и устройств АСУ. М.: Радио и связь, 1982. 288с.

60. Юдин Д.Б., Немировский А.С. Оценка информационной сложности задач математического программирования. ЭММ, 1976. Вып. 1. Сс. 129-142.

61. Antamoshkin A.N., Koshkin Y.G. The cutting off algorithms for pseudoboolean optimization. Informatika, 4(2), 1991. Pp. 539-551.

62. Antamoshkin A., Semenkin E., Volovik M. The Models and Methods System for CAD of Spacecrafts Control Systems. Optimization-Based Computer-Aided Modeling and Design. Leidschendam: Lansa, 1992. Pp. 31-42.

63. Antamoshkin A. et al. The Problem of the Control Board Software Optimization. Proc: Conf of the Int. Association on Non-traditional Methods of Optimization. -Krasnoyarsk: KIKT, 1992.

64. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. In Proc. Of the 12th Intern. Conf. on Machine Learning, Lake Tahoe, 1995.

65. Battiti, R. and G. Tecchiolli (1992a). The Reactive Tabu Search, IRST Technical Report 9303-13, to appear in ORSA Journal on Computing.

66. DeH'Amico, M. and M. Trubian (1993). Applying Tabu Search to the Job-Shop Scheduling Problem, Annals of Operations Research, Vol. 41, 231-252.

67. Dolezal J., Fidler J. Dialogue system OP*1 A for minimization of functions of several variables: Version 3.0. Users' Guide. - Institute of information theory and Automation, Prague, 1993. 125 pp.

68. Floudas C.A., Pardalos P.M. (Eds.) Recent Advances in Global Optimization -New Jersey: Primceton University Press, 1992.

69. Fogel, D.B. (1991). System identification through simulated evolution. Needhaw Heights, MA: Ginn.305

70. Fridman A., Levner E. Advances in Discrete Optimization. 14th IFIP Conf. on System Modelling and Optimization. - Leipzig: Techn. Hochschule, 1989. Heft 4.

71. Glover F. Tabu Search: A Tutorial. Interfaces, 1990, vol 20, 4. Pp. 131-141.

72. Glover, F. (1977). Heuristics for Integer Programming Using Surrogate Constraints,Decision Sciences, Vol. 8, No. I, January, 156-166.

73. Glover, F. (1989a). Tabu Search Part I, ORSA Journal on Computing, 1(3), 190-206.

74. Glover, F. (1990a). Tabu Search-Part 11, ORSA Journal on Computing, 2, 4-32.

75. Glover, F. (1990b). Tabu Search: A Tutorial, Interfaces, Vol. 20, No. I, 74-94.

76. Glover, F. (1991). Tabu Search for Nonlinear and Parametric Optimization (with Links to Genetic Algorithms), to appear in Discrete Applied Mathematics.

77. Glover, F. (1993) Tabu Thresholding: Improved Search by Nonmonotonic Trajectories, to appear in ORSA Journal on Computing.

78. Glover, F. and M. Laguna (1993). Tabu Search, Modern Heuristic Techniques for Combinatorial Problems, C. Reeves, ed., Blackwell Scientific Publishing, 70141. .

79. Glover, F., M. Laguna, E. TalHard, and D. de Werra, eds. (1993) Tabu Search, special Issue of the Annals of Operations Research, Vol. 41, J. C. Baltzer.

80. Goldberg D.E. (1989). Genetic Algorithms in search, optimization and machine learning

81. Holland J.H. Adaptation in natural and artifical systems. Ann Arbor: The University of Mithigan Press, 1975.

82. Keeney R.L., Raiffa H. Decision with multiple objectives: preferences and value trade-offs. New York, Willey, 1976.

83. T05.Kirkpatrick S., Gelett C.D., Vecchi M.P. Optimization by Simulated Annealing. Science 220, 1983. Pp. 621-630.

84. Klein D., Hannan E. An algorithm for multiple objective linear programming problem. European Journal of Operations Research, vol. 9, '4, 1982.

85. Kovaljov I. Optimization-Based Design of Software of the Spacecraft Control Systems. Modelling, Measurement and Control. AMSE Press, France, 1994. Vol. 56.-Pp. 14-19.

86. Koza J. R. Genetic Programming: On the Programming of Computers by means of Natural Selections. MIT Press, 1992.

87. Jll.Laguna M. Methods and Strategies,for Robust Combinatorial Optimization. -"Operations Research'94" Thes. of the International Conference, TU Berlin, Berlin, 1994. P. 81.

88. Laguna, M. and F. Glover (1993). Integrating Target Analysis and Tabu Search for Improved Scheduling Systems, Expert Systems with Applications, Vol. 6, 587-297.

89. Michalewicz Z. Genetic algorithms, numerical optimization and constraints. // Proc. of the Sixth Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, 1995.

90. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, New York, second edition, 1992.

91. Moscato, P. and F. Tinetti (1994). Blending Heuristics with a Population-Based Approach: A Memetic Algorithm for the Traveling Salesman Problem // Discrete Applied Mathematics. .

92. Mueller R., Semenkin E., Semenkina O. Job-Shop Scheduling Modeling in Operational Modeling Language. -"Optimization-Based Computer-Aided Modelling and Design" Thes. of the 3rd Working Conf. of the IFIP-TC 7 Working Group 7.6, Prague, 1994. Pp.127-128.

93. Pareto V. Cours d'Economie Politique. Lausanne: Houge, 1889.

94. Parmee I. (Ed.) Adaptive Computing in Engineering Design and Control.

95. Proceedings of the 1st International Conference, Plymouth, 1994. 203 pp. • 119.Parmee I. (Ed.) Adaptive Computing in Engineering Design and Control.

96. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: Frommann-Holzboog (1973).

97. Reeves C.R. Modern Heuristic Techniques. Oxford: Blackwell Scientific, 1993.

98. Roy B. Problems and methods with multiple objective functions. Math. Programming. Amsterdam: North-Holland Publish. Company, 1972. Vol. 1. 12. Pp. 239-266.

99. Schittkowski К. EMP: An expert system for mathematical programming. -Mathematisches Iristitut, Universitaet Bayreuth, Bayreuth, 1993. 69 pp.307

100. Schwefel H.-P. Evolution and Optimum Seeking.-N.Y.:Whiley Publ.,1995. 612pp.

101. BO.Schwefel H.-P. Kybernetische Evolution als Strategie der Stromangstechik. Diploma thesis, Technical University of Berlin (1965).- 131.Schwefel H.-P. Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, Volume 26, Basel, 1977.

102. Semenkin E., Abramovitch K. Software system for solving multi-scale optimization problems. System Modelling and Design. London: Chapman & Hall, 1995. Pp. 497-501.

103. Semenkin E., Volovik M. Modeling and optimization of spacecrafts' system design. Operations Research. Berlin: Springer, 1995. Pp. 353-358.

104. Soriano, P. and M. Gendreau (1993). Diversification Strategies in Tabu Search Algorithms for the Maximum Clique Problem, Publication #940, Centre de Recherche sur les Transports, Universite de Montreal.

105. Sorkin R. A quantitative Occam's razor // International journal of theoretical physics, 22. 1983. - P. 1091-1104.

106. Sywerda E. Uniform crossover in genetic algorithms. In H. Schaffer, editor, 3rd Int. Conf. On Genetic Algorithms, pages 2-9, San Mateo, 1989. Morgan Kaufmann.

107. Vaessens, R., E. Aarts and J.K. Lenstra (1994). Job Shop Scheduling by Local Search, Eindhoven University of Technology, the Netherlands.

108. Voss, S. (1994). Concepts for Parallel Tabu Search, Technische Hochschule Dormstadt, Germany.

109. Weiss H.J. Communication-satellite-system hangover requirement and associated design problems. RCF Review, September 1973. Pp. 421-458

110. Hl.Zimmerman H.-J., Zadeh L.A., Gaines B.R. (Eds.) Fuzzy sets and system analysis -NY, 1984.

111. Публикации автора диссертации:

112. Семенкина О.Э., Жидков В.В. Оптимизация управления сложными системами методом обобщенного локального поиска. М.: МАКС Пресс, 2002.-215 с.

113. Семенкина О.Э. Анализ и формализация задачи выбора эффективного варианта технологического контура системы управления // Метод308обобщенного адаптивного поиска для синтеза систем управления сложными объектами. М: МАКС Пресс, 2002. С. 46-49.

114. Семенкина О.Э. Локальный поиск для оптимизации на дискретной решетке // Вестник НИИ СУВПТ, вып. 7. Красноярск: НИИ СУВПТ, 2001. -С. 268-278.

115. Семенкина О.Э. Поисковые методы оптимизации функций с булевыми переменными // Вестник НИИ СУВПТ, вып. 7. Красноярск: НИИ СУВПТ, 2001.-Сс. 235-246.

116. Mueller R., Semenkin Е., Semenkina О., Solte D. OML-models of job-shop scheduling problems and algorithms // Вестник НИИ СУВПТ, вып. 3, 2000. -Красноярск: НИИ СУВПТ, 2000. С. 121-126.

117. Семенкина О.Э., Коробейников С.П. Программная система решения задач' многокритериальной оптимизации // Непараметрика'2000. Красноярск: САА, 2000^ С. 56-57.

118. Семенкина О.Э., Ильина Т.Р. Коробейников С.П. Формализация задачи планирования загрузки ресурсов мелкосерийного производства // Интеллектуальные технологии и адаптация Красноярск: НИИ СУВПТ, 1999.-Сс. 31-40.

119. Antamoshkin A., Semenkina O. Local search efficiency when optimizing uni-modal pseudoboolean functions II Informatica, 1998, Vol. 9, No 3. Pp. 279-296.

120. Семенкина О.Э., Брюханова E.M. Обобщенные локальные алгоритмы поисковой оптимизации функций с булевыми переменными // Информатика и системы управления. Красноярск: КГТУ, 1998. - Сс. 6775.309

121. Семенкин Е.С., Семенкина О.Э., Коробейников С П. Адаптивные поисковые методы оптимизации сложных систем. Красноярск: СИБУП, 1997.-355 с.

122. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Красноярск: СИБУП, 1997. - 285 с.

123. Semenkina О. Adaptive search algorithms for solving mixed optimization problems in CAD of spacecraft control systems // Abs. of International symposium on operations research. Jena: TU-Jena, 1997.

124. Semenkin E., Semenkina O. Hybrid methods in design of spacecrafts' control systems // Adaptive computing in engineering design and control. Plymouth: Plymouth University Press, 1996. - Pp. 277-284.

125. Abramovich K., Semenkina O., Vishnevskaya S. Solving multi-scale optimization problems with artificial neural networks // Abs. of. International symposium on operations research, Braunschweig,'1996.

126. Semenkin E., Semenkina 0. Design decision making with adaptive search techniques // Journees de 1'Optimisation, Vankuver, 1996.

127. Семенкина О.Э., Брюханова E.M. Гибридные методы оптимизации на основе генетического • алгоритма и локального спуска в задачах проектирования космических систем // Вестник КГТУ: Сборник трудов ФИПУ. Красноярск: КГТУ, 1996. Сс. 131-137.

128. Семенкина О.Э. и др. Оптимизационные программные системы при поддержке принятия решений в проектировании сложных систем // Вестник КГТУ: Сборник трудов ФИПУ. Красноярск: КГТУ, 1996. Сс. 121-128.

129. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Поисковые методы синтеза систем управления космическими аппаратами. Красноярск: СИБУП, 1996. - 325 с.

130. Mueller R., Semenkin Е., Semenkina О. Job-shop scheduling modeling with the operational modeling language // Optimization-based computer-aided modeling and design. Prague: Lansa, 1995. Pp. 61-68.

131. Semenkina O. OPTLA software extension by discrete optimization algorithms // Optimization-based computer-aided modeling and design. Prague: Lansa, 1995. Pp. 94-101.

132. Semenkina O. Local search algorithms in pseudoboolean and discrete optimization problems // Abs. of. International symposium on operations research, Passau, 1995. P.87.

133. Semenkina O. et al. Optimization tools for support of decision making in design of spacecrafts' systems // Operations research. Berlin: Springer-Verlag, 1995. Pp. 329-334.

134. Antamoshkin A., Semenkina O. Complex of dicrete optimization algorithms for spacecraft optimum design // Operations Research'94 Thes. Of the Intern. Conf., TU Berlin, Berlin, 1994. Pp. 87-88.311