Архив статей журнала
Исследованы способы определения размера популяции в генетическом алгоритме и изучена зависимость между количеством особей и скоростью работы алгоритма. Описываются методы определения оптимального количества особей в популяции разными методами: в зависимости от размера хромосом, для древовидного типа хромосом, при наличии фактора зашумленности и по методу соседнего элемента с выставлением максимальной и минимальной границы. Данные, полученные по выполнении каждого метода, отличаются между собой, по причине этого произведена оценка с целью проверить точность теоретических данных, сравнив их с экспериментальными. Для проведения экспериментов была разработана программа на графической платформе «Unity» с возможностью изменения количества особей в популяции. После получения результатов было проведено сравнение экспериментальных данных с данными, полученными на основе методов определения размера популяции в генетическом алгоритме из первой части работы. Эксперимент показал, что оптимальный размер популяции лежит в диапазоне 100-160 особей. При уменьшении их количества время выполнения поставленной задачи начинает существенно увеличиваться, а при увеличении за расчетный предел - сокращение времени выполнения не соответствует затрачиваемым вычислительным ресурсам. Сами полученные экспериментальные данные имеют наименьшую погрешность с методом, используемым древовидное представление хромосом. Результаты исследования могут быть использованы для выбора размера популяции при обучении для достижения лучшего соотношения затрачиваемой вычислительной мощности к скорости обучения, а определенный в процессе работы метод может помочь в теоретических расчетах.
ассмотрена задача двумерной упаковки геометрических фигур сложных форм. Задачи данного класса отнесены к классу NP-трудных проблем комбинаторной оптимизации. Помимо этого, упаковка фигур сложных геометрических форм, является одним из наиболее сложных подтипов задачи двумерной упаковки. В связи с этим необходима разработка эффективных эвристических подходов к решению данной задачи. В статье дана постановка задачи, описаны ее основные особенности, приведены ограничения и условия характерные для данного подтипа задачи двумерной упаковки. Описан критерий для подсчета эффективности решения. Для решения данной задачи в статье предлагается архитектура комбинированного поиска, состоящая из двух метаэвристических вычислительных алгоритмов. В данной архитектуре в качестве оптимизационных методов были реализованы модифицированный генетический и роевой мультиагентный биоинспирированный алгоритм, основанный на поведении пчелиной колонии. Данные алгоритмы позволяют получать наборы квазиоптимальных решений за полиномиальное время. Приведены преимущества от использования предлагаемого подхода. Для проверки эффективности предложенного подхода был разработан программный продукт, который использует предложенную архитектуру и метаэвристические вычислительные алгоритмы при решении поставленной задачи. Разработка программного продукта велась на языке программирования C++ и написана в среде разработки Microsoft Visual Studio Code. Проведен вычислительный эксперимент на наборе тестовых примеров-бенчмарок. По результатам экспериментальных исследований сделан вывод об эффективности предложенного комбинированного поиска при решении задачи двумерной упаковки геометрических фигур сложных форм в сравнении с решениями, базирующимися на классических алгоритмах.