Using Generic Algorithms to Layout Circuit Boards

Figure 1 - Parts layout of a typical circuit board

The UML design for this particular Algorithm is shown below in a WithClass 2000 UML diagram

(Click for bigger image)

Figure 2 - WithClass UML Diagram of Layout Algorithm (Reverse engineered with WithClass 2000)

The classes implementing the Genetic Algorithm consist of the Population, Genome, andListGenome classes.  The Node class represents an electronic component on the board. The Node has position and size attributes to indicate its position on the circuit board and it has a ConnectingNode collection that holds all of the components to which it is wired.   The Genomes of this algorithm consist of a list of integers representing a N x N grid of relative positions.  The first integer represents the upper-left hand corner and the last integer represents the lower right hand corner.  Each integer can be any number representing the node at a particular position.  For example:

The Genome   1 4 3 5 9 2 7 8 6 11 14 10 12 16 15 13  would look like the following in an N x N grid:

Figure 3 - Genome Representation in 2 dimensions

We use the method TranslateNodeSetPositions to handle this transformation from array to component grid.  The method TranslateNodeSetPositions in the ListGenome class translates the Genome array of integers into a set of nodes relatively position in a 2d grid as shown in figure 3.  Once we have a node 2d spacial representation of our Genome, we can now use this in our fitness function to determine the distance between connected nodes for every node.  By summing all of the connection distances between nodes, we can come up with a single  number representing the fitness of our particular gene.

The TranslateNodeSetPositions method of the ListGenome is shown below:

Listing 1 - Translating the Genome String of Numbers into a 2d Grid of Nodes Placed on the Grid

public static void TranslateNodeSetPositions(ListGenome g)
{// first we need to translate the Gene array into node positionsint currentX = 0;int currentY = 0;int maxHeight = 0; // go through each item in the array and set the node collection in the form// to the relative position represented by the Genome Arrayfor (int i = 0; i < Population.kXDimension ; i++)
{for (int j = 0; j < Population.kYDimension ; j++)
{// set the particular node specified by the Genome Item to the relative position on the 2D gridNode currentNode = ((Node)Form1.Nodes[(int)g.TheArray[i*Population.kYDimension + j]]);
currentNode.X = currentX;
currentNode.Y = currentY;
currentX += currentNode.Width + 10; // now advance to next X positionif (currentNode.Height > maxHeight)
maxHeight = currentNode.Height;
}// advance the Y PositioncurrentY += maxHeight + 10;
currentX = 0;
maxHeight = 0; // reset max height}
}

Now that we have the Node Positions set, we can calculate the fitness based on the distances to connected nodes.  This is accomplished using the CalculateSumNodeDistance method of the ListGenome class.  This method also weights the Sum if duplicate nodes are found in the Genome to discourage duplicate nodes.  Note that a larger sum is a poorer fitness:

Listing 2 - Calculate the Sum of the Distances between connected nodes to produce a fitness

public float CalculateSumNodeDistance()
{
TranslateNodeSetPositions(this);// Now we can calculate sum of the distanceslong sum = 0;foreach (Node n in Form1.Nodes)
{
sum += n.SumOfSquareNodeConnections();
} // check for unique nodesint[] histogram = new int[Population.kLength];foreach (int val in TheArray)
{
histogram[val]++;
}foreach (int val in histogram)
{// in any non unique number weight the sum heavilyif (val > 1)
sum += sum*val*val;
}// compute the fitness of the Genome by inverting the sum (add a small value so we never get the 0 divisor error)return 1/((float)sum + .0001f);
}

That's all there is to the Genetic Algorithm.  All we have to do now is set up a sample node set with connections to various nodes.  Our first node set is a simple set of 16 nodes that connect one to another:

Listing 3 - Set up an initial set of nodes with uninitialized positions and connect them together

protected void InitializeNodePopulation0()
{// create 16 nodes and add them to the node collectionNode node1 = new Node(0, 10, 50, 60, "1");
Nodes.Add(node1);
Node node2 = new Node(0, 10, 50, 60, "2");
Nodes.Add(node2);
Node node3 = new Node(0, 10, 50, 60, "3");
Nodes.Add(node3);
Node node4 = new Node(0, 10, 50, 60, "4");
Nodes.Add(node4);
Node node5 = new Node(0, 10, 50, 60, "5");
Nodes.Add(node5);
Node node6 = new Node(0, 10, 50, 60, "6");
Nodes.Add(node6);
Node node7 = new Node(0, 10, 50, 60, "7");
Nodes.Add(node7);
Node node8 = new Node(0, 10, 50, 60, "8");
Nodes.Add(node8);
Node node9 = new Node(0, 10, 50, 60, "9");
Nodes.Add(node9);
Node node10 = new Node(0, 10, 50, 60, "10");
Nodes.Add(node10);
Node node11 = new Node(0, 10, 50, 60, "11");
Nodes.Add(node11);
Node node12 = new Node(0, 10, 50, 60, "12");
Nodes.Add(node12);
Node node13 = new Node(0, 10, 50, 60, "13");
Nodes.Add(node13);
Node node14 = new Node(0, 10, 50, 60, "14");
Nodes.Add(node14);
Node node15 = new Node(0, 10, 50, 60, "15");
Nodes.Add(node15);
Node node16 = new Node(0, 10, 50, 60, "16");
Nodes.Add(node16); // connect the nodes one after another 1-->2-->3-->4--->5-->6-->etc.node1.ConnectNode(node2);
node2.ConnectNode(node3);
node3.ConnectNode(node4);
node4.ConnectNode(node5);
node5.ConnectNode(node6);
node6.ConnectNode(node7);
node7.ConnectNode(node8);
node8.ConnectNode(node9);
node9.ConnectNode(node10);
node10.ConnectNode(node11);
node11.ConnectNode(node12);
node12.ConnectNode(node13);
node13.ConnectNode(node14);
node14.ConnectNode(node15);
node15.ConnectNode(node16);
}

When we run the genetic algorithm and display the best gene after 3000 generations we get the following output to the Form shown in Figure 4.  As you can see, the healthiest Genomes produced a Node layout with the shortest distance between connected nodes.

Figure 5 - Node Layout after 3000 generations

Although we had a nice result here, generations don't always produce a perfect result after convergence, but its still pretty good as shown in Figure 5:

Best Genome after 3000 Generations
13 12 11 16 1 14 15 10 2 5 6 9 3 4 7 8 -->1.260784E-05

Figure 6 - Another Node Layout produced on the same Node Set

To further illustrate the power  of GA in laying out nodes, we came out with a few other initial node scenarios.  The next scenario connects all nodes to a central node (Node 8).  Although this layout is fairly obvious, it is still pretty cool to see the computer come up with the answer.  Here is the initial Node Connections in Code:

Listing 4 - Connecting all nodes to a central node

node1.ConnectNode(node8);
node2.ConnectNode(node8);
node3.ConnectNode(node8);
node4.ConnectNode(node8);
node5.ConnectNode(node8);
node6.ConnectNode(node8);
node7.ConnectNode(node8);
node9.ConnectNode(node8);

After running for 3000 generations, we produce the star configuration we would expect from a central node as shown in Figure 7

Best Genome after 3000 Generations
2 7 1 10 4 8 3 12 9 5 6 15 16 14 13 11 -->1.960784E-05

Figure 7 - Node configuration for central node placement

For the last experiment, we connected two of the nodes (node #1 and node #16)  each to 4 other nodes as shown in listing 5:

Listing 5 - Two centralized nodes each connected to 4 other nodes

node1.ConnectNode(node2);
node1.ConnectNode(node3);
node1.ConnectNode(node4);
node1.ConnectNode(node5); node16.ConnectNode(node12);
node16.ConnectNode(node13);
node16.ConnectNode(node14);
node16.ConnectNode(node15);

This run of 3000 generations produces two spider connections centered around the two nodes in question (1 and 16) as shown in Figure 8.

Best Genome after 3000 Generations
9 6 5 8 11 4 1 3 15 16 12 2 13 14 10 7 -->2.427185E-05

Figure 8 - two central nodes each with 4 connections

Conclusion

Genetic Algorithms are very powerful tools for helping solve optimization problems. Laying out PC boards is certainly one practical example of how to use Genetic Algorithms to solve what is normally a very difficult problem to solve in your head.  I suspect the user can  improve upon the fitness function a bit by measuring the shortest distance between node corners instead of the connections between the center of the nodes. You can also play with different node widths and node heights and try the algorithm to see if it can handle the different component sizes such as for a large IC or a small resistor.  The code in this project can also be expanded to handle nodes in 3 dimensions. The sky is the limit, it just depends on what your imagination lays out for you in .NET.