Geodesic
Genetic algorithm with tournament selection as a~local search method
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 41-53.

Voir la notice de l'article provenant de la source Math-Net.Ru

Sufficient conditions are found ensuring that the populational genetic algorithm with tournament selection visits a local optimum within polynomial time on average. These conditions are proven to hold for the class of problems with guaranteed local optima, provided that parameters of the algorithm are chosen appropriately. Bibliogr. 17.
Keywords: genetic algorithm, local search, approximate solution. 
@article{DA_2012_19_2_a2,
     author = {A. V. Eremeev},
     title = {Genetic algorithm with tournament selection as a~local search method},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--53},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_2_a2/}
}
TY  - JOUR
AU  - A. V. Eremeev
TI  - Genetic algorithm with tournament selection as a~local search method
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 41
EP  - 53
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_2_a2/
LA  - ru
ID  - DA_2012_19_2_a2
ER  - 
%0 Journal Article
%A A. V. Eremeev
%T Genetic algorithm with tournament selection as a~local search method
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 41-53
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_2_a2/
%G ru
%F DA_2012_19_2_a2
A. V. Eremeev. Genetic algorithm with tournament selection as a~local search method. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 2, pp. 41-53. http://geodesic.mathdoc.fr/item/DA_2012_19_2_a2/

[1] Gnedenko B. V., Kurs teorii veroyatnostei, Nauka, M., 1988, 451 pp. | MR | Zbl

[2] Zagoruiko N. G., “Samoobuchayuschiisya geneticheskii algoritm prognozirovaniya (GAP)”, Iskusstv. intellekt i ekspert. sistemy, 160, Vychisl. sistemy, Novosibirsk, 1997, 3–17

[3] Kitaev A., Shen A., Vyalyi M., Klassicheskie i kvantovye vychisleniya, MTsNMO, CheRo, M., 1999, 192 pp.

[4] Kochetov Yu. A., “Vychislitelnye vozmozhnosti lokalnogo poiska v kombinatornoi optimizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 48:5 (2008), 788–807 | MR | Zbl

[5] Kochetov Yu. A., “Veroyatnostnye metody lokalnogo poiska dlya zadach diskretnoi optimizatsii”, Diskret. matematika i eë prilozheniya, Sb. lektsii molodezhnykh nauchnykh shkol po diskretnoi matematike i eë prilozheniyam, Izd-vo tsentra prikl. issled. pri mekh.-mat. fak. MGU, M., 2001, 84–117

[6] Rutkovskaya D., Pilinskii M., Rutkovskii L., Neironnye seti, geneticheskie algoritmy i nechëtkie sistemy, Goryachaya liniya – Telekom, M., 2006, 452 pp.

[7] Saiko L. A., “Issledovanie moschnosti $L$-nakrytii nekotorykh zadach o pokrytii”, Diskret. optimizatsiya i analiz slozhnykh sistem, Sb. nauch. tr., VTs SO AN SSSR, Novosibirsk, 1989, 76–97

[8] Aarts E. H. L., Lenstra J. K., “Introduction”, Local search in combinatorial optimization, John Wiley Sons Ltd., New York, 1997, 1–19 | MR

[9] Ausiello G., Protasi M., “Local search, reducibility and approximability of NP-optimization problems”, Inf. Process. Lett., 54 (1995), 73–79 | DOI | MR | Zbl

[10] Balas E., Niehaus W., “Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems”, J. Heurist., 4:2 (1998), 107–122 | DOI | MR | Zbl

[11] Droste S., Jansen T., Wegener I., “Upper and lower bounds for randomized search heuristics in black-box optimization”, Theory Comput. Syst., 39:4 (2006), 525–544 | DOI | MR | Zbl

[12] Eremeev A. V., “Modeling and analysis of genetic algorithm with tournament selection”, Proc. Artificial Evolution Conf. (Dunkerque, France, November 3–5, 1999), Lect. Notes Comp. Sci., 1829, Springer-Verl., Berlin, 2000, 84–95 | DOI | MR | Zbl

[13] Eremeev A. V., Reeves C. R., “Evolutionary algorithms in discrete optimization”, Discrete Optimization and Operations Research Conf. (Novosibirsk, June 24–28, 2002), Abstr., IM Press, Novosibirsk, 2000, 40–45

[14] Goldberg D. E., “A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing”, Complex Syst., 4 (1990), 445–460 | Zbl

[15] Holland J., Adaptation in natural and artificial systems, Univ. Michigan Press, Ann Arbor, 1975, 183 pp. | MR

[16] Reeves C. R., “Genetic algorithms for the operations researcher”, INFORMS J. Comput., 9:3 (1997), 231–250 | DOI | Zbl

[17] Rödl V., Tovey C., “Multiple optima in local search”, J. Algorithms, 8 (1987), 250–259 | DOI | MR