GA - objective and constraints have to run the same expensive function

Hi,

I'm trying to use GA for a constrained optimisation problem. The issue is that constraint function requires a value that is calculated during the execution of the objective function. In this code snippet, I've kept a dummy fem function.

But in the actual code (Which I can't share), the fem.m function returns the fitness value (needed for objective function) and a displacement value (needed for constraint function).

Is there a way that I can call the function only once? Or somehow store the displacement value and use it while calling the constraint?

clear
clc

fun = @(x) objective(x);
con = @(x) constraint(x);

% dummy number of variables. here taken as 3
lb = [ 0 0 0 ];
ub = [ 100 100 100];
options = optimoptions('ga','Display','iter');
[x,fval,exitflag,output,population,scores]=ga(fun,3,[],[],[],[],lb,ub,con,options);

function energy = objective(x)
    % expensive finite element function call
     [energy, displacement] = fem(x); 
end

function [c,ceq] = constraint(x)
    ceq = [];

    % need to call expensive fem again
     [energy, displacement]  = fem(x);
     c = [4 - displacement];
end

%Dummy fem function, in reality not explicit and computationally expensive
function [energy,displacement] = fem(x);
    energy = sum(x);
    displacement = x(2);
end

Answer 1

[Alan Weiss]

This is a difficult problem because of the way that ga calls functions, both fitness and nonlinear constraint. For most solvers, the objective and constraint functions at a point are called right after each other. However, for ga I believe that all of the fitness functions for a population are called together, and all the constraint functions are called together, meaning there is little opportunity to cache these values as done for other solvers in Objective and Nonlinear Constraints in the Same Function or Objective and Constraints Having a Common Function in Serial or Parallel, Problem-Based.

Sorry.

But do you really need to use ga? Have you tried patternsearch, possibly starting from a variety of initial points? Or possibly surrogateopt, which is designed for computationally intensive functions?

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Steven Lord]

One potential solution would be to memoize your expensive function, pass the memoized function into your objective and constraint function as an additional parameter, and evaluate it using that memoized function.

f = memoize(@expensiveFunction);
tic
y = f(1);
toc

Elapsed time is 2.007072 seconds.

tic
z = f(1);
toc

Elapsed time is 0.002627 seconds.

check = isequal(y, z) % true

check = logical
   1

function out = expensiveFunction(in)
pause(2)
out = in + 1;
end

Answer 3

[John D'Errico]

I would try memoization.

help memoize

 MEMOIZE Adds memoization semantics to the input function handle, 
  and returns a MemoizedFunction object.
 
  Memoization is an optimization technique used primarily to speed up
  programs by storing the results of expensive function calls and returning
  the cached result when the same inputs occur again.
 
  Consider memoizing function calls which are:
  1. time consuming, and
  2. pure functions
     i.e. Functions whose return value is only determined by its input values,
     without observable side effects
 
  The MemoizedFunction object returned from MEMOIZE can be used
  just like the function handle used to create it.
 
  The object will maintain caches of inputs its called with and the 
  corresponding outputs produced.
  For more information refer to matlab.lang.MemoizedFunction
 
  Example 1: General usage
 
    inputs = rand(1000);
    output = eigs(inputs); % Slow function call
  
    % Creation
    memoizedEigs = MEMOIZE(@eigs);
  
    % First call will execute EIGS and cache the results
    output = memoizedEigs(inputs); 
  
    % Subsequent calls are faster, as they simply return cached results
    output2 = memoizedEigs(inputs); %
 
  In the above example, it is safe to memoize EIGS as it will always give
  the same results for the same inputs.
 
  Example 2: Unsafe usage
     Consider the MATLAB function RANDI. Every call to it with the input
     10, should result in a random integer from 1-10.
  
    f = memoize(@randi); % RANDI has the side effect of setting global state
    y = f(10)
    y =
        9
  
    y = f(10) % Subsequent runs also give same result for same input
    y =
        9
 
  Notes: 
  1. Multiple calls to MEMOIZE with the same function handle will return 
     the same MemoizedFunction object.
     Example:
       x = memoize(@plus);
       y = memoize(@plus);
       isequal(x, y)
       ans = 
              1
 
  2. If you memoize a function with side effects such as setting some
     global state, or performing I/O operations. The side effects are not
     repeated on susbsequent calls to the memoized function with the same
     inputs. As demonstrated in Example 2.
  
  See also: MATLAB.LANG.MEMOIZEDFUNCTION, CLEARALLMEMOIZEDCACHES

    Documentation for memoize
       doc memoize

For example, we can use it as in the example below. I've created a function that does little computationally, but all that matters is it will be called only once for a given set of parameters.

myfunmemo = memoize(@myfun);

Now test it out. First, see that myfun does execute when we call it, and it dumps out a comment that it was called, and executed.

myfun(1:5)

Initial call for this set of parameters

ans = 15

myfun(1:5)

Initial call for this set of parameters

ans = 15

However, do the same for myfunmemo.

myfunmemo(1:5)

Initial call for this set of parameters

ans = 15

myfunmemo(1:5)

ans = 15

As you can see, there was only one call made to the origianl function. The second call used the cached value. So if it is terribly expensive to make that call, a memoization will allow you to avoid that repeated call. Note that memoization does work for non-integer arguments.

myfunmemo(pi + (1:10))

Initial call for this set of parameters

ans = 86.4159

myfunmemo(pi + (1:10))

ans = 86.4159

Will memoization cause a problem if the cache grows large? Well, probably so. I assume there will be a quadratic cost penalty associated with memoization, as the cache grows internally. But if the call itself was too costly to be done twice, you may still see a gain.

function Y = myfun(X)
  Y = sum(X); % what it does internally is irrelevant.
  disp("Initial call for this set of parameters")
end