Учитывая, что популяции X = min {x 1,…, x 2n }, положим
Формула (9) служит для измерения расстояния между популяцией и оптимальным решением.
Последовательность {d (x k ); k = 0, 1, 2,…}, порожденная биоинспирированным алгоритмом, является случайной последовательностью, которая моделируется однородной цепью Маркова.
Тогда дрейф случайной последовательности в момент времени k определяется как
Время останова алгоритма оценивается как t = min {k : d (x k ) = 0}. Задача состоит в изучении взаимосвязи между временем t и размерностью задачи n . При каких значениях дрейфа D(d (x k )) можно оценить математическое ожидание E [t ]? Найдет ли в среднем алгоритм оптимальное решение за полиномиальное время или ему потребуется экспоненциальное время.
Идея анализа дрейфа довольно проста. Ключевым вопросом здесь является оценка соотношения d и D .
Биоинспирированный алгоритм может решить оптимизационную задачу за полиномиальное среднее время при следующих условиях дрейфа:
· если существует полином h 0 ( n ) > 0 (n - размерность задачи) такой, что d (X ) <= h 0 ( n ) для любой данной популяции X , т.е. расстояние от любой популяции до оптимального решения является полиномиальной функцией от размерности задачи;
· в любой момент k >= 0, если d (x k ) > 0, то существует полином h 1 ( n ) > 0 такой, что
т.е. дрейф случайной последовательности {d (x k ); k = 0, 1, 2,…} по отношению к оптимальному решению всегда положителен и ограничен обратным полиномом.
В [51] доказано следующее:
· если данные условия соблюдаются для случайной последовательности {d (x k ); k = 0, 1, 2,…}, то уже с начальной популяции X с d (X ) > 0 выполняется неравенство
где h (n ) - полиномом размерности задачи n ;
· если имеется множество задач и биоинспирированный алгоритм для их решения, то для любой начальной популяции X с d (X ) > 0, справедливо
· если целевая функция является линейной с положительными коэффициентами
(c 1 > c 2 >…> с n > 0), то для получения оптимального решения биоинспирированному алгоритму с вероятностью мутации pm = 1/n потребуется в среднем O (n ln ( n ) ) шагов;
· если целевая функция f : S >R является псевдо модульной для любых x , y ? S (например, f (x ) = Summai =1n П j =1 isj ), то при вероятности мутации pm = 1/n ожидаемое время останова алгоритма удовлетворяет неравенству E [t ] <= n 2(exp - 1);
Если биоинспирированный алгоритм не в состоянии найти оптимальное решение за полиномиальное время, то тогда есть смысл искать приближенное решение, определив момент останова алгоритма t как t = min {k : d (x k ) <= db }, где db >= 0. Это выполняется при следующих условиях дрейфа [51]:
· для любой популяции X с db < d (X ) < da , где db >= 0, da > 0 справедливо
Это условие означает, что интервал (db , da ) < da ) является очень сложным для поиска, если, d (x k +1 ) > d (x k ). Другими словами, потомки в популяции в среднем не становятся ближе к оптимальному решению, а, возможно, отдаляются от него;
· для любой популяции X с d (X ) > da , где da > 0, справедливо
Условие (15) означает, что популяция на интервале [da , + ?) не будет в среднем дрейфовать к оптимальному решению, потому что d (x k ) >= (da - ln (D )).
В [51] доказано, что при выполнении условий (14), (15), если d (x 0 ) > da , D >= 1, r < 1, то существуют некоторые д1 > 0 и д 2 > 0 такие, что справедливо неравенство
Иными словами, биоинспирированный алгоритм при некоторых условиях может потребовать в среднем экспоненциального времени для поиска оптимального решения.
Следствием результатов дрейф-анализа является то обстоятельство, что оценка значения дрейфа превращается в оценку времени работы алгоритма, а локальное свойство (дрейф за один шаг) преобразуется в глобальное свойство (время работы алгоритма до нахождения оптимума)! Это новый результат в оценке временной сложности биоинспирированных алгоритмов, полученный посредством анализа дрейфа. Оценить дрейф проще. С помощью анализа дрейфа определены условия, выполнение которых гарантирует решение некоторых задач в среднем за полиномиальное время, а также условия, при которых алгоритм требует для решения задачи в среднем экспоненциальное время вычисления.
Отметим, что эти результаты были получены в предположении, что число поколений (что эквивалентно числу вычислений функции приспособленности) является наиболее важным фактором при оценке времени вычислений алгоритма. Это, пожалуй, справедливо для большинства приложений биоинспирированных алгоритмов, поскольку в них оценка приспособленности является наиболее трудоёмкой частью алгоритма, в отличие от операций кроссинговера и мутации, трудоемкость которых оценивалась как O (n ), и операции селекции, трудоемкость которой оценивалась как O (n ln ( n ) ).
В этом плане заслуживает внимания работа [52], в которой использовалась теорема «аддитивного дрейфа». Было предложено множество вариантов теорем такого вида, включая верхние и нижние оценки в случае мультипликативного и переменного дрейфа [53]. Значительный прогресс наблюдается в области порождения функций расстояния, которые используются для адаптации процесса оптимизации к входным условиям дрейф-теорем. Теоретический аппарат дрейф-теорем, существующий в настоящее время, позволяет анализировать биоинспирированные алгоритмы на тестовых задачах и задачах комбинаторной оптимизации.
Несомненно, на временную сложность биоинспирированных алгоритмов оказывают влияние их параметры (вероятность кроссинговера, мутации и др.). Было бы интересно исследовать степень этого влияния для различных задач, чтобы получить некоторое представление об эффективности различных операторов и параметров настройки алгоритма.
Требуют дальнейшего изучения более строгие условия дрейфа, чтобы получить более жесткие верхние оценки для среднего времени вычислений.
Перспективным представляется проведение дрейф-анализа биоинспирированных алгоритмов на известных трансвычислительных задачах, чтобы понимать насколько эффективным является их применение для решения этих задач.
Заключение
Когнитивные биоинспирированные алгоритмы - один из наиболее перспективных способов решения задач оптимизации, когда точные методы решения задачи неизвестны или слишком трудоемки, при этом требуется найти не доказуемо точное решение, а «достаточно хорошее» решение, или решение, удовлетворяющее каким-либо критериям качества.
Одна из метафор когнитивных биоинспирированных алгоритмов состоит в том, что задача оптимизации решается так, как если бы ее решала природа: с помощью направленной эволюции потенциальных решений задачи путем внесения случайных небольших изменений и рекомбинации хороших решений с целью получить лучшие.
Когнитивные биоинспирированные алгоритмы в настоящее время активно используются в различных областях: в дизайне космических кораблей и зубных щеток, при разработке антенн для микро спутников, усилителей, фильтров, контроллеров, осцилляторов и других электронных схем [54], двигателей самолетов и новых антибиотиков, для конструирования роботов и спам-фильтров, когнитивных музыкальных ди-джеев и др. Среди фирм, использующих когнитивные биоинспирированные технологии, присутствуют такие известные организации и компании, как NASA , General Motors, Boeing, Honda, Yamaha, Gillette, General Electric, Genetic Programming, Cloudmark, Yandex , Hewlett-Packard, Proctor&Gamble, Coca Cola и др.
Одна из серьезнейших проблем биоинспирированных алгоритмов связана с оценкой времени их работы. Причиной этого на фундаментальном уровне можно назвать их обобщенность вследствие отсутствия специализации под какие-либо задачи. В обзоре приводятся современные теоретические результаты, полученные с помощью дрейф анализа. С их помощью оценка значения дрейфа превращается в оценку времени работы алгоритма. Теоретический аппарат дрейф-анализа, существующий в настоящее время, позволяет анализировать биоинспирированные алгоритмы на тестовых задачах и задачах комбинаторной оптимизации.
Перспективными направлениями здесь является исследование влияния операторов и параметров настройки биоинспирированных алгоритмов на эффективность решения различных задач, проведение дрейф-анализа биоинспирированных алгоритмов на известных трансвычислительных задачах для понимания того насколько эффективным является их применение для решения этих задач.
Библиография
1.Rastrigin L.A. The convergence of the random search method in the extremal control of a many parameter system // Automation and remote control. - 1963. - No. 24(10). - P. 1337-1342.
2.Nelder J.A., Mead R. A simplex method for function minimization // Computer journal. - 1965. - No. 7. - P. 308-313.
3.Fogel L., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolution. -Wiley, 1966. - 452 р.
4.Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // Bell system technical journal. - 1970. - No. 49. - P. 291-307.
5.Holland J.H. Adaptation in natural and artificial systems. - Uni of Michigan press, 1975.
6.Smith S.F. A Learning system based on genetic adaptive algorithms. - PhD thesis, Uni of Pittsburgh, 1980.
7.Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. - 1983. - No. 220. - P. 671-680.
8.Glover F. Future paths for integer programming and links to artificial intelligence // Computers and operations research. - 1986. - No. 13. - P.533-549.
9.Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms // Caltech concurrent computation program, 1989. - Report 826.
10.Dorigo M. Optimization, learning and natural algorithms // PhD thesis, Politecnico di Milano, Italy, 1992. - 152 р.
11.Wolpert D.H., Macready W.G. The no free lunch theorems for optimization // IEEE Trans. evol. comp. - 1997. - vol.1. - No. 1. - P.67-82.
12.Петровский А.Б. Теория принятия решений. - М.: Академия. - 400 с.
13.Eremeev A.P., Vagin V.N. A real-time decision support system prototype for management of a power block // Int. jour. information theories & applications. - 2003. - vol. 10. - No.3. - P. 248-255.
14.Городецкий В.И., Карсаев О.В., Самойлов В.В., Серебряков С.В. Прикладные многоагентные системы группового управления // Интеллектуальные системы. - 2009. - № 2. - С. 3-24.
15.Смирнов А.В. и др. Контекстно-управляемая поддержка принятия решений в распределенной информационной среде // Информационные технологии и вычислительные системы. - 2009. -№ 1. - С. 38-48.
16.Bianchi L., Dorigo M., Gambardella L.M., Gutjahr W.J. A survey on metaheuristics for stochastic combinatorial optimization // Natural computing: an int. jour. - 2009. - No.8. - P. 239-287.
17.Abraham A., Grosan G., Ramos V. Swarm intelligence in data mining. - Berlin-Heidelberg: Springer verlag, 2006. - DOI 10.1007 / 978-3-540-34956-3.
18.Goncalves G., Allaoui H., Kurejchik V. Hybrid parallel genetic approach for one-dimensional bin packing problem // 23rd european conf. of operational research, Bonn, 2009. - P. 202-208.
19.Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison // ACM computing surveys. - 2003. - No. 35. - P. 268-308.
20.Glover F., Kochenberger G.A. Handbook of metaheuristics. - Springer, 2010. - 648 p.
21.Talbi E.-G. Metaheuristics: from design to implementation. - Wiley, 2009. - 596 p.
22.Tomoiaga B., et. Pareto optimal reconfiguration of power distribution systems using a genetic algorithm based on NSGA-II // Energies. - 2013. - No. 6. - P. 1439-1455.
23.Yang X.S. Metaheuristic optimization // Scholarpedia. - 2011. - No. 6(8): 11472.
24.Auger A., Teytaud O. Continuous lunches are free plus the design of optimal optimization algorithms. - Springer-verlag, 2013. - P. 121-146.
25.Kaucic M. A multi-start opposition-based particle swarm optimization algorithm with adaptive velocity for bound constrained global optimization // Jour. glob. optimization. - 2013. - No. 55. - Р. 165-188.
26.Qin A.K., Forbes F. Dynamic regional harmony search with opposition and local learning // Proc. of 13th annual conf. on genetic and evolutionary computation, Dublin, Ireland, 2011. - Р. 53-54.
27.Yang X.J., Huang Z.G. Opposition-based artificial bee colony with dynamic cauchy mutation for function optimization // Int. jour. adv. computer technol. - 2012. - No. 4. - Р. 56-62.
28.Ergezer M., Sikder I. Survey of oppositional algorithms // Proc. of int. conf. on computer and information technology, Dhaka, Bangladesh, 2011. - Р. 623-628.
29.Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. - М.: Физматлит, 2012. - 260 с.
30.Rodzin S. Smart dispatching and metaheuristic swarm flow algorithm // Jour. of computer and systems sciences international. - 2014. - vol. 53. - No. 1. - P. 109-115.
31.Dorigo M., et. A survey on metaheuristics for stochastic combinatorial optimization // Int. jour. natural computing. - 2009. - No. 8 (2). - P. 239-287.
32.Blum C., Roli A. Metaheuristics in combinatorial optimization: overview and conceptual comparison // ACM computing surveys. - 2003. - No. 35 (3). - P. 268-308.
33.Карпенко А.П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Информационные технологии». - 2012. - № 7. - С. 1-31.
34.Wall M. GAlib - A C++ library of genetic algorithm components [электронный ресурс]: информационный портал - режим доступа http://lancet.mit.edu/ga/