Karush Kuhn Tucker Proximity Measure (KKTPM)¶
Warning
Not supported in the current version anymore. Gradient calculation needs to be reworked.
In 2016, Deb and Abouhawwash proposed Karush Kuhn Tucker Proximity Measure (KKTPM) [36], a metric that can measure how close a point is from being “an optimum”. The smaller the metric, the closer the point. This does not require the Pareto front to be known, but the gradient information needs to be approximated. Their metric applies to both single objective and multi-objective optimization problems.
In a single objective problem, the metric shows how close a point is from being a “local optimum”, while in multi-objective problems, the metric shows how close a point is from being a “local Pareto point”. Exact calculations of KKTPM for each point requires solving a whole optimization problem, which is extremely time-consuming. To avoid this problem, the authors of the original work again proposed several approximations to the true KKTPM, namely Direct KKTPM, Projected KKTPM, Adjusted KKTPM, and Approximate KKTPM. Approximate KKTPM is simply the average of the former three and is what we call simply “KKTPM”. Moreover, they were able to show that Approximate KKTPM is reliable and can be used in place of the exact one [37].
Let us now see how to use pymoo to calculate the KKTPM for point:
[1]:
from pymoo.constraints.from_bounds import ConstraintsFromBounds
from pymoo.gradient.automatic import AutomaticDifferentiation
from pymoo.problems import get_problem
problem = AutomaticDifferentiation(ConstraintsFromBounds(get_problem("zdt1", n_var=30)))
For instance, the code below calculates the KKTPM metric for randomly sampled points for the given an example;
[2]:
from pymoo.indicators.kktpm import KKTPM
from pymoo.operators.sampling.rnd import FloatRandomSampling
X = FloatRandomSampling().do(problem, 100).get("X")
kktpm = KKTPM().calc(X, problem)
---------------------------------------------------------------------------
UnboundLocalError Traceback (most recent call last)
Cell In[2], line 5
2 from pymoo.operators.sampling.rnd import FloatRandomSampling
4 X = FloatRandomSampling().do(problem, 100).get("X")
----> 5 kktpm = KKTPM().calc(X, problem)
File ~/anaconda3/envs/default/lib/python3.12/site-packages/pymoo/indicators/kktpm.py:46, in KKTPM.calc(self, X, problem, ideal, utopian_eps, rho)
43 # for convenience get the counts directly
44 n_solutions, n_var, n_obj, n_ieq_constr = X.shape[0], problem.n_var, problem.n_obj, problem.n_ieq_constr
---> 46 F, G, dF, dG = problem.evaluate(X, return_values_of=["F", "G", "dF", "dG"])
47 CV = calc_cv(G=G)
49 # loop through each solution to be considered
File ~/anaconda3/envs/default/lib/python3.12/site-packages/pymoo/core/problem.py:257, in Problem.evaluate(self, X, return_values_of, return_as_dictionary, *args, **kwargs)
254 only_single_value = not (isinstance(X, list) or isinstance(X, np.ndarray))
256 # this is where the actual evaluation takes place
--> 257 _out = self.do(X, return_values_of, *args, **kwargs)
259 out = {}
260 for k, v in _out.items():
261
262 # copy it to a numpy array (it might be one of jax at this point)
File ~/anaconda3/envs/default/lib/python3.12/site-packages/pymoo/gradient/automatic.py:54, in AutomaticDifferentiation.do(self, x, return_values_of, *args, **kwargs)
51 from pymoo.gradient.grad_autograd import autograd_vectorized_value_and_grad
52 out, grad = autograd_vectorized_value_and_grad(f, x)
---> 54 for k, v in grad.items():
55 out["d" + k] = v
57 return out
UnboundLocalError: cannot access local variable 'grad' where it is not associated with a value
Moreover, a whole run of a genetic algorithm can be analyzed by storing each generation’s history and then calculating the KKTPM metric for each of the points:
[ ]:
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.problems import get_problem
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter
from pymoo.core.evaluator import Evaluator
algorithm = NSGA2(pop_size=100, eliminate_duplicates=True)
# make sure each evaluation also has the derivatives - necessary for KKTPM
evaluator = Evaluator(evaluate_values_of=["F", "G", "dF", "dG"])
res = minimize(problem,
algorithm,
('n_gen', 100),
evaluator=evaluator,
seed=1,
save_history=True,
verbose=False)
[ ]:
import numpy as np
gen, _min, _median, _max = [], [], [], []
for algorithm in res.history:
if algorithm.n_gen % 5 == 0:
X = algorithm.pop.get("X")
kktpm = KKTPM().calc(X, problem)
gen.append(algorithm.n_gen)
_min.append(kktpm.min())
_median.append(np.median(kktpm))
_max.append(kktpm.max())
[ ]:
import matplotlib.pyplot as plt
plt.plot(gen, _min, label="Min")
plt.plot(gen, _median, label="Median")
plt.plot(gen, _max, label="Max")
plt.yscale("log")
plt.legend()
plt.show()