Algorithmic and program software of the memetic algorithm for the search of the conditional global extremum

Аuthors

Pismennaya V. A.

Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia

e-mail: wildangel9@yandex.ru

Abstract

The memetic algorithm for finding the conditional global extremum of functions created by the author based on the concept of meme is considered.

Currently a great attention is paid to solving global optimization problems. Aircraft designing requires the solution of these problems especially when optimizing the characteristic parameters (weight, flight range, aerodynamic characteristics) and developing control systems of individual structural elements and whole object as well.

This article deals with the problem of the orientation of the spacecraft. During the flight the spacecraft orientation maintaining is the most common problem. In the article flat version of the problem when the spacecraft is turning in a single plane due to the rotation of the flywheel, mounted inside the spacecraft, is considered. At start time, the angular velocity of the spacecraft and the orientation angle are zero. It is necessary to bring the spacecraft orientation angle to the target for the finite time due to the rotation of the flywheel, with zero angular velocity.

Application of the algorithm is also advisable for a number of optimization problems such as the problem of stabilization of the satellite (problem of damping rotational motion of the satellite using engines installed on it), the problem of interception (target interception by missile), the problem of stabilization of the height of the aircraft. Application of the described algorithm significantly reduces the time required for solution of such problems.

Usage of existing numerical methods is associated with a number of difficulties: large computational load, the requirements for the task, difficulties in achieving convergence of the method. So there is a need to develop and use the so-called heuristics. These methods have no rigorous justification of convergence, but in most cases they allow to obtain an acceptable solution to the problem.

The term «meme» was introduced and defined by R. Dawkins in 1976 as «the basic unit of cultural transmission, or imitation». The term «Memetic Algorithm» was first introduced by P. Moscato in his report in 1989 as hybrid genetic algorithm coupled with an individual learning procedure for refining the solution of the problem. At the stage of particular learning the solution (individual or its genotype) is replaced with a new one (learned) solution in case if the new solution has a larger adaptation value independent upon the rest part of the population. Thus, there is the so-called cultural development of the individual, which is then transmitted to its descendants during next generations.

At the moment, the term «Memetic Algorithm» is widely used as a designation of the interactions of evolutionary or other approach based on the concept of population, and particular learning of individuals or other local procedure enhancing the solution of the problems of the global extremum search.

In the developed algorithm, the cultural evolutionary component is implemented while solving optimization problem by using either the ant colony method or simulated annealing method. During the cultural evolution information about memes is used to generate in terms of the solving problem better individual.

On the basis of the proposed algorithm the software complex is formed in C# language, allowing to apply the developed algorithm to different functions, as well as to analyze its performance. Effectiveness of the method is demonstrated on several model examples that have both simple and complex structure of level lines.

Keywords:

conditional global extremum, meme, memetic algorithm, optimization, hybrid algorithm, simulated annealing method, ant colony algorithm, optimal control, orientation of the spacecraft

References

1. Popov V.I. Sistemy orientatsii i stabilizatsii kosmicheskikh apparatov (System orientation and stabilization of spacecraft), Moscow, Mashinostroenie, 1986, 184 p.
2. Raushenbakh B.V., Tokar’ E.N. Upravlenie orientatsiei kosmicheskikh apparatov (Attitude control of spacecraft), Moscow, Nauka, 1974, 600 p.
3. Krylov I.A. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 1968, vol. 8, no.1, pp.203-208.
4. Dawkins R. Universal Darwinism in D.S. Bendall (ed.), Evolution: From Molecules to Men, Cambridge University Press, Cambridge, 1983, pp. 403-425.
5. Dawkins R. The Selfish Gene. Oxford University Press, 1976, 192 p.
6. Moscato P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Caltech Concurrent Computation Program (report 826), 1989.
7. Krasnogor N. Coevolution of genes and memes in memetic algorithms, Graduate Student Workshop, 371 p.
8. Kendall G., Soubeiga E., Cowling P. Choice function and random hyperheuristics, 4th Asia-Pacific Conference on Simulated Evolution and Learning, SEAL 2002, pp. 667–671.
9. Ong Y.S., Keane A.J. Meta-Lamarckian learning in memetic algorithms, IEEE Transactions on Evolutionary Computation, vol. 8 (2), 2004, pp. 99–110.
10. Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of Adaptive Memetic Algorithms: A Comparative Study, IEEE Transactions on Systems Man and Cybernetics, Part B. 36 (1), 141 p.
11. Smith J.E. Coevolving Memetic Algorithms: A Review and Progress Report, IEEE Transactions on Systems Man and Cybernetics, Part B 37 (1), 2007, pp. 6-17.
12. Krasnogor N., Gustafson S. Toward truly «memetic» memetic algorithms: discussion and proof of concepts, Advances in Nature-Inspired Computation, the PPSN VII Workshops, PEDAL (Parallel Emergent and Distributed Architectures Lab), University of Reading, 2002.
13. Ichimura T., Kuriyama Y. Learning of neural networks with parallel hybrid GA using a royal road function, IEEE International Joint Conference on Neural Networks, New York, NY, 1998, pp. 1131–1136.
14. Aguilar J., Colmenares A. Resolution of pattern recognition problems using a hybrid genetic/random neural network learning algorithm, Pattern Analysis and Applications, vol. 1 (1), 1998, pp. 52-61.
15. Wehrens R., Lucasius C., Buydens L., Kateman G. HIPS, A hybrid self-adapting expert system for nuclear magnetic resonance spectrum interpretation using genetic algorithms, Analytica Chimica ACTA, vol. 277 (2), 1993, pp. 313-324.
16. Dorigo M., Socha K. Ant colony optimization for continuous domains, European Journal of Operational Research, 2008, vol. 185, pp. 1155-1173.
17. Panteleev A.V. Metaevristicheskie algoritmy poiska global’nogo ekstremuma, (Metaheuristic algorithms for finding the global extremum), Moscow, MAI, 2009, 129 p.
18. Panteleev A.V., Aleshina E.A. Nauchnyi vestnik MGTU GA, 2013, vol. 194 (8), pp. 47- 54.
19. Panteleev A.V., Dmitrakov I.F. Nauchnyi Vestnik MGTU GA, 2009, vol. 145(8), pp. 26-31.
20. Panteleev A.V., Pis’mennaya V.A. Aviakosmicheskoe priborostroenie, 2014, no. 3, pp. 26-34.

Download