Typed Ratings and Dependency Injection via Ratings

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()

            

Every rating function is of one of the following types:

The lower the rating the better the solution. A cost function is also called loss function. 

    d:toDo
    • mathematical formalization

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.

    d:toDo
    • mathematical formalization

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.

    d:toDo
    • mathematical formalization

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.

    d:toDo
    • mathematical formalization

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.

    d:toDo
    • mathematical formalization

If a given solution is rated multiple times with such a function, then the result is always the same.

    d:toDo
    • mathematical formalization

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:

    d:toDo
    • mathematical formalization

An alternative approach is to implement the rating function as a monad:

    d:toDo
    • mathematical formalization

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:

    d:toDo
    • mathematical formalization

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:

    d:toDo
    • mathematical formalization

For a given solution, feasible region and solver this cost function returns the expected minimal distance between the given solution and any optimal solution:

    d:toDo
    • mathematical formalization

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:

    d:toDo
    • mathematical formalization

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:

    d:toDo
    • mathematical formalization
wide screen
  1. splitcells
    1. dem
      1. README.html
      2. external-documentation.html
      3. guidelines
        1. backwards-compatibility.html
        2. complexity-management.html
        3. dependency.html
        4. documentation.html
        5. index.html
        6. infrastructure.html
        7. program-code.html
        8. project.html
        9. software-project-file-system-standards.html
        10. software-project-file-system-standards.todo.html
        11. task-management.html
        12. technology-stack.html
        13. xslt.html
      4. history.html
      5. index.html
      6. lang
        1. perspective
          1. guidelines
            1. networks.html
            2. perspectives.html
          2. index.html
      7. project
        1. compatibilty-and-portability.html
        2. data-as-source-code.html
        3. effect-system.html
        4. interfaces.html
    2. gel
      1. README.html
      2. constraint
        1. index.html
      3. history
        1. origin-of-the-project-generic-allocator.html
        2. universal-allocation-program-manual.html
      4. index.html
      5. latest-articles.html
      6. model
        1. optimization
          1. interactive
            1. guidelines.html
          2. typed-ratings.html
        2. rating
          1. index.html
      7. presentation
        1. covid.html
      8. problem
        1. theory
          1. assignment
            1. problem
              1. bibliography
                1. 10.1145.321958.321975.html
                2. 1995.DISKI.86.html
              2. complexity
                1. linear.html
                2. nonlinear.html
                3. quadratic.html
              3. index.deprecated.html
              4. index.html
              5. index.illustration.svg
              6. linear.deprecated.html
              7. multidimensional.html
      9. project
        1. artificial-intelligence.html
        2. compatibilty-and-portability.html
        3. constraint-language.html
        4. documentation.html
        5. endless-recursion.html
        6. new-articles.html
        7. persistency.html
        8. reasoning-system.html
        9. release-process.html
        10. test-injection.html
        11. user-interface.html
      10. solution
        1. Solution.html
      11. test
        1. functionality
          1. n-queen-problem
            1. constraint.graph.svg
            2. constraint.tree.svg
            3. illustration.svg
          2. n-queen-problem.html
          3. n-queen-problem.implementation.html
    3. martins
      1. avots
        1. website
          1. 404.html
          2. advertisement-object-social.html
          3. advertisement-object-technical.html
          4. archive
            1. academic-publishers-of-research-papers-etc-with-open-accessin-computer-science.html
            2. blogs-related-to-computer-science.html
            3. complete-correlation-matrix-memories-orthogonal-key.tests.html
            4. complete-correlation-matrix-memories.html
            5. html-to-image-conversion-via-wkhtmltopdf.html
            6. information-related-to-managment.html
            7. optimization-software.html
            8. publications-defining-optimization-problems.html
            9. publications-related-to-optimization-algorithms.html
            10. publications-related-to-optimization-software.html
            11. writings-related-to-complexities-relevant-to-optimization.html
          5. art
            1. a-city-at-night.html
            2. average-source-code-image-generator.html
            3. average-source-code.html
            4. bird_s-banner.html
            5. community-at-moonlight.html
            6. community.html
            7. dream-about-a-city-at-night.html
            8. gallery.html
            9. index.html
            10. little-big-present.html
            11. music.external.html
            12. neural-biological-cell.html
            13. neural-birds.html
            14. night-at-home.html
            15. simple-bird.html
            16. simple-ruins.html
            17. some-things-are-done-without-reason.html
            18. starting-to-learn-how-to-draw-face.html
            19. visiting-card.html
          6. crib-sheet
            1. emacs.html
            2. emacspeak.html
            3. microsoft-narrator.html
            4. sway.html
          7. dedicated-menu-page.html
          8. den
            1. style.css
            2. test.html
            3. test.minimal.html
          9. experimental
            1. browser.layout.html
            2. desktop.layout.html
          10. images
            1. icon.png
            2. icon.svg
            3. license.standard
              1. a.city.at.night.jpg
              2. average.source.code.image.generator.jpg
              3. average.source.code.insight.jpg
              4. average.source.code.jpg
              5. bird_s.banner.jpg
              6. black.background.blog.discovery.0.jpg
              7. black.background.blog.discovery.1.jpg
              8. black.background.blog.programming.0.jpg
              9. black.background.cooperation.discovery.jpg
              10. community.2016.12.11.chrom.0.dina4.jpg
              11. community.DSC02958.jpg
              12. community.DSC03192.jpg
              13. community.DSC03197.jpg
              14. dream.about.a.city.at.night.jpg
              15. gallery.0.jpg
              16. gallery.1.jpg
              17. gallery.2.jpg
              18. gallery.3.jpg
              19. gallery.4.jpg
              20. gallery.5.jpg
              21. gallery.6.jpg
              22. gallery.7.jpg
              23. little_big_present.jpg
              24. net.splitcells.network.logo.jpg
              25. neural.birds.2.jpg
              26. neural.birds.3.jpg
              27. neural.birds.4.jpg
              28. neural.birds.5.jpg
              29. neural.birds.6.jpg
              30. night.at.home.jpg
              31. simple.bird.jpg
              32. simple.ruins.jpg
              33. some_things_are_done_without_reason.1.jpg
              34. some_things_are_done_without_reason.2.jpg
              35. some_things_are_done_without_reason.3.jpg
              36. starting-to-learn-how-to-draw-a-face.jpg
              37. surreal.biological.cell.jpg
              38. thumbnail
                1. big
                  1. medium
                    1. small
                    2. white.background.blog.discovery.0.jpg
                    3. white.background.blog.discovery.1.jpg
                    4. white.background.blog.programming.0.jpg
                    5. white.background.cooperation.discovery.jpg
                    6. white.dream.about.a.city.at.night.jpg
                    7. white.project.logo.art.jpg
                    8. white.project.logo.generic.allocator.jpg
                2. index.html
                3. info
                  1. about-this-site.html
                  2. contact.html
                  3. visibility-problem.html
                  4. xml-based-blog-framework-for-splitcells-net.html
                4. js
                  1. advertisment.js
                  2. basic.default.js
                  3. basic.js
                  4. jquery.particleground.min.js
                  5. math-jax
                    1. tex-mml-chtml.js
                  6. syntaxhighlighter.white
                    1. index.html
                    2. syntaxhighlighter.js
                    3. syntaxhighlighter.js.map
                    4. theme.css
                5. legal
                  1. impressum.html
                  2. licensing.html
                  3. privacy-policy.html
                6. license-AGPL-3-0.txt
                7. license-Apache-2-0.txt
                8. license-CC-BY-SA-4.txt
                9. license-CC0-1-0.txt
                10. license-MIT.txt
                11. premature-content.html
                12. programming
                  1. calculus-languages.html
                  2. math-formulas-implementation-pitfall.html
                  3. programming-language-concepts.html
                  4. simplifying-the-ast-of-set-manipulation-via-foreach.html
                13. programs
                  1. index.html
                  2. search.html
                  3. vnc-client.html
                14. projects
                  1. index.html
                  2. operation-system-state-interface.html
                15. protocol
                  1. feed.atom.html
                  2. feed.rss.html
                  3. http-404-not-found.html
                  4. sitemap.html
                16. symbiosis
                  1. an-attempt-at-defining-intelligence.html
                  2. apocrypha-of-free-open-source-software.html
                  3. apocrypha-of-software-development.html
                  4. free-will.html
                  5. funding-of-free-open-source-software.html
                  6. hate-as-a-popular-tool-in-politics.html
                  7. index.html
                  8. the-end-justifies-the-means.html
                  9. the-hug-of-life-and-death.html
                17. test.html
                18. unstructured-thoughts
                  1. a-review-on-the-dell-s-xps-15-9570-as-a-mobile-workstation.html
                  2. external-documentation.html
                  3. fun-and-chill.html
                  4. index.html
                  5. soundboard.html
                19. websites
                  1. cards
                    1. visiting
                      1. back.htm
                      2. back.jpg
                      3. front.htm
                      4. front.jpg
                20. white
                  1. 2015
                    1. 03
                      1. 01
            4. network
              1. CHANGELOG.html
              2. README.html
              3. deployment.html
              4. dictionary.html
              5. external-contribution.html
              6. guidelines
                1. changelog.html
                2. commonmark.html
                3. gist
                  1. git.html
                  2. pgp.html
                4. linking.html
                5. maven.html
                6. source-types.html
                7. tickets.html
              7. legal
                1. Developer_Certificate_of_Origin.v1.1.html
                2. Developer_Certificate_of_Origin.v1.1.txt
                3. licenses
                  1. Apache-2.0.html
                  2. Apache-2.0.txt
                  3. BSD-2-Clause.html
                  4. BSD-2-Clause.txt
                  5. BSD-3-Clause.html
                  6. BSD-3-Clause.txt
                  7. EPL-2.0.html
                  8. EPL-2.0.txt
                  9. GPL-2.0-or-later-WITH-Classpath-exception-2.0.html
                  10. GPL-2.0-or-later-WITH-Classpath-exception-2.0.txt
                  11. ISC.html
                  12. ISC.txt
                  13. LGPL-2.1-or-later.html
                  14. LGPL-2.1-or-later.txt
                  15. MIT.html
                  16. MIT.txt
                  17. MPL-2.0.html
                  18. MPL-2.0.txt
              8. overview.html
              9. project.html
              10. tickets
                1. done
                  1. 0.html
                  2. 2.html
                  3. 77.html
                2. index.html
                3. open
                  1. 10.html
                  2. 37.html
                  3. 71.html
                  4. 72.html
            5. system
              1. README.html
              2. index.html
              3. project.html
            6. website
              1. 404.html
              2. css
                1. basic.css
                2. basic.themed.css
                3. den.css
                4. gallery.themed.css
                5. graphml.css
                6. layout.column.main.fullscreen.css
                7. layout.cooperation.css
                8. layout.default.css
                9. layout.default.with.two.main.columns.css
                10. theme.black.variables.css
                11. theme.white.variables.css
                12. theme.white.yellow.variables.css
              3. den
                1. style.css
                2. test.html
                3. test.minimal.html
              4. empty.html
              5. images
                1. icon.png
                2. icon.svg
                3. license.standard
                  1. a.city.at.night.jpg
                  2. average.source.code.image.generator.jpg
                  3. average.source.code.insight.jpg
                  4. average.source.code.jpg
                  5. bird_s.banner.jpg
                  6. black.background.blog.discovery.0.jpg
                  7. black.background.blog.discovery.1.jpg
                  8. black.background.blog.programming.0.jpg
                  9. black.background.cooperation.discovery.jpg
                  10. community.2016.12.11.chrom.0.dina4.jpg
                  11. community.DSC02958.jpg
                  12. community.DSC03192.jpg
                  13. community.DSC03197.jpg
                  14. dream.about.a.city.at.night.jpg
                  15. gallery.0.jpg
                  16. gallery.1.jpg
                  17. gallery.2.jpg
                  18. gallery.3.jpg
                  19. gallery.4.jpg
                  20. gallery.5.jpg
                  21. gallery.6.jpg
                  22. gallery.7.jpg
                  23. little_big_present.jpg
                  24. net.splitcells.network.logo.jpg
                  25. neural.birds.2.jpg
                  26. neural.birds.3.jpg
                  27. neural.birds.4.jpg
                  28. neural.birds.5.jpg
                  29. neural.birds.6.jpg
                  30. night.at.home.jpg
                  31. simple.bird.jpg
                  32. simple.ruins.jpg
                  33. some_things_are_done_without_reason.1.jpg
                  34. some_things_are_done_without_reason.2.jpg
                  35. some_things_are_done_without_reason.3.jpg
                  36. starting-to-learn-how-to-draw-a-face.jpg
                  37. surreal.biological.cell.jpg
                  38. thumbnail
                    1. big
                      1. a.city.at.night.jpg
                      2. average.source.code.image.generator.jpg
                      3. average.source.code.insight.jpg
                      4. average.source.code.jpg
                      5. bird_s.banner.jpg
                      6. community.2016.12.11.chrom.0.dina4.jpg
                      7. community.DSC02958.jpg
                      8. community.DSC03192.jpg
                      9. community.DSC03197.jpg
                      10. dream.about.a.city.at.night.jpg
                      11. little_big_present.jpg
                      12. neural.birds.2.jpg
                      13. neural.birds.3.jpg
                      14. neural.birds.4.jpg
                      15. neural.birds.5.jpg
                      16. neural.birds.6.jpg
                      17. night.at.home.jpg
                      18. simple.bird.jpg
                      19. simple.ruins.jpg
                      20. some_things_are_done_without_reason.1.jpg
                      21. some_things_are_done_without_reason.2.jpg
                      22. some_things_are_done_without_reason.3.jpg
                      23. starting-to-learn-how-to-draw-a-face.jpg
                      24. surreal.biological.cell.jpg
                      25. white.project.logo.art.jpg
                      26. white.project.logo.generic.allocator.jpg
                    2. medium
                      1. a.city.at.night.jpg
                      2. average.source.code.image.generator.jpg
                      3. average.source.code.insight.jpg
                      4. average.source.code.jpg
                      5. bird_s.banner.jpg
                      6. community.2016.12.11.chrom.0.dina4.jpg
                      7. community.DSC02958.jpg
                      8. community.DSC03192.jpg
                      9. community.DSC03197.jpg
                      10. dream.about.a.city.at.night.jpg
                      11. gallery.0.jpg
                      12. gallery.1.jpg
                      13. gallery.2.jpg
                      14. gallery.3.jpg
                      15. gallery.4.jpg
                      16. gallery.5.jpg
                      17. gallery.6.jpg
                      18. gallery.7.jpg
                      19. little_big_present.jpg
                      20. neural.birds.2.jpg
                      21. neural.birds.3.jpg
                      22. neural.birds.4.jpg
                      23. neural.birds.5.jpg
                      24. neural.birds.6.jpg
                      25. night.at.home.jpg
                      26. simple.bird.jpg
                      27. simple.ruins.jpg
                      28. some_things_are_done_without_reason.1.jpg
                      29. some_things_are_done_without_reason.2.jpg
                      30. some_things_are_done_without_reason.3.jpg
                      31. starting-to-learn-how-to-draw-a-face.jpg
                      32. surreal.biological.cell.jpg
                      33. white.project.logo.art.jpg
                      34. white.project.logo.generic.allocator.jpg
                    3. small
                      1. a.city.at.night.jpg
                      2. average.source.code.image.generator.jpg
                      3. average.source.code.insight.jpg
                      4. average.source.code.jpg
                      5. bird_s.banner.jpg
                      6. community.2016.12.11.chrom.0.dina4.jpg
                      7. community.DSC02958.jpg
                      8. community.DSC03192.jpg
                      9. community.DSC03197.jpg
                      10. dream.about.a.city.at.night.jpg
                      11. little_big_present.jpg
                      12. neural.birds.2.jpg
                      13. neural.birds.3.jpg
                      14. neural.birds.4.jpg
                      15. neural.birds.5.jpg
                      16. neural.birds.6.jpg
                      17. night.at.home.jpg
                      18. simple.bird.jpg
                      19. simple.ruins.jpg
                      20. some_things_are_done_without_reason.1.jpg
                      21. some_things_are_done_without_reason.2.jpg
                      22. some_things_are_done_without_reason.3.jpg
                      23. starting-to-learn-how-to-draw-a-face.jpg
                      24. surreal.biological.cell.jpg
                      25. white.project.logo.art.jpg
                      26. white.project.logo.generic.allocator.jpg
                  39. white.background.blog.discovery.0.jpg
                  40. white.background.blog.discovery.1.jpg
                  41. white.background.blog.programming.0.jpg
                  42. white.background.cooperation.discovery.jpg
                  43. white.dream.about.a.city.at.night.jpg
                  44. white.project.logo.art.jpg
                  45. white.project.logo.generic.allocator.jpg
              6. index.html
              7. js
                1. advertisment.js
                2. basic.default.js
                3. basic.js
                4. math-jax
                  1. tex-mml-chtml.js
                5. syntaxhighlighter.white
                  1. index.html
                  2. syntaxhighlighter.js
                  3. syntaxhighlighter.js.map
                  4. theme.css
              8. license-AGPL-3-0.txt
              9. license-Apache-2-0.txt
              10. license-CC-BY-SA-4.txt
              11. license-CC0-1-0.txt
              12. license-MIT.txt
              13. white
                1. 2015
                  1. 03
                    1. 01
                      1. impressum.html