Monday, June 24, 2013

An Introduction to Particle Swarm Optimization (PSO) with Applications to Antenna Optimization Problems

I'm in the early stages of research Particle Swarm Optimization (PSO) and applying it to evolving my anti-jamming beamforming antenna arrays. By early, I mean that I've been reading books and articles on PSO. I have not yet written my own PSO codes, nor have I tested any PSO code on my antenna array. With my next antenna array, I hope to do experiments with my own PSO code and compare PSO performance to that of the genetic algorithm (GA) with an interim goal of publishing a conference paper and an end goal of publishing my thesis. In this post, I will give an introductory explanation of how PSO works, and how it applies to antenna optimization.

PSO is a stochastic optimization algorithm developed by computer scientists to solve difficult problems.  (By difficult, computer scientists mean that the problem cannot be easily solved by simpler optimization algorithms like Newton's Method, simplex methods, gradient descent, and/or Least Mean Squares.) Like the GA, the PSO is a population based search algorithm that integrates randomness in a guided search of the parameter / solution space. However, the PSO is modeled after social behaviors instead of "survival of the fittest" mate selection and genetic chromosomal crossovers and mutations.

Think of a swarm of animals (like bees, birds, fish, or even people) searching for a food source. In the beginning of their search, the swarm will be randomly spread out with various positions and velocities as shown below in Figure 1. PSO is a minimization algorithm meaning that it searches for solutions that minimize an objective function. In this example, the blue star represents a minimum that the PSO needs to find. Each particle records its own minimum (i.e., best) solution as well as the globally best solution. One should note that the globally best solution is not necessarily the optimization function's global minimum: It is simple the best solution found by the swarm so far by the current iteration. In other words, the particles communication with each other, as they tell each other where they're located, and the swarm will propagate itself toward the particle closest to the objective function's minimizer (i.e., food source)

Figure 1: Conceptual diagram of PSO in action with a single global minimum (Copyright Jonathan Becker)
As noted, each particle is characterized by both its position in the search space and its current velocity. Technically, a particle's velocity is just a vectorial change in position. However, computer scientists call this quantity a velocity because the time unit is always one iteration. In its original form, Parsopoulos et. al. [1] noted that the PSO had no means of stopping: The swarm would simply oscillate around the minimizer. Paropoulos et. al. later added a linearly decreasing inertia weight to slow the particles' velocities. They found that this caused the swarm to settle on the minimizer as expected.

Of course, PSO would be better suited at multimodal optimization problems that have local minima as well as a global minimum. I give example of how the PSO might behave in minimizing a problem that has two non-equal minima in Figure 2. I've labeled the two minima A and B. At iteration N, the swarm is divided between solutions A and B. How the swarm behaved depends on whether A is the global minimum or if B is the global minimum. In either case, the swarm will eventually migrate towards the global minimum, in theory any way.

Figure 2: PSO example with two non-equal minima (Copyright Jonathan Becker)
I would like to point out another differing quality between PSO and genetic algorithms. (GAs are used in maximization optimization problems, but a minimization optimization problem can be easily converted into a maximum optimization problem.) Suppose that B is the global minimum. You may notice that there are particles at iteration N that are not near B nor A. The GA would simply kill these solutions off, as they would have low fitness function values. However, PSO does not remove particles from the swarm, and particles communicate with each other. The particles not near a minima would move towards the direction of the best solution found so far. Of course, the information might get diluted, as Clerc noted that a given particle might find a better solution at the next iteration and move in a different direction [2].

In the reading stage of my research, I am finding that there are multiple variants of PSO each of which attempts to solve deficiencies that earlier variants possessed. At this stage of my research, I have not decided which PSO variant I will use in solving the anti-jamming beamforming problem, or if I will attempt to create a new variant. What I do know is that I'll want my PSO code to tackle mobile signals (i.e., moving signals of interest and/or moving jammers), so I won't want to use an inertial dampening term that completely diminishes the swarm's searching abilities.

Other researchers have used PSO to optimize antenna designs as well as antenna arrays for focusing electromagnetic energy in the direction of a signal of interest [3 - 5]. The procedure for optimizing antennas with a PSO is similar to the procedure used by the GA to optimize antennas. Except, the objective function is defined with minimization (not maximization) in mind. I list the steps below for optimizing an antenna design using a PSO:

  1. Define the type of antenna that will be optimized: Yagi, log-periodic, helix, custom design, etc.
  2. Define the problem parameters that need to be minimized: antenna gain, impedance matching, antenna physical size, etc.
  3. Define the objective function to be minimized with the problem parameters in mind. For techniques on multiobjective optimization, refer to the text written by Deb [6].
  4. Generate a randomly defined population. Some PSO variants generate a uniformly distributed population, others apply another optimization algorithm (such as simplex) to prime the population before starting the PSO. (Parsopoulos noted that this gives better results overall [1].)
  5. Run the PSO for a predefined number of iterations.
  6. Stop the PSO when a design that meets the design specifications is found or when the maximum number of iterations is run, whichever comes first.
  7. If the final best solution does not meet the design specifications, consider another antenna design by going back to step 1 or relax the problem parameters / specifications in step 2 and rerun the PSO from there.
  8. If the best solution meets the design specifications, fabricate the antenna and test it.
The steps above assume that the antenna designs will be simulated with a computer and then built to be tested for verification. In antenna array optimization in-situ with hardware (i.e., my research), the PSO would be run on a machine (whether computer, FPGA, etc.) while simultaneously optimizing the antenna array hardware. Typically phase shifters and step attenuators settings are set by the optimization algorithm not the antennas themselves. It is possible to adapt a reconfigurable antenna array by adjusting the shapes the antennas or of the array itself, but this is harder (and possibly slower) than adjusting only phase shifters and step attenuators because it involved mechanical mechanisms

In a nutshell, that is how particle swarm optimization works and how one would apply it to antenna optimization problems. In addition, I've listed my reference below for anyone who wants to learn more about PSO and its application towards antenna / antenna array optimization below. There are certainly other references out there, but these would be a good start for learning about PSO and its applications towards antenna optimization.


Best,

Jonathan Becker
ECE PhD Candidate


References:
[1] K. E. Parsopoulos and M. N. Vrahatis, Particle Swarm Optimization and Intelligence: Advances and Applications, Hershey: Information Science Reference, Hershey, PA, 2010.

[2] M. Clerc, Particle Swarm Optimization, ISTE USA, Newport Beach, CA, 2006.


[3] M. Benedetti, G. Oliveri, and A. Massa, "Validation of a smart antenna prototype: model and experiments." In 2009 European Radar Conference, EuRAD 2009. pp. 172–175, September 30 2009 - October 2, 2009.

[4] H. Huang, A. Hoorfar, and S. Lakhani, "A comparitive study of evolutionary programming, genetic algorithms, and particle swarm optimization in antenna design." In 2007 IEEE Antennas and Propagation Society International Symposium, pp. 1609–1612, June 2007.

[5] M. Ohira, A. Miura, M. Taromaru, and M. Ueba, "Efficient gain optimization techniques for azimuth beam/null steering of inverted-F multiport parasitic array radiator (mupar) antenna." IEEE Transactions on Antennas and Propagation, Vol. 60, Num 3, pp. 1352–1361, 2012.

[6] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 2009.