Petrova digitální zahrada 🚀

KOP 7. lecture

7 min čtení

20% to remember

The majority of algorithms solving combinatorial problems operate in a state space or search space. The state space is a pair of two sets: 1) the set of states and 2) the set of operators. The states are represented by configuration variables and operators allow moves betwenn states (by changing values of configuration variables).

Properties of a state space:

  • completeness: when the state space includes all possible and available states for the problem (the encoding of the configuration variables has to be able to capture all states)
  • continuousness: when we are able to get from any state to another (and back) with defined operators

Search space: state space includes only “full configurations” with concrete values, whereas the search space also includes “partial configurations” with some undecided assignments of configuration variables.

  • state space is a subset of the search state

A complete method = will explore the whole state space A systematic method = will always visit each state only once (will not return)

Local heuristic methods

  • they greedily explore only the -neighborhood
  • heuristic: a function created by human that is driving the algorithm
  • two different types:
    • constructive method: starts from an empty configuration (trivial state) and tries to find a solution by assigning configuration variables (constructing). The number of steps is usually minimized (uses search space)
    • iterative method: starts from a given “full” state (can be random) and moves around the state space to find the optimum
  • examples:
    • Random Walk, First Improvement, Best-only
  • they tend to get stuck in the local optimum, how to solve it:
    • backtracking, complete search (bruteforce) etc.
      • extremely time-consuming
    • advanced methods (Simulated annealing, Genetic algorithms…)
      • higher iterative power, can escape local minimum, slower than simple local methods

Local vs. global methods

  • global methods do not operate with the state space

State space

  • operators are moving around the state space
  • state space is a pair of two sets: set of states and set of operators
  • operation performs a move in the state space (= changing the values of conf. variables)
    • precisely: the change of configuration and internal variable values
    • configuration variables have to be able to describe all possible combinations
  • important properties
    • by my state space I am able to get to any configuration
      • complete = there have to be all states
      • the encoding has to be good (it has to be able to encode all states = configurations)
    • every state must be reachable from any state (and back)
      • this is more strict
      • = continuous
    • example of complete, but not continuous state space:
      • encoding of configuration variables can encode all configurations = states
      • but in the State graph it is not possible to get from any state to another (and back)

State graph

  • there could be graph loops - but there are useless (they just represent “longer” ways to get from one state to another)
  • move from state to another state is: operation
  • it does not have to contain all configurations, but only those, which are possible (= pruning the search state)

Neighborhood

  • -neighbourhood size grows exponentially with

slide no. 15 - this state space is not continuous - it’s wrong

slide no. 25 - number of all possible states in TSP is

  • on the slide 25 there are only options starting from A and end in A
  • there is a big difference between instance graph and state space

State vs search space

  • state space
    • we know about all states in the state space, each state has a cost, or it could be computed (for optimization problems)
    • one state = complete configuration (the assignment of conf. variables is complete)
    • all states are defined
    • state with the best cost is looked for (all final costs are given or could be computed)
    • examples: Knapsack problem, TSP etc.
  • search space
    • item could have undecided parts of the solution = parts of the state = parts of the configuration
    • operations
      • decide (assign a value to undecided configuration variable)
      • backtrack = “undecide”, go back from assigned to undecided
        • this is often not used
    • state space is a subset of the search space
      • state space includes all “fully-assigned” configurations, meanwhile search space includes “fully-assigned” AND “partially-assigned” configurations
    • the (partial) cost of the state does not have to reflect the final cost of the state (= solution)
    • the number of visited states is usually minimized (optimization)
    • examples: Chess, Sokoban, planning problems, robot motion problems etc.

Exploration strategies for state space

  • complete state space exploration
    • brute-force, B&B
    • if the optimal solution exists, these methods will find them (but they are often really slow)
  • systematic state space exploration
    • each state is visited only once
    • also brute-force, B&B
  • iterative deepening
    • combination of DFS and BFS
    • continuous cutting by depth and the applying DFS from the start to explore the first part of the cut
  • blind exploration strategies
    • BFS, DFS, iterative deepening
    • they do not know the problem structure
  • informed search methods
    • they act on the problem nature and properties, often heuristic function is involved
    • heuristic function assigns each found state a cost
      • states with higher costs are preferred
    • example: A*

slide no. 47 - if I have a priority queue and all the priorities will be the same, the items will be drawn in the random order (it is not a queue)

  • in theory

  • in practice, in different languages, the implementation differ

  • Greediness means, that we are locally choosing the best option

  • Heuristics means that there is some function made by a human driving the algorithm

    • there is nothing said about the finding an optimum result or not (some can, some cannot)

Local heuristic methods

  • not complete = the optimum is not guaranteed
  • explores only a bounded neighborhood (-neighborhood)
  • constructive method = starting from scratch (the trivial state)
    • going through the search state (in most cases) and constructing the solution
  • iterative method = starting from some state
    • the state could be randomly generated
    • going purely through the state space and improving the solution
    • they are converging/approaching the optimum

Random walk

  • is finished when all iterations are exhausted or time limit passes
  • any move is taken (no matter the cost)
    • after each step, the best solution found so far is saved
  • not systematic (can visit same states again or go in a loop) and not complete

First improvement

  • somehow choose a new state (by performing an operation)
  • making only moves that improve the solution
  • it is systematic (it cannot return to visited state, since it only chooses better neighbors)
  • but it takes the first better neighbor (there could be even better neighbors)

Best only

  • first try all neighbors and then take the best one
    • keeping the local best

Best-first

  • the best neighbor is taken first and other neighbors are put into the priority queue
  • it is not local-based (just to compare it to the three local methods), it is complete

Getting stuck in local optimum

  • global optimum is the best solution possible
  • local optimum - best cost in the -neighborhood
  • if an algoritm begins with different initial states and they all converge to the same optimum, maybe we have found the global optimum (but we cannot be 100 % sure)
  • how to avoid local optimums:
    • increase -neighborhood (but I get slower exploration)
    • use randomized algorithms (for random restarts)
    • allow returns (Best-first, backtracking) - these are not polynomial

Handling unfeasible states

  • = states not meeting the constraints
  • death = do not admit infeasible states (if generated, generate a new one)
  • repair = include operators that can “repair” an unfeasible state
  • decoders = choose encoding such that only valid states could be generated
Relaxation
  • incorrect configurations are admitted, but are penalized (proportionally to their “incorrectness”)
  • every infeasible configuration has to be worse than any feasible solution (even the worst feasible configurations)
  • why use relaxation?
    • by admitting unfeasible state, we can explore other feasible states quickly (that are reachable only as neighbors of that unfeasible state)

Tutorial

  • Knapsack operators
    • adding + removing items (both must be there)
  • Minimum vertex cover operators
    • adding + removing items (both must be there)
  • TSP
    • switching two cities
    • be aware of the configuration variable
      • for permutation it’s okay
      • for general ordered list we have to introduce adding/removing cities
        • it can have missing cities, duplicite cities etc.
  • always ask:
    • are we complete with this operator?
    • are we continuous with this operator?
  • if the operation produces (or can produce) an infeasible state
    • we can deal with it later (e.g. using relaxation), but I have to mention it

Graf

Příchozí odkazy