Geodesic
A fully polynomial randomized approximation scheme based on an evolutionary algorithm
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 3-17.

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

A fully polynomial randomized approximation scheme is proposed on the basis of an evolutionary algorithm for discrete optimization problems satisfying the conditions of existense of fully polynomial randomized approximation schemes due to Woeginger. Bibliogr. 24.
Keywords: evolutionary algorithm, approximation solution, approximation scheme, dynamic programming, randomization. 
@article{DA_2010_17_4_a0,
     author = {A. V. Eremeev},
     title = {A fully polynomial randomized approximation scheme based on an evolutionary algorithm},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--17},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_4_a0/}
}
TY  - JOUR
AU  - A. V. Eremeev
TI  - A fully polynomial randomized approximation scheme based on an evolutionary algorithm
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 3
EP  - 17
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_4_a0/
LA  - ru
ID  - DA_2010_17_4_a0
ER  - 
%0 Journal Article
%A A. V. Eremeev
%T A fully polynomial randomized approximation scheme based on an evolutionary algorithm
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 3-17
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_4_a0/
%G ru
%F DA_2010_17_4_a0
A. V. Eremeev. A fully polynomial randomized approximation scheme based on an evolutionary algorithm. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 3-17. http://geodesic.mathdoc.fr/item/DA_2010_17_4_a0/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Eremeev A. V., O svyazi dinamicheskogo programmirovaniya i mnogokriterialnykh evolyutsionnykh algoritmov, Preprint, Izd-vo Omskogo gos. un-ta, Omsk, 2008, 20 pp.

[3] Kovalev M. Ya., Shafranskii Ya. M., “Postroenie $\varepsilon$-priblizhennykh algoritmov optimizatsii funktsii na posledovatelno konstruiruemykh mnozhestvakh”, Zhurn. vychisl. matematiki i mat. fiziki, 26:7 (1986), 1006–1018 | MR | Zbl

[4] Moiseev N. N., Ivanilov Yu. P., Stolyarova E. M., Metody optimizatsii, Nauka, M., 1978, 352 pp.

[5] Norenkov I. P., “Evristiki i ikh kombinatsii v geneticheskikh metodakh diskretnoi optimizatsii”, Informatsionnye tekhnologii, 1999, no. 1, 2–7

[6] Beyer H.-G., Schwefel H.-P., Wegener I., “How to analyse evolutionary algorithms”, Theor. Comp. Sci., 287:1 (2002), 101–130 | DOI | MR | Zbl

[7] Chauhan S. S., Eremeev A. V., Romanova A. A., Servakh V. V., Woeginger G. J., “Approximation of the supply scheduling problem”, Oper. Res. Lett., 33:3 (2005), 249–254 | DOI | MR | Zbl

[8] Doerr B., Eremeev A., Horoba C., Neumann F., Theile M., “Evolutionary algorithms and dynamic programming”, Proc. Genetic Evolutionary Computation Conf. (GECCO), ACM Press, New York, 2009, 771–777

[9] Friedrich T., Hebbinghaus N., Neumann F., He J., Witt C., “Approximating covering problems by randomized search heuristics using multi-objective models”, Proc. Genetic Evolutionary Computation Conf. (GECCO), ACM Press, New York, 2007, 797–804

[10] Giel O., Wegener I., “Evolutionary algorithms and the maximum matching problem”, Proc. Symp. Theor. Aspects Comput. Sci. (STACS), Springer-Verl., Berlin–Heidelberg–New York, 2003, 415–426 | MR | Zbl

[11] Held M., Karp R. M., “A dynamic programming approach to sequencing problems”, J. SIAM, 10 (1962), 196–210 | MR | Zbl

[12] Ibarra O. H., Kim C. E., “Fast approximation algorithms for the knapsack and sum of subset problems”, J. ACM, 22:4 (1975), 463–468 | DOI | MR | Zbl

[13] Koza J. R., Genetic programming, v. II, Automatic discovery of reusable programs (complex adaptive systems), MIT Press, Cambridge, MA, 1994, 746 pp. | Zbl

[14] Michalewicz Z., Genetic algorithms + data structures = evolution programs, Springer-Verl., Berlin–Heidelberg–New York, 1996, 387 pp. | MR | Zbl

[15] Neumann F., Reichel J., Skutella M., “Computing minimum cuts by randomized search heuristics”, Proc. Genetic Evolutionary Computation Conf. (GECCO), ACM Press, New York, 2008, 779–786

[16] Neumann F., Wegener I., “Randomized local search, evolutionary algorithms, and the minimum spanning tree problem”, Theor. Comput. Sci., 378:1 (2007), 32–40 | DOI | MR | Zbl

[17] Rechenberg I., Evolutionsstrategie: optimerung technischer Systeme nach prinzipen der biologischen Evolution, Formann–Holzboog Verl., Schtuttgart, 1973, 170 pp.

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

[19] Reeves C. R., Rowe J. E., Genetic algorithms: principles and perspectives, Kluwer, Norwell, MA, 2002, 332 pp. | MR

[20] Reichel J., Skutella M., “Evolutionary algorithms and matroid optimization problems”, Proc. Genetic Evolutionary Computation Conf. (GECCO), ACM Press, New York, 2007, 947–954

[21] Rudolph G., “Finite Markov chain results in evolutionary computation: a tour d'horizon”, Fundam. Inform., 35:1–4 (1998), 67–89 | MR | Zbl

[22] Scharnow J., Tinnefeld K., Wegener I., “The analysis of evolutionary algorithms on sorting and shortest paths problems”, J. Math. Model. Algorithms, 3 (2004), 349–366 | DOI | MR | Zbl

[23] Theile M., “Exact solutions to the travelling salesperson problem by a population-based evolutionary algorithm”, Proc. European Conf. Evolutionary Computation Combinatorial Optimisation (EvoCOP), Lect. Notes Comput. Sci., 5482, Springer-Verl., Berlin–Heidelberg–New York, 2009, 145–155

[24] Woeginger G. J., “When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?”, INFORMS J. Computing, 12:1 (2000), 57–74 | DOI | MR | Zbl