GA initial solution not used in problem base solver

8 views (last 30 days)
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

Answers (2)

Nikhilesh
Nikhilesh on 9 Mar 2023
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.
  1 Comment
Veli-Pekka Kutinlahti
Veli-Pekka Kutinlahti on 11 Mar 2023
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().

Sign in to comment.


Alan Weiss
Alan Weiss on 10 Mar 2023
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
  2 Comments
Veli-Pekka Kutinlahti
Veli-Pekka Kutinlahti on 11 Mar 2023
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
Alan Weiss on 13 Mar 2023
Thanl you for letting me know about the typo. I'll fix it in the next release.
Alan Weiss
MATLAB mathematical toolbox documentation

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!