A rating function determines the fitness of a given solution to the problem in question.
They are generally used in order to guide problem solvers. However, rating functions
can also be used in order to inject additional code into solvers. This can be seen
as a form of dependency injection. A simple example is provided at the end of this article.
Note: During the design phase of the second version of Gel I searched for methods to create
complex constraints out of relatively simple constraints. Typed ratings can be used
in order to i.e. negate a given constraint with high quality. I also looked for ways
to organize complex manipulations of solutions. However, typed ratings were of no
use for the solvers during my master thesis. Instead, the given solution was queried
for variables that dissatisfy certain aspects of the constraints.
Note: This article does currently not consider existing research yet.
The hill climber for discrete values is able to imitate any discrete solving algorithm
that optimizes a given complete solution. For a given history of intermediate solutions
one has to determine a path in the search space visiting all intermediate solutions
in the given order. The rating function can be used in order to determine the next
step of the hill climber at the current step of the solution path.
If there is a high number of neighbors at the current position of the problem space,
then the performance of the hill climber might be inappropriate. This can be compensated
by adjusting the problem space dynamically in order to minimize the number of neighbors
during a hill climbing step. This shows that the solution space can also be used in
order to inject code into solving programs.
The following Python code shows how Simulated Annealing can be injected into the hill climbing algorithm. Note that the implemented rating functions are based on side effects and are therefore
not suitable for certain local search algorithms.
#!/usr/bin/env python3 """This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.""" __author__ = 'Mārtiņš Avots' import unittest from random import uniform, shuffle from math import log, inf class annealing_relative_rating: def __init__(self, rating_function, temperature_function, rating_improvement_factor, rating_diminishment_factor): self.rating_function = rating_function self.temperature_function = temperature_function self.counter = 0 self.rating_improvement_factor = rating_improvement_factor self.rating_diminishment_factor = rating_diminishment_factor def __call__(self, solution): rating = self.rating_function(solution) self.counter += 1 temperature = self.temperature_function(self.counter) if rating == 0 or temperature == 0: return rating elif uniform(0, 1) >= temperature: return rating * self.rating_improvement_factor else: if rating * self.rating_diminishment_factor == 0: return rating else: return rating * self.rating_diminishment_factor class annealing_absolute_rating: def __init__(self, rating_function, temperature_function, max_rating): self.rating_function = rating_function self.temperature_function = temperature_function self.counter = 0 self.max_rating = max_rating def __call__(self, solution): rating = self.rating_function(solution) self.counter += 1 temperature = self.temperature_function(self.counter) if rating == 0 or temperature == 0: return rating elif uniform(0, 1) >= temperature: return rating else: return self.max_rating def climb_hill(rating_function, problem_space, current_solution): best_solution = current_solution for neighbour in problem_space(current_solution): if rating_function(best_solution) > rating_function(neighbour): best_solution = neighbour return best_solution def Queen_N_problem(n): return [0] * n def Queen_N_rating(queen_problem): rVal = 0 for i in range(len(queen_problem)): for j in range(len(queen_problem)): if [i] != [j] and queen_problem[i] == queen_problem[j]: rVal += 1 for i in range(0, len(queen_problem) - 1): for j in range(i + 1, len(queen_problem)): k = j - i if queen_problem[i] == queen_problem[j] - k: rVal += 1 if queen_problem[i] == queen_problem[j] + k: rVal += 1 return rVal def Queen_N_neighbours(queen_problem): rVal = [] for i in range(len(queen_problem)): for j in range(len(queen_problem)): neighbour = list(queen_problem) neighbour[i] = j rVal.append(neighbour) shuffle(rVal) return rVal class HillClimbingTestLocalOptima(unittest.TestCase): """By default only functions starting with test are executed during testing.""" def __temperatureTestFunction(self, x): """Determined by trial and error from universal allocation program's temperature functions.""" return (log(4.0) / log((x + 1)**1.5)) - 0.05 def __hillClimbingTest_GetsStuckInBadLocalOptima(self, rating_function, max_iterations): for i in range(max_iterations): solution = Queen_N_problem(8) for i in range(1000): solution = climb_hill(rating_function, Queen_N_neighbours, solution) if Queen_N_rating(solution) == 0: break if Queen_N_rating(solution) != 0: return True return False def testClassicHillClimbingHasBadLocalOptima(self): self.assertTrue( self.__hillClimbingTest_GetsStuckInBadLocalOptima(Queen_N_rating, 10) ) def testAbsoluteAnnealingHillClimberFindsGlobalOptima(self): self.assertFalse( self.__hillClimbingTest_GetsStuckInBadLocalOptima( annealing_absolute_rating( Queen_N_rating, self.__temperatureTestFunction, inf), # A floating-point positive infinity. 10) ) def testRelativeAnnealingHillClimberFindsGlobalOptima(self): self.assertFalse( self.__hillClimbingTest_GetsStuckInBadLocalOptima( annealing_relative_rating( Queen_N_rating, self.__temperatureTestFunction, 1./8., # Determined by trial and error. 8), # Determined by trial and error. 10) ) if __name__ == "__main__": unittest.main()
d:toDo
Every rating function is of one of the following types:
The higher the rating the better the solution. Such a function is also called an objective function, a reward function, a object
function, a utility function or a fitness function.
-
mathematical formalization
d:toDo
The lower the rating the better the solution. A cost function is also called loss function.
-
mathematical formalization
d:toDo
Consecutively, some properties related to the quality of rating functions are listed.
A proportional object function evaluates the compliance of a solution to a given problem:
if the rating of a solution A is X-times higher as the rating of another solution
B then B disagrees the given constraints X-times as much as A. Constraint weights
are considered in this context.
-
mathematical formalization
d:toDo
An exact cost function is a proportional cost function where an optimal solution is
rated with zero. Note that a rating function that only returns the number of dissatisfied
constraints may not be exact. An exact object function needs to respect the weights
of the constraints in questions.
-
mathematical formalization
d:toDo
An invertible objective function has a return value with a known upper bound. This
means that one can take an invertible cost function and create a negation of that
function. This is equal to a conversion of a fitness function into a loss function
and vice versa.
-
mathematical formalization
d:toDo
For a given distorted cost function: If the rating of a solution A is X times higher
as the rating of another solution B then A might not disagree the given constraints
X-times more than B. Constraint weights are considered in this context.
-
mathematical formalization
d:toDo
If a given solution is rated multiple times with such a function, then the result
is always the same.
-
mathematical formalization
d:toDo
If a given solution is rated multiple times with such a function than the rating may
not be the same: i.e. a learning program that learned a rating function but still
adjusts its weightings. If a side effect free system is used, then this can be implemented
via the concept of time. This can be done by adding a parameter to the rating function
representing the current time:
-
mathematical formalization
d:toDo
An alternative approach is to implement the rating function as a monad:
-
mathematical formalization
d:toDo
A rating function where every solving algorithm has a low probability to find an optimal
solution to a randomly chosen problem instance for a given problem:
-
mathematical formalization
d:toDo
Subsequently, some types of object functions with different qualities are listed:
For a given solution and search space this cost function returns the minimum distance
between the given solution and any optimal solution:
-
mathematical formalization
d:toDo
For a given solution, feasible region and solver this cost function returns the expected
minimal distance between the given solution and any optimal solution:
-
mathematical formalization
d:toDo
For a given feasible region, solution, local search algorithm and a maximum search
space walk distance this profit function returns the rating improvements that the
search algorithm is expected to find for a given neighbor of the current solution:
-
mathematical formalization
d:toDo
For a given feasible region, solution, local search algorithm and a maximum search
space walk distance this fitness function returns the probability that the search
algorithm will find an optimal solution:
-
mathematical formalization
d:toDo