Нечунаева К.А.
Модификации бионических алгоритмов в применении к задачам на ориентированных графах
Для многих задач комплексных систем (сложных информационных, телекоммуникационных, вычислительных, транспортных и прочих сетей) часто моделью сети выступает орграф [1], [2]. Он не только показывает структуру сети, но и отображает связи между её узлами, учитывая пропускную способность дуг и рёбер.
Не все сетевые задачи можно решить точными методами, так как при реальных условиях появляются ограничения, накладываемые на структуру, длину путей, стоимость сети, и задача может стать NP-трудной. Одним из популярных инструментов решения таких задач являются эвристические методы, в нашем случае бионические алгоритмы: генетический алгоритм [1], алгоритм клонирования [3]. Эти алгоритмы имеют схожие элементы: кодирование особей/антител, некоторые мутации.
Для настройки этих алгоритмов используются такие параметры как размер популяции, вероятность мутации, процент отсева худших особей, пригодность особи. Мы будем оценивать количество мутаций, чтобы, отталкиваясь от этих показателей, можно было настроить алгоритмы под конкретные задачи. В случае орграфов основные операторы и кодирование будут изменены.
Работа поддержана грантом №14-07-31069.
ЛИТЕРАТУРА
1. Edwin S. H., Hou Ninvan Ansari and Hong Ren: ”A genetic algorithm for multiprocessor scheduling”, IEEE Transactions On Parallel And Distributed Systems, Vol. 5, No. 2(1994), pp. 113-120.
2. Dai, Y.S., and Poh, K.L.: ”Solving the Network Interdiction Problem with Genetic Algorithms”, In Proceedings of the Fourth Asia-Pacifc Conference on Industrial Engineering and Management Systems, 2002, Taiwan.
3. Ulutas, B.H., Islier, A.A.: ”Parameter Setting for Clonal Selection Algorithm in Facility Layout Problems”, In Proc. of the ICCSA-2007, LNCS 4705, Part I, pp. 886-899.
To reports list