Структурное моделирование в классе задач о назначении и исследование генетического метода решения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Минаков, Сергей Владимирович

• Минаков, Сергей Владимирович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Минаков, Сергей Владимирович

ВВЕДЕНИЕ.

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

Список литературы диссертационного исследования кандидат физико-математических наук Минаков, Сергей Владимирович, 2004 год

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.