Experimental study on solution possibilities of multiextremal optimization problems through heuristic methods

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. 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 evolyutsionnogeneticheskogo 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 multiextreme 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. 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).