The work objective is to study a vital task of the multiextremal objects search engine optimization which is much more complicated than monoextremal problems. It is shown that only heuristics is appropriate in achieving this goal. Therefore, three best known and developed search engine optimization techniques are studied: particle swarm method, evolutionary genetic approach, and ant colony algorithm. The analysis is performed in the environment common for all methods of the test research problems of the multiextremal Rastrigin function. It is proved that all these methods are well suited for the multiextremal problem solution. While it is necessary to use proper specific approaches to solving the local extremum detection and identification problem in each of the heuristic algorithms, they all require data clustering. Each method can provide any desired accuracy of the extremum problem solution, and it utilizes an acceptable time resource.
optimization, extremum, multiextremality, search engine optimization, clustering, heuristic methods, evolutionary genetic approach, particle swarm method, ant colony algorithm.
Многие современные проблемы науки, техники, экономики, военного дела и пр. связаны с решением задач поиска оптимальных характеристик объектов проектирования: конструкций, технологий, режимов и условий работы, динамических и статических состояний и т. д. Иными словами, разработчикам приходится решать задачи поисковой оптимизации (ПО) [1–3]. Характерно, что большинство известных на сегодня методов ПО разработано и эффективно используется для нахождения одного оптимума — чаще всего, глобального [3, 4]. Однако многие задачи планирования, сложные технологические комплексы, транспортные задачи и другие объекты оптимизации (особенно дискретной природы) характеризуются многоэкстремальностью (МЭ) [4–11]. Столь существенное отличительное свойство требует специфических методов решения таких задач. Вряд ли эти методы целесообразно искать в классе детерминированных методов ПО. Они слишком чувствительны к знакопеременности и разрывности функций отклика в континуальных факторных пространствах, а также описываются NP-полными алгоритмами в дискретных факторных пространствах. Для решения большинства реальных оптимизационных задач все чаще стремятся применять методы, получившие название «эвристические». Эти методы наиболее перспективны и для решения МЭ задач [5–11].
1. Boettcher, S., Percus, A.-G. Extremal Optimization: Methods derived from Co-Evolution. Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO ’99), 1999, pp. 825-832.
2. Floudas, C.-A., Pardalos, P. M. Encyclopedia of Optimization, 2nd edition. New York: Springer, 2009, 4646 p.
3. Jones, K.-B. Search Engine Optimization, 2nd edition. Indianapolis: Wiley Publishing, 2010, 336 p.
4. Shreves, R. Drupal Search Engine Optimization. Birmingham: Packt Publishing, 2012, 116 p.
5. Vinogradov, I.M., ed. Matematicheskaya entsiklopediya: v 5 t. T. 4. [Mathematical encyclopedia: in 5 vol. Vol. 4.] Moscow: Sovetskaya entsiklopediya, 1984, pp. 135-140 (in Russian).
6. Strongin, R. G. Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. Journal of Global Optimization, 1992, vol. 2, iss. 4, pp. 357-378 .
7. Neydorf, R.А., Filippov, A.V., Yagubov, Z.K. Perestanovochnyy algoritm biekstremal´nogo resheniya odnorodnoy raspredelitel´noy zadachi. [Exchange algorithm of the homogeneous distribution problem biextremal solution.] Vestnik of DSTU, 2011, no. 5 (56), vol. 11, pp. 655-666 (in Russian).
8. Neydorf, R.А., Zhikulin, A.A. Issledovanie svoystv mnogoekstremal´nosti resheniya raspredelitel´nykh zadach. [Investigation of properties of distribution problem solution multiextremality.] Sistemnyy analiz, upravlenie i obrabotka informatsii: sb. tr. 2-go Mezhdunar. nauch. seminara. [System analysis, management and information processing: Proc. 2nd Int. Sci. Seminar.] Rostov-on-Don: DSTU Publ. Centre, 2011, pp. 377-380 (in Russian).
9. Neydorf, R.А., Derevyankina, A.A. Metodologiya resheniya mnogoekstremal´nykh zadach modifitsirovannym metodom royashchikhsya chastits. [Methodology of solving multiextremal problems by the modified particle swarm method.] Innovatsii, ekologiya i resursosberegayushchie tekhnologii na predpriyatiyakh mashinostroeniya, aviastroeniya, transporta i sel´skogo khozyaystva: tr. IX mezhdunar. nauch.-tekhn. konf. [Innovations, ecology, and resource-saving technologies at the enterprises of mechanical engineering, aviation, transport, and agriculture: proc. IX Int. Sci.-Tech. Conf.] Rostov-on-Don: DSTU Publ. Centre, 2010, pp. 328-330 (in Russian).
10. Neydorf, R.А., Sklyarenko, A.A. Reshenie mnogoekstremal´nykh zadach metodom delyashchikhsya roev. [The solution of multiextreme problems by the swarm sharing method.] Vestnik of DSTU, 2010, vol. 10, no. 4 (47), pp. 492-499 (in Russian).
11. Neydorf, R.А., Derevyankina, A.A. Reshenie zadach raspoznavaniya metodom royashchikhsya chastits s deleniem roya. [The decision of tasks of recognition by the method of swarming particles with division of the plenty.] Izvestiya SFedU. Engineering Sciences, 2010, no. 7 (108), pp. 21-28 (in Russian).
12. Rastrigin, L. A. Systems of Extremal Control. Moscow: Nauka, 1974, 316 p.
13. Eberhart, R., Kennedy, J. A New Optimizer Using Particle Swarm Theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya, 1995, pp. 39-43.
14. Kennedy, J., Eberhart, R.-C. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. Piscataway, 1995, pp. 1942-1948.
15. Shi, Y., Eberhart, R.-C. A modified particle swarm optimizer. Proceedings of the IEEE Congress on Evolutionary Computation. Piscataway, 1998, pp. 69-73.
16. Clerc, M., Kennedy, J. The particle swarm-explosion, stability, and convergence in a multi-dimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, vol. 6, iss. 1, pp. 58-73.
17. Mendes, R., Kennedy, J., Neves, J. The fully informed particle swarm: simpler, maybe better. IEEE Transactions on Evolutionary Computation, 2004, vol. 8, iss. 3, pp. 204-210.
18. Neydorf, R.А., Chernogorov, I.V. Parametricheskaya nastroyka algoritma poiskovoy optimizatsii metodom royashchikhsya chastits s ispol´zovaniem planirovaniya eksperimenta. [Parametric identification of search engine optimization algorithm by particle swarm method using experiment design.] International Scientific Institute “Educatio”, 2015, vol. 4, no. 2 (9), pp. 44-49 (in Russian).
19. Neydorf, R.А., Chernogorov, I.V. Rasshirenie funktsionala metoda royashchikhsya chastits kinematicheskoy i dinamicheskoy modifikatsiey algoritma ego realizatsii. [Expansion of particle swarm method functional by kinematic and dynamic modification of the algorithm of its realization.] “Aeterna” LLC, Coll. Sci. Papers “The role of science in the development of society”, Coll.-17, vol. 1, 2015, pp. 24-28 (in Russian).
20. Neydorf, R.А., Chernogorov, I.V. Parametricheskoe issledovanie algoritma royashchikhsya chastits v zadache poiska global´nogo ekstremuma. [Parametric study of the particle swarm algorithm in the global hill-climbing problem.] Matematicheskie metody v tekhnike i tekhnologiyakh - MMTT-28: sb. trudov XXVIII mezhdunar. nauch. konf. : v 12 t. T. 3 / pod obshch. red. A. A. Bol´shakova. - Saratov: Saratov. gos. tekhn. un-t; Yaroslavl´ : Yaroslav. gos. tekhn. un-t ; Ryazan´: Ryazansk. gos. radiotekhn. un-t. [Mathematical techniques in methods and technologies - MMTT-28: Proc. XXVIII Int. Sci. Conf.: in 12 vol., vol. 3; under gen. ed. A.A. Bolshakov; Saratov: Saratov State Tech. Univ.; Yaroslavl: Yaroslavl State Tech. Univ.; Ryazan: Ryazan State Radiotech. Univ.] 2015, 108 p. (in Russian).
21. Fraser, A. Computer Models in Genetics. New York: McGraw-Hill, 1970, 192 p.
22. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning. Boston: Addison-Wesley, 1989, 372 p.
23. Mühlenbein, H., Schomisch, D., Born, J. The Parallel Genetic Algorithm as Function Optimizer. Parallel Computing, 1991, vol. 17, iss. 6-7, pp. 619-632.
24. Barricelli, N.-A. Esempi numerici di processi di evoluzione. Methodos, 1954, vol. 6, pp. 45-68.
25. Boettcher S. Extremal Optimization - Heuristics via Co-Evolutionary Avalanches. Computing in Science & Engineering, 2000, vol. 2, iss. 6, pp. 75-82.
26. Boettcher, S. Extremal optimization of graph partitioning at the percolation threshold. Journal of Physics A: Mathematical and General, 1999, vol. 32, pp. 5201-5211.
27. Neydorf, R.А., Polyakh, V.V. Metod mnogoekstremal´nogo poiska s ispol´zovaniem evolyutsionno-geneticheskogo algoritma i vyborochnogo kriteriya St´yudenta. [Method of multiextremal search using an evolutionary genetic algorithm and Student’s t-test.] Innovation Science, 2015, vol. 1, no. 3, pp. 135-140 (in Russian).
28. Neydorf, R.А., Polyakh, V.V. Issledovanie mnogoekstremal´nykh zavisimostey s ispol´zovaniem evolyutsionno geneticheskogo metoda i odnovyborochnogo kriteriya St´yudenta. [Study of multiextremal dependencies using an evolutionary genetic method and one sample Student´s t-test.] Matematicheskie metody v tekhnike i tekhnologiyakh - MMTT-28: sb. trudov XXVIII mezhdunar. nauch. konf. : v 12 t. T. 3 / pod obshch. red. A. A. Bol´shakova. - Saratov: Saratov. gos. tekhn. un-t; Yaroslavl´ : Yaroslav. gos. tekhn. un-t ; Ryazan´: Ryazansk. gos. radiotekhn. un-t. [Mathematical techniques in methods and technologies - MMTT-28: Proc. XXVIII Int. Sci. Conf.: in 12 vol., vol. 3; under gen. ed. A.A. Bolshakov; Saratov: Saratov State Tech. Univ.; Yaroslavl: Yaroslavl State Tech. Univ.; Ryazan: Ryazan State Radiotech. Univ.] 2015, 108 p. (in Russian).
29. Neydorf, R.А., Polyakh, V.V. Lokalizatsiya oblastey poiska evolyutsionno-geneticheskogo algoritma pri reshenii zadach mnogoekstremal´nogo kharaktera. [Localization area of search of evolutionary genetic algorithm for solving multi-extreme tasks.] Science. Technology. Production. 2015, no. 5(9). pp. 32-35 (in Russian).
30. Gosset, W.-S. The probable error of a mean. Biometrika, 1908, no. 6 (1), pp. 1-25.
31. Lovric, M. International encyclopedia of statistical science. Berlin: Springer-Verlag, 2011, 1671 p.
32. Kazharov, А.А., Kureichik, V.M. Murav´inye algoritmy dlya resheniya transportnykh zadach. [Ant colony optimization algorithms for solving transportation problems.] Journal of Computer and Systems Sciences International, 2010, vol.49, iss. 1, pp. 30-43 (in Russian).
33. Dorigo, M., Gambardella, L.-M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997, vol. 1, no. 1, pp. 53-66.
34. Liu, X., Fu, X. An effective clustering algorithm with ant colony. Journal of Computers, 2010, vol. 5, no. 4, pp. 598-605.
35. Toksari, M.-D. Ant Colony Optimization for finding the global minimum. Applied Mathematics and Computation, 2006, no. 176, pp. 308-316.
36. Neydorf, R.А., Yarakhmedov, O. T. Razrabotka, optimizatsiya i analiz parametrov klassicheskogo murav´inogo algoritma pri reshenii zadachi kommivoyazhera v polno-svyaznom grafe. [Design, optimization, and analysis of parameters of classical ant algorithm for solving the travelling salesman problem.] Science. Technology. Production. 2015, no. 3 (7), pp. 18-22 (in Russian).
37. Neydorf, R.А., Yarakhmedov, O. T. Statisticheskoe issledovanie optimizatsionnykh svoystv resheniya klassicheskim murav´inym algoritmom zadachi kommivoyazhera. [Statistical analysis of optimized properties of the traveling salesman problem solution by classical ant colony algorithm.] International Scientific Institute “Educatio”, 2015, no. 4 (11), pp. 141-144 (in Russian).
38. Neydorf, R.А., Yarakhmedov, O. T. Issledovanie vozmozhnostey optimal´nogo resheniya zadachi kommivoyazhera parametricheski optimizirovannym murav´inym algoritmom. [Feasibility study of the traveling salesman problem solution by parametrically optimized ant colony algorithm.] Matematicheskie metody v tekhnike i tekhnologiyakh - MMTT-28: sb. trudov XXVIII mezhdunar. nauch. konf.: v 12 t. T. 3 / pod obshch. red. A. A. Bol´shakova. - Saratov: Saratov. gos. tekhn. un-t; Yaroslavl´ : Yaroslav. gos. tekhn. un-t ; Ryazan´: Ryazansk. gos. radiotekhn. un-t. [Mathematical techniques in methods and technologies - MMTT-28: Proc. XXVIII Int. Sci. Conf.: in 12 vol., vol. 3; under gen. ed. A.A. Bolshakov; Saratov: Saratov State Tech. Univ.; Yaroslavl: Yaroslavl State Tech. Univ.; Ryazan: Ryazan State Radiotech. Univ.] 2015, 108 p. (in Russian)
39. Pang, C.Y.,et al.Apply Ant Colony Algorithm to Search All Extreme Points of Function. Available at: http://www.cornell.edu/ arxiv.org/pdf/0911.3209v1.pdf (accessed: 17.10.15).
