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

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

МИНАКОВ Сергей В ладим ирович

Структурное моделирование в классе задач о назначении и исследование генетического метода решения

Специальность 05.13.18 -Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Воронеж-2004

Работа выполнена на кафедре «Прикладной математики и экономико-математических методов» Воронежской государственной технологической академии

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

Матвеев Михаил Григорьевич

Официальные оппоненты:

доктор физико-математических наук, профессор Сумин Александр Иванович

кандидат физико-математических наук, доцент Никитин Борис Егорович

Ведущая организация: Ростовский государственный

университет

Защита диссертации состоится «16» декабря 2004 г. в 1450 на заседании диссертационного совета Д 212.035.02 в Государственном образовательном учреждении Воронежской государственной технологической академии по адресу: 394000, г. Воронеж, пр. Революции, 19, а. 30 (конференц-зал).

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

Автореферат разослан «15» ноября 2004 г.

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

к.т.н. В.М. Самойлов

2005-1!

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

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

Тематика диссертационной работы соответствует научному направлению кафедры ПМиЭММ «Разработка математических моделей, методов и информационных технологий в технических и

I .А ЦП ОПАЛЬНАЯ БИБЛИОТЕКА СПст«|

оэ

экономических системах перерабатывающей промышленности» (№ г.р. 01200003664).

Объектом диссертационных исследований являются математические модели и численные методы решения класса задач о назначении.

Предметом диссертационных исследований являются свойства моделей и численных методов.

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

Для достижения поставленной цели необходимо решение следующих задач:

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

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

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

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

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

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

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

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

3. Оператор мутации генетического алгоритма, в котором реализована проверка хромосомы на соответствие ограничениям.

Практическая ценность. Использование структурного

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

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на III Всероссийской научно-технической конференции «Теория конфликта и ее приложения» (Воронеж, 2004), на VII Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (ТВАИИ, Тамбов, 2004), III Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2003), IV Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2004), а также на научных семинарах кафедры прикладной математики и экономико-математических методов ВГТА.

Публикации. Результаты диссертации отражены в 9 печатных работах, из них 5 - без соавторов, 1 - из списка ВАК.

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

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

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

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

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

Рис. 1. Схематическое представление задачи структурного моделирования

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

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

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

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

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

Пусть заданы множества элементов Ц, (= 1 В каждом множестве имеется пэлементов:

между которым и задано ш отношений:

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

Каждому отношению Я1 между элементами на множестве M1 соспоставим булевую матрицу

С\ , = {0,1}, г1 = {1,•••,"}. (3) ['.—»']

1 - если элемент а1 вступает в отношение R с элементом а,

0 - иначе.

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

х[г',,..,У = {0,1}, г, = {1,...,л}, (4)

1 -еслиэлементы я,,...,а назначаются друг другу, 0 - иначе.

Одному элементу из множества можно сопоставить только один элемент из любого другого множества, поэтому ограничения задачи примут вид: п

= 1, ц = {1,...и}, / = {2,3,...,т},

п

л[/1 ,...,!„] = 1, г, = {1,...и}, ¿ = {1,3,...,т),

¡2=\ ^'

п

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

У •••У С 1 1 х-хГ"\ I х Гг I 1-1х'"хГг* ¿1 -> МАХ

'т '-.-' .

'-«-' т *

кит

(б)

Из целевой функции видно, что в частном случае при т = 2 и к = 2 получается квадратичная задача о назначении.

Полученную математическую модель можно интерпретировать на графах как задачу поиска наибольшего клика. В целевой функции находится многочлен степени к состоящий из суммы произведений двоичных переменных. Каждое произведение может быть равным 0 или 1. Введем переменные I = {0, 1}, V % ~

1.^. Произведениям из суммы в многочлене сопоставим введенные переменные I.. В результате переопределения переменных получили многочлен первой степени:

(9)

Чтобы учесть ограничения введем матрицу смежности, в которой:

(1, если = tj-\

О, иначе

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

В третьей главе предлагается генетический алгоритм и

исследование его эффективности.

Определим основные термины генетического алгоритма для математической модели (4)-(6).

Индивидуум -матрица X удовлетворяющая ограничениям (5). Хромосома - вектор-строка матрицы Х1Г Ген- любая позиция хромосомы, т.е. О или 1.

Приспособленность индивидуума Х- значение функции ¥(Х), где ¥ целевая функция (6).

Определим функцию кроссовера К(Х,, X), т.е. скрещивания двух индивидуумов Х1 и X. Результатом кроссовера является новый индивидуум Х3 -К(Х'„ X).

Обозначим операцию скрещивания как Х. Потомок Х3 должен быть чем-то «средним» между родителями

X, и Скрещивание происходит похромосомно, т.е. потомок формируется из хромосом родителей. Т.к. индивидуум должен удовлетворять ограничениям модели, то в каждой хромосоме присутствует только один ненулевой ген, следовательно /-я хромосома индивидуума Xопределяется позицией ^(Х) ненулевого гена. Таким образом, если

J¡(X¡) - позиция ненулевого гена г'-й хромосомы

позиция ненулевого гена 1-й хромосомы Jí(X3)Jщя потомка, определим как

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

Щ) = тт((Щ), 3^)) + гапс1от(\(Щ)-Щ)\), где гап^т(п) - функция случайного целого числа в промежутке [О, и]. Таким образом, потомок будет находится на случайной позиции между двумя родителями. Следующий пример иллюстрирует функцию кроссовера:

"0 1 0 о" "о 0 0 г 0 0 ] о"

1 0 0 0 /0| 0 0 1 0 0 1 0 0

0 0 0 1 1 0 0 0 0 0 0 1

0 0 1 0_ 0 1 0 0 1 0 0 0

Рис. 2. Пример скрещивания особей.

Работа операции кроссовера Х1 0 Х^ заключается в последовательном пересчете позиций ненулевых генов хромосом индивидуумов Х1 И Х^. При вычислении новой хромосомы необходимо учитывать вторую часть ограничений (5), т.е. в столбце матрицы находится только один единичный элемент. Для соблюдения этого ограничения, после вычисления позиции единичного гена, достаточно корректировать ее сдвигая поочередно вправо и влево. Данную коррекцию позиции можно назвать случайной М-мутацией хромосомы. Согласно введенного

понятия мутации последняя хромосома индивидуума будет предопределяется предыдущими.

Имеется много способов реализации идеи биологической эволюции в рамках ГА. Для математической моделл (4)-(6) предлагается следующий генетический алгоритм:

НАЧАЛО /* Генетический алгоритм */ (10)

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

2. к := р * п!

3 . Распределим к индивидуумов начальной популяции в множестве п! возможных. ПОКА НЕ Останов ВЫПОЛНЯТЬ НАЧАЛО

^=1, s:=0

ПОКА ^=к-1 ВЫПОЛНЯТЬ /* Воспроизводство */ НАЧАЛО

1. Выберем двух соседних особей Хх и Х1п

к:=к-1 // т.е. особи X! и Х1+1 очень похожи 4. Вычислим приспособленности Г(Х1), Р(Х1+1),

КОНЕЦ

1. Если к = 1, то Останов:=true

2. Если 8=к, то Останов: ^гие / / ПОТОМСТЕО лучше не становится

КОНЕЦ КОНЕЦ

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

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

Утверждение: Генетический алгоритм (10) представим в каноническом виде.

Доказательство: Для представления алгоритма в каноническом виде закодируем каждый индивидуум матрицы X в двоичный вектор. Пространство поиска составляет п\ вариантов, что соответствует всем возможным матрицам X размерности п, у которых на пересечении строк и столбцов находится 1 согласно ограничениям модели (4)-(6). Значит, множество допустимых решений можно представить множеством перестановок без повторения п натуральных чисел:х={ху,х2, ...,х},х1 е {1, 2,...,п}, где г - строка, ах, - индекс столбца с не нулевым элементом. Каждому элементу перестановки х={х,х, ...,х} сопоставим

матричный блок Х{ матрицы X, у которого левый верхний угол совпадает с X, а правый нижний ограничен элементом х1 включая строку элемента и исключая столбец. Пусть функция 8(х) для элемента вектора х={х,,х, ...,х} возвращает количество столбцов не содержащих единичные элементы в соответствующем ему

матричному блоке • В пространстве двоичных матриц введем

п

следующую норму:

1=1

где х1 - элементы вектора-перестановки соответствующие матрице X. Эта норма позволяет установить взаимно однозначное соответствие между допустимыми по ограничениям (5) матрицами и множеством (0,1,2,..., (п)!-1}. Теперь для кодирования матрицы X, у которой не нулевые элементы находятся только на пересечении строк и столбцов, в двоичный вектор (Ьи Ь, ..., ЬJ, достаточно ее норму разложить в бинарный вид: + ... + 2х6п1.| + Ь . Таким образом, существует способ преобразования матрицы X в двоичный вектор, что позволяет алгоритм (10) представить в каноническом виде. Утверждение доказано.

Приведены примеры кодирования и декодирования матрицы X предложенным методом.

( 0 0 1 0' '■?(*,)= 2>

0 1 0 0 =>(3,2,4,1)=» $(*,) = 1

0 0 0 1

0 0

>3!х2+2'х1 + 11х1 + 0!х0 = 15-(ОНИ)

Рис.2. Пример кодирования матрицы в двоичный вектор.

(1 О 11 о) 22 = З'хЗ+2!х 2+1!х 0+О'хО:

5(1.) = 3' Я*2) = 2 5(х,) = 0

-(4,3,1,2):

ГО О О Г 0 0 10 10 0 0 0 10 0

Рис. 3. Пример декодирования двоичного вектора в матрицу.

Шимой называется строка вида (я,, ..., ап\ а) е {0, 1, *}. Символом «*» в некотором разряде обозначается то, что там может быть как 1, так и 0. Шима является обобщением нескольких бинарных строк.

Определяющая длина 5(Я) шИМЫ Н называется расстояние между двумя крайним и сим волам и «0» и/или «1».

р(Н, 0 - доля хромосом, соответствующих шиме Н в текущем поколении t. Данную величину можно трактовать как вероятность появления шимы Я в хромосомах популяции.

Следствие: Для генетического алгоритма (10) вероятность появления шимы Я в хромосомах следующего поколения оценивается неравенством:

8{Н)

(р(Н,( + \))>р(Н,1)Щ^-

т

1 ~рс

1-1

о-рт)0(Н].

где (11)

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

Доказательство: Существует теорема о шимах, доказанная Д.Холландом в 1992 г., что для генетического алгоритма канонического вида популяция не ухудшается в процессе эволюционного цикла и вероятность появления шимы оценивается

как (11). Из доказанного выше утверждения следует, что алгоритм (10) представим в каноническом виде, следовательно оценка (11) верна для предлагаемого алгоритма (10). Следствие доказано.

Численные эксперименты тестирования генетического алгоритма (10) подтверждают достоверность теоретических заключений.

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

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

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

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

I 2 3 4 8 * ♦ • «• *

6 7 8 8 10

II 12 13 14^ "15 18 17 /

18 19 20/

Рис.5. Заготовка Рис.6. Изделия

Пусть Щ = {1,...,я} - множество ячеек сетки заготовок, Мя = {1,...,7г} - множество ячеек сетки изделий. В случае не равных по мощности множеств дополняем меньшее из них нужным количеством фиктивных ячеек.

Чтобы учесть форму изделий и заготовок введем на множествахЩ и Мя следующие отношения:

5у = {0,1},Уг',у = 1..п, где 1 - если ячейка г из множества М3 является соседней для 0 - иначе.

Д,; = {0,1},У/,У = 1..", где 1 - если ячейка г из множества Мк является соседней для}, 0 - иначе.

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

Решение задачи о раскрое заключается в поиске X = {0,1}, /,у =1 ..п, где 1 - если элементу из множества Ц. назначен элемент из Мя, 0-иначе.

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

И I ах

М у=1 Ы+1 /=у+1 Т.к. элементы из множеств Щ и Мя могут назначаться друг другу только один раз, то добавляются следующие ограничения:

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

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

№ Вычисленное Точное значение Время поиска

эксп. : значение ЦФ ЦФ решения, сек.

1 16 18 110

2 19 20 95

3 22 25 121

4 17 17 89

5 15 16 78

6 19 20 98

7 23 24 142

8 17 19 132

9 20 21 122

10 22 24 128

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

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

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

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

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

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

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

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

Список публикаций:

1. Матвгев М.Г., Минаков СВ. Генетический алгоритм решения целочисленной задачи оптимального раскроя // Материалы докладов VII всероссийской научно-технической конференции. -Тамбов, 2004.-С.273-275.

2. Минаков С.В. Генетический алгоритм в задачах целочисленного программирования //Сборник научных трудов /ВГТА.-Воронеж, 2004.-С. 214-215.

3. Минаков СВ. Ранжированный доступ к базам данных через Internet // Материалы XLI отчетной научной конференции / ВГТА. -Воронеж, 2003. -С.77.

4. Минаков СВ. Проект «Коммунальные платежи» // Информатика : проблемы, методология, технологии материалы III регион, науч.—метод, конф. -Воронеж, 2003. -С. 101-103.

5. Минаков СВ. Проект «Касса» // Информатика : проблемы, методология, технологии : Материалы IV регион, науч.-метод. конф. -Воронеж,2004. -С 176-178.

6. Каширина И.Л., Минаков СВ. Система автоматического построения расписания учебных занятий // Математика.

Экономика. Образование. Ряды Фурье и их приложения : тр. Рос. ассоциации «Женщины-математики». - Воронеж, 2002. -Т. 10.-С. 67-70.

7. Минаков СВ. Задача о назначении и размещении структурированных объектов // Математические и инструментальные методы в экономике : сб. науч. тр./ВГТА. -Воронеж, 2004. -С. 171-175.

8. Матвеев М.Г., Минаков СВ. Генетический алгоритм для решения квадратичной задачи о назначениях // Вестн. Воронеж, гос. ун-та. Сер. Физика, математика. - 2004.

9. Матвеев М.Г., Минаков СВ. Моделирование структур в задачах назначения // Теория конфликта и ее приложения : материалы III всерос. науч.-техн. конф. -Воронеж, 2004. -С. 357-361.

Подписано к печати 5, //. 04, Формат 60x84 1/16. Бумага для м нож. аппаратов. Печать офсетная. Усл. печ. л. 1,0. Уч.-изд.л. 1,0. Тираж 100 экз. Заказ № Н77

Участок оперативной полиграфии Воронежской государственной технологической академии 394000 Воронеж, пр. Революции, 19

^ 2 2 О 6 8

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

2005-4 21013

ВВЕДЕНИЕ.

1. МОДЕЛИРОВАНИЕ СТРУКТУР В ЗАДАЧАХ НАЗНАЧЕНИЯ.

1.1. Постановка задачи о назначении как задачи структурного моделирования.

1.2. Анализ частных случаев формализованных постановок задач.

1.2.1. Транспортная задача.

1.2.2. Задача о размещении и раскрое.

1.2.3. Двухуровневая задача о назначении.

1.2.4. Конечные автоматы.

1.3. Методы решения задач.

1.3.1. Комбинаторные методы.

1.3.2. Методы линеаризации.

1.3.3. Генетические алгоритмы.

1.4. Выводы и постановка задачи исследования.

2. ЗАДАЧА СТРУКТУРНОГО МОДЕЛИРОВАНИЯ.

2.1. Постановка задачи в общем виде.

2.2. Интерпретация задачи на графах.

2.3. Разработка способов формализации ограничений.

2.4. Квадратичная задача о назначении как частный случай.

3. РАЗРАБОТКА ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ СТРУКТУРНОГО МОДЕЛИРОВАНИЯ.

3.1. Математическая интерпретация основных понятий и этапов генетического алгоритма.

3.2. Синтез и исследование алгоритма решения квадратичной задачи о назначениях.

3.3. Преимущества и недостатки метода.

4. ПРИМЕРЫ РЕАЛИЗАЦИИ ЗАДАЧ СТРУКТУРНОГО

МОДЕЛИРОВАНИЯ.

4.1. Задача о раскрое с произвольным видом границ.

4.2. Задача составления расписания занятий.

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

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

Тематика диссертационной работы соответствует научному направлению кафедры ПМиЭММ «Разработка математических моделей, методов и информационных технологий в технических и экономических системах перерабатывающей промышленности» (№ г.р. 01200003664).

Объектом диссертационных исследований являются математические модели и численные методы решения класса задач о назначении.

Предметом диссертационных исследований являются свойства моделей и численных методов.

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

Для достижения поставленной цели необходимо решение следующих задач:

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

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

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

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

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

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

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

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

3. Оператор мутации генетического алгоритма, в котором реализована проверка хромосомы на соответствие ограничениям.

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

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на III Всероссийской научно-технической конференции «Теория конфликта и ее приложения» (Воронеж, 2004). На VII Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования» (ТВАИИ, Тамбов, 2004). III Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2003). IV Региональной научно-методической конференции «Информатика: проблемы, методологии, технологии», (ВГУ, Воронеж, 2004), а также на научных семинарах кафедры прикладной математики и экономико-математических методов ВГТЛ.

Публикации. Результаты диссертации отражены в 9 печатных работах, из них 5 - без соавторов, 1 - из списка ВАК.

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

Во второй главе рассматривается задача структурного моделирования в общем виде, в которой оптимальным образом требуется сопоставить некоторое конечное число множеств с заданными структурами. При этом критерием является учет структуры множеств, от которого зависит качество назначения. Структура объекта иредставима в виде множества элементов с заданным на нем отношением, а отношения на множествах можно задавать в виде булевых матриц. В зависимости от того насколько сложна структура множества, настолько много потребуется элементов в отношении, чтобы ее описать. Поэтому вводится понятие показателя сложности структуры. Каждому отношению между элементами на множестве сопоставляется булевая матрица. Переменной в математической модели также является многомерная булевая матрица. Задается целевая функцию задачи. Оиа учитывает матрицу отношений и взаимозависимость элементов. Поэтому в целевой функции проверяются поэлементно назначения из каждого множества, если отношения соблюдаются, то произведение равняется 1, в противном случае - 0. Таким образом, целевая функция стремиться к максимуму, чтобы увеличить количество выполненных отношений. Из целевой функции и ограничений видно, что квадратичная задача о назначении является частным случаем предлагаемой модели. Полученная математическая модель интерпретируется на графах как задача поиска наибольшего клика. Но при больших размерностях задач, требуется поиск решения за приемлемое время, что не могут обеспечивать алгоритмы, реализованные на графах. Также метод ветвей и границ, различные способы линеаризации целевой функции вызывают ряд сложностей при реализации вычислительной схемы. Итак, во второй главе, построена общая модель задач о структурном назначении.

В третьей главе предлагается генетический алгоритм и исследование его эффективности. Для реализации разработанной математической модели определяются основные термины: индивидуум, хромосома, ген, приспособленность. Задается функция кроссовера скрещивания двух индивидуумов. Скрещивание происходит похромосомно, т.е. потомок формируется из хромосом родителей. Т.к. индивидуум должен удовлетворять ограничениям модели, то в каждой хромосоме присутствует только один ненулевой ген, следовательно /-я хромосома индивидуума X определяется позицией ненулевого гена. Чтобы приблизить генетический алгоритм к более реальному биологическому процессу, в кроссовере используется функция рандомизации. Работа операции кроссовера заключается в последовательном скрещивании позиций ненулевых генов хромосом индивидуумов. При вычислении новой хромосомы необходимо учитывать ограничения модели, т.е. в каждой строке и столбце матрицы находится только один не нулевой элемент. Для соблюдения этого ограничения, после вычисления позиции единичного гена, достаточно корректировать ее сдвигая поочередно вправо и влево. Данная коррекция позиции называется случайной Л/ - мутацией хромосомы. Согласно введенного понятия мутации последняя хромосома индивидуума будет предопределяется предыдущими. Доказано утверждение, что предлагаемый алгоритм представим в каноническом виде. Канонический вид генетического алгоритма оперирует двоичными векторами-хромосомами, в нем используется одноточечный кроссовер, эффективность канонического вида алгоритма доказана в теореме о шимах Д.Холландом в 1972. Численные эксперименты тестирования предлагаемого генетического алгоритма подтверждают достоверность теоретических заключений.

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

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

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

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

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

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

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

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

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

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

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

Сппсок публикации:

1. Матвеев М.Г., Минаков C.B. Генетический алгоритм решения целочисленной задачи оптимального раскроя // Материалы докладов VII всероссийской научно-технической конференции. - Тамбов, 2004. - С. 273-275.

2. Минаков C.B. Генетический алгоритм в задачах целочисленного программирования // Сборник научных трудов / ВГТЛ. - Воронеж, 2004.-С. 214-215.

3. Минаков C.B. Ранжированный доступ к базам данных через Internet // Материалы XLI отчетной научной конференции / ВГТА. -Воронеж, 2003. - С. 77.

4. Минаков C.B. Проект «Коммунальные платежи» // Информатика : проблемы, методология, технологии ¡материалы III регион, науч.— метод, конф. - Воронеж, 2003. - С. 101-103.

5. Минаков C.B. Проект «Касса» // Информатика : проблемы, методология, технологии : Материалы IV регион, науч.-метод. конф. - Воронеж, 2004. - С. 176-178.

Каширина ИЛ., Минаков C.B. Система автоматического построения расписания учебных занятий // Математика. Экономика. Образование. Ряды Фурье и их приложения : тр. Рос. ассоциации «Женщины-математики». - Воронеж, 2002. - Т. 10. - С. 67-70. Минаков C.B. Задача о назначении и размещении структурированных объектов // Математические и инструментальные методы в экономике : сб. науч. тр./ ВГТА. -Воронеж, 2004. - С. 171-175.

Матвеев М.Г., Минаков C.B. Генетический алгоритм для решения квадратичной задачи о назначениях // Вестн. Воронеж, гос. ун-та. Сер. Физика, математика. - 2004.

Матвеев М.Г., Минаков C.B. Моделирование структур в задачах назначения // Теория конфликта и ее приложения : материалы III всерос. науч.-техн. конф. - Воронеж, 2004. - С. 357-361.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

1. Айгнер, М. Комбинаторная теория. - М.: Мир, 1982.

2. Александров, Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, тЗ (1998), Иркутск, с. 1720.

3. Александров, П. С. Введение в теорию множеств и общую топологию. -М.: Наука, 1977.

4. Ашманов, С.А. Линейное программирование. М.: Наука, 1981. С. 304.

5. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы.- М.: Мир, 1982.

6. Береснев, В. Л. Алгоритм неявного перебора для задачи типа размещения и стандартизации. В кн.: Управляемые системы. Вып. 12. Новосибирск. Ин-т математики Сиб. отд. АН СССР. 1974.

7. Береснев, В.Л. Об одном классе задач оптимизации параметров однородной технической системы. Управляемые системы. Вып. 9, 1971 г., Новосибирск, Ин-т математики Сиб. отд. АН СССР, с. 65-74.

8. Береснев, В.Л., Гимади, Э.Х., Дементьев, В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978 г.

9. Береснев В.Л., Гимади, Дементьев В.Т. Экстремальные задачи стандартизации, Новосибирск, 1978 г.

10. Ю.Беркович, М. М. Задачи стандартизации и некоторые методы их решения.- «Экономика и математические методы», 1969, т. 5, вып. 2.

11. Бертесекас, Д. Условная опимизация и методы множителей Лагранжа. — М.: Радио и связь. 1987.

12. Болтянский В. Г., Солтан П. С. Комбинаторная геометрия различных классов выпуклых множеств. Кишинев: Штииница, 1978.

13. Бохманн Д., Постхоф X. Двоичные динамические системы. Москва, 1986 г. с. 282-288.

14. Булавский В. А., Звягина Р. Л., Яковлева М. А. Численные методы линейного программирования. М.: Наука, 1977.

15. Васильев, Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1988.

16. Васильев, Ф. П. Численные методы теории экстремальных задач. М.: Наука, 1980.

17. Галеев Э.М., Тихомиров В.М. Оптимизация. Теория, примеры, задачи. Москва 2000 г., с. 122-142.

18. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

19. Гимади, Э.Х. Выбор оптимальных шкал в одном классе задач типа размещения, унификации и стандартизации. Управляемые системы. Вып. 6, 1970 г., Новосибирск, Ин-т математики Сиб. отд. АН СССР, с. 57-70.

20. Глушков, В. М. Введение в кибернетику. Киев. Изд-во АН СССР, 1964.

21. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер. 2. тб (1999), Л'я 1, с. 12-32.

22. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 249-252.

23. Горбачевская, Л.Е. Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода. // Дискретный анализ и исследование операций. 1998 г. Серия 2. Том 5, № 2. С. 20-33.

24. Горбачевская, Л.Е. Алгоритмы и сложность решения двухуровневых задач стандартизации с коррекцией дохода. // Дискретный анализ и исследование операций. 1998 г. Серия 2. Том 5, № 2. с. 20-33.

25. Гришухин, В. П. Алгоритмы ветвей и границ в задачах с булевыми переменными, оценка их эффективности. Экономика и мат. Методы, 1976, XII, №4.

26. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

27. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва, 1982 г.

28. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

29. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

30. Зойтендейк, Г. Методы возможных направлений. М.:Изд-во иностр. Лит., 1963.

31. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. — М.: Наука, 1974.

32. Карманов, В. Г. Математическое программирование. М.: Наука, 1985.

33. Карпов, Ю.Г. Теория автоматов. Москва, 2002 г. с. 96-110.

34. Каширина И.Л., Минаков С.В. Система автоматического построения расписания учебных занятий. // Труды российской ассоциации «Женщины-математики», Том 10, 2002 г.

35. Корбут А. А., Финкельштейн 10. Ю. Дискретное программирование. Москва, 1969.-368.

36. Корбут А.А., Сигал И.Х., Финкенштельн IO.IO. Метод ветвей и границ. -Math. Operations for Sch. Und Statist., Ser. Optimiz., 1977, 8, 2, c. 253280.

37. Кузин, JI.Т. Основы кибернетики. 1973 г. Том 1.

38. Ларин P.M., Пяткин Л. В. Двухуровневая задача о назначениях. // Дискретный анализ и исследование операций. 2001 г. Серия 2. Том 8, № 2, С. 42-51.

39. Ларин P.M., Пяткин А. В. Двухуровневая задача о назначениях. // Дискретный анализ и исследование операций. 2001 г. Серия 2. Том 8, № 2, с. 42-51.

40. Лесин В. В, Лисовец Ю. П. Основы методов оптимизации. М.: Изд-во МАИ, 1995.

41. Летова Т. А., Пантелеев А. В. Экстремум функций в примерах и задачах. -М.: Изд-во МАИ, 1998.

42. Магарил-Ильяев Г.Г., Тихомиров В. М., Выпуклый анализ и его приложения. М.: Эдиториал УРСС, 2000. Матем. Сборник. Т. 188, № 12, 1997.

43. Матвеев М.Г., Минаков C.B. VII Всероссийская научно-техническая конференция. Тамбов, 2004 г. с. 273-275.

44. Матвеев М.Г., Минаков C.B. Генетический алгоритм решения целочисленной задачи оптимального раскроя. // Материалы докладов VII всероссийской научно-технической конференции. Тамбов, 2004 г.

45. Мелихов А. Н., Бернштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

46. Месарович М., Такахара Я. Общая теория систем: математические основы. 1978 г.

47. Мину М. Математическое программирование. М.: Наука, 1990.

48. Михалевич В. С, Кукса А. И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. Москва, 1983.-208 с.

49. Моисеев, H. I I. Математические задачи системного анализа. М.: Наука, 1981.

50. Мухачева Э. Л., Мухачева Л. С., Валеева Л. Ф., Картак В. М. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур. // Приложение к журналу "Информационные технологии" №5, 2004.

51. Олешко М. В., Шило В. П. Алгоритм для решения задач целочисленного программирования с булевыми переменными, использующий вероятностные оценки. Киев: Ин-т кибернетики АН УССР, 1982.

52. Петренко, А. И. Основы автоматизированного проектирования. Киев: Техника, 1982.

53. Поляк, Б. Т. Введение в оптимизацию. М.: Наука, 1983.

54. Поляк, В. Т. Введение в оптимизацию. М.: Наука, 1983.

55. Растригин, Л. А. Вычислительные системы и сети как объекты применения случайного поиска. В кн.: Пробл. случайн. поиска, 1983, вып. 10.

56. Растригин, Л. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3-16.

57. Реклейтис Г., Рейвиндран А., Рагедел К. Оптимизация в технике. — М.: Мир, 1986.

58. Рокафеллар, Р. Выпуклый анализ. М.: Мир, 1973.

59. Романовский, И. В. Алгоритмы решения экстремальных задач. М.: Наука, 1977.

60. Сергеев, С.И. Автоматика и телемеханника. № 8, 1999. с. 127-144.6265,6661,68,69,70,71,72,73,74,75,

61. Сергиенко, И. В. О некоторых направлениях в развитии методов дискретной оптимизации и их программного обеспечения. -Кибернетика, 1982, Jtè 6.

62. Сергиенко И. В., Каспшицкая М. Ф. Модели и методы решения на ЭВМкомбинаторных задач оптимизации. Киев, 1981. 288 с.

63. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методырешения дискретных задач оптимизации. Киев, 1980. 276 с.

64. Сергиенко, И.В. Математические модели и методы решения задачдискретной оптимизации. Киев, 1985 г. с. 63-68.

65. Скорняков, J1. А. Элементы теории структур. 2-е изд. М.: Наука, 1982.

66. Стоян Ю. Г., Соколовский В. 3. Решение некоторыхмногоэкстремальных задач методом сужающихся окрестностей. — Киев,1980.

67. Taxa, X. Введение в исследование операций: В 2-х томах. Том 1, пер.с англ. Москва. -479 с.

68. Трубин, В. А. О некоторых задачах типа размещения. Применение мат. методов в экон. исслед. и планир., 1968, ЛЬ 1.

69. Цурков, В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.

70. Червак, 10. 10. Дискретное программирование, геометрические методы построения отсечений. Экономика и мат. методы, 1974, № 5.

71. Чуев 10. В., Погожев И. Б. Иерархическая система задач оптимизации. -В кн.: Исследование операций : Методол. Аспекты. М. : Наука, 1972.

72. Эрдэш М., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976.

73. Adams W.P., Johnson Т.А. Improved linear programming-based lower bounds for the quadratic assignment problem, Quadratic assignment and related problems, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 1994, p. 43-75.

74. Agganval С. C., Orlin J. В., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225-234.

75. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29-49.

76. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107-122.

77. Boese K. D., Kahng А. В., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. vl6 (1994), N2, pp 101-114.

78. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

79. Cooper M. W. Postoptimality analyses in nonlinear integer programming the right-hand side case. Nav. Res. Log. Quart., 1981, 28, N 2.

80. Cornuejols G., Fisher M.L., Nemhauser G.L. Location of bank accounts to optimize float. Management Science. v22, 1977, p. 789-810.

81. Darrel Whitley, "A Genetic Algorithm Tutorial", 1993.

82. David E. Goldberg, Kumara Sastry "A Practical Schema Theorem for Genetic Algorithm Design and Tuning", 2001.

83. Eiben A. E., Raue P. E., Ruttkay Zs. Genetic Algorithms with multiparent recombination. Parallel Problem Solving from Nature III. Berlin: Springer Verlag, (LNCS), v866 (1994), pp 78-87.

84. Eremeev, A. V. A genetic algorithm with a non-binary representation for the set covering problem. Operations Research Proceedings 1998. Berlin: Springer Verlag. 1999. pp 175-181.

85. Garfinkel R. S., Nemhauser G. L. Integer programming. New York : Wiley, 1972.

86. Geoffrion A.M., Marsten R.E. Integer programming: a framework and state of the art survey. Manag. Sci., 1972, 18, N 9, p. 465-491.

87. Goldberg, D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

88. Hammer P. L., Rudeanu S., Pseudo-Boolean programming. "Operat. Res.", 1969, v. 17, N2.

89. Holland, J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

90. Holland, J.H. Adaptation in natural and artificial systems. Ann Arbor: Univ. of Michigan Press, 1975, 183 p.

91. Horst R., Pardalos P.M. Handbook of global optimization, Kluwer, 1995.

92. Johnson D. S., McGeoch L. A. The traveling salesman problem: a case study. Local search in combinatorial optimization. Chichester: Wiley, pp 215-310.

93. Juel, H. Bounds in the generalized weber problem under locational uncertainty. Oper. Res., 1981, 29, N 6.

94. Kaufmann L., Broeckx F. An algorithm for the quadratic assignment problem using Benders'decompositions, European Journal of Operational Research, 1978, p. 204-211.

95. Khumawala, B.M. An Efficient Branch-Bound Algorithm for the Warehouse Location Problem. Management Science. vl8, 1972, p. 718-731.

96. Kirkpatrick S., Toulouse G. Configuration space analysis of traveling salesman problems. J. de Phys. v46 (1985), pp 1277-1292.

97. Krarup J., Pruzan P.M. The simple plant location problem: Survey and synthesis. European Journal of Operational Research. vl2, 1983, p. 36-81.

98. Land A. H., Doig A. G. An automatic methods of solving discrete programming problems. "Econometrica", 1960, v.28, N 3.

99. Lawler, E.L. The quadratic assignment problem. Management Science, 1963, p. 586-599.

100. Levin, L. A. Universal sorting problems. Probl. Inform. Trans., 1973, N 9.

101. Mirchandani P. B., Francis R. L. Discrete Location Theory. New York: John Wiley and Sons, 1990.

102. Mirchandani P.B., Francis R.L. Discrete Location Theory. John Wiley & Sons, 1990. (32)

103. Muhlenbein, II. Parallel genetic algorithm, population dynamics and combinatorial optimization. Proc. Third Inter. Conf. Genetic Alg. San Mateo: Morgan Kaufman, 1989. pp 416-421.

104. Mutten, L. G. Branch-and-Bound methods: general formulation and properties. "Operat.Res.", 1970, v.18,N 1.

105. Rechenberg, I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der Biologischen Information, Freiburg: Fromman, 1973.

106. Robin, B. "Genetic Algorithm Tutorial. 4.1 Mathematical foundations", 1999.

107. Schwefel, H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.