НАУКА и ОБРАЗОВАНИЕ

Файл статьи: Karpenko_P.pdf (1106.83Кб)

УДК 519.6	Россия, МГТУ им. Н.Э. Баумана

Опыт решения сложных задач глобальной оптимизации с помощью мета эвристических алгоритмов показывает, что применение одного такого алгоритма далеко не всегда приводит к успеху. Поэтому в последние годы большое внимание уделяется гибридизации мета эвристических алгоритмов глобальной оптимизации. В гибридных алгоритмах, объединяющих различные алгоритмы либо одинаковые алгоритмы, но с различными значениями свободных параметров, эффективность одного алгоритма может компенсировать слабость другого.

Работа посвящена гибридизации популяционного алгоритма на основе искусственной иммунной системы (Artificial Immune System, AIS) и алгоритма роя частиц (Particle Swarm Optimization, PSO). Используем гибридизацию по схеме препроцессор / постпроцессор (preprocessor / postprocessor). AIS и PSO алгоритмы оптимизации обладают взаимодополняющими свойствами. Так, известно, что алгоритмы AIS имеют высокую вероятностью локализации глобального экстремума целевой функции, но невысокую скоростью сходимости. Напротив, для алгоритмов PSO характерна высокая скорость сходимости, но, если не прикладывать дополнительных усилий, относительно невысокая вероятность локализации глобального экстремума. Гибридизация алгоритмов AIS и PSO преследует цель объединить указанные достоинства этих алгоритмов и нивелировать их недостатки.

Предложен алгоритм AIS_PSO, который представляет собой модификацию гибридного алгоритма, построенного на основе иммунного алгоритма CLONALG и алгоритма роя части PSO. Модификация заключается в замене алгоритма CLONALG этим же, но модифицированным алгоритмом. Средствами программного комплекса MatLab выполнена программная реализация алгоритма AIS_PSO. На тестовых функциях Резенброка, Химмельблау и Растригина выполнено исследование эффективности разработанного алгоритмического и программного обеспечения. С помощью программы AIS_PSO решена задача оптимального управления движением вибрационного робота. Использован известный метод решения задачи оптимального управления динамической системой, основанный на сведении этой задачи к задаче нелинейного программирования высокой размерности. Результаты исследований показали высокую эффективность разработанного алгоритмического и программного обеспечения.

Список литературы

1. Wang X. Hybrid nature-inspired computation method for optimization. Doctoral Dissertation. Helsinki University of Technology, TKK Dissertations, 2009, 161 p.
2. El-Abd, Kamel M. A taxonomy of cooperative search algorithms // In: Hybrid Metaheuristics. Second International Workshop. Vol. 3636. 2005. P. 32-41.
3. Raidl G.R. A Unified View on Hybrid Metaheuristics // In: Hybrid Metaheuristics. Springer Berlin Heidelberg, 2006. P. 1-12. (Ser. Lecture Notes in Computer Science; vol. 4030). DOI: 10.1007/11890584_1
4. Castro L.N., Zuben F.J. Learning and optimization using the clonal selection principle // IEEE Transactions on Evolutionary Computation. 2002. Vol. 6, no. 3. P. 239-251. DOI: 10.1109/TEVC.2002.1011539
5. Herrera-Lozada J.C., Calvo H., Taud H. A Micro Artificial Immune System // Polibits. 2011. Vol. 43. P. 107-111.
6. Карпенко А.П., Шуров Д.Л. Метод глобальной оптимизации SIA. Гибридизация иммунного метода HIA и метода локального поиска SUBPLEX. Saarbrücken: LAMBERT Academic Publishing, 2012. 57 с.
7. D'haeseleer P., Forrest S., Helman P. An immunological approach to change detection: algorithms, analysis and implications // Proceedings of the 1996 IEEE Symposium on Security and Privacy. 1996. P. 110-119. DOI: 10.1109/SECPRI.1996.502674
8. Castro L.N., Timmis J. An artificial immune network for multimodal function optimization // Proceedings of the 2002 IEEE Congress on Evolutionary Computation (CEC'02). Vol. 1. 2002. P. 699- 674. DOI: 10.1109/CEC.2002.1007011
9. КарпенкоА.П., СеливерстовЕ.Ю. Глобальная оптимизация методом роя частиц. Обзор // Информационные технологии. 2010. № 2. С. 25-34.
10. Черноусько Ф. Л., Болотник Н. Н. Мобильные роботы, управляемые движением внутренних тел // Труды института математики и механики УрО РАН. 2010. Т. 16, № 5. C. 213-222.
11. Болотник Н. Н., Зейдис И. М., Циммерманн К., Яцун С.Ф. Динамика управляемых движений вибрационных систем // Известия РАН. Теория и системы управления. 2006. № 5. С. 157-167.
12. Yap D.F.W., Koh S.P., Tiongand S.K., Prajindra S.K. Particle Swarm based Artificial Immune System for Multimodal Function Optimization and Engineering Application Problem // Trends in Applied Sciences Research. 2011. Vol. 6, no. 3. P. 282-293.
13. Дьяконов В.П. MATLAB и SIMULINK для радиоинженеров. М.: «ДМК-Пресс», 2011. 976 c.
14. Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Наука, 1978. 488 с.