Разработка и реализация гибридного генетического алгоритма для автоматизированного проектирования маршрутов обхода геометрических объектов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Пушкарёва, Галина Витальевна

• Пушкарёва, Галина Витальевна
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Пушкарёва, Галина Витальевна

Введение

1. Постановка задачи и метод решения

1.1. Содержание проблемы оптимизации траектории движения исполнительного инструмента

1.2. Методы решения оптимизационных задач маршрутизации

1.3. Выбор метода решения. Методология генетического программирования

1.4. Выводы 35 2. Гибридный генетический алгоритм

2.1. Общая схема разработанного гибридного генетического алгоритма

2.2. Определение вложенности контуров

2.3. Характеристика применяемых генетических операторов

2.3.1. Оператор скрещивания

2.3.2. Оператор мутации

2.3.3. Оператор селекции

2.4. Целенаправленное изменение хромосом

2.4.1. Оператор инверсии

2.4.2. Оператор разнообразия

2.5. Оценка временной сложности гибридного генетического алгоритма

2.6. Выводы 70 3. Исследование эффективности гибридного генетического алгоритма

3.1. Сравнительный анализ разработанного алгоритма с другими методами

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

3.3. Исследование влияния параметров генетического алгоритма на эффективность поиска

3.3.1. Число генераций и количество попыток

3.3.2. Размер популяции и степень её обновления

3.3.3. Вероятности скрещивания и мутации

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

3.5. Выводы 109 4. Реализация гибридного генетического алгоритма

4.1. Программная реализация разработанного алгоритма и её связь с графической БД системы AutoCAD

4.2. Интерфейс пользователя с программой

4.3. Тестовые примеры и инструкция пользователю

4.4. Выводы 126 Заключение 127 Список использованной литературы 130 Приложение

Введение диссертации (часть автореферата) на тему «Разработка и реализация гибридного генетического алгоритма для автоматизированного проектирования маршрутов обхода геометрических объектов»

Актуальность проблемы. Содержательная сторона рассматриваемой задачи связана с решением проблемы автоматизации сложного и трудоемкого процесса генерации управляющих программ для станков ЧПУ тепловой резки металла, которые являются результатом сквозного цикла обработки информации от чертежа детали до программ ее изготовления в NC-кодах конкретного оборудования. Известные программные комплексы автоматизированного проектирования управляющих программ в значительной мере используют элементы интерактивной графики, в то время как более перспективным представляется полная автоматизация проектных решений на основе математических моделей и оптимизационных методов [82-84].

Траектория движения режущего инструмента состоит из следующих элементов [80]:

1) внешних контуров вырезаемых деталей;

2) внутренних контуров;

3) траекторий, связывающих смежные контуры (вырезаемые с одной врезки);

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

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

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

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

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

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

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

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

Для нахождения приближённого решения задачи в работе было решено разработать гибридный генетический алгоритм, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению. Генетические алгоритмы (ГА) успешно используются при проектировании СБИС в задачах размещения [92,99], в задачах двумерной упаковки [52], при решении комбинаторно-логических задач [102], задач канальной трассировки [93,103,104,106], задачи распределения инвестиций и других экономических задач [70]. Известны научные работы JI.A. Растригина по направлению генетических алгоритмов [67].

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

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

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

- развитие современных отечественных систем сквозного проектирования.

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

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

2) специализация гибридного генетического алгоритма для решения задачи маршрутизации:

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

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

- модификация генетических операторов для решения задачи маршрутизации;

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

3) программное приложение системы AutoCAD, реализующее гибридный генетический алгоритм;

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

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

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

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

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

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

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

- повысить коэффициент использования оборудования в среднем на 510%;

- снизить энергетические затраты на резку металла;

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

- сократить в несколько раз сроки проектирования;

- улучшить качество проектных решений.

Программная реализация гибридного генетического алгоритма показала значительные преимущества перед классическим ГА и используемыми на практике эвристическими методами для широкого класса задач маршрутизации. Предложенный гибридный генетический алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (без целенаправленного изменения хромосом), на 30% лучше алгоритма «ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения».

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

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

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

1) Региональная научно-практическая конференция «Вузы Сибири и Дальнего Востока — Транссибу», 27-29 ноября 2002 г., Сибирский государственный университет путей сообщения, Новосибирск, Россия;

2) Региональная научная конференция студентов, аспирантов и молодых учёных «Наука. Техника. Инновации», 5-8 декабря 2002 г., Новосибирский государственный технический университет, Новосибирск, Россия;

3) 7-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», декабрь 2002 г., МВВО АТН РФ, Н. Новгород, Россия;

4) 8-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», 18 апреля 2003 г., МВВО АТН РФ, Н. Новгород, Россия;

5) Международная научно-техническая конференция «Информационные системы и технологии», 22-25 апреля 2003 г., Новосибирский государственный технический университет, Новосибирск, Россия;

6) 6th International Conference in Computer Graphics and Artificial Intelligence (3IA'2003), 14-15 of May, 2003, Limoges, France;

7) 1-ая Всероссийская научно-практическая конференция «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках», 23-24 октября 2003 г., ФГУП ЦНИИ технологии судостроения, Санкт-Петербург, Россия;

8) Научно-практическая конференция «Дни науки в НГТУ», 7 марта 2004 г., Новосибирский государственный технический университет, Новосибирск, Россия;

9) 8th Korea-Russia International Symposium on Science and Technology (KORUS 2004), June 26 — July 3, 2004, at Tomsk Polytechnic University, Russia.

Работа выполнена при поддержке гранта МО РФ (тема — Т02-10.4

3668).

Публикации. По теме диссертации опубликовано 9 работ объёмом 50 страниц (2,5 печатных листа) [61-66, 81,96, 97].

Содержание диссертационной работы по главам:

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

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

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

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

Заключение диссертации по теме «Теоретические основы информатики», Пушкарёва, Галина Витальевна

Результаты исследования, содержащиеся в этой главе, были опубликованы в [63, 64, 81, 96, 97].

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан гибридный генетический алгоритм.

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

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

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

2.4. Разработано целенаправленное изменение хромосом, улучшающее каждое решение задачи. Оно реализовано посредством оператора инверсии и оператора разнообразия. Оператор инверсии исключает пересечения в маршруте, учитывая матрицу структуры технологической карты. Оператор разнообразия улучшает качество решения, используя метод циклического координатного спуска, и минимизирует количество врезок. 2.5. Проведена оценка временной сложности гибридного генетического алгоритма, которая составила 0(п2).

3. Исследована эффективность гибридного генетического алгоритма. Предложенный алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (без целенаправленного изменения хромосом), на 30% лучше алгоритма «ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения». Рассмотрен процесс получения эффективного решения в ходе итерационного поиска посредством гибридного ГА. Исследовано влияние параметров расчёта на скорость и устойчивость поиска эффективного решения. Даны рекомендации по выбору значений этих параметров. Отмечены перспективные направления исследования с целью повышения эффективности ГА, такие как распараллеливание процесса поиска и построение адаптивных многоуровневых генетических алгоритмов.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Пушкарёва, Галина Витальевна, 2004 год

1. Автоматизация технологической подготовки заготовительного производства / Под ред. Г.П. Гырдымова. Ленинград: Машиностроение, 1990. - 350с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. -М.: Наука, 1987. -247 с.

3. Альбрехт Э.Г. и др. Методы оптимизации. Введение в теорию решения экстремальных задач: Учебное пособие. — Екатеринбург: Уральский гос. ун-т, 1993.-165 с.

4. Аттетков А.В. и др. Методы оптимизации: Учебник для втузов. — М.: МГТУ им. Н.Э. Баумана, 2001. 439 с.

5. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988.-215 с.

6. Банди Б. Основы линейного программирования: Пер. с англ. — М.: Радио и связь, 1989. 176 с.

7. Банк Б. И др. Математическая оптимизация: вопросы разрешимости и устойчивости. М.: МГУ, 1986. - 216 с.

8. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Наука, 1989. - 160 с.

9. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. - 189 с.

10. Васильев О.В. Лекции по методам оптимизации: Учебное пособие. Иркутск: Изд-во Иркутского ун-та, 1994. - 340 с.

11. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002. — 823 с.

12. Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Применение метода "Поиск с запретами" (TS) для решения задач нерегулярного раскроя-упаковки // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2000. - С. 123-127.

13. Владимирова Н.Ю., Сигал И.Х. Параметризация при решении некоторых классов задач дискретной оптимизации большой размерности. М.: ВЦ РАН,2001.-79 с.

14. Габасов Р.Ф. и др. Конструктивные методы оптимизации: В 5 ч. — Минск: Университетское, 1998.

15. Габасов Р.Ф., Кириллова Ф.М. Методы оптимизации: Учебное пособие. -Мн.:БГУ, 1981.-350 с.

16. Галеев Э.М. Оптимизация: Теория. Примеры. Задачи. М.: УРСС, 2002. -302 с.

17. Гилл Ф.И. др. Практическая оптимизация: Пер. с англ. М.: Мир, 1985. -509 с.

18. Глебов Н.И. Об условиях разрешимости оптимизационных задач жадным алгоритмом // Дискретный анализ и исследование операций. Июль-декабрь2002. Серия 2. -Том 9, №2. - С.3-12.

19. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций. Июль-декабрь 2002. - Серия 2. - Том 9, №2. - С. 13-30.

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

21. Давиденко В.Н., Курейчик В.М. Генетический алгоритм для трассировки двухслойных каналов // Автоматизация проектирования. 1999. №1. - С. 3441.

22. Даффин Р. и др. Геометрическое программирование: Пер. с англ. М.: Мир, 1972.-311 с.

23. Дегтярев Ю.И. Методы оптимизации. М.: Сов. радио, 1980. - 320 с.

24. Дробязко О.Н. Оптимизация в САПР, часть 1: Учебное пособие. Барнаул: АлтГТУ, 2000. - 70 с.

25. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. -М.: Наука, 1982. 432 с.

26. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. Январь-июнь 2000. - Серия 2. - Том 7, №1. -С. 47-60.

27. Ериклинцев В.В., Фридман С.С., Розенфельд В.Х. Оптимизация раскроя проката. М.: Металлургия, 1984. - 362 с.

28. Ерош И.Л. Дискретная математика. Комбинаторика: Учебное пособие. -СПб.: СПбГУАП, 2001. 35 с.

29. Жадан В.Г. Дополнительные главы методов оптимизации: Учебное пособие для вузов. М.: МФТИ, 2002. - 72 с.

30. Жадан В.Г. Численные методы линейного и нелинейного программирования: вспомогательные функции в условной оптимизации. М.: ВЦ РАН, 2002. -159 с.

31. Жак С.В. О методах решения задач, сочетающих эвристику и случайный выбор // Кибернетика. 1972. №1. - С.119-121.

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

33. Зайцева Е.Н., Станкевич Ю.А. Некоторые современные методы решения оптимизационных задач.http://bsuinet 125 .bsu.unibel.by/conferences/nite/doklad 13 .html

34. Измаилов А.Ф. Численные методы оптимизации: Учебное пособие. М.: Физматлит, 2003. - 300 с.

35. Канторович J1.B., Залгаллер В. А. Рациональный раскрой промышленных материалов. Новосибирск: Наука, 1971.- 298 с.

36. Карапетян Г.К., Шульденов Г.А. Однопроходный алгоритм линейной аппроксимации последовательности точек на плоскости // Кибернетика. 1984. №1. - С. 114-117.

37. Карманов В.Г. Математическое программирование: Учебное пособие. — М.: Физматлит, 2000. 263 с.

38. Ковалёв М.М. Дискретная оптимизация. Целочисленное программирование. Минск: БГУ, 1977. - 191 с.

39. Комплекс программ "Маршрут" (руководство пользователя) / Моск. гос. техн. ун-т им. Н.Э.Баумана, каф. Системы автоматизированного проектирования. http://vikt.mega.ru/route.html.

40. Коннов В.В. и др. Геометрическая теория графов. М.: Народное образование, 1999.-240 с.

41. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2000. - 352 с.

42. Костюк Ю.Л., Жихарев С.А. Эффективный алгоритм приближённого решения метрической задачи коммивояжера // Дискретный анализ и исследование операций. Январь-июнь 2000. - Серия 2. - Том 7, №1. - С. 65-74.

43. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Январь-июнь 2003. - Серия 2. - Том 10, №1. - С. 11-43.

44. Красовская М.А. Методы и алгоритмы нелинейного программирования в АСУ: Учебное пособие. М.: МАИ, 1994. - 40 с.

45. Кузюрин Н.Н. Вероятностные приближённые алгоритмы в дискретной оптимизации И Дискретный анализ и исследование операций. Июль-декабрь 2002. - Серия 2. - Том 9, №2. - С. 97-114.

46. Курейчик В.М. Генетические алгоритмы и их применение в САПР, интеллектуальные САПР // Межведомственный тематический научный сборник. -Таганрог, 1995. С. 7-11.

47. Лбов Г.С. Выбор эффективной системы зависимых признаков // Сборник трудов Института математики СО АН СССР. 1965. Выпуск 19. - С.21-34.

48. Лихтенштейн В.Е. Модели дискретного программирования. М.: Наука, 1971.-239 с.

49. Мастяева И.Н. Методы оптимизации: Текст лекций. М.: МЭСИ, 1990. -66с.

50. Медынский М.М., Антоний Е.В. Численные методы нелинейной оптимизации: алгоритмы и программы: Учебное пособие. М.: МАИ, 2003. - 189 с.

51. Мудров В.И. Задача о коммивояжере. М.: Знание, 1969. - 62 с.

52. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. М.: Машиностроение, 1984. - 176 с.

53. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998. - 217с.

54. Напалков А.В. Эвристическое программирование: Учебное пособие. Ростов н/Д: Изд-во Ростовского ун-та, 1971. - 127 с.

55. Ногин В.Д., Протодьяконов И.О., Евлампиев И.И. Основы теории оптимизации: Учебное пособие / Под ред. И.О. Протодьяконова. М.: Высш. шк., 1986.-384 с.

56. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.

57. Норенков И.П. Эвристики и их комбинация в генетических методах дискретной оптимизации // Информационные технологии. 1999. №1. - С. 2-7.

58. Полещук Н.Н. VisualLISP и секреты адаптации AutoCAD. СПб.: БХВ-Петербург, 2001. - 576 с.

59. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

60. Пушкарёва Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ // Сборник научных трудов НГТУ. 2004. №1. - С. 67-72.

61. Пушкарёва Г.В. Оптимизация траектории движения исполнительного инструмента тепловой резки металла на оборудовании с ЧПУ // Материалы докладов региональной научной конференции «Наука. Техника. Инновации». -Новосибирск: НГТУ, 2002. С.183-185.

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

63. Редько В.Г. Эволюционная кибернетика: Тезисы курса лекций / Институт прикладной математики им. В.М. Келдыша РАН. -http://www.keldvsh.ru/BioCvber/Lectures.html.

64. Редько В.Г., Дябин М.И., Елагин В.М., Карпинский Н.Г., Половянюк А.И., Сереченко В.А., Ургант О.В. К микроэлектронной реализации эволюционного оптимизатора // Микроэлектроника. 1995. №3. - С.207-210.

65. Романов В.П. Интеллектуальные информационные системы в экономике: Учебное пособие / Под ред. Н.П. Тихомирова. М.: Экзамен, 2003. - 496 с.

66. Рубиштейн М.И. Задачи и методы комбинаторного программирования. -М.: Наука, 1976.

67. Сигал И.Х. Последовательность применения алгоритмов приближённого решения в комбинированном алгоритме решения задачи коммивояжера // Журнал вычислительной математики и математической физики. 1989. Т.29. №11. — С. 1714-1721.

68. Сигал И.Х. Приближённые методы и алгоритмы в дискретной оптимизации: Учебное пособие. М.: МИИТ, 2000. - 107 с.

69. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. -М.: Физматлит, 2002. 237 с.

70. Слэйк Дж.Р. Искусственный интеллект. Подход на основе эвристического программирования: Пер. с англ. -М.: Мир, 1973. 319 с.

71. Смирнов А.П. Методы оптимизации: Учебное пособие. М.: МИСиС, 2002.- 134 с.

72. Сухарев А.Г. Оптимальный поиск экстремума. М.: МГУ, 1975. - 100 с.

73. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986. 328 с.

74. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наук, думка, 1986. - 286 с.

75. Фроловский В.Д. Моделирование и алгоритмизация процессов геометрического проектирования изделий из листового материала: Диссертация на соискание уч. степени д.т.н. Новосибирск, 2001. 340с.

76. Фроловский В.Д., Эстрайх И.В. Об одной задаче оптимизации движения режущего инструмента при раскрое листового проката // Машинные методы оптимизации, моделирования и планирования эксперимента. Новосибирск: НЭТИ, 1988.-С. 60-65.

77. Фроловский В.Д., Эстрайх И.В., Петров С.В. Автоматизация проектирования процессов тепловой резки металла на оборудовании с ЧПУ // Автоматизация проектирования и производства в электромашиностроении. М., 1989. — С. 86-93.

78. Хахулин Г.Ф. Постановки и методы решения задач дискретного программирования: Учебное пособие. М.: Изд-во МАИ, 1992. - 59 с.

79. Хохлюк В.И. Задачи целочисленной оптимизации. Алгоритмы: Учебное пособие. Новосибирск: НГУ, 1980. - 91 с.

80. Шабунин М.И., Шеверов В.Г. Некоторые вопросы математического программирования. Дискретное программирование: Учебное пособие. — Долгопрудный, 1980. 102 с.

81. Эвристические алгоритмы оптимизации / Сборник статей. Ярославль, 1975.-217 с.

82. Bard J.F. and Feo N.F. Operations Sequencing in Discrete Parts Manufacturing // Management Science.- 1989.- 35:249-255.

83. Bellman R. Dynamic Programming // Princeton University Press, USA, 1957.

84. Bellman R.E. and Dreyfus S.E. Applied Dynamic Programming // Princeton University Press, USA, 1962.

85. Cohoon J.P. and Paris W.D. Genetic placement // IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst.- 1987.- Vol.6.- 6:956-964.

86. Davidenko V.N., Kureichik V.M., and Miagkikh V.V. Genetic Algorithm for Restrictive Channel Routing Problem // Proc. of the 7th International Conf. on Genetic Algorithms.- M. Kaufmann Publisher.- San Mateo, California, 1997.- P.636-642.

87. Dereli T. and Filiz I.H. Optimizing Cutting Parameters in Process Planning of Prismatic Parts by Using Genetic Algorithms // International Journal of Production Research.- 2001.- Vol. 39.- 15:3303-3328.

88. Feo N.F. and Bard J.F. The Cutting Path and Tool Selection Problem in Computer-Aided Process Planning // Journal of Manufacturing Systems.- 1989.- 8:17-26.

89. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning // Adison Wesley, Reading, MA, 1989.

90. Goodman E., Tetelbaum A. and Kureichik V. A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems // Case Center Technical Report № 940702.- Michigan State University, 1994.

91. Hart J.P. and Shogan A.W. Semi-Greedy Heuristica: An Empirical Study // Operation Research Letters.- 1987.- 6:107-114.

92. Holland J. Adaptation in Natural and Artificial Systems // University of Michigan Press Ann Arbor, USA, 1975.

93. Kureichik V.M. et all. Some New Features in Genetic Solution of the Traveling Salesman Problem // Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control.- Plymouth, UK, 1996.- P. 294-296.

94. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits // Evolutionary Computation.- MIT, 1994, 1(4). P. 293-311.

95. Liu X., Sakamoto A., Shimamoto T. Restrictive Channel Routing with Evolution Programs // Trans. IEICE.- 1993.- Vol. E76-A.- 10:1738-1745.

96. O'Rourke J. and Rippel J. Two Segment Classes with Hamiltonian Visibility Graphs / Перевод М.Ю. Ратаева // Вычислительная геометрия. 1994. №4. - С. 209-218.

97. Rahmani А.Т. and Ono N. A Genetic Algorithm for Channel Routing Problem // Proc. 5th Intl. Conf. on Gas.- 1993.- P. 494-498.