September 12, 2020

Intro to AI - Optimization

Definitions

search space

A set of possible states modeling the candidate solutions that need to be evaluated.

local search

Local search algorithms move from solution to a neighboring solution in the search space by applying local changes, until a solution deemed as optimal is found, or a time constraint is reached.

objective function

A Function that returns for any given state, a value reflecting some sort of value for a state is. Usually used in optimization Problems for finding maximums.

cost function

A Function that returns for any given state, a value reflecting some sort of cost for a state. Usually used in optimization Problem for finding minimums.

hill climbing

A simple algorithm that checks neighbor states and compares them with the current state in order to find a minimum or maximum for the cost or objective function in order to find an optimal state.

The problem of hill climbing algorithm is that it might get stuck in a local optimal solution, and not find the global optimal solution.

simulated annealing

Simulated annealing is a probabilistic technique for finding the global optimum in a given search space.

The algorithm is basically hill climbing except instead of picking always the best move, with a certain probability a worse move might be selected under a time and move quality dependant probability distribution.

linear programming

Linear programming algorithms, also called linear optimization are methods to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

constraint satisfaction

Constraint satisfaction algorithms model the process of finding a solution to a set of constraints that impose conditions that a set of variables must satisfy. Each variable has a domain of possible values, the algorithm picks the domains values for the variables that meet the constraints.
A Constraint satisfaction problem can be modeled as a graph with all involved variables as nodes and constraints referring to two variables as edges.

hard constraints

Hard constraints are constraints that must be satisfied in a correct solution.

soft constraints

Soft constraints that express some notion of which solutions are preferred over others.

unary constraints

Unary constraint are constraints involving only one single variable.

binary constraints

Binary constraints are constraints involving two variables.

node consistency

Node consistency is a property when all the values in a variable’s domain satisfy the variable’s unary constraints

arc consistency

when all the values in a variable’s domain satisfy the variable’s binary constraints.
A variable \$X\$ is called arc-consistent with respect to \$Y\$, if \$X's\$ domain only contains values for which a value in \$Y's\$ exist that any binary constraint for \$X\$ and \$Y\$ can be met.

Search Algorithms

Hill Climbing

pseudo code for the hill climbing algorithm

function hill-climb(problem):
  current_state = initial state of problem
  repeat:
    neighbor = highest value neighbor of current
    if neighbor not better than current
      return current_state  // found a solution
    current_state = neighbor

List of Hill Climbing Variants

steepest-ascent: choose the highest-valued neighbor
stochastic: choose randomly from higher-valued neighbors
first-choice: choose the first higher-valued neighbor
random-restart: conduct hill climbing multiple times, keep the best result
local-beam search: chooses the k highest-valued neighbors

Simulated Annealing

pseudo code for the simulated annealing algorithm

function simulated-annealing(problem, runtime):
  current_state = initial state of problem
  for t = 1 to runtime
    T = temperature(t)
    neighbor = randomg neighbor of current
    dE = how much better neighbor is than current
    if dE > 0:       // randomly found a better solution
      current_state = neighbor
    else with probability exp(dE/T):  // select a worse solution
      current_state = neighbor
  return current_state

Linear Programming

Linear Programming describes a problem that consists of:

a linear objective function defining the quantity to be optimized of the form:
\$f(x_1,x_2) = c_1x_1 + c_2x_2\$
a system of linear constraints:
\$a_11 x_1 + a_12 x_2 lt b_1\$
\$a_21 x_1 + a_22 x_2 lt b_2\$
\$a_31 x_1 + a_32 x_2 lt b_3\$
Non-negative variables:
\$x_1 ge 0\$
\$x_2 ge 0\$

There exists a number of statndard algorithms for solving linear programming problems, such as:

Simplex Algorithm
Interior-Point Algorithm

Constraint Satisfaction

Given a constrain satisfaction problem with:

Set of variables \${X_1, X_2, ..., X_n}\$
Set of domains for each variable \${D_1, D_2, ..., D_n}\$, each domain contains the possible values for a variable.
Set of constraints \$C\$.

To solve the problem the following algorithms can be used:

pseudocode for achieving arc consistency between any two variables \$X\$ and \$X\$

function revise(X, Y):
  revised = false
  for x in X.domain:
    if no y in Y.domain satisfies constraint for (X, Y):
      delete x from X.domain
      revised = true
  return revised

pseudocode to solve the while problem graph

function ac3():
  queue = all arcs
  while queue non-empty:
    (X, Y) = DEQUEUE(queue)
    if revise(X, Y):
      if size of X.domain == 0:
        return false       // no solution
      for each Z in X.neighbors - {Y}:
        ENQUEUE(queue, (Z, X))
  return true

A Constraint Satisfaction Problem can be turned into a Search Problems:

initial state: empty assignment (no variables)
actions: add a {variable = value} to assignment
transition model: shows how adding an assignment changes the assignment
goal test: check if all variables assigned and constraints all satisfied
path cost function: all paths have same cost

Backtracking Search

function backtrack(current_solution, constrain_satisfaction_problem):
  if current_solution is complete:
    return current_solution
  node = SELECT-UNASSIGNED-NODE(current_solution, constrain_satisfaction_problem)
  for value in DOMAIN-VALUES(node, current_solution, constrain_satisfaction_problem):
    if value consistent with current_solution:
      add {node = value} to current_solution
      result = BACKTRACK(current_solution, constrain_satisfaction_problem)  // recursion
      if result is not failure:
        return result
      remove {var = value} from assignment // backtrack, pick next value in loop
  return failure

Some possible optimizations of the algorithm:

applying interference: After adding \${node = value}\$ to the current solution it might be possible to reduce the solution space by applying interferences.
selecting unassigned node with minimum remaining values: When picking the unassigned node we can choose the node with the smallest domain, this reduces the number of values we have to try out in the next step.
selecting unassigned node with the highest degree: When picking the unassigned node we can choose the node with the highest number of edges, this effects the highest number of neighboring nodes and reduces the problem space.
selecting the domain value that is least constraining: When picking a domain value, picking the least constraining one makes it more likely we have to backtrack less often for finding the solution.