How to find fixed number of variables with value 1 using Genetic Algorithm with population type Bitstring ?

I am solving an objective function with Genetic Algorithm with population type bitstring (values 0 and 1 only) using toolbox.

The variables select rows of a matrix (10*10) and the objective function is to find a minimum value in a further calculated matrix using values from those rows.

The current variables are 10. So the the GA solves and find values of all 10 variables.

How to select a fix number of variables with a value of 1 ? example out of 10 variables, i need to find the solution of 1 for 5 variables only i.e. i want to find the 5 best rows from matrix.

Answer 1

[Alan Weiss]

If I understand you correctly (and I might not have understood), you want to impose a linear constraint on the population x

sum(x,2) == 5

meaning each row (individual) has exactly 5 with value 1, the rest have value 0.

If that is what you are trying to do, then I believe that you need to impose custom creation, mutation, and possibly crossover functions. The creation and mutation functions should ensure that you maintain exactly five individuals that have value 1. Some crossover functions might do this automatically, but you would have to check to be sure.

Custom creation function syntax which also has details on using bitstring such as which built-in crossover functions are available

Custom mutation function syntax

Custom crossover syntax

Alan Weiss

MATLAB mathematical toolbox documentation

[Ankur Shah]

Thank you for your reply. Yes this exactly what i am trying to do (each row (individual) has exactly 5 with value 1, the rest have value 0).

Creating custom creation, mutation and crossover functions would complicate my problem.The crux is i need to select best possible 5 rows which has minimum objective function value. Is there any way around or another way for solving the problem ?.

[Alan Weiss]

Well, if you are willing to change your data type, then you might be able to do something. Instead of bitstring, I recommend that you use Mixed Integer ga Optimization, which allows you to use linear constraints. You will notice that this type of optimization does not allow equality constraints. Nevertheless, you can express your constraint as two linear inequalities:

A = ones(2,nvar); % nvar is the number of variables
A(2,:) = -A(2,:);
b = [5.5 -4.5];
% Implements sum(x) <= 5.5, -sum(x) <= -4.5 meaning sum(x) >= 4.5
intcon = 1:nvar; % All variables integer
lb = zeros(nvar,1);
ub = ones(nvar,1);
[x,fval,exitflag,output,population] = ga(fun,nvar,A,b,[],[],lb,ub,[],intcon)

I don't know how well this will work, but it gives you a chance of getting your solution without a lot of coding.

Alan Weiss

MATLAB mathematical toolbox documentation

[Ankur Shah]

Thank you. Yes, It works as a way around and gives good results. In the help menu following is written to improve the results

https://in.mathworks.com/help/gads/mixed-integer-optimization.html#bs1ofqn

• Decrease the mutation rate. To do so, increase the value of the CrossoverFraction option from its default of 0.8 to 0.9 or higher.
• Increase the value of the EliteCount option from its default of 0.05*PopulationSize to 0.1*PopulationSize or higher.

The first point seems a bit confusing, It is mixed integer so does it use special crossover and mutation function inbuilt ?... or it ignores mutation ?

How come increasing crossover fraction decreases mutation rate ?

[Alan Weiss]

mutation rate + crossover fraction = 1

Alan Weiss

MATLAB mathematical toolbox documentation

[Ankur Shah]

Can you share the source of it i.e ."mutation rate + crossover fraction = 1" ?

Also is it possible to know the creation, crossover and mutaiton function which matlab uses for solving it ?. I couldn't find in the documentation.