Artificial Intelligence: Optimization

Optimization is a continuous process in AI, and researchers and practitioners often explore new methods and techniques to enhance the efficiency and effectiveness of AI systems. It involves a balance between achieving better performance and considering computational constraints.

Local Search

A local search algorithm is an optimization algorithm that iteratively explores the solution space by making incremental changes to a current solution with the goal of finding an optimal or satisfactory solution. Unlike global search algorithms that explore the entire solution space, local search algorithms focus on improving a single solution through local moves.

Current State: an initial starting point to be considered
Neighborhood: a state that the current state can transition to. A neighborhood function defines the set of neighboring solutions that can be reached from the current solution by making small modifications or changes.
Cost Function: an evaluation function that assigns a value or score to each solution based on how well it satisfies the optimization criteria. The goal is to minimize this value by distance to the hospital.
Objective Function: explores the neighborhood of the current solution, moving to a neighboring solution that improves the evaluation function score.
Termination Criteria: a stopping criterion is met. This could be a certain number of iterations, reaching a satisfactory solution, or other specified conditions.

Local search algorithms are often used in problems where the solution space is too large to be exhaustively searched. They are particularly effective in cases where finding a global optimum is not necessary, and a locally optimal solution is sufficient.

Examples of local search algorithms include:

• Hill Climbing(problem): Iteratively moves toward the direction of increasing elevation (improvement in the objective function). In pseudocode:

function Hill-Climb(problem):
    current = initial state of problem
    repeat:
        neighbor = best valued neighbor of current
        if neighbor not better than current:
            return current
        current = neighbor

• Simulated Annealing: Allows for occasional moves to worse solutions to escape local optima and explore a broader solution space.

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
        else:
            with probability e^(ΔE/T) set current = neighbor
    return current

Local search algorithms are widely used in various fields, including artificial intelligence, operations research, and optimization problems in computer science and engineering.

Linear Programming with Sudoku

Cost Function: the objective we want to minimize. For Sudoku, we don't have a cost function in the traditional sense, as we aim to find a feasible solution rather than optimize a cost. However, in linear programming terms, this could be associated with the effort or resources required to fill in the cells.

Constraints: the limitations on the variables. In Sudoku, variables are the values placed in each cell. Constraints ensure that the values placed in the cells adhere to the rules of Sudoku:

• Each row must contain unique numbers.
• Each column must contain unique numbers.
• Each 3x3 subgrid must contain unique numbers.

Bounds on Variables:

• Variables (cell values in Sudoku) are bounded by the set {1, 2, 3, 4, 5, 6, 7, 8, 9}. They cannot take negative values or exceed 9.

Example:

Consider a 4x4 Sudoku puzzle:

2 _ | _ _
_ _ | _ 1
_ 3 | 4 _
_ _ | _ 2

• Cost Function:
  • There is no explicit cost function in Sudoku, but we can associate a minimalistic objective, such as minimizing the effort or number of filled cells.
• Constraints:
  • Each row, column, and 2x2 subgrid must contain unique numbers. This can be represented as linear constraints, ensuring the sum of variables in each set is equal to the size of the set:
    • Row 1: Row 1: x11​+x12​+x13​+x14​=10
    • Column 1: x11​+x21​+x31​+x41​=10
    • Subgrid 1: x11​+x12​+x21​+x22​=10
• Bounds on Variables:
  • 1≤xij​≤4 for each cell in the 4x4 Sudoku puzzle.

This adaptation illustrates how the components of linear programming, such as the cost function, constraints, and variable bounds, can be applied to model and solve optimization problems like Sudoku. Keep in mind that Sudoku is typically solved using constraint satisfaction techniques, but linear programming concepts can be applied for modeling purposes.

Constraint Satisfaction with Sudoku

A problem-solving paradigm that deals with problems where the goal is to find a solution that satisfies a set of constraints.

Problem Representation:

• Variables: Each cell in the Sudoku grid is a variable.
• Domains: The domain of each variable is the set of numbers {1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Constraints: The constraints are derived from the rules of Sudoku, where each row, column, and 3x3 subgrid must contain unique numbers from 1 to 9.

Example:
Consider the following Sudoku puzzle:

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ 3 5
_ _ _ | _ 8 _ | _ 7 9

Constraint Satisfaction:

Initial State: Variables are the empty cells with domains {1, 2, 3, 4, 5, 6, 7, 8, 9}.

Constraints: Rows, columns, and subgrids must contain unique numbers. For example, in the first row, there must be no repeated numbers.

Constraints Propagation:Initially, some cells may have unique solutions based on the given numbers. For example, the first cell in the top-left (5) constrains the neighboring cells.

Backtracking: Use backtracking to systematically fill in values for empty cells, considering constraints. If a conflict arises (e.g., violating a constraint), backtrack to a previous state and try a different value.

function Solve-Sudoku(board):
    if board is complete:
        return board
    var = Select-Unassigned-Cell(board)
    for value in Domain-Values(var, board):
        if value consistent with assignment:
            set cell value to board
            result = Solve-Sudoku(board)
            if result is not failure:
                return result
            reset cell value to empty (undo assignment)
    return failure

Final State: Continue the process until all cells are filled, satisfying all constraints.

The solution to the above Sudoku puzzle would be a consistent assignment of values to all variables, ensuring that each row, column, and subgrid contains unique numbers from 1 to 9. The final state represents a completed and valid Sudoku solution.

[1]: Brian Yu, David J. Malan; Harvard University CS50's Introduction to Artificial Intelligence with Python

[2]: Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani, Jonathan Taylor; An Introduction to Statistical Learning with Applications in Python