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