Найти

Результаты поиска

• НОВЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ПУТИ ОБХОДА КОНЕЧНОГО МНОЖЕСТВА НЕПЕРЕСЕКАЮЩИХСЯ КОНТУРОВ НА ПЛОСКОСТИ

  А. А. Петунин, Е.Г. Полищук , С. С. Уколов

  2021-04-04

  Аннотация ▼

  Рассматривается проблема маршрутизации режущего инструмента машин листо-
  вой резки с ЧПУ для случая, когда точки врезки расположены на границах деталей, ограни-
  ченных отрезками прямых и дугами окружностей, при этом используется техника непрерывной резки (CCP), т.е. каждый контур вырезается целиком, но не используется предва-
  рительная дискретизация, то есть резка может начинаться с любой точки контура. Об-
  щая задача поиска оптимального маршрута в этом случае сводится к минимизации длины
  холостого хода. Показано, что она эквивалентна поиску кратчайшей ломаной с вершинами,
  расположенными на контурах. Предложен новый эвристический алгоритм построения
  такой ломаной для заранее заданного порядка обхода контуров. Показано, что получаю-
  щееся решение представляет собой локальный минимум. Описаны некоторые достаточ-
  ные условия, того, что решение является также глобальным минимумом, которые легко
  проверяются численно, а некоторые даже визуально. Описана методика автоматического
  учёта ограничений предшествования для практически важного случая наличия вложенных
  контуров, возникающих как за счёт отверстий в деталях, так и за счёт расположения
  мелких деталей в отверстиях крупных. При этом происходит также уменьшение размер-
  ности задачи, что положительно сказывается на времени оптимизации, особенно дис-
  кретной. Предложен эвристический алгоритм выбора порядка обхода контуров на основе
  метода переменных окрестностей (VNS). Описаны альтернативные подходы применения
  других методов дискретной оптимизации совместно с предложенным алгоритмом по-
  строения кратчайшей ломаной для решения полной задачи непрерывной резки и возникаю-
  щие при этом сложности как теоретического, так и практического характера. Описано
  обобщение задачи непрерывной резки до более широкого класс задач сегментной резки и
  обобщённой сегментной резки, что позволяет продвинуться в решении общей задачи пре-
  рывистой резки. Описана схема применения предложенного алгоритма для решения задач
  сегментной и обобщённой сегментной резки. Приведены некоторые результаты численных
  экспериментов в сравнении с точным решением задачи для дискретной модели GTSP.

• ГИБРИДНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ

  Л. А. Гладков, Н.В. Гладкова , М. Д. Ясир

  2021-11-14

  Аннотация ▼

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

• ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

  Б.К. Лебедев , О.Б. Лебедев , Е.О. Лебедева

  2022-11-01

  Аннотация ▼

  Рассматривается эволюционный популяционный метод решения транспортной за-
  дачи на основе метаэвристики кристаллизации россыпи альтернатив. Исследуется за-
  крытая (или сбалансированная) модель транспортной задачи: сумма груза у поставщиков
  равно общей сумме потребностей в пунктах назначения. Цель оптимизации – минимизация
  стоимости (достижение минимума затрат на перевозку) или расстояний и критерий вре-
  мени (затрачивается минимум времени на перевозку). В основу метаэвристики кристалли-
  зации россыпи альтернатив положена стратегия, основанная на запоминании и повторе-
  нии прошлых успехов. Стратегия делает упор на «коллективную память», под которой
  подразумевается любой вид информации, которая отражает прошлую историю развития
  и хранится независимо от индивидуумов. В качестве кода решения транспортной задачи
  рассматривается упорядоченная последовательность Dk маршрутов. Объектами являют-
  ся маршруты, альтернативами – множество позиций P в списке, где np – число позиций в
  списке Dк. Множество объектов Dк соответствует множеству всех маршрутов. Множе-
  ство альтернативных состояний P объекта соответствует множеству альтернативных
  вариантов размещения объекта списке Dк. Работа популяционного эволюционного алго-
  ритма кристаллизации россыпи альтернатив опирается на коллективную эволюционную
  память, называемую россыпью альтернатив. Под россыпью альтернатив решения в рабо-
  те называется структура данных, используемая в качестве коллективной эволюционной
  памяти, несущая информацию о решении, включающую сведения о реализованных альтер-
  нативах агентов в данном решении и о полезности решения. Разработан конструктивный
  алгоритм формирования опорного плана путем декодирования списка Dк. На каждом шаге
  t решается задача выбора очередного в последовательности Dк маршрута и определения
  количества груза, перевозимого из пункта отправления Ai в пункт назначения Bj по этому
  маршруту. Разработанный алгоритм является популяционным, реализующим стратегию
  случайного направленного поиска. Каждый агент является кодом некоторого решения
  транспортной задачи. На первом этапе каждой итерации l конструктивным алгоритмом
  на базе интегральной россыпи альтернатив формируется nk кодов решений
  Dk.Формирование каждого кода решения Dk выполняется последовательно по шагам путем
  последовательного выбора объекта и позиции. Для построенного кода решения Dk рассчи-
  тывается оценка решения ξk и оценка полезности δk. Формируется индивидуальная рос-
  сыпь альтернатив Rk и переход к построению следующего кода решения.
  На втором этапе итерации производится суммирования интегральной россыпи альтерна-
  тив, сформированной на предыдущих итерациях от l до (l-1), cо всеми индивидуальными
  россыпями альтернатив, сформированных на итерации l. На третьем этапе итерации l
  производится снижение всех интегральных оценок полезности r*αβ интегральной россыпи
  альтернатив R*(l) на величину δ*. Алгоритм решения транспортной задачи был реализован
  на языке С++ в среде Windows. Сравнение значений критерия, на тестовых примерах, сизвестным оптимумом показало, что у 90% примеров полученное решение было оптималь-
  ным, у 2% примеров решения были на 5% хуже, а у 8% примеров решения отличались ме-
  нее, чем на 2%. Временная сложность алгоритма, полученная экспериментальным путем,
  лежит в пределах О(n2).

• ОПТИМИЗАЦИЯ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ С НЕЧЕТКИМИ ПАРАМЕТРАМИ

  А. В. Боженюк , О. В. Косенко , М.В. Князева

  2022-05-26

  Аннотация ▼

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