Prev: deploy tool in matlab 2010
Next: Having problems with the convolution theorem on power spectrum vs autocorrelation
From: Jim Kurdzo on 3 Aug 2010 02:25
I am attempting to only create population members which are within the borders of an odd shape; for instance, a state. The members each have, say 10 variables; the variables alternate x- and y-coordinates, meaning I have 5 definitive locations defined. The member may look something like this:

x = [-100.0 30.0 -98.7 31.2 -99.4 33.1 -101.3 30.5 ......] and so on

I have been using a custom creation function to make sure that each location is within the bounds of a state, by testing each point using inpolyogn and re-generating if it is not within the bounds. I generate the polygon of the state(s) by using the mapping toolbox. This has become increasingly inefficient, and I am beginning to believe it is defeating the purpose of how the genetic algorithm is supposed to work. Shouldn't I let the default creation function simply operate within those bounds?

So, what I think may be a better way to do this is to define some type of constraint (using the nonlcon spot in the ga call?). I am not sure how I could program this, and if I could, how to make it more efficient than a "guess and check" method. I am a bit unclear as to how exactly the nonlinear constraints work, and to complicate matters, my variable list is not the easiest method in the world for making a constraint.

One other piece is that I need to generate these locations only to the tenths place (as seen in the example of x above).

Here is what I've done so far... it doesn't seem to work.


function [c, ceq] = ok_constraint(x0t,vars,lonOK,latOK)

c = [];
in(1,1:vars/2) = zeros;
remx(1,1:vars/2) = zeros;
remy(1,1:vars/2) = zeros;

for i = 1:vars/2
in(i) = inpolygon(x0t((2*i)-1),x0t(2*i),lonOK,latOK);
remx(i) = rem(x0t((2*i)-1),.1);
remy(i) = rem(x0t(2*i),.1);
end

ceq = [(vars/2) - sum(in);
sum(remx);
sum(remy)];


The first constraint is supposed to keep the points in the state, and the 2nd and 3rd constraints are meant to keep the points divisible by .1. I get strange values between about -2 and +2 for my members, so clearly this isn't right (oh, and they aren't divisible by .1 either).

It seems almost like 'constraint' is not the way I want to do this... more like I want non-linear 'bounds' instead. The way the constraint is designed (either =0 or <=0) does not seem to work with what I'm looking to do. Am I misunderstanding the difference between constraint and bound? And should I just do this via creation function?

Any help would be greatly appreciated.
From: Alan Weiss on 3 Aug 2010 14:29
It is difficult for me to understand what you are really trying to do.
You didn't say why you want to use ga, or what you are optimizing.

In any case, nonlinear constraints are almost certainly not the way to
go for your problem for initial point generation. You would need to be
able to define a function
c(x)
which gives negative values inside your feasible region, zero on the
border, and positive values on the infeasible region. Not easy to define
such a function and make it continuous.

It is not a bad idea to take random integer points in some range, divide
them by 10, and then discard infeasible points. But I really don't see
what you are going to do to ensure that points remain inside the
feasible region as the algorithm progresses. For that, you would need to
use a nonlinear constraint function, which will take some work to
define. And are you 100% sure you need your points to be multiples of
1/10 during the solver run?

Perhaps you can define the nonlinear constraint as the minimum distance
to any boundary, where the distance is negative for feasible points and
positive for infeasible points. I am not sure how you would calculate
such a distance.

I am also unsure why you want to use ga instead of patternsearch.

Good luck,

Alan Weiss
MATLAB mathematical toolbox documentation

On 8/3/2010 2:25 AM, Jim Kurdzo wrote:
> I am attempting to only create population members which are within the
> borders of an odd shape; for instance, a state. The members each have,
> say 10 variables; the variables alternate x- and y-coordinates, meaning
> I have 5 definitive locations defined. The member may look something
> like this:
>
> x = [-100.0 30.0 -98.7 31.2 -99.4 33.1 -101.3 30.5 ......] and so on
>
> I have been using a custom creation function to make sure that each
> location is within the bounds of a state, by testing each point using
> inpolyogn and re-generating if it is not within the bounds. I generate
> the polygon of the state(s) by using the mapping toolbox. This has
> become increasingly inefficient, and I am beginning to believe it is
> defeating the purpose of how the genetic algorithm is supposed to work.
> Shouldn't I let the default creation function simply operate within
> those bounds?
>
> So, what I think may be a better way to do this is to define some type
> of constraint (using the nonlcon spot in the ga call?). I am not sure
> how I could program this, and if I could, how to make it more efficient
> than a "guess and check" method. I am a bit unclear as to how exactly
> the nonlinear constraints work, and to complicate matters, my variable
> list is not the easiest method in the world for making a constraint.
>
> One other piece is that I need to generate these locations only to the
> tenths place (as seen in the example of x above).
>
> Here is what I've done so far... it doesn't seem to work.
>
>
> function [c, ceq] = ok_constraint(x0t,vars,lonOK,latOK)
>
> c = [];
> in(1,1:vars/2) = zeros;
> remx(1,1:vars/2) = zeros;
> remy(1,1:vars/2) = zeros;
>
> for i = 1:vars/2 in(i) = inpolygon(x0t((2*i)-1),x0t(2*i),lonOK,latOK);
> remx(i) = rem(x0t((2*i)-1),.1);
> remy(i) = rem(x0t(2*i),.1);
> end
>
> ceq = [(vars/2) - sum(in);
> sum(remx);
> sum(remy)];
>
>
> The first constraint is supposed to keep the points in the state, and
> the 2nd and 3rd constraints are meant to keep the points divisible by
> .1. I get strange values between about -2 and +2 for my members, so
> clearly this isn't right (oh, and they aren't divisible by .1 either).
>
> It seems almost like 'constraint' is not the way I want to do this...
> more like I want non-linear 'bounds' instead. The way the constraint is
> designed (either =0 or <=0) does not seem to work with what I'm looking
> to do. Am I misunderstanding the difference between constraint and
> bound? And should I just do this via creation function?
>
> Any help would be greatly appreciated.

From: Jim Kurdzo on 3 Aug 2010 15:47
I'm using ga to attempt to find a global minimum. I am doing a radar coverage study using circles, and I am trying to maximize coverage for a minimal cost. I change the number of radars iteratively, and attempt to get a score for each iteration. This can then be used to develop cost-benefit fields. As far as why I want to use ga, I'm already pretty far down that road and I'm reluctant to change so late in the game, although I'd be interested in looking at other methods at some point (just not at this time).

You mentioned that it's a bad idea to use nonlinear constraints for initial point generation. By initial, did you think I meant just the first generation? I basically just want to constrain my options within the algorithm to only allow points inside the boundaries of a state, and I'm trying to find out if doing so via the creation function is the best way to go about this, or if I should be trying to do a nonlinear constraint instead.

The most basic way to ask the question is: if I use a custom creation function that will only create points inside my boundary (the state), is that defeating the purpose of the ga? Or by using one of the MATLAB mutation and crossover functions, will that still effectively allow the ga to work properly?

I am getting results using this method (the creation function), but they aren't always optimal; the basic idea works, aka, my fitness function continues to allow the score to get better, and the radars are only within the state... but I'm wondering if I can do this better.

Hope this helps...
From: Alan Weiss on 5 Aug 2010 07:35
Thanks for explaining your procedure. I did misunderstand, and thought
you were looking at something just for initial point generation.

If you want to try using a nonlinear constraint function along with
built-in crossover and mutation functions, then I suggest you try to use
a function designed to operate as in my previous post:

"Perhaps you can define the nonlinear constraint as the minimum distance
to any boundary, where the distance is negative for feasible points and
positive for infeasible points. I am not sure how you would calculate
such a distance."

On the face of it, your current method looks OK to me. But, like you, I
don't know whether there might be some benefit to using a nonlinear
constraint.

Good luck,

Alan Weiss
MATLAB mathematical toolbox documentation

On 8/3/2010 3:47 PM, Jim Kurdzo wrote:
> I'm using ga to attempt to find a global minimum. I am doing a radar
> coverage study using circles, and I am trying to maximize coverage for a
> minimal cost. I change the number of radars iteratively, and attempt to
> get a score for each iteration. This can then be used to develop
> cost-benefit fields. As far as why I want to use ga, I'm already pretty
> far down that road and I'm reluctant to change so late in the game,
> although I'd be interested in looking at other methods at some point
> (just not at this time).
>
> You mentioned that it's a bad idea to use nonlinear constraints for
> initial point generation. By initial, did you think I meant just the
> first generation? I basically just want to constrain my options within
> the algorithm to only allow points inside the boundaries of a state, and
> I'm trying to find out if doing so via the creation function is the best
> way to go about this, or if I should be trying to do a nonlinear
> constraint instead.
>
> The most basic way to ask the question is: if I use a custom creation
> function that will only create points inside my boundary (the state), is
> that defeating the purpose of the ga? Or by using one of the MATLAB
> mutation and crossover functions, will that still effectively allow the
> ga to work properly?
>
> I am getting results using this method (the creation function), but they
> aren't always optimal; the basic idea works, aka, my fitness function
> continues to allow the score to get better, and the radars are only
> within the state... but I'm wondering if I can do this better.
>
> Hope this helps...

From: Jim Kurdzo on 5 Aug 2010 19:28
Glad to hear it... I actually found this documentation (which I had viewed months ago): http://www.mathworks.com/support/solutions/en/data/1-10PDHC/

That describes integer programming, but it can also be adapted to test whether the points are within a state boundary. I had forgotten about this example, and was a bit worried that making such restrictive conditions in both the creation and mutation functions would potentially be limiting my results. I've gotten things working pretty well now with a setup similar to that document, and all seems to be well. I think the coding of a nonlinear constraint would probably only result in modest speed increases, but very possibly results that aren't much better than what I am getting now.

Thanks for your replies!
 | 
Pages: 1
Prev: deploy tool in matlab 2010
Next: Having problems with the convolution theorem on power spectrum vs autocorrelation