Optimització per mitjà d'algoritmes genètics- de la projecció de grafs en dues dimensions

Abstract

La projecció de grafs és una disciplina complexa que s'aplica en àmbits molt diversos. La qualitat d'una projecció és pot mesurar quantitativament en funció d'unes determinades convencions gràfiques però també influeixen el context, el propòsit i, en certa manera, un component subjectiu, el que fa que no hi hagi un procés vàlid i universal per a la generar una projecció d'un graf determinat. El treball procura afrontar aquest repte considerant totes les vessants des de les que es pot avaluar la bondat d'una projecció. Així, el objectiu principal ha estat el de desenvolupar un sistema que, donat un graf d'entrada, sigui capaç de generar una projecció òptima (suficientment bona) del graf en dues dimensions. L'adequació al context de la projecció es realitza per mitjà de parametritzacions del sistema

La proyección de grafos es una disciplina compleja que se aplica en ámbitos muy diversos. La calidad de una proyección es puede medir cuantitativamente en función de unas determinadas convenciones gráficas pero también influyen el contexto, el propósito y, en cierto modo, un componente subjetivo, el que hace que no haya un proceso válido y universal para la generar una proyección de un grafo determinado. El trabajo procura afrontar este reto considerando todas las vertientes desde las que se puede evaluar la bondad de una proyección. Así, el objetivo principal ha sido lo de desarrollar un sistema que, dado un grafo de entrada, sea capaz de generar una proyección óptima (suficientemente buena) del grafo en dos dimensiones. La adecuación al contexto de la proyección se realiza por medio de parametrizaciones del sistema.

The projection of graphs is a complex discipline that applies in very diverse fields. The quality of a projection can be measured quantitatively in function of certain graphic conventions but also influence the context, the purpose and, in a way, a subjective component, which makes that there is not a valid and universal process to generate a projection Of a given graph. The work tries to face this challenge considering all the slopes from which the goodness of a projection can be evaluated. Thus, the main objective has been to develop a system that, given an input graph, is capable of generating an optimal (good enough) projection of the graph in two dimensions. The adaptation to the context of the projection is done by means of parameterizations of the system.