Модифицированные эволюционные алгоритмы и программные решения задачи ортогональной упаковки объектов (1095065)

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

Текст из файла

На правах рукописиЧ ека н ин В л ад ис л ав А л екс а н д р о ви чМОДИФИЦИРОВАННЫЕ ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ИПРОГРАММНЫЕ РЕШЕНИЯ ЗАДАЧИОРТОГОНАЛЬНОЙ УПАКОВКИ ОБЪЕКТОВ05.13.17 – Теоретические основы информатикиАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата технических наукМосква – 2011Работа выполнена в государственном образовательном учреждениивысшего профессионального образования «Московский государственныйтехнологический университет «Станкин» на кафедре «Управление иинформатика в технических системах»Научный руководитель:доктор технических наук, профессорКовшов Евгений ЕвгеньевичОфициальные оппоненты:доктор технических наук, доцентДемидова Лилия Анатольевнадоктор технических наук, доцентТолчеев Владимир ОлеговичВедущая организация:ГОУ ВПО «Московский государственныйуниверситет приборостроения иинформатики»Защита состоится «31» марта 2011 г.

в 1400 часов на заседаниидиссертационного совета Д 212.147.03 при Московском государственномуниверситете печати (127550, Москва, ул. Прянишникова, 2а).С диссертацией можно ознакомиться в библиотеке«Московский государственный университет печати» (МГУП).ГОУВПОАвтореферат разослан «26» февраля 2011 г.Учёный секретарьдиссертационного советад.т.н., профессорАгеев В.Н.Общая характеристика работыАктуальность работы. Задачи упаковки представляют собой важныйприкладной раздел комбинаторной оптимизации.

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

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

Разработке методов решениязадач ортогональной упаковки посвящены работы, как отечественных авторов(А.С. Филиппова, А.Ф. Валеева, Ю.Г. Стоян, И.В. Романовский, В.М. Картак,Ю.И. Валиахметова,И.П. Норенков,Р.Р. Ширгазин,А.В. Чиглинцев,В.В. Бухвалова, А.Р. Усманова, М.А. Смагин и др.), так и зарубежных(П. Гилмори,Р. Гомори,И.

Терно,Г. Шайтхауэр,Э. Фолкенауэр,А. Бортфельдт, Х. Дикхофф, С. Мартелло, Д. Виго, А. Лоди, Е. Хоппер и др).Значительный вклад в развитие методов решения задач упаковки внеслаотечественная научная школа Э.А. Мухачевой. Проблемы эволюционногомоделирования в задачах упаковки изучены в работах таких исследователей,какВ.М.

Курейчик,В.В. Курейчик,В.В. Емельянов,И.П. Норенков,4Д.И. Батищев, Э. Фолкенауэр и других отечественных и зарубежныхисследователей.Давая, безусловно, положительную оценку результатам работы всехвышеперечисленных исследователей, отметим наличие ещё нерешённыхпроблем, среди которых – выбор эффективной модели представленияортогональных объектов в контейнерах; разработка модели, выполняющейвыбор наиболее подходящей области контейнера для каждого размещаемогообъекта; разработка унифицированной модели решения задач упаковкипроизвольной размерности.Целью работы является повышение эффективности решения задачортогональной упаковки различной размерности.Для достижения указанной цели в работе поставлены следующиенаучные задачи:1.

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

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

Разработаны модель «виртуальные объекты» для конструированияортогональной упаковки и унифицированный декодер строки решениядля ортогональных объектов произвольной размерности.2. Определенкритерийостановаэволюционногоалгоритма,отслеживающий попадание популяции решений в локальныеоптимумы целевой функции.53. Разработаны эвристики размещения объектов в контейнерах длямультиметодного генетического алгоритма.4. Разработанаинформационнаямодель,обеспечивающаяунифицированный подход к решению задач упаковки произвольнойразмерности.Основные положения, выносимые на защиту:1. Модель «виртуальные объекты» быстрого конструированияортогональной упаковки и унифицированный для ортогональныхобъектов различной размерности декодер строки решения.2.

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

Результаты диссертационной работывнедрены в учебный процесс ГОУ ВПО МГТУ «Станкин» и в настоящее времяиспользуются при подготовке бакалавров по направлению 080800.62«Прикладная информатика», магистрантов по магистерским программам:220200.68-20 «Человеко-машинные системы управления» и 230100.68-01«Теоретическая информатика». Материалы диссертационной работыиспользованы в качестве методологической основы при разработкеобщеуниверситетских курсов лекций и практических занятий по дисциплинам«Информатика» и специальным дисциплинам магистерской подготовки:«Интеллектуальныесистемыобработкиинформации»,«Технологияпрограммирования в интеллектуальных системах управления».Определена целесообразность применения разработанных методик присоздании прикладного программного обеспечения в малом инновационномпредприятии ООО «Компьютерные системы и технологии» (г.

Характеристики

Тип файла PDF

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

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

Список файлов диссертации