Step one was to understand how I wanted to implement my algorithm. I primarily focused on Genetic Algorithms at first as I personally felt it would involve more thought than PSO (and I was right, to an extent). A big issue with GAs that I discovered throughout my research is that most of the algorithms absolutely LOVE to converge on a locally optimal solution, rather than the globally optimal one. Luckily, this wasn’t as big of an issue for my project since I had no intention of making an algorithm that will find the BEST solution for a circuit design problem: I’m not even sure we’ll ever get to that point. Far too many variables. What I wanted was for my program to spit out a circuit that a designer could start with rather than spending a lot of man-hours trying to converge onto the same starting point. Anyways… I ended up implementing a variant of GA with elitism that bases itself off of a bee colony- I ended up calling it QBGA (Queen Bee Genetic Algorithm). Essentially you have a queen bee and a multitude of “drone” bees that have randomly generated “genes”. Every generation, each drone mates with the queen and produces two virgin queen bees with a sample of genes from both parents (explained graphically below). The drone is then killed. The two new “virgin queens” then compete and the best one survives. Once this process is completed for each drone, the new virgin queens then enter another tournament round until only one remains. This virgin then attempts to usurp the current queen bee’s throne and either succeeds, becoming the new queen, or fails and simply dies off. This method, below in graphical form, allows for a very large solution space to be explored (because of all the random behavior) but still maintains a connection to the best solution found so far via the queen bee.
A bee’s genes consisted of transfer function coefficients which could then be used to calculate the phase margin, gain, etc (which, unsurprisingly, I used as my fitness function). The Implementation I quickly discovered that my original plan had a few problems with convergence. In order to alleviate this, I implemented a parabolic fitness function with penalties applied if a solution exceeds some predefined bounds whose equation is shown below where is a coefficient for a fitness variable .
is a normalization function and is a penalty function. I also implemented age behavior for the queen bee. Essentially, as the queen maintains her position as queen of the hive, the gene mutation rate begins to increase in order to try and prevent convergence on a local optima. If, however, the queen is already the global-best solution, the extra mutation will have no impact on the solution so it could ONLY help. As it turns out, it doubled the accuracy of the algorithm (more details in my paper). Below is the comparison between this QBGA implementation and three different forms of PSO (none of which I’ve covered in this post). The three PSO algorithms are a constriction PSO, Chaotic Decreasing Intertial Weight (CDIW) and Chaotic Random Intertial Weight (CRIW). More information can be found in my paper (surprise!).