Сборники тезисов • Информационные и интеллектуальные системы и технологии • Технологии программирования, искусственный интеллект, биоинформатика
Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, 2016.
Эффективный алгоритм вычисления бинарного эпсилон индикатора для многокритериальных эволюционных алгоритмов
УДК: 004.021
Аннотация:
Генетические алгоритмы применяются для решения оптимизационных задач, у которых может присутствовать несколько параметров оптимизации, например, необходимое время и необходимые денежные ресурсы. В данном случае возможно несколько оптимальных решений, некоторые из которых будут требовать меньшего количества времени при больших финансовых вливаниях, некоторые будут требовать обратного. На основе множеств таких решений производится сравнение качества работы генетических алгоритмов относительно друг друга. Для сравнения вышеупомянутых множеств решений используются различный индикаторы как гиперобъем и эпсилон индикатор, о котором пойдет речь в дальнейшем. Эпсилон индикатор представляет собой минимальное число, которое необходимо прибавить к каждой координате векторов решений из одного множества, чтобы каждый вектор решения из второго множества был не лучше по каждой координате по сравнению с каким-либо вектором из первого множества. Существующее решение данной проблемы пропорционально произведению мощностей вышеупомянутых множеств. Таким образом, целью данной работы стала разработка алгоритма, который имел бы меньшее время работы по сравнению с существующим решением. В результате работы предложено несколько решений данной задачи: решение с использованием двоичного поиска по ответу, решение со сведением задачи к задаче поиска минимума в ортанте, где поиск минимума возможен как с помощью двоичных деревьев, так и с помощью подхода "разделяй и властвуй". Каждое из предложенных решений превзошло существующее решение по времени работы с ростом размерности векторов решений и ростом числа количества векторов решений во множествах. Наиболее удачным решением из предложенных является решение, основанное на сведении задачи с дальнейшим использованием подхода "разделяй и властвуй". Вышеупомянутые подходы позволят производить вычисление эпсилон индикатора с меньшими временными затратами, что в свою очередь позволит вычислять данный индикатор для множеств, состоящих из большего количества векторов решений и имеющих большую размерность.