Graph design using knowledge-driven, self-adaptive multi-objective evolutionary graph algorithms

Abstract

Επιπλέον, αξιοποιούμε τις προτεινόμενες μεθόδους για την επίλυση ενός πρακτικού ζητήματος. Συγκεκριμένα, αναπτύσσουμε ένα σύστημα το οποίο προσφέρει αξιόπιστες συστάσεις (recommendations) σε ευρωπαϊκούς οργανισμούς για καινούριες συνεργασίες. Για να το επιτύχουμε αυτό ομαδοποιούμε τους οργανισμούς που έχουν συμμετάσχει σε έργα που χρηματοδοτήθηκαν από την Ευρωπαϊκή Ένωση στο πλαίσιο του προγράμματος Horizon 2020. Στην συνέχεια, προτείνουμε μια μέθοδο που αναλύει τα αποτελέσματα της ομαδοποίησης για να εξάγει πιθανές συνεργασίες. Οι οργανισμοί και οι ερευνητές μπορούν να χρησιμοποιήσουν το σύστημά μας για να για να εντοπίσουν νέους συνεργάτες. Από όσο γνωρίζουμε, το σύστημα μας είναι το πρώτο που προσφέρει τέτοιες υπηρεσίες στην κοινότητα.

Optimal Graph Design is a problem frequently occurring in several common applications ranging from designing communication and transportation networks to discovering new drugs. More often than not the graphs to be designed need to satisfy multiple, conflicting, objectives e.g. total length, complexity or other shape and property limitations. In addition to problem specific criteria, the methods proposed to solve the problem need to consider several issues related to the representation of the solutions and the manipulation of graphs. These graph-structure specific issues coupled with the multi-objective nature of applied OGD form a challenging problem of increased complexity with wide applications in several research fields. Our research proposes, MEGA, an algorithmic framework for solving the problem of multi-objective optimal graph design for labeled, undirected graphs. The method uses multi-objective evolutionary graphs, a graph-specific meta-heuristic optimization technique that combines evolutionary algorithms with graph theory and local search techniques exploiting domain-specific knowledge, to efficiently explore the feasible search space and obtain multiple equivalent compromising solutions. The algorithm introduces a novel niching mechanism that takes into account both parameter and objective space solution diversity. Moreover, the method implements a self-adaptive approach to control and ensure appropriate local search use. In the experimental section we present results for the problem of designing molecules satisfying multiple pharmaceutically relevant objectives. The results suggest that the method can provide a variety of valid, interesting graph solutions. In comparisons with commonly used algorithms, MEGA is found to produce statistically significant better results.