Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации

Теорема Холланда

Согласно основной теореме теории генетических алгоритмов ^[5], доказанной Дж. Холландом и дающей обоснование эффективности ГА, нижняя оценка количества примеров схем после очередной смены поколений определяется следующим неравенством:

где N (h , t ) - количество примеров схемы h на шаге t , N (h , t + 1) - то же на следующем шаге, f ( h , t ) - функция приспособленности схемы на шаге t , f (t ) - среднее значение функции приспособленности во всей популяции на том же шаге t , L - число позиций в хромосоме, d (h ) - определяющая длина схемы, o (h ) - порядок схемы, p_c - вероятность уничтожения схемы под действием оператора кроссинговера, p_m - вероятность уничтожения схемы под действием оператора мутации. Согласно (7) шаблоны, обладающие малой определяющей длиной, низким порядком и пригодностью, выше средней в популяции, будут увеличивать число строк, сходных с шаблоном, в последующих генерациях по экспоненциальному закону.

Теорема Холланда весьма упрощенно описывает поведение генетических алгоритмов, а её доказательство, построенное на элементах теории вероятности, не учитывает достаточно большой разброс значений функций пригодности шаблонов в некоторых практических задачах. Была установлена вычислительная ошибка, которая приводит к неверным результатам для задачи об игровых автоматах. К тому же, поскольку популяция в генетических алгоритмах имеет конечную величину, то возникает неизбежная ошибка при определении значения функции пригодности шаблона. Эта ошибка в оценке ставит под сомнение значение теоремы в плане ее практического применения, за исключением очень простых приложений, для которых теорема становится почти тавтологией, описывающей пропорциональный селективный отбор. Эффект ошибки при определении значения пригодности шаблона состоит в том, что в популяции реального размера, действительное значение функции пригодности может существенно отличаться от среднестатистического значения, даже для начальной популяции.

Другое критическое замечания относительно теоремы Холланда касается предположения о независимости экземпляров, выбираемых из различных шаблонов популяции. Нельзя считать независимыми экземпляры хромосом, если популяции на основе двух пересекающихся шаблонов имеют различную скорость сходимости. Этот факт имеет место даже для бесконечно больших популяций. Он состоит в том, что значение функции пригодности шаблона в популяции быстро начинает отклоняться от теоретического среднего значения, что никак нельзя объяснить на основании теоремы Холланда . Для любого метода оптимизации особый теоретический интерес представляет вопрос о сходимости к глобальному оптимуму и об условиях сходимости. Из теоремы Холланда не следует сходимость ГА к глобальному оптимуму. Исследования в области сходимости ГА сконцентрированы в основном на простейших ГА, а сходимость многочисленных модификаций ГА для решения практических оптимизационных задач является малоисследованной проблемой. Доказано, что простейший ГА не сходится к глобальному оптимуму за конечное время. Доказательство основано на фундаментальной теории цепей Маркова . Следует признать, что методология управления сходимостью даже для простейшего ГА до сих пор не выработана, хотя подтверждением эффективности алгоритма является доказательство его сходимости и оценка вычислительной сложности. Но, как правило, это возможно только в случае упрощенной постановки задачи. Другой альтернативой является проверка алгоритмов на тестовых задачах (benchmarks ) данной проблемной области. К сожалению, в настоящее время не существует согласованного каталога таких задач для оценки старых или новых алгоритмов решения, хотя для многих типовых задач, таких как задача коммивояжера, построения расписания, поиск минимального связывающего дерева, задача о рюкзаке они уже сложились и широко используются. Вероятно, для практики более важным является не вопрос сходимости, а другой вопрос: находит или нет биоинспирированный алгоритм близкое к оптимальному решение за возможно более короткое время? Ответ на этот вопрос также не выглядит однозначным, поскольку в теории пока не получено исчерпывающих объяснений успешных эмпирических результатов, связанных с практическим решением многих оптимизационных задач. Каковы критерии того, насколько подходящим является ГА для решения тех или иных задач? В ^[39] исследовались так называемые обманчивые проблемы (deceptive problems ), при решении которых интуитивно можно предположить, что алгоритм должен найти глобальный оптимум. Очевидно влияние эволюционных операторов на результаты работы биоинспирированного алгоритма. Обозначим эту взаимосвязь применяемого эволюционного оператора через коэффициент корреляции r _eo . Этот коэффициент устанавливает взаимосвязь между значениями функций приспособленности родительских хромосом и хромосом-потомков. В ^[29] приводится несколько тестовых задач с известным значением глобального максимума, для которых определялись значения r_eo , после чего исследуемые задачи классифицировались на следующие группы:

· легко разрешимые (r _eo ? - 0,15);

· трудно разрешимые (- 0,15 < r _eo < 0,15);

· обманчивые (r _eo ? 0,15)

Если значение глобального оптимума заранее неизвестно, то можно использовать вместо него лучшее из известных решений.

Дрейф-анализ

Перспективным направлением в анализе времени работы когнитивных биоинспирированных алгоритмов на сегодняшний день является анализ дрейфа (d rift ) ^[51].

Например, пусть задана следующая задача комбинаторной оптимизации. В конечном пространстве состояний S имеется некоторая функция f ( x ), x ?S . Найти

Пусть x ^* - состояние с максимальным значением функции f_max = f ( x ^* ). Абстрактный биоинспирированный алгоритм для решения поставленной оптимизационной задачи включает следующие шаги.

Шаг 1. Инициализация популяции (случайным образом или эвристически) x ₀ = (x ₁,…, x _2n ) из 2n особей (n - целое число). Присвоить k = 0. Для каждой популяции x _k определить

x _k = max {f(x_i) : x_i ? x _k }.

Шаг 2. Генерация популяции x _{k +1/2} с помощью эволюционных операторов.

Шаг 3. Селекция и репродукция 2n особей из популяций x _{k +1/2} и x _k и получение новой популяции x _{k + S} .

Шаг 4. Если f ( x _{k + S} ) = f_max ,, то stop , иначе x _{k +1} =x _{k + S} , k = k + 1 и переход к шагу 2.

Приведенная выше структура алгоритма ближе к эволюционной стратегии ^[42] и эволюционному программированию ^[29], чем к генетическим алгоритмам, в том смысле, что селекция применяется после выполнения эволюционных операторов. Однако для анализа дрейфа эти детали не имеют значения.

Пусть х ^* - точка оптимума. Обозначим d (x , x ^*) расстояние между точкой х и х ^*. Если имеется множество оптимумов S ^*, то d (x , S ^*) = min {d (x , x ^*): x ^* ? S ^*)} является расстоянием между точкой x и множеством S ^* . Это расстояние будем просто обозначать через d ( x ) . Тогда d (х ^*) = 0, d (х ) > 0 для любого х не принадлежащего S ^*.

Учитывая, что популяции X = min {x ₁,…, 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 ₀ ( n ) > 0 (n - размерность задачи) такой, что d (X ) <= h ₀ ( n ) для любой данной популяции X , т.е. расстояние от любой популяции до оптимального решения является полиномиальной функцией от размерности задачи;

· в любой момент k >= 0, если d (x _k ) > 0, то существует полином h ₁ ( 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 ₁ > c ₂ >…> с _n > 0), то для получения оптимального решения биоинспирированному алгоритму с вероятностью мутации p_m = 1/n потребуется в среднем O (n ln ( n ) ) шагов;

· если целевая функция f : S >R является псевдо модульной для любых x , y ? S (например, f (x ) = Summa_{i =1}ⁿ П _{j =1} is_j ), то при вероятности мутации p_m = 1/n ожидаемое время останова алгоритма удовлетворяет неравенству E [t ] <= n ²(exp - 1);

Если биоинспирированный алгоритм не в состоянии найти оптимальное решение за полиномиальное время, то тогда есть смысл искать приближенное решение, определив момент останова алгоритма t как t = min {k : d (x _k ) <= d_b }, где d_b >= 0. Это выполняется при следующих условиях дрейфа ^[51]:

· для любой популяции X с d_b < d (X ) < d_a , где d_b >= 0, d_a > 0 справедливо

Это условие означает, что интервал (d_b , d_a ) < d_a ) является очень сложным для поиска, если, d (x _{k +1} ) > d (x _k ). Другими словами, потомки в популяции в среднем не становятся ближе к оптимальному решению, а, возможно, отдаляются от него;

· для любой популяции X с d (X ) > d_a , где d_a > 0, справедливо

Условие (15) означает, что популяция на интервале [d_a , + ?) не будет в среднем дрейфовать к оптимальному решению, потому что d (x _k ) >= (d_a - ln (D )).

В [51] доказано, что при выполнении условий (14), (15), если d (x ₀ ) > d_a , D >= 1, r < 1, то существуют некоторые д₁ > 0 и д ₂ > 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/

35.Merelo J.J. Library for doing evolutionary computation in Perl [электронный ресурс]:-режим доступа http://opeal.sourceforge.net/

36.[Электронный ресурс]: - режим доступа https://github.com/dknoester/ealib/

37.[Электронный ресурс]: - режим доступа http://www.math.nsc.ru/AP/benchmarks/index.html

38.[Электронный ресурс]: - режим доступа http://watchmaker.uncommons.org/

39.Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. - USA: Addison-Wesley publishing company, inc., 1989. - 432 р.

40.Гладков Л.А., Курейчик В.В., Курейчик В.М., Сорокалетов П.В. Биоинспирированные методы в оптимизации. - М.: Физматлит, 2009. - 380 с.

41.Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование (обзор) // Известия РАН. Теория и системы управления. - 2002. - № 1. - С. 127-137.

42.Rodzin S.I. Schemes of evolution strategies // Proc. of 2002 IEEE int. conf. on AI-systems (ICAIS'2002). - P. 375-380.

43.Eberhart R., Shi Yu., Kennedy J. Swarm intelligence. - Morgan Kaufmann, 2010. - 512 р.

44.Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. - М.: Горячая линия - Телеком, 2013. - 384 с.

45.Родзин С.И. Интеллектуальные системы. Генетические алгоритмы: базовая концепция, когнитивные возможности и проблемные вопросы теории. - М.: Физматлит, 2007. - С. 47-66.

46.Rodzin S., Rodzina O. New computational models for big data and optimization // Proc. of the 9th IEEE int. conf. application of information and communication technologies (AICT'2015). - P. 3-7.

47.Родзин С.И., Родзина О.Н. Алгоритмы биомеметики // Образовательные ресурсы и технологии. - 2014. - № 2(5). - С. 129-132.

48.Rodzin S., Rodzina O. Metaheuristics memes and biogeography for trans computational combinatorial optimization problems // Proc. of the 6th IEEE int. conf. on cloud system and big data engineering (Confluence-2016), India, 14-15 jan., 2016.

49.Kureichik V.M., Rodzin S.I. Evolutionary algorithms: genetic programming // Jour. of computer and systems sciences international. - 2002. - vol. 41. - No. 1. - P. 123-132.

50.Коробейников А.Г., Кутузов И.М., Колесников П.Ю. Анализ методов обфускации // Кибернетика и программирование. - 2012. - № 1. - C. 31 - 37. URL: http://www.e-notabene.ru/kp/article_13858.html

51.He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms // Artificial intelligence. - 2001. - vol. 127. No. 1. - P. 57-85.

52.Jansen T. Fixed budget computations: why, how and what? // Proc. of Dagstuhl seminar on theory of evolutionary algorithms, 2013. - P. 1325-1332.

53.Doerr B., Goldberg L. Adaptive drift analysis // Algorithmica. - 2013. - vol. 65, No. 1. - P. 224-250.

54.Rodzin S., Rodzina L. Theory of bionic optimization and its application to evolutionary synthesis of digital devices // Proc. of the 14th IEEE east-west design & test symposium (EWDTS'14), 2014. - P. 147-152

Размещено на Allbest.ru