View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Creating UML diagrams with simmulated annealing

One method I found effective for creating a UML diagram was to use simmulated annealing.

Simmulated Annealing

Simulated annealing evolves a better way to do something. A uml diagram evolves a better way to show itself by randomly mutating, selecting the "most fit" diagram based on certain constraints, and after a while comes up with a optimal diagram.

The graph

You can represent a UML Diagram with a graph. A UML class is a node and the node has coordinates. The edges are relationships and also have coordinates where they meet the UML class.

The Population

As in evolution, you have a population that struggles to survive. The most fit survives. This population is made up of graphs. Each previous generation creates mutated offspring and all the diagrams are compared using a fitness function. The most fit diagrams are selected based on several things.

The Mutations

I found it effective to randomly mutate the positions of the UML classes, the positions of the edge-node junctions, and to flip the edge-node junctions to the opposite side. Using random probability, the node positions mutate about 50% of the time, the edge junctions flip about 45% of the time, and they move about 5% of the time. This creates a slightly different (and possibly better) representation of the diagram.

The Fitness Function

This is the most important part of the algorithm. The fitness function tells how fit a diagram is. I counted long distances between related classes, overlapping classes, edge crossing edges, edges crossing classes, and subclasses higher than superclasses against the overall fitness. Each part is scaled and given a certain weight as to how "unfit" the characteristic is. The parts that gave trouble were the collision detection for edge crossings and class overlaps.
To tell if two edges cross, treat their junction points like vectors. Take the cross product of one vector of a edges junction points and each junction point of the other edge. If the sign of both cross products is different, then they cross. As far as the classes go, they can be represented by the class Rectangle and LineSegment provided in visualworks.
They both have a function which takes in a Rectangle object and tells you whether or not they overlap.

Local Maxima

Unfortunately, Smalltalk doesn't have a class for a standard distribution which you need to get good results every time. If you use your own probabilities instead of a standard distribution, you may get stuck in local maximums of fitness, where there are optimal solutions, but you find yourself stuck at a sub-optimal solution with nowhere "up" to go. This can be corrected by certain AI algorithms that won't get stuck in local maxima, but thats beyond the scope of this page (and my current knowledge :-) ).