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

На правах рукописи Масич Игорь Сергеевич [

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

05.13.01 — Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск—2004

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнё-ва», г. Красноярск

Официальные оппоненты: доктор физ.-мат. наук, профессор

Данилов Николай Николаевич

Ведущая организация: Институт вычислительного моделирования СО РАН, г. Красноярск

Защита состоится "4" ноября 2004 года в 14 часов на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете имени академика М.Ф. Решетнёва» по адресу: 660014, г. Красноярск, просп. им. газ. Красноярский рабочий,

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета

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

Антамошкин Александр Николаевич

доктор физ.-мат. наук, профессор Терпугов Александр Федорович

31.

Автореферат разослан Я 2004

г.

Ученый секретарь диссертационного совете

Ковалев И.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Поставленная цель определила следующие основные задачи исследования.

1. Проведение классификации задач условной псевдобулевой оптимизации и исследование свойств множеств допустимых решений выделенных классов задач.

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

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

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

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

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

Методы исследования. Аппарат теории множеств, теории вероятностей, исследования операций, дискретной оптимизации, математического программирования. Элементы теории вычислительной сложности.

Научная новизна работы:

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность работы

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

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

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

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

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

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

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

из них отдельно.

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на всероссийских конференциях «Решетневские чтения» (2001-2003 гг.), на международной научно-практической конференции "САКС-2001" (г. Красноярск), на XL международной научной конференции "Студент и научно-технический прогресс" (г. Новосибирск) в 2002 году, на V международном симпозиуме «Интеллектуальные системы ШTELS'2002» (г. Калуга), на всероссийских конференциях «Туполев-ские чтения» (г. Казань) в 2002-2003 гг., на всероссийской научно-технической конференции «Совершенствование технологии поиска и разведки, добычи и переработки полезных ископаемых» (г. Красноярск) в 2003 году, на всероссийской научной конференции «Королевские чтения» (г. Самара) в 2003 г., на всероссийской научной конференции «Наука. Технологии. Инновации» (г. Новосибирск) в 2003 г.

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

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

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

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

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

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

Впервые задачи псевдобулевой оптимизации подробно исследовались в работе P.L. Hammer и S. Rudeanu. Там также были разработаны методы решения аналитически заданных задач псевдобулевой оптимизации.

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

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

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

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

Определение. Точки Xх,X1 е В£ назовем к-соседними, если они

отличаются значением к координат, k = \,п . 1-соседние точки будем называть просто соседними.

Определение. Множество Ok(X), k = 0,n, всех точек , к-соседних к точке X, назовем к-м уровнем точки X. При этом О0(Х)= X.

Лемма. \fX e-iij '■ card Ok (X) = С*, где Ckn - число сочетаний из n по к.

п

Лемма. УХ е В! : Вп2 ={JOk(X).

ы о

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

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

Определение. Точку X* для которой

f(X*)< f(X),4XeOl(X ), назовем локальным минимумом псевдобулевой функции/

Определение. Псевдобулевую функцию, имеющую только один

локальный минимум, будем называть унимодальной на функцией.

Определение. Унимодальную функцию / назовем монотонной на 52я, если VXk <=Ok(X*),k = \n:

f(X) < /(Z * ), VX6Ок_,(X*)r\Ol(Хк).

В работе рассматривается задача вида

\С{Х) -» шах

ХлВ'2 (1) Л;(Х)<Ну,] = 1,т

где С(Х) и Aj(X) - псевдобулевые функции, обладающие некоторыми конструктивными свойствами (модальность, монотонность и т.п.).

Задача (1) является iVP-полной задачей дискретной оптимизации, т.е. ее нельзя решить никаким известным точным полиномиальным алгоритмом.

Определение. Точка Y е А является граничной точкой множества А, если существует X е Ox(Y), для которой X £ А.

Определение. Точку Т е 0/Х°) О А будем называть крайней

точкой множества А с базовой точкой Х° е А, если \/Х е ОД) П Ом(Х°) выполняется X € А.

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

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

Лемма. Количество крайних точек связного множества допустимых решений задачи (1) 5 < 5тах =С^2\ где [и/2] - целая часть числа и/2. В случае 5 = все крайние точки расположены на и/2-ом уровне точки Х° при четном и и на (и —1)/2-ом (или (п +1)/2 -ом) уровне при нечетном п.

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

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

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

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

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

Антамошкиным А.Н. построены регулярные точные алгоритмы для оптимизации произвольных псевдобулевых функций без дополнительных ограничений на переменные. В результате сведения условной задачи к задаче оптимизации без ограничений путем составления обобщенной функции со штрафом полученная функция будет являться полимодальной немонотонной псевдобулевой функцией. Оценка трудоемкости соответствующего алгоритма Т < q(n +1) + п — 3 , где q - число изолированных локальных максимумов полимодальной функции. Количество локальных максимумов обобщенной функции равно числу крайних точек множества допустимых решений задачи.

Поэтому max q = С^'1^, откуда видно, что оценка трудоемкости является экспоненциальной, и max Т = 2"

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

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

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

Кроме того, показано, что использование более сильной системы окрестностей (состоящей из соседних и 2-х соседних точек существенно уменьшает трудоемкость и сокращает количество необходимых точек мультистарта.

о-1-1-1-1-1-1-1-

О 2 4 6 8 10 12 14 16

А. п .Ц.

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

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

Рассматривается применение схемы метода ветвей и границ для решения задачи (1), в которой целевая функция и ограничение монотонно возрастают от Х° = . Стандартные алгоритмы метода ветвей и границ с использованием решения релаксированной задачи не подходят для задач, в которых функции заданы алгоритмически.

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

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

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

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

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

Для случая, когда целевая функция С(X) и функция ограничения А(Х) монотонно возрастают от Х° е В^ , оптимальное решение принадлежит подмножеству крайних точек множества допустимых решений. Если решение У е является крайней точкой, то в подкубах и крайних точек нет, и их можно ис-

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

Алгоритм 1.

1. Полагаем к = 1, £2=0, 5 = 0, Х0 =Х°.Еслн А(Х°)>Н, то задача не имеет допустимого решения.

2. Выбираем Х1+1 6 (О, (Хк) П Ош )) \ О, для которого А(Хк+1) < Я. Если для какого-либо X е О, (Хк) п Ок+1 (Х°) не выполняется А(Х) < Н, то = О и К(Х, Х]).

3. Если такой Хк+1 существует, то к = к +1 и на 2.

4. 5 = 5 + 1, Г, =Хк, П = ПиК(Х°,У!)иК(Г!,Х1).

5. Выбираем X € (Ок П 02т (У,)) \ О. таким образом, чтобы т бьшо наибольшим, 1< т <тт{к,п-к}. Если таких точек

6. Если А(Х)>Н, то П = и выбираем

8. Если А(Х) < Н, то выбираем X' е (О, (X) п Ом (Х°)) \ П, для которого А(Х) < Н. Если таких точек нет, то на 10.

11. Определяем оптимальное решение X* из условия

Трудоемкость алгоритма 1 Тх <

+ С

п п

А. +с .2.

+1

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

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

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

Ф(Х)-

1,

т

¡противном случае

Теорема. Если все функции Ау(Х) системы ограничений являются монотонно возрастающими от точки то и функция Ф(Х) является монотонной.

Таким образом, вместо системы неравенств используется неравенство Ф(Х) <0, и задача решается соответствующим алгоритмом.

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

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

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

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

Случайный поиск

1. Полагаем 1 = 1.

2. Х,=Х°,/ = 1.

3. Случайным образом выбираем точку Хм еО1(Х1)пО1(Х0)п{Х^Вп2 : А(Х)<Н}, / = / + 1. Если таких нет, то на 4, иначе цикл повторяется.

4. У, =Х,..Если/<£,то/ = / + 1 ина2.

5. Определяем X* из условия С(Х") = шах С(Х1).

Задаваемое число Ь - количество граничных точек, которое планируется найти. Трудоемкость этого алгоритма

При этом все найденные граничные

точки являются крайними.

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

Рассматривается применение алгоритмов с гриди эвристикой для задачи (1). Для задачи оптимизации монотонной целевой функции с монотонным ограничением возможны две стратегии гриди поиска: поиск из допустимой области и из области недопустимых решений. Соответственно построено два гриди алгоритма: прямой и двойственный.

Гриди алгоритм 1 (прямой)

1. Х = Х°,1 = 1.

2. Вычисляем С(Ху) и А(Х;) для Х] е О^пОДХ0), У = 1,и-/ + 1.

3. Если нет X }, для которых А{Х< Н , то X* = X - решение задачи.

4. Из тех X ■, для которых A(Xj ) < Н , находим

С(ХЛ

X = агц шах-—.

5. / = / + 1, на 2.

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

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

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

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

соответствии с вектором вероятностей Р'*1 = {р"хр'*^} ,

р, -о. / о., где о,=<

7Й' 7 [О, А(Х;)>Н,

У = 1, и — I, X, еО.^пО^СХ0), - текущая

точка поиска.

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

Граничные точки У1, обнаруженные с помощью этого алгоритма

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

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

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

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

ции, являющуюся -трудной, в задачу при-

/(X ) „.»

надлежащую классу Р (полиномиально разрешима), где Л - оптимальное решение, - приближенное решение.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

Основные результаты работы:

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

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

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

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

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

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

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

множестве допустимых решений.

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

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

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

1. Антамошкин, А.Н. Регулярный алгоритм оптимизации загрузки оборудования / А.Н. Антамошкин, Д.А. Дегтерев, И.С. Масич // Труды конф. «Информационные недра Кузбасса». Кемерово: КемГУ, 2003, с. 59-61.

2. Антамошкин, А.Н. Гриди алгоритмы и локальный поиск для условной псевдобулевой оптимизации / А.Н. Антамошкин, И.С. Ма-сич // Электронный журнал "Исследовано в России", 177, стр. 21432149,2003 г. http://zhurnal.ape.relarn.ru/articles/2003/177.pdf

3. Антамошкин, А.Н. Идентификация свойств псевдобулевых функций / А.Н. Антамошкин, И.С. Масич // Электронный журнал "Исследовано в России", 130, стр. 1391-1396, 2004 г. http://zhumal.ape.relam.ru/articles/2004/130.pdf

4. Антамошкин, А.Н. Не улучшаемый алгоритм условной оптимизации монотонных псевдобулевых функций / А.Н. Антамошкин, И.С. Масич // Электронный журнал "Исследовано в России", 64, стр. 703-708, 2004 г. http://zhumal.ape.relam.ru/articles/2004/064.pdf

5. Антамошкин, А.Н. Регулярные алгоритмы для задач условной псевдобулевой оптимизации / А.Н. Антамошкин, И.С. Масич // САКС-2001: Материалы Международной научно-практической кон-ференции./САА - ч.2. - Красноярск, 2001, с. 328-330.

6. Антамошкин, А.Н. Сравнительная эффективность двух схем локального поиска при оптимизации псевдобулевых функций / А.Н. Антамошкин, И.С. Масич // Электронный журнал "Исследовано в России", 51, стр. 544-546, 2004 г. http://zhumal.ape.relam.ru/articles/2004/051 .pdf

7. Антамошкин, А.Н. Эффективные алгоритмы условной оптимизации монотонных псевдобулевых функций / А.Н. Антамошкин, И.С. Масич // Вестник СибГАУ: Сб. науч. тр. / Под. ред. проф. Г.П. Белякова; СибГАУ. - Вып. 4. - Красноярск, 2003, с. 60-67.

8. Дегтерев, Д.А. Оптимизация загрузки технологического оборудования предприятия / Д.А. Дегтерев, И.С. Масич, Г.А. Нейман // Вестник Ассоциации выпускников КГТУ. Вып. 8 / Красноярск: ИПЦ КГТУ,2002, 166-170 с.

9. Дегтерев, Д.А. Поиск граничных точек в задаче условной оптимизации монотонных псевдобулевых функций / Д.А. Дегтерев, И.С. Масич // Объединенный научный журнал. «ТЕЗАРУС», Москва, 2003 №2-3, 89-95 с.

10. Масич, И.С. Алгоритмы случайного поиска для условной оптимизации псевдобулевых функций / И.С. Масич // VII Королёвские чтения: Всероссийская молодежная научная конференция: Тезисы докладов. Том I. Самара: Изд-во Самарского научного центра РАН, 2003, 42-43 с.

11. Масич, И.С. Локальная оптимизация для задачи выбора информативных факторов / И.С. Масич // НАУКА. ТЕХНОЛОГИИ. ИННОВАЦИИ // Материалы докладов всероссийской научной конференции молодых ученых в 6-ти частях. Новосибирск: Изд-во НГТУ, 2003. Часть 1,50-51 с.

12. Масич, И.С. Метод ветвей и границ в задаче оптимизации систем отказоустойчивого программного обеспечения / И.С. Масич // Научная сессия ТУ СУР / Материалы докладов межрегиональной научно-технической конференции / ТУ СУР, Томск, 2002, с. 31-34.

13. Масич, И.С. Метод ветвей и границ для решения задачи условной оптимизации с булевыми переменными / И.С. Масич // Материалы XL Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика / НГУ, Новосибирск, 2002, с. 118-119.

14. Масич, И.С. Отбор существенных факторов в виде задачи псевдобулевой оптимизации / И.С. Масич // Решетневские чтения: Тез. докл. VII Всероа науч. конф./ СибГАУ. - Красноярск, 2003, с. 234-235.

15. Масич, И.С. Регулярный алгоритм поиска граничных точек в задаче условной оптимизации монотонных псевдобулевых функций / И.С. Масич // «Совершенствование технологий поиска и разведки, добычи и переработки полезных ископаемых»: Сб. материалов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых, КрасГАЦиЗ. - Красноярск, 2003, с. 170-172.

16. Масич, И.С. Случайный поиск граничных точек в задаче условной псевдобулевой оптимизации / И.С. Масич // XI Туполевские чтения: Всероссийская (с международным участием) молодёжная научная конференция: Том III. Казань: Изд-во Казан, гос. техн. ун-та. 2003.-с. 14.

17. Масич, И.С. Сравнительная эффективность некоторых регулярных алгоритмов условной псевдобулевой оптимизации / И.С. Ма-сич // Юбилейные X Всероссийские (с международным участием) Ту-

«¡8194

полевские чтения студентов. Том П. Казань: Изд-во Казан, гос. техн. ун-та. 2002. - с. 11.

18. Масич, И.С. Сравнительная эффективность регулярных процедур условной оптимизации псевдобулевых функций / И.С. Масич // Вестник НИИ СУВПТ: Интеллектуальные технологии и адаптация: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко.-Красноярск: НИИ СУВПТ, 2002. - с. 160-177.

19. Masich, I.S. Multi-version methods of software reliability growth in intelligence systems /I.S. Masich // Intelligent Systems //Proceeding of the Fifth International Symposium / Moscow: BMSTU, 2002. p. 74-76._

РНБ Русский фонд

2005-4

Масич Игорь Сергеевич

15161

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

Автореферат

Подписано к печати 23.09.2004 Формат 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ № ш

Отпечатано в отделе копировальной и множительной техники

СибГАУ

660014 г. Красноярск, просп. им. газеты "Красноярский рабочий", 31

Введение

1 Постановка задачи. Необходимый математический аппарат

1.1 Состояние проблемы

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

1.3 Классы псевдобулевых функций

1.4 Постановка задачи оптимизации

1.5 Свойства множества допустимых решений задачи

1.6 Идентификация свойств псевдобулевых функций

1.6.1 Применение регулярного алгоритма оптимизации для идентификации свойств

1.6.2 Идентификация свойств посредством квадратичной аппроксимации

1.6.2.1 Способы квадратичной аппроксимации псевдобулевых функций

1.6.2.2 Определение свойств квадратичной функции Выводы

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

2.1 Составление обобщенной функции со штрафом

2.2 Регулярные точные алгоритмы безусловной оптимизации

2.3 Локальный поиск

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

2.3.2 Локальный поиск для условной оптимизации

2.4 Схема метода ветвей и границ

2.4.1 Общая схема метода ветвей и границ

2.4.2 Алгоритм метода ветвей и границ для задачи с неявно заданными функциями

2.4.3 Приближенные алгоритмы метода ветвей и границ

2.4.4 Условная оптимизация изотонных псевдобулевых функций 56 Выводы

3 Регулярные точные процедуры оптимизации, реализующие 61 свойства классов задач

3.1 Классы задач условной псевдобулевой оптимизации

3.1.1 Свойства функций ограничений

3.1.2 Свойства целевых функций

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

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

3.3.1 Случай монотонной целевой функции

3.3.2 Случай унимодальной целевой функции

3.3.3 Случай целевой функции общего вида

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

3.4.1 Случай монотонной целевой функции

3.4.2 Случай унимодальной целевой функции

3.4.3 Случай целевой функции общего вида

3.5 Алгоритмы псевдобулевой оптимизации с функциями 87 ограничений общего вида

3.5.1 Случай монотонной целевой функции

3.5.2 Случай унимодальной целевой функции

3.5.3 Случай целевой функции общего вида

3.6 Системьрограничений 91 Выводы

4 Приближенные*алгоритмы условной псевдобулевой оптимизации

4.1 Случайный поиск граничных точек

4.2 Гриди алгоритмы

4.2.1 Основные принципы и обоснование гриди эвристики

4.2.2 Гриди алгоритмы для условной псевдобулевой оптимизации

4.2.3 Оценка точности гриди алгоритмов

4.3 Адаптивный случайный поиск

4.4 Экспериментальные исследования приближенных алгоритмов 108 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

Методы исследования. Аппарат теории множеств, теории вероятностей, исследования операций, дискретной оптимизации, математического программирования. Элементы теории вычислительной сложности.

Научная новизна работы:

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

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

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

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

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

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

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

Теоретическая и практическая ценность работы

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

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

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

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

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

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

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

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на всероссийских конференциях «Решетневские чтения» (2001-2003 гг.), на международной научно-практической конференции "САКС-2001" (г. Красноярск), на XL международной^ научной конференции "Студент и научно-технический у прогресс" (г. Новосибирск) в. 2002 году, на V международном: симпозиуме

ИнтеллектуальнБю- системы INTELS'2002» (г. Калуга), на всероссийских конференциях «Туполевские чтения» (г. Казань) в 2002-2003 гг., на всероссийской научно-технической конференции «Совершенствование технологии поиска и разведки, добычи и переработки полезных ископаемых» (г. Красноярск) в 2003 году, на всероссийской; научной конференции «Королевские чтения», (г. Самара) в 2003 г., на всероссийской научной. I конференции «Наука. Технологии. Инновации» (г. Новосибирск) в 2003 г.

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

Публикации^По теме диссертации: автором опубликовано девятнадцать работ.

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

Выводы

Приведенные в этой главе регулярные и стохастические алгоритмы переводят исходную задачу условной псевдобулевой оптимизации, являющуюся iVP-трудной, в задачу f{X') принадлежащую классу Р (полиномиально разрешима), где X" - оптимальное решение, X' - приближенное решение.

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

-4-

Заключение

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

Основныерюзультаты работы:

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

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

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

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

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

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

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

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

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

1. Антамошкин, А.Н. Системный анализ: проектирование, оптимизация и приложения / А.Н: Антамошкин и др. Красноярск: САА и СО РИА, 1996, т.1 -334"с.,,т.2 -290 с.

2. Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными ЛД.Н. Антамошкин. Томск: Изд-во Томского ун-та, 1987, 218 с.

3. Антамошкин, А.Н. Регулярная < оптимизация псевдобулевых функций >■ / А.Н. Антамошкиц^ Красноярск: Изд-во Красноярского ун-та, 1989, 284 с.

4. Антамошкин, А.Н. Регулярный: алгоритм оптимизации загрузки оборудования / А.Н. Антамошкин; Д.А'. Дегтерев, И.С. Масич // Труды конф. «Информационные недра Кузбасса». Кемерово: КемГУ, 2003, с. 59-61.

5. Антамошкин, А.Н. Гриди алгоритмы, и локальный поиск для условной псевдобулевой оптимизации / А.Н: Антамошкин, И.С. Масич // Электронный журнал "Исследовано в России", 177, стр. 2143-2149;, 2003 г. http://zhurnaliape.relarn.ru/articles/2003/177.pdf

6. Антамошкин, А.Н. Идентификация; свойств псевдобулевых. функций / А.Н. Антамоиташ, И.С. Масич // Электронный журнал "Исследовано в России", 130, стр. 1391-1396. 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/130.pdf

7. Антамошкин, А.Н: Не улучшаемый: алгоритм- условной- оптимизации-монотонных; псевдобулевых функций; / А.Н: Антамошкин, И.С. Масич; // Электронный журнал "Исследовано в России", 64, стр. 703-708, 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/064.pdf

8. Масич // Электронный журнал "Исследовано в России", 51, стр. 544-546, 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/051 .pdf

9. Антамошкин, А.Н. Эффективные алгоритмы условной оптимизации монотонных псевдобулевых функций; / А.Н. Антамошкин, И.С. Масич // Вестник СибГАУ: Сб. науч. тр. / Под. ред. проф. Г.П. Белякова; СибГАУ. -Вып. 4. Красноярск, 2003, с. 60-67.

10. Антамошкин, А.Н. Оптимизация полимодальных псевдобулевых функций / А.Н. Антамошкин, B.C. Рассохин // ОФАП Минвуза РСФСР. Инв.№85119.М., 1985, 43 с.

11. Береснев, В Л: Математические модели планирования, развития систем, технических средств / В. Л. Береснев // Дискретный анализ и исследование операций. Серия 2. 1997, том 4, № 1, с.4-29.

12. Береснев, B.JI. Алгоритмы минимизации для некоторых классов полиномов от булевых переменных / В;Л. Береснев, А.А. Агеев // Модели и методы оптимизации: Сб. науч. тр. Новосибирск: Наука, 1988. Том 10. с.5-17.

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

14. Вайнгауз, A.M. Оптимизация изотонных функций с булевыми переменными / A.M. Вайнгауз // Деп. в ВИНИТИ; 3761 В86. Кемерово, 1986, 49 с.

15. Гене, Г. В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор) / Г. В. Гене, Е. В. Левнер // Известия АН СССР. Техническая кибернетика, 1976, № 6, с. 84-92.

16. Гене, Г7В. Эффективные приближенные алгоритмы для комбинаторных задач / Г. В. Гене, Е. В: Левнер М., 1981. - 68 с.

17. Гришухин, В.П. Полиномиальность в простейшейзадаче размещения / В.П. Гришухин // Препринт ЦЭМИ АН СССР. М., 1987, 64 с.

18. Дегтерев, Д.А. Оптимизация загрузки технологического оборудования предприятия / Д.А. Дегтерев, И.С. Масич, Г.А. Нейман // Вестник Ассоциации выпускников КГТУ. Вып. 8 / Красноярск: ИПЦ КГТУ, 2002, 166-170 с.

19. Дегтерев, Д.А. Поиск граничных точек в задаче условной оптимизации монотонных псевдобулевых функций / Д.А. Дегтерев, И.С. Масич // Объединенный научный журнал. «ТЕЗАРУС», Москва, 2003 № 2-3, 89-95 с.

20. Дюбин,- КЙТ Жадные- алгоритмы для- задачи- о ранце: поведение в среднем / Г.Н. Дюбин, А.А. Корбут// Сиб. ж. индустр. мат. 2, N2(4), 1999. - с. 68-93.

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

22. Имануилов,. П:А. Решение задачи формирования кредитного портфеля банка методом Мивер / П.А. Имануилов, В.А. Пуртиков // Вестник НИИ СУВПТ выпуск №5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко.- Красноярск: НИИ СУВПТ, 2000.

23. Казаковцев, JI.A. Подходы к автоматизации задач планирования ассортимента на торговых предприятиях / Л.А. Казаковцев // Вестник НИИ СУВПТ выпуск 1^5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко.- Красноярск: НИИ СУВПТ, 2000.

24. Ковалев, И. В. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами / И: В; Ковалев// Дис. док. техн. наук. Красноярск: КГТУ, 1997, 238 с.

25. Ковалев, М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. Минск, 1977. - 191 с.

26. Корбут, А.А. Дискретное программирование / А.А. Корбут, Ю.Ю. Финкелыитейн М. Наука. Гл. ред. физ.-мат. лит. 1969, 389 с.

27. Лбов, Tv'C. Выбор эффективной системы зависимых признаков / Г. С. Лбов. В; кн.: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1965, вып. 19, с. 21*94.

28. Лбов, Г. С. Программа "Случайный поиск с адаптацией для выбора эффективной системы зависимых признаков" 7 Г. С. Лбов. В кн.: Геология и математика. Новосибирск: Наука, 1970, с. 204-219.

29. Масич, И.С. Метод ветвей и границ в задаче оптимизации систем отказоустойчивого программного обеспечения / И.С. Масич // Научная сессия ТУ СУР / Материалы докладов межрегиональной научно-технической конференции / ТУ СУР, Томск, 2002, с. 31-34.

30. Масич, И.С. Отбор существенных факторов; в виде задачи псевдобулевой оптимизации / И.С. Масич // Решетневские. чтения: Тез. докл. VII Всерос. науч. конф./ СибГАУ. Красноярск, 2003, с. 234-235.

31. Нейман, Г.А. Регулярные алгоритмы псевдобулевой оптимизации систем отказоустойчивого программного обеспечения / Г.А. Нейман // Вестник НИИ СУВПТ выпуск №5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 2000.

32. Нейман, Г.А. Метод случайного поиска граничной точки / Г.А. Нейман, Н.А. Филатов // Вестник НИИ СУВПТ: вып. 7: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 2001, с. 84-87.

33. Пападимитриу, X. Комбинаторная оптимизация / X. Пападимитриу, К.54 W

34. Стайглиц. Алгоритмы и сложность: Пер. с англ. - М:: Мир, 1985. - 512 с.

35. Попов, А.А. Оптимизационные методы формирования мультиверсионного программного обеспечения критичных по надежности систем управления / А.А. Попов // Дис. . канд. техн. наук. / Красноярск: НИИ СУВПТ, 2002, 192 с.

36. Попов, Rfor. Структурная оптимизация систем отказоустойчивого программного обеспечения / А.А. Попов, И.Н. Давыдов // Вестник НИИ СУВПТ выпуск №2: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 1999, с. 47-63.

37. Растригин, JI.А. Адаптация сложных систем / JI.A. Растригин. Рига: Зинатне.- 1981-. - 375 с.

38. Растригин, JI.A. Случайный поиск / Л.А. Растригин. М.: Знание, 1979,64 с.

39. Растрищн, Л.А. Решение задач разношкальной оптимизации методами случайного поиска / Л.А. Растригин, Э.Э. Фрейманис // Проблемы случайного поиска, 1988, выцЦ^, с. 9-25.

40. Семенкин, Е.С. Оптимизация технических систем / Е.С. Семенкин Е.С., О.Э. Семенкина, С.П. Коробейников. Красноярск: СИБУП, 1996, 358 с.

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

42. Сергиенко, И.В. Приближенные методы решения дискретных задач оптимизации 7 И.В. Сергиенко, Т.Т. Лебедева, В.А. Рощин. Киев: Наукова думка, 1981.-272 с.

43. Сигал, И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы / И.Х. Сигал, А.П. Иванова. Учеб. пособие. - М.: ФИЗМАТЛИТ, 2002. - 240 с.

44. Стоян, Ю.Г. Об одном отображении комбинаторных множеств в евклидово пространство / Ю.Г. Стоян // Препринт ИПМаш АН УССР. Харьков, 1982,33 с.

45. Финкельштейн, Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Ю.Ю. Финкельштейн. — М.: Наука, 1976. -264 с.

46. Хачатуров, В.Р. Аппроксимационно-комбинаторный метод и некоторые-а* ' ^