GA initial solution not used in problem base solver

Hi,

I am using ga with integer variables to solve a minimization problem. I started by using a single point as the initial guess, but found out that it was not used, as ga resulted in worse solutions than the initial point. After this I tried with a population, but it did as poorly, losing to the original solution I had.

After this, I tried the example for initial population generation for GA when using solve(). Example is the first one in this link Create values for optimization problem - MATLAB optimvalues - MathWorks Nordic

I modified the example to include the best solution it finds with default rng and also to display each iteration. My script for this is below, with my additions commented. I concluded that having the best solution (x,y) = (1,1) in the initial population does not change the output, which to me seems that it is not actually using the given population. Same result with a single point guess.

Am I making some mistake, or is the initial population actually ignored here? I am using R2022b.

%%
clc
x = optimvar("x",LowerBound=-5,UpperBound=5);
y = optimvar("y",LowerBound=-5,UpperBound=5);
rosenbrock = (10*(y - x.^2)).^2 + (1-x).^2;
prob = optimproblem(Objective=rosenbrock);

rng default % For reproducibility
xval = -5 + 10*rand(1,100);
yval = -5 + 10*rand(1,100);

xval(1) = 1; %The best
yval(1) = 1; %solution
x0.x = 1; %The best solution for
x0.y = 1; %single point guess

vals = optimvalues(prob,x=xval,y=yval);

opts = optimoptions("ga",PopulationSize=100,Display="iter"); %Added 'iter' display
[sol,fv] = solve(prob,vals,Solver="ga",Options=opts)%Use x0 or vals as 2nd argument

Solving problem using ga.

Single objective optimization:
2 Variable(s)

Options:
CreationFcn:       @gacreationuniform
CrossoverFcn:      @crossoverscattered
SelectionFcn:      @selectionstochunif
MutationFcn:       @mutationadaptfeasible

                                  Best           Mean      Stall
Generation      Func-count        f(x)           f(x)    Generations
    1              200           1.948            6872        0
    2              295          0.3606            3947        0
    3              390          0.3606            1494        1
    4              485          0.3606            1188        2
    5              580         0.03715           97.45        0
    6              675         0.03715           94.79        1
    7              770         0.02279           50.82        0
    8              865         0.02279           45.63        1
    9              960         0.02279            44.8        2
   10             1055         0.02279           22.02        3
   11             1150         0.01428           14.61        0
   12             1245         0.01428            12.2        1
   13             1340         0.01428           12.15        2
   14             1435        0.002091           3.712        0
   15             1530        0.002091           1.134        1
   16             1625        0.002091           1.316        2
   17             1720        0.002091          0.8313        3
   18             1815       2.645e-06          0.5775        0
   19             1910       2.645e-06          0.3189        1
   20             2005       2.645e-06          0.2115        2
   21             2100       2.645e-06          0.1267        3
   22             2195       2.645e-06           0.074        4
   23             2290       1.231e-06         0.03748        0
   24             2385       1.231e-06         0.03921        1
   25             2480       1.231e-06        0.001636        2
   26             2575       1.231e-06       0.0007342        3
   27             2670       1.231e-06       0.0007495        4
   28             2765       1.231e-06       0.0007096        5
   29             2860        9.57e-07       0.0006081        0
   30             2955        9.57e-07       2.917e-05        1

                                  Best           Mean      Stall
Generation      Func-count        f(x)           f(x)    Generations
   31             3050        9.57e-07        1.81e-05        2
   32             3145        9.57e-07        5.53e-06        3
   33             3240       8.574e-07       4.521e-06        0
   34             3335       8.574e-07       5.881e-06        1
   35             3430       8.574e-07        5.59e-06        2
   36             3525       8.574e-07       4.856e-06        3
   37             3620       8.574e-07       4.023e-06        4
   38             3715       7.441e-07       3.053e-06        0
   39             3810       7.441e-07       5.107e-06        1
   40             3905       7.332e-07       4.946e-06        0
   41             4000       6.114e-07       7.182e-06        0
   42             4095       6.114e-07       1.759e-05        1
   43             4190       3.877e-07       1.067e-05        0
   44             4285       3.877e-07        1.58e-05        1
   45             4380       3.877e-07       1.917e-05        2
   46             4475       3.877e-07       1.203e-05        3
   47             4570       3.877e-07       1.027e-05        4
   48             4665        3.75e-07       6.668e-06        0
   49             4760        3.75e-07       8.551e-06        1
   50             4855        3.75e-07       6.032e-06        2
   51             4950       2.481e-07       4.111e-06        0
   52             5045       2.481e-07       5.319e-06        1
   53             5140       2.481e-07       3.958e-06        2
   54             5235       2.481e-07       4.474e-06        3
   55             5330        1.89e-07       4.705e-06        0
   56             5425       1.618e-07        6.21e-06        0
   57             5520       1.361e-07       1.748e-05        0
   58             5615       4.405e-09       6.044e-05        0
   59             5710       4.405e-09       0.0002542        1
   60             5805       4.405e-09       0.0001364        2

                                  Best           Mean      Stall
Generation      Func-count        f(x)           f(x)    Generations
   61             5900       4.405e-09       6.827e-05        3
   62             5995       4.405e-09       4.879e-05        4
   63             6090       4.405e-09       3.444e-05        5
   64             6185       4.405e-09       2.596e-05        6
   65             6280       4.405e-09       1.675e-05        7
   66             6375       4.106e-09       8.551e-06        0
   67             6470       4.106e-09       8.632e-06        1
   68             6565       4.106e-09       3.696e-06        2
Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

sol = struct with fields:
    x: 1.0000
    y: 1.0000

fv = 4.1061e-09

Answer 1

[Nikhilesh]

It seems that you have correctly modified the example code to add a custom initial population and display the iterations. Regarding your question, the initial population is indeed used by the genetic algorithm solver, but there is no guarantee that any of the solutions in the initial population will be selected to create the next generation. The genetic algorithm solver starts by evaluating the fitness of each individual in the population, and then uses selection, crossover, and mutation operators to create the next generation of solutions. The selected individuals are not necessarily the fittest individuals from the previous generation, but rather a probabilistic selection process is used to favor fitter individuals. This means that even if you include the best solution in the initial population, it may not be selected to create the next generation if it is not one of the fittest individuals.

[Veli-Pekka Kutinlahti]

The only modifications I have done to the code above otherwise taken as a direct example are lines 12-15. The issue here is that with the point (x,y)=(1,1) in the initial population should make "Best f(x)" in generation 1 be 4.1061e-09, but it does not. It is always 1.948.

To be fair, I don't truely know how ga finds the minimum, how next generations are produced etc, but I would sure hope it would keep the best f(x) and x values so far in memory. Even if they are used to produce the next generation. In the output it can be seen, that best f(x) is always decreasing, so this case confirms my understanding of how it should work. Keeping the best solution in memory. The only issue I have is the fact that having (x,y)=(1,1) in the initial population does not do anything. From this I still conclude, that solve() does not accept initial population for ga.

I have tried the same with ga() without solve() formulation, and it is accepting the initial guess. I am using it in my work now, so I don't mind solve() not working, but I am still interested in if the problem is in my coding ability (I don't think so at the moment) or is the problem actually in solve().

Answer 2

[Alan Weiss]

When using the problem-based approach you must pass initial points to ga using optimvalues. See https://www.mathworks.com/help/releases/R2022a/gads/global-initial-points.html

Alan Weiss

MATLAB mathematical toolbox documentation

[Veli-Pekka Kutinlahti]

It is done in my example that way. Either way, giving the initial population with optimvalues or not does not trigger a warning with a single point guesses, which would have helped me identify the problem much earlier.

Also, the example in that second link in your message has a typo. Last line in the code is

[sol,fval] = solve(problem,Solver="ga")

but it should be

[sol,fval] = solve(prob,Solver="ga")

At the moment the example code throws an error.

[Alan Weiss]

Thanl you for letting me know about the typo. I'll fix it in the next release.

Alan Weiss

MATLAB mathematical toolbox documentation