3 - Optimization

Local Search

Hill Climbing

Choose a random state, and keep moving to a better neighbor state.
It can find the local extrema.
Variants:

• Steepest-ascent - always 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
• Local beam search - choose the k-highest-valued neighbor

Simulated Annealing

High temperature to lower temperature.
Less and less likely to accept worse result.

Function Simulated-Annealing (problem, max):

• current = initial state of problem
• For t = 1 to max:
  • T = Temperature (t)
  • neighbor = random neighbor of current
  • ΔE = how much better neighbor is than current
  • If ΔE > 0:
    • current = neighbor
  • With probability e^(ΔE/T) set current = neighbor
• Return current

Local search can be used to solve TSP problem.

Linear Programing

• Minimize c_{1}x_{1}+\dots+c_{n}x_{n}.
• With constraints of form a_{1}x_{1}+\dots+a_{n}x_{n}\leq b or a_{1}x_{1}+\dots+a_{n}x_{n}=b.
• With bounds for each variable l_{i}\leq x_{i}\leq u_{i}.

Algorithms:

• Simplex
• Interior Points

import scipy.optimize

# Objective Function: 50x_1 + 80x_2
# Constraint 1: 5x_1 + 2x_2 <= 20
# Constraint 2: -10x_1 + -12x_2 <= -90

result = scipy.optimize.linprog(
    [50, 80],  # Cost function: 50x_1 + 80x_2
    A_ub=[[5, 2], [-10, -12]],  # Coefficients for inequalities
    b_ub=[20, -90],  # Constraints for inequalities: 20 and -90
)

if result.success:
    print(f"X1: {round(result.x[0], 2)} hours")
    print(f"X2: {round(result.x[1], 2)} hours")
else:
    print("No solution")

Constraint Satisfaction

• Set of variables \{ X_{1},X_{2},\dots,X_{n} \}
• Set of domains for each variable \{D_{1},D_{2},\dots,D_{n}\}
• Set of constraint C

Graph of constraints : use a graph to express the constraints

• Hard constraints - must be satisfied
• Soft constraints - preferred to be satisfied
• Unary constraint - 1 variable
• Binary constraint - 2 variable

An edge connecting A and B - binary constriant (A,B)
Node consistency - unary constraint for A - remove some values from A ‘s domain
Arc consistency - binary constraint - edge

Function Revise (csp, 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

Function AC-3 (csp):

• queue = all arcs in csp
• While queue non-empty:
  • (X, Y) = Dequeue (queue)
  • If Revise (csp, X, Y):
    • If size of X. Domain == 0:
      • Return false
    • For each Z in X. Neighbors - {Y}:
      • Enqueue (queue, (Z, X))
• Return true

Backtracking Search

CSPs as Search Problems
（Assigning each variable with a value and checking the constraints）

Function Backtrack (assignment, csp):

• If assignment complete:
  • Return assignment
• var = Select-Unassigned-Var (assignment, csp)
• For value in Domain-Values (var, assignment, csp):
  • If value consistent with assignment:
    • Add {var = value} to assignment
    • result = Backtrack (assignment, csp)
    • If result ≠ failure:
      • Return result
    • remove {var = value} from assignment
• Return failure

Enhanced version: Maintaining Arc-Consistency

• Enforcing arc-consistency every time we make a new assignment
• Call AC-3

Select-Unassigned-Var

• Minimum remaining values heuristic - select the smallest value
• Degree heuristic - select the highest degree

Domain-Values

• Least-constraining Values Heuristic: return values in order by #(choices ruled out for neighboring variables)