A conceptual model for detecting structures in graphs using evolutionary optimization algorithms

“A conceptual model for detecting structures in graphs using evolutionary optimization algorithms” by R. Santana and E. Ponce de León, Institute of Cybernetics. Mathematics and Physics technical report ICIMAF 98-69, CENIA 98-03, (Havana, Cuba), Dec. 1998.

Abstract

Search and identification of structures on graphs have been topics extensively considered in the literature. Different approaches are known that face these problems as functions optimization. Most of them emphasize on the search of a particular structure (e.g. cliques, spanning trees, hamiltonian paths). In the same way, functions are conceived to be optimized using just one method (e.g. gradient, annealing, genetic algorithms.) Here we analyze the convenience of defining families of functions to be used in the search of different structures. Starting from the identification of a dissection on a graph we propose a family of functions that shows good results in the search of a wide set of structures on graphs. A hierarchy that associates the function definition to a constraint addition process is introduced. We also deal with the question of an optimal representation for the solutions space. Finally we present the results obtained using two different optimization algorithms. A heuristic hill-climbing and a population based search method, which are utilized to deal with the multi-objective character of our constraint optimization problem.

BibTeX entry:

@techreport{Santana_and_Ponce:1998,
   author = {R. Santana and E. Ponce de Le{\'o}n},
   title = {A conceptual model for detecting structures in graphs using
	evolutionary optimization algorithms},
   institution = {Institute of Cybernetics, Mathematics and Physics},
   number = {ICIMAF 98-69, CENIA 98-03},
   address = {Havana, Cuba},
   month = dec,
   year = {1998},
   issn = {0138-8916}
}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.