Feb 14, 2011, 09:44 PM
Sink stinks
Joined Apr 2005
4,825 Posts
The visualizations have actually allowed me to improve my code (I believe). Notice in the last video how random the behavior of the swarm seems to be early on in the optimization. This is because they particles are allowed to have a very high speed.

Because of this, I decided to impose a speed limit on the particles. Now, if the particles exceed the speed limit (2% of the total design space / time seems to work well), their speed is reduced to the speed limit but the direction is preserved. With my 2D test function, this seems to improve the ability to find the global optimum with less particles required. Here's a video. Tonight I will be running an airfoil optimization with a speed limit applied to see if it improves the optimization.

 Particle Swarm Visualization (speed limit on particles) (0 min 7 sec)
 Feb 14, 2011, 11:49 PM Registered User United States, KS, Andover Joined Oct 2005 551 Posts Dan, I found some time this evening to work on my swarm optimizer. I've got the framework for the constraints, but I haven't implemented any penalties for violations. I start with a seed airfoil, parameratize it, then work off perturbations of that parameterization. To my surprise, it seems to be working. I'm not letting it go too far, but all the particles seem to be approaching the minimum. Since I'm starting with a seed, I'll need to restart from time to time with the best individual as the new seed. I've built it so that I have a lot of freedom for my individual design points. For example, if I want, I can use a flap for a subset of the design points. Likewise, I've got a fairly general objective function that basically includes everything. I just zero out the weights of what I don't want. This means I can have different objective functions for different design points. I've also included transition locations in the objective. Right now my geometric constraints are limited to t/c, but I need to add max curvature (to prevent really sharp LEs) and something to penalize me for curvature where I may not want it, say if I wanted a flat lower surface for easier building. I'm testing this with a swarm method, but may fall back to the genetic to see how they compare. I also found out pretty early that I needed to limit the velocities.
Feb 15, 2011, 12:00 AM
Sink stinks
Joined Apr 2005
4,825 Posts
Mark,

That sounds very cool, and perhaps a bit more sophisticated than mine. At least, it seems like you have the possibility for more constraints and design features. Once you get yours running the way you want it again maybe we'll do some more comparisons of the two different parameterization methods.

Interestingly, the method still seems to work well even when you don't impose a low speed limit. Without the speed limit the airfoils end up being quite random for the first 10 or 20 iterations, as you saw in the first video I posted on the previous page. I'm not honestly sure if it will work better with a speed limit when many design variables are involved, because there is some benefit to random search behavior, but it will at least make for a much smoother design progression for each particle.

EDIT: I really should be in bed, but here's one more video (3D multimodal function).

 3D PSO Visualization (0 min 9 sec)

And here's an airfoil optimized for Cl = -0.2 to 0.4 at Re = 100k. If you compare this to my other video like it, you'll see the effect of using the speed limit especially in the beginning. This test case did do a little bit better than when I ran the same optimization with no speed limit, although not significantly better.

 PSO airfoil optimization (speed limit on particles) (0 min 9 sec)
Last edited by Montag DP; Feb 15, 2011 at 11:23 AM.
 Feb 15, 2011, 06:36 PM Registered User United States, KS, Andover Joined Oct 2005 551 Posts Dan, You need some music for your videos, maybe "Flight of the Bumblebee." I was up too late, also, but I have to take the opportunities I get. I say the velocity limit had an impact, but I think I also found a small bug at the same time. Honestly, I'm just happy it worked. My method is pretty simple. I use the global and individual best values to steer the swarm. I'm thinking that with it comes to constraints I may just not include any influence of those particles that violate constraints. For example, if one of the particles has the best fitness, either globally or individually, that "best" value will be ignored if that particle also violates a constraint. Not sure if it will work or not. I really need to step back and do some polishing and get things working independently of the optimizer, be it a swarming method or a genetic algorithm. In my first stab at this about a year ago, I had everything hard coded into a single code. That made it hard to try different things. I'm trying to remain as flexible as I can. Mark
Feb 16, 2011, 12:07 AM
Sink stinks
Joined Apr 2005
4,825 Posts
I took your advice and added some music to this one. I have to say I think this one is the coolest. I made a function that moves a "food source" randomly around the design space. The objective function is the distance of each particle from the food source. Like with any optimization, the particles don't know where the "food source" (current optimum point) is, only where the best particle in the swarm is currently.

I had to change a bunch of things to make this work. First, I set each particle's personal-best trust factor (the one that attracts each particle to its personal best location) to 0, since that's not relevant with a moving optimum. I also removed the attraction to the overall best design, since that's also not helpful with a moving optimum, and replaced it with an attraction to the best design for the current iteration. Finally, the inertial multiplier was moved way up. This was just for fun.

 Particle swarm optimization: moving food source (0 min 27 sec)

Your idea to not allow the particles to be attracted to designs that violate constraints early on seems like a good one, and I think that is something I should implement with the speed limit. Otherwise the particles will start swarming in a bad direction simply because it is the best available direction. It would be better for them to just keep going in whatever direction they please until a design that doesn't violate constraints is found.
Last edited by Montag DP; Feb 16, 2011 at 12:38 AM.
 Feb 16, 2011, 07:09 AM Registered User United States, KS, Andover Joined Oct 2005 551 Posts Call me a geek, but that is funny. You should include something like that in your defense.
Feb 16, 2011, 12:06 PM
Sink stinks
Joined Apr 2005
4,825 Posts
Quote:
 Originally Posted by markschaffin Call me a geek, but that is funny. You should include something like that in your defense.
I'd like to, but this whole airfoil optimization thing isn't part of my actual research. It's just for fun / hobby use. I am sending some of the videos to the professor who teaches the optimization class who will probably show some of them in class.

This visualization tool is really useful for making sure things are working right. Here's an example of "selective swarming" that you suggested where the particles move randomly until a good enough design is found. This should work well with the penalty function approach because if a design constraint is violated, the objective function value will be high and particles won't swarm towards that design, even if it happens to be the best found so far.

 Particle Swarm Optimization: Selective swarming (0 min 8 sec)
 Feb 16, 2011, 07:58 PM Registered User United States, KS, Andover Joined Oct 2005 551 Posts How about defining a box that has an edge passing through the global minimum/maximum and use the box edges as a constraint? Will the particles pass through it, i.e. not stop in it, slide along the edges, something else?
Feb 16, 2011, 08:46 PM
Sink stinks
Joined Apr 2005
4,825 Posts
Quote:
 Originally Posted by markschaffin How about defining a box that has an edge passing through the global minimum/maximum and use the box edges as a constraint? Will the particles pass through it, i.e. not stop in it, slide along the edges, something else?
If I tell the particles to honor side constraints, which is what I normally do, they should bounce off the edge initially but lose velocity and converge on the minimum pretty quickly anyway, kind of like a squishy bouncing ball. If you look at some of the particles near the edges in the previous video you'll notice they bounce off the walls but don't always leave the wall with the same speed they hit it (I have it randomized). Other particles which are near the boundary to the side of the minimum should essentially slide along the wall. I'll try making a video of that when I get a chance.
 Feb 16, 2011, 10:14 PM Registered User United States, KS, Andover Joined Oct 2005 551 Posts I am probably not exactly sure what you mean when you say "side" constraint. Here's what I'm getting at. Say we have a minimum allowable thickness for the airfoil. If the particle yields an airfoil that violates this minimum thickness we need to deal with it. We could penalize the objective function. That seems a bit brute force to me, though, as the optimum may be an airfoil with the minimum allowable thickness. We could ignore the fitness value of that particle, which would keep it from attracting others or using it's current location to steer itself, but then again, it may be really close to where we want to go. A couple of thoughts: 1) reverse the direction of the particle, i.e. make the airfoil a bit thicker. 2) move the particle in a direction perpendicular to the current velocity. I'd bet that a hitting the objective function hard would be sufficient. The randomness in the velocity calculation should work in our favor. Mark
Feb 16, 2011, 10:39 PM
Sink stinks
Joined Apr 2005
4,825 Posts
Quote:
 Originally Posted by markschaffin I am probably not exactly sure what you mean when you say "side" constraint. Here's what I'm getting at. Say we have a minimum allowable thickness for the airfoil. If the particle yields an airfoil that violates this minimum thickness we need to deal with it. We could penalize the objective function. That seems a bit brute force to me, though, as the optimum may be an airfoil with the minimum allowable thickness. We could ignore the fitness value of that particle, which would keep it from attracting others or using it's current location to steer itself, but then again, it may be really close to where we want to go. A couple of thoughts: 1) reverse the direction of the particle, i.e. make the airfoil a bit thicker. 2) move the particle in a direction perpendicular to the current velocity. I'd bet that a hitting the objective function hard would be sufficient. The randomness in the velocity calculation should work in our favor. Mark
Mark,

By side constraints I mean physical constraints on the design variables. Since my design variables are the locations of the control points, the side constraints are just the bounds on where I allow them to move. These don't give much useful information about the airfoil like max thickness or anything like that; I just set them to what I think are reasonable levels. For example, if there are four control points on the top surface that may move in the x-direction, each one of them would be relegated to its own 1/4 of the chord length.

Regarding your concern with the penalty function approach for other constraints, it actually does seem to work pretty well. The tests I've been doing lately have a constraint to keep the airfoil within 6% and 10% thickness, and the final result consistently hits that 6% bound, at least within Matlab's standard display precision.

The way I work the penalty function method is for each violated constraint, calculate how much it is violated by, scale the result so that all violated constraints are on roughly the same order of magnitude, add all of these up, and then multiply the result by 10^6. It seems to work pretty well.

Your method seems a little "smarter" but not as simple to implement and I'm not sure if it would actually work better or not. In order to implement it you would have to pass the constraints directly to the optimization algorithm so that it knows when one of them is violated. That's not easy to do if you also want to keep the algorithm generic so it can be used with any problem.

What I could do is make a visualization with a penalty function on designs that include the unconstrained minimum, but make the side constraints much broader. This would put the constrained minimum at the constraint boundary. Then we can see how the swarm behaves near the boundary.

Dan
 Feb 17, 2011, 07:14 AM Registered User United States, KS, Andover Joined Oct 2005 551 Posts In thinking about this (that's all I have time to do right now), using a penalty is the same as ignoring a particle if it's best value violates a constraint. For the way I've done things, if I eventually hit what you are calling a side constraint, I simply use that new design as my seed and start over. This effectively shifts my side constraints or my design space. In your simulations, your optimum is not near your side constraints. My question was what would happen if you put your optimum inside a constrained volume. How stable will the method be? I'm probably not being clear enough, but I'm out of time....
 Feb 17, 2011, 07:38 PM Registered User Joined Feb 2011 12 Posts Hey guys, I'm looking to apply some similar techniques to a 3D problem - human powered vehicle design (three-wheeler recumbent with a fully enclosed fairing). I've got the simulation package working nicely (OpenFOAM - using the 'motorbike' example as a starting point), but I'm in a bit of a quandry about the optimization algorithm to use. I was thinking of writing my own GA, but the time constraints to get a solution are pretty tight (2 months), and the time to simulate per case is about 10-15 minutes (... a very long time, I know ... S ) so I have to get my PC crunching on the problem ASAP. A friend of mine suggested NOMADs (http://www.gerad.ca/nomad/Project/Home.html) as a good out-of-the-box solution (might be useful to you guys too?). Problem is, the algorithm is only efficient up to about 20 parameters... not nearly enough to cover the solution space I'd like to explore. Even with a constrained solution space and some better parametrization, I'd be looking at about 40 variables - the shape of the thing is fairly complex, having to account for not only overall shape in a situation where there is a 'wall' (i.e. the ground) very close by, but also wheel openings (which will likely need some special local treatment) & duct positions. So, I'm looking for any advice on improving the parametrization of the design, and / or whether the particle swarm method is appropriate to problems with a large number of parameters? Thanks
 Feb 17, 2011, 08:08 PM Sink stinks Joined Apr 2005 4,825 Posts Madact, The particle swarm method seems to be good even with a large number of design variables. Just having more design variables doesn't necessarily slow it down, except for in the sense that you may need more particles and/or more iterations to find the optimum for a problem with a large number of design variables, but that is very problem-dependent. It's not like a gradient-based method where you need to estimate as many derivatives as design variables with each iteration. Just to give you a sense of how long it might take, for my airfoil optimization I generally use 35 particles and it takes ~100 - 150 iterations to converge in most cases, but if I decreased the restrictions on the convergence criteria it would easily be less than 100 iterations. The number of function evaluations is (# of iterations)*(# of particles). It's also a very simple method to program. Unfortunately, I can't help you with parameterization. Are you sure that an automated optimization procedure is really needed? The optimization algorithm is really the simplest part of a problem like that. Much more work would go into the parameterization and making sure you can have it interface with your flow solver. I haven't used OpenFOAM, but I can only imagine that making your 3D geometry generation work automatically and automatically creating the mesh for the solver would be no small task. If you don't already have a good start on that, I really doubt you would be able to get it working satisfactorily and also run the optimization in the time frame you have. Perhaps you can use a more traditional design approach?
Feb 17, 2011, 10:21 PM
Sink stinks
Joined Apr 2005
4,825 Posts
Quote:
 Originally Posted by markschaffin In your simulations, your optimum is not near your side constraints. My question was what would happen if you put your optimum inside a constrained volume. How stable will the method be? I'm probably not being clear enough, but I'm out of time....
Mark,

I made a couple of videos to illustrate what happens when you have a constrained problem. The first one applies a penalty function to any design below the dotted line (infeasible space), which is where the unconstrained optimum would be. The second one has the minimum on the side constraint boundary, in which case no penalty function is required. In both cases you can see the particles sliding along the constraint boundary. That should also help explain the difference between a general constraint and a side constraint.

Dan

 Particle swarm constrained optimization (0 min 7 sec)

 PSO: Minimum on side constraint boundary (0 min 7 sec)