Why Linear Inequalities in gamultiobj make the process slow when increasing the population?

I am running the gamultiobj using the optimization tool app with the function attached to this question (at the bottom of this question are the settings used). I notice two things:

1. As I increase the population size the longer it took to start the iteration process. Example: 90 seconds to start the iterations when the population is 150. 650 seconds when population is 400. 17,600 seconds when the population is 1,000. When the iterations started the process is quite fast.

2. If I remove the linear inequalities from the problem there an insignificant time gap between the moment I click the start button and the iterations starting (this is with a population size of 1,000).

My guess is that the time delay when using linear inequalities is caused by the creation of the initial population (ran in all the examples with the option: "Contraint dependent"). I wanted to know:

a) If this slowness in starting the iteration process is due to the creation function?

    a1) If yes, is there a way to reduce the creation time?

    a2) If no, what would be the reason and how can the time be reduced?

The thing is that I need to run this optimization process 5 times to arrive to the solution, meaning that it would take a little bit more than a day to have a result. The population size was chosen to guarantee a good degree of repeatability in the solution.

PC with 4 cores and 6GB RAM, Win7. Matlab 2014a.

Optimization Tool: gamultiobj

Fitness function: TESTMO1

Variables = 4;

A = [0 1 1 0; 0 -1 -1 0; -1 0 0 1];

b = [486.15;-433.15;-293.15;

Aeq = []; beq = [];

options = gaoptimset;

options = gaoptimset('UseParallel', true, 'Vectorized', 'off');

options = gaoptimset(options,'PopulationSize', 100);

options = gaoptimset(options,'CrossoverFraction', 0.40);

options = gaoptimset(options,'MigrationFraction', 0.35);

options = gaoptimset(options,'SelectionFcn', { @selectiontournament 4 });

options = gaoptimset(options,'CrossoverFcn', { @crossoverintermediate 1 });

options = gaoptimset(options,'Display', 'iter');

options = gaoptimset(options,'PlotFcns', { @gaplotscorediversity @gaplotpareto });

Thanks a lot for your time!

Answer 1

[Matt J]

My guess is that the creation function is trying to selection an initial population that is uniform over your feasible region. When you have linear inequality constraints, this region has a complicated polyhedral shape and spreading the population uniformly is a more involved computation than over a simple box.

If you must use a population of a 1000, one solution might be to save the initial population for use in later runs.

[Matt J]

You might try the code below to generate your initial population. It requires some tools from the File Exchange, namely lcon2vert and randfixedsum. It also requires that you impose some lower and upper bounds lb and ub (in my example 0 and 1000, but change them as you see fit).

    A = [0 1 1 0; 0 -1 -1 0; -1 0 0 1];

    b = [486.15;-433.15;-293.15];

    lb=0;
    ub=1000;

    A=[A;eye(4);-eye(4)];
    b=[b;ub*[1 1 1 1]'; -lb*[1 1 1 1]'];

    V=lcon2vert(A,b).';

    w=randfixedsum(size(V,2),1000,1,0,1);

    InitialPopulation=(V*w).';

I'm not 100% certain about how uniformly this will distribute the Initial Population over your feasible region as compared to what ga() currently does. The above computation is fast, though, and might be worth a try.

[Santiago]

Thanks Matt.

I agree that it is a complicated shape. So, do you think if I force the creation function from uniform to constraint dependent the time would be reduced?

Thanks again.

[Santiago]

Thanks Matt!!

I will try it and let you know how it went!

Answer 2

[Alan Weiss]

In fact, the population creation function is solving linear programming problems to give a feasible initial population, meaning one that satisfies all the bounds and linear constraints. This can be time consuming, as you have seen.

However, it is essential that you have a feasible initial population. ga uses an algorithm that enforces feasibility only if the original population is feasible. So if you start with an infeasible population, you can end up with an infeasible solution, and ga will not warn you about it.

The creation function does not make a uniform initial population, but one that is weighted to lie on the boundaries of the region. You can find out more about the linearly constrained creation function in the documentation.

Alan Weiss

MATLAB mathematical toolbox documentation

[Santiago]

Thanks Alan.

I will read the documentation suggested.