Abstract:
Metaheuristics are a set of related ideas that provide a general framework to obtain the approximated solution of combinatorial optimization problems. We present ideas for a new method that we call SN. SN is based on the idea of dividing a given optimization problem into decision subproblems which are easier to solve heuristically. In order to verify the effectiveness of this metaheuristic approach, we developed an algorithm to solve a classic graph theory problem, the Steiner Problem in Graphs. Preliminary results show that the new algorithm is competitive when compared with the best heuristic algorithms known for this problem. © 2001 IEEE.
Registro:
Documento: |
Artículo
|
Título: | A new metaheuristic and its application to the Steiner problems in graphs |
Autor: | Urrutia, S.; Loiseau, I. |
Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, Buenos Aires 1428, Argentina
|
Palabras clave: | Combinatorial optimization; Graph theory; Heuristic algorithms; Approximated solutions; Combinatorial optimization problems; ITS applications; Meta heuristics; Meta-heuristic approach; Metaheuristic; Optimization problems; Steiner problems; Optimization |
Año: | 2001
|
Volumen: | 2001-January
|
Página de inicio: | 273
|
Página de fin: | 281
|
DOI: |
http://dx.doi.org/10.1109/SCCC.2001.972657 |
Título revista: | Proceedings - International Conference of the Chilean Computer Science Society, SCCC
|
Título revista abreviado: | Proc. Int. Conf. Chilean Comput. Sci. Soc. SCCC
|
ISSN: | 15224902
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15224902_v2001-January_n_p273_Urrutia |
Referencias:
- Beasley, J.E., OR-Library: Distributing test problems by electronic mail (1990) Journal of the Operational Research Society, 41, pp. 1069-1072
- Dongarra, J.J., (1995) Performance of Various Computers Using Standard Linear Equations Software, , Working paper. University of Tennessee, Knoxville
- Duin, C.W., Volgenant, A., Reduction tests for the Steiner problem in graphs (1989) Networks, 19, pp. 549-567
- Esbensen, H., Computing near-optimal solutions to the Steiner problems in a graph using a genetic algorithm (1995) Networks, 26, pp. 173-185
- Gendreau, M., Larochell, J.-F., Brunilde, S., A tabu search for the Steiner Tree Problem (1999) Networks, 34, pp. 162-172
- Glover, F., Laguna, M., (1997) Tabu Search, , Kluwer
- Hwang, F.K., Richards, D.S., Steiner Tree Problems (1992) Networks, 22, pp. 55-89
- Karp, R.M., Reducibility among combinatorial problems (1972) Complexity of Computer Computations, , R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York
- Michalewicz, Z., (1999) Genetic Algorithms + Data Structures = Evolutions Programas, , Springer
- Rayward-Smith, V.J., Clare, A., On finding Steiner vertices (1986) Networks, 16, pp. 283-294
- Ribeiro, C.C., De Souza, M.C., Tabu search for the Steiner problem in graphs (2000) Networks, 36, pp. 138-146
- Takahashi, H., Matsuyama, A., An approximate solution for the Steiner problem in graphs (1980) Math. Japonica, 24, pp. 573-577
- Urrutia, S., (2001) SN: Una Nueva Metaheurística, , Tesis de Licenciatura, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
- Winter, P., Steiner problem in networks: A survey (1987) Networks, 17, pp. 129-167
- Winter, P., MacGregor Smith, J., Path-distance heuristics for the Steiner problems in undirected networks (1992) Algorithmica, 7, pp. 309-327
Citas:
---------- APA ----------
Urrutia, S. & Loiseau, I.
(2001)
. A new metaheuristic and its application to the Steiner problems in graphs. Proceedings - International Conference of the Chilean Computer Science Society, SCCC, 2001-January, 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657---------- CHICAGO ----------
Urrutia, S., Loiseau, I.
"A new metaheuristic and its application to the Steiner problems in graphs"
. Proceedings - International Conference of the Chilean Computer Science Society, SCCC 2001-January
(2001) : 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657---------- MLA ----------
Urrutia, S., Loiseau, I.
"A new metaheuristic and its application to the Steiner problems in graphs"
. Proceedings - International Conference of the Chilean Computer Science Society, SCCC, vol. 2001-January, 2001, pp. 273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657---------- VANCOUVER ----------
Urrutia, S., Loiseau, I. A new metaheuristic and its application to the Steiner problems in graphs. Proc. Int. Conf. Chilean Comput. Sci. Soc. SCCC. 2001;2001-January:273-281.
http://dx.doi.org/10.1109/SCCC.2001.972657