Впервые идея использования для решения оптимизационных задач аналогии с поведением колонии муравьев высказана в 1992 г. [1]. Применение методов ACO показано на примерах задачи коммивояжера [2], раскроя и упаковки [3] и др. Обзор методов ACO приведен в [4].
Метод колонии муравьев (ACO) основан на имитации поведения муравьев, минимизирующих длину своих маршрутов на пути от муравьиной кучи до источника пищи. Особенностью метода ACO является — возможность при многоточечном кроссовере использовать более двух родителей (полигамность). Значение -го гена формируемой хромосомы выбирается из имеющегося набора возможных значений на основе оцкнок, зафиксированных в матрице =[] , =1,2…τ, =1,2…, τ — число используемых аллелей, – число генов в хромосоме, – полезность использования -го аллеля в -м гене, которая рассчитывается по формуле:
= ( k / )β, (1)
где k – полезность –й хромосомы, – множество номеров хромосом, имеющих в -м локусе ссылку на -ый аллель, β — коэффициент, выбираемый в диапазоне 1…3, – размер популяции. Полезность k определяется как
k = ( -) + (1-)( -),
где € [0,1], – наилучшее значение целевой функции, полученное на данный момент поиска, — значение целевой функции, соответствующее –й хромосоме, – максимальное (наихудшее) значение целевой функции в популяции хромосом на данном шаге.
В соответствии с (1) вероятность выбора -го аллеля в -м гене на очередном шаге
= / .
Список литературы
1. Dorigo M. Optimization, Lеarning and Natural Algorithms. PhD thesis, Dipartimento di Electronica. - Politecnico di Milano, 1992.
2. Dorigo M., Gambardella L. Ant Coloony for Traveling Salesman Problem. - Bruxelles: TR/TRIDIA/1996-3
3. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки //Информационные технологии, 2005, № 10.
4. Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization. //Artificial Life, v.5, 1999, # 3.