Constraining number of active bits in GA solution

Hi,

I am trying to build a discrete selection optimizer using bitstring optimization with the ga that allows me to create a 40 bit long input, but constrain the number of active bits within the string to some subset (say, no more than 10). The 40 bit long input is used as a selector to choose from among 40 separate data vectors to be incorporated into the actual objective calculation, and my problem is to optimize which of the vectors can be selected with the constraint of only being allowed to use a limited subset.

I can't use the nonlcon function to impose the constraint because it won't allow me to use a bitstring variable inside of it, so something simple like c=sum(bitstring x)-nMaxNumber isn't allowed.

I suppose it might be possible to have the populationType be double and impose an integer constraint on all of them, but it seems like there should be a more elegant way to do this.

Any ideas out there?

thx, Xander

[Walter Roberson]

Is "active bit" the same as "number of bits set to 1", or is a bit that is not active one that is "don't care" ?

Answer 1

[Alan Weiss]

I wonder if you can use the bintprog function for your problem. You can use a linear constraint to represent the inequality you wrote. My only question is whether your objective function can be written as a linear combination of the design variables.

Alan Weiss

MATLAB mathematical toolbox documentation

[Xander]

Hi Alan,

Unfortunately, my actual objective function is a non-linear function of the design variables, so bintprog is out. Should have mentioned this in the original post.

thx, Xander

Answer 2

[Matt J]

Instead of parametrizing the problem in terms of length-40 bit strings, I wonder if it might be better if your parameters instead specify the integer positions of the active bits in the bitstring. This way, the dimension of your search space would be nMaxNumber (lower) instead of 40.

There are several ways you could allow for bitstrings with fewer than nMaxNumber active bits. You could allow the positions of the active bits to be specified multiple times by the variables, but ignore repititions when you construct a bitstring. For example, with nMaxNumber=5, the following parameter vector would only generate 3 active bits

 x=[4 2 4 4 10]

at locations 2,4,10. Alternatively, you could also allow positions greater than 40 to be indexed, but ignore those when deriving the actual bitstring.