How to find the best combinations of calculation of function with 36 input constants, each constant is possible to calculate in 3 ways

9 views (last 30 days)
Hi community,
I have a function with 36 constants (it possible to image the function as an surface). Each of the 36 constant is possible to calculate in 3 ways (named/substituted for example as 0, 1, 2). It is totally 3 ^ 36 of possible combinations. I am looking for the best combination to find the minimum sum error from reference values set.
My idea to solve it was with brute force at first: for each combination 1 to 3 ^ 36 to calculate input control vector in ternary system (0...000, 0...001, 0...002, 0...010, etc.) and then to evaluate function output (based on control vector) for each reference values set. If the solution was better than previous one, I stored the "better combination" and go to the next combination. But the solution takes unreal time.
It is there any better solution how to solve it? I read something about optimalization toolbox, but I am not familiar with it. I read also about parfor function, but my solution described above is evaluating every step if is better than previous one. So, I don’t know, if it is even possible to calculate it in parallel way.
Thank you in Advance
  9 Comments
Bruno Luong
Bruno Luong on 18 Nov 2023
Edited: Bruno Luong on 18 Nov 2023
A least squares problem is minimizing the objective function defined as
norm(abs(model(param) - data)^2
or
sum(abs(model(param) - data).^2)
sum is over output variables (your surface data).
Such objective function usually eases the minimizer for convergence.
Might be you problem is simply too hard to solve
Lubos Brezina
Lubos Brezina on 19 Nov 2023
A least square implementation significantly increase quality of results (ga). It was good advice. Ga founded some solutions. Question is, if there could be any better solutions. Because, it was quite hard to force ga to not be stalled at beginning. After hours of "debugging", I changed Crossovefraction to 0.6 (I tried change anything) and it helped. (solution after 30 sec). But that was all. This solution is not the best, I expected more. Does it have any meaning to keep ga running, f.e. 1 day more? I dont think so.
Gamultiobj is stalled. I let it go.
With brute force, I validated ga result. It was possible, because solution was at "side" of 36 constants range (only 18 positions of 36). Other "side" of control matrix (the rest) would take 37years of calculation :))

Sign in to comment.

Answers (1)

John D'Errico
John D'Errico on 15 Nov 2023
Brute force is NEVER going to be a good idea. Instead, if you have the global optimization toolbox...
help ga
GA Constrained optimization using genetic algorithm. GA attempts to solve problems of the following forms: min F(X) subject to: A*X <= B, Aeq*X = Beq (linear constraints) X C(X) <= 0, Ceq(X) = 0 (nonlinear constraints) LB <= X <= UB X(i) integer, where i is in the index vector INTCON (integer constraints) Note: If INTCON is not empty, then no equality constraints are allowed. That is:- * Aeq and Beq must be empty * Ceq returned from NONLCON must be empty X = GA(FITNESSFCN,NVARS) finds a local unconstrained minimum X to the FITNESSFCN using GA. NVARS is the dimension (number of design variables) of the FITNESSFCN. FITNESSFCN accepts a vector X of size 1-by-NVARS, and returns a scalar evaluated at X. X = GA(FITNESSFCN,NVARS,A,b) finds a local minimum X to the function FITNESSFCN, subject to the linear inequalities A*X <= B. Linear constraints are not satisfied when the PopulationType option is set to 'bitString' or 'custom'. See the documentation for details. X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq) finds a local minimum X to the function FITNESSFCN, subject to the linear equalities Aeq*X = beq as well as A*X <= B. (Set A=[] and B=[] if no inequalities exist.) Linear constraints are not satisfied when the PopulationType option is set to 'bitString' or 'custom'. See the documentation for details. X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, X, so that a solution is found in the range lb <= X <= ub. Use empty matrices for lb and ub if no bounds exist. Set lb(i) = -Inf if X(i) is unbounded below; set ub(i) = Inf if X(i) is unbounded above. Linear constraints are not satisfied when the PopulationType option is set to 'bitString' or 'custom'. See the documentation for details. X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON) subjects the minimization to the constraints defined in NONLCON. The function NONLCON accepts X and returns the vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. GA minimizes FITNESSFCN such that C(X)<=0 and Ceq(X)=0. (Set lb=[] and/or ub=[] if no bounds exist.) Nonlinear constraints are not satisfied when the PopulationType option is set to 'bitString' or 'custom'. See the documentation for details. X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON,options) minimizes with the default optimization parameters replaced by values in OPTIONS. OPTIONS can be created with the OPTIMOPTIONS function. See OPTIMOPTIONS for details. For a list of options accepted by GA refer to the documentation. X = GA(FITNESSFCN,NVARS,A,b,[],[],lb,ub,NONLCON,INTCON) requires that the variables listed in INTCON take integer values. Note that GA does not solve problems with integer and equality constraints. Pass empty matrices for the Aeq and beq inputs if INTCON is not empty. X = GA(FITNESSFCN,NVARS,A,b,[],[],lb,ub,NONLCON,INTCON,options) minimizes with integer constraints and the default optimization parameters replaced by values in OPTIONS. OPTIONS can be created with the OPTIMOPTIONS function. See OPTIMOPTIONS for details. X = GA(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a structure that has the following fields: fitnessfcn: <Fitness function> nvars: <Number of design variables> Aineq: <A matrix for inequality constraints> bineq: <b vector for inequality constraints> Aeq: <Aeq matrix for equality constraints> beq: <beq vector for equality constraints> lb: <Lower bound on X> ub: <Upper bound on X> nonlcon: <Nonlinear constraint function> intcon: <Index vector for integer variables> options: <Options created with optimoptions('ga',...)> rngstate: <State of the random number generator> [X,FVAL] = GA(FITNESSFCN, ...) returns FVAL, the value of the fitness function FITNESSFCN at the solution X. [X,FVAL,EXITFLAG] = GA(FITNESSFCN, ...) returns EXITFLAG which describes the exit condition of GA. Possible values of EXITFLAG and the corresponding exit conditions are 1 Average change in value of the fitness function over options.MaxStallGenerations generations less than options.FunctionTolerance and constraint violation less than options.ConstraintTolerance. 3 The value of the fitness function did not change in options.MaxStallGenerations generations and constraint violation less than options.ConstraintTolerance. 4 Magnitude of step smaller than machine precision and constraint violation less than options.ConstraintTolerance. This exit condition applies only to nonlinear constraints. 5 Fitness limit reached and constraint violation less than options.ConstraintTolerance. 0 Maximum number of generations exceeded. -1 Optimization terminated by the output or plot function. -2 No feasible point found. -4 Stall time limit exceeded. -5 Time limit exceeded. [X,FVAL,EXITFLAG,OUTPUT] = GA(FITNESSFCN, ...) returns a structure OUTPUT with the following information: rngstate: <State of the random number generator before GA started> generations: <Total generations, excluding HybridFcn iterations> funccount: <Total function evaluations> maxconstraint: <Maximum constraint violation>, if any message: <GA termination message> [X,FVAL,EXITFLAG,OUTPUT,POPULATION] = GA(FITNESSFCN, ...) returns the final POPULATION at termination. [X,FVAL,EXITFLAG,OUTPUT,POPULATION,SCORES] = GA(FITNESSFCN, ...) returns the SCORES of the final POPULATION. Example: Unconstrained minimization of Rastrigins function: function scores = myRastriginsFcn(pop) scores = 10.0 * size(pop,2) + sum(pop.^2 - 10.0*cos(2*pi .* pop),2); numberOfVariables = 2 x = ga(@myRastriginsFcn,numberOfVariables) Display plotting functions while GA minimizes options = optimoptions('ga','PlotFcn',... {@gaplotbestf,@gaplotbestindiv,@gaplotexpectation,@gaplotstopping}); [x,fval,exitflag,output] = ga(fitfcn,2,[],[],[],[],[],[],[],options) An example with inequality constraints and lower bounds A = [1 1; -1 2; 2 1]; b = [2; 2; 3]; lb = zeros(2,1); fitfcn = @(x)0.5*x(1)^2 + x(2)^2 -x(1)*x(2) -2*x(1) - 6.0*x(2); % Use mutation function which can handle constraints options = optimoptions('ga','MutationFcn',@mutationadaptfeasible); [x,fval,exitflag] = ga(fitfcn,2,A,b,[],[],lb,[],[],options); If FITNESSFCN or NONLCON are parameterized, you can use anonymous functions to capture the problem-dependent parameters. Suppose you want to minimize the fitness given in the function myfit, subject to the nonlinear constraint myconstr, where these two functions are parameterized by their second argument a1 and a2, respectively. Here myfit and myconstr are MATLAB file functions such as function f = myfit(x,a1) f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) + 2*x(2) + a1); and function [c,ceq] = myconstr(x,a2) c = [1.5 + x(1)*x(2) - x(1) - x(2); -x(1)*x(2) - a2]; % No nonlinear equality constraints: ceq = []; To optimize for specific values of a1 and a2, first assign the values to these two parameters. Then create two one-argument anonymous functions that capture the values of a1 and a2, and call myfit and myconstr with two arguments. Finally, pass these anonymous functions to GA: a1 = 1; a2 = 10; % define parameters first % Mutation function for constrained minimization options = optimoptions('ga','MutationFcn',@mutationadaptfeasible); x = ga(@(x)myfit(x,a1),2,[],[],[],[],[],[],@(x)myconstr(x,a2),options) Example: Solving a mixed-integer optimization problem An example of optimizing a function where a subset of the variables are required to be integers: % Define the objective and call GA. Here variables x(2) and x(3) will % be integer. fun = @(x) (x(1) - 0.2)^2 + (x(2) - 1.7)^2 + (x(3) -5.1)^2; x = ga(fun,3,[],[],[],[],[],[],[],[2 3]) See also OPTIMOPTIONS, FITNESSFUNCTION, GAOUTPUTFCNTEMPLATE, PATTERNSEARCH, @. Documentation for ga doc ga
  4 Comments
Torsten
Torsten on 16 Nov 2023
I have no knowledge about "ga". Maybe you can help here: Is "ga" really better suited for this problem than simply testing a fixed number of random triples ?
Lubos Brezina
Lubos Brezina on 16 Nov 2023
Basically: I want to fit surface given by my function to reference surface (reference points) by mentioned 36 constants (1, 2, 3).
Based on your recommendation, I tried it with GA. My attitude is, that function output is sum of errors of all reference points. It works, but I don´t know, if it converts/leads to any solution.
I am also trying GAmultiobj. Each error of each reference point is a separate output of function. It doesn´t seems to be work well now, but maybe it need to be tuned more.
P.S. f.e. these I meant about focusing: If it is better for GA or GAmultiobj, etc.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!