COMP 424 – Artificial Intelligence Constraint Satisfaction Problems
Instructors: Jackie CK Cheung and Readings: R&N Ch 6 (3rd or 4th ed)
Announcements
Copyright By PowCoder代写 加微信 powcoder
• Quiz 1 posted
• A1 posted
• Study guide 1 posted
• Final exam will be online take-home exam, centrally scheduled
Typical genetic algorithm
GA(Fitness, threshold, p, r, m)
• Initialize: P p random individuals
• Evaluate: for each h P, compute Fitness(h)
• While maxh Fitness(h) < threshold
• Select: Probabilistically select (1-r)p members of P to include in Ps
• Crossover: Probabilistically select rp/2 pairs of individuals from P.
For each pair (h1, h2), produce two offspring by applying a crossover operator. Include all offspring in Ps.
• Mutate: Invert a randomly selected bit in m*p randomly selected members of Ps
• Update: P Ps
• Evaluate: for each h P, compute Fitness(h)
• Return the individual from P that has the highest fitness.
Selection: Survival of the fittest
• As in natural evolution, fittest individuals are more likely to survive.
• Several ways to implement this idea:
1. Fitness proportionate selection:
Can lead to crowding (multiple copies being propagated).
2. Tournament selection:
Pick i, j at random with uniform probability. With prob p select the fitter
one. Only requires comparing two individuals.
3. Rank selection:
Sort all hypothesis by fitness. Probability of selection is proportional to rank.
4. Softmax (Boltzman) selection:
• Elitism: separately, store the best solution ever encountered 4
Genetic algorithms as search
• States: possible solutions
• Search operators: mutation, crossover, selection
• Relation to previous search algorithms:
• Parallel search, since several solutions are maintained in parallel
• Hill-climbing on the fitness function, but without following the gradient
• Mutation and crossover should allow us to get out of local minima
• Very related to simulated annealing.
Example: Solving TSP with a GA
• Each individual is a tour.
• Mutation swaps a pair of edges (many other operations
are possible and have been tried in literature.)
• Crossover cuts the parents in two and swaps them. Reject
any invalid offsprings.
• Fitness is the length of the tour.
• Note that GA operations (crossover and mutation) described here are fancier that the simple binary examples given before.
Example: Solving TSP with a GA
TSP example: Initial generation
TSP example: Generation 15
TSP example: Generation 30
The good and bad of GAs
• Intuitively appealing, due to evolution analogy.
• If tuned right, can be very effective (good solution with few steps.)
• Performance depends crucially on the problem encoding. Good
encodings are difficult to find!
• Many parameters to tweak! Bad parameter settings can result in very slow progress, or the algorithm is stuck in local minima.
• With mutation rate is too low, can get overcrowding (many copies of the identical individuals in the population).
• Optimization problems are widespread and important.
• It is infeasible to enumerate lots of solutions.
• Goal is to get a reasonable (not necessarily optimal) solution.
• Apply a local search and move in a promising direction.
• Hill climbing always moves in the (locally) best direction
• Simulated annealing allows some moves towards worse solutions
• Parallelism and beam search can be exploited to improve results;
find a better local optimum
• Genetic algorithms are an alternative related to simulated annealing which has an analogy to biological evolution
Specifying search problems
• So far, we have assumed that the search problem is given to us, for example as a search graph.
• How do we actually formulate practical problems as search?
• I have 5 midterms in the space of two weeks. The one for COMP 424 is before the one for COMP 551, but COMP 551 is pretty hard so I need to start studying in advance, because I cannot study more than 5 hours per course per week, or 8 hours in total across all the courses...
• Problems are often specified declaratively (i.e., we list what we know, not how to solve them), as constraints!
Searching with constraints
• Many other interesting problems have strict constraints: E.g. Must visit city A (to re-supply) before visiting city B (to sell).
• How can we incorporate this information in the search process?
• At a minimum, ensure the search will be limited to solutions that respect the constraints. Sometimes very few “legal solutions”.
• Even better, use the constraints to narrow the search space.
• Colour a map so that no adjacent territories have the same colour.
Constraint satisfaction problems (CSPs)
• A CSP is defined by:
• Set of variables Vi, that can take values from domain Di
• Set of constraints specifying what combinations of values are allowed (for subsets of variables, eg. pairs of variables)
• Constraints can be represented:
• Implicitly, as a function, testing for the satisfaction of the constraint.
E.g. C1C2
• Explicitly, as a list of allowable values. E.g. (C1=R, C2=G), (C1=G, C2=R),
(C1=B, C2=R), ...
• A CSP solution is an assignment of values to variables such that all the constraints are true.
• We typically want to find any solution or find that there is no solution.
• Variables WA, NT, Q, NSW, V, SA, T
• Domains Di = {red,green,blue}
• Constraints: adjacent regions must have different colors
• E.g., WA ≠ NT
• Solutions are complete and consistent assignments.
• E.g., WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green
• Every row, column, 3x3 block must contain exact one instance of a number from 1 to 9.
Initial state Solution
Image source: https://blogs.unimelb.edu.au/sciencecommunication/2016/10/23/i-promise-you-that-sudoku-could-win-you-a-million-dollars-but-youll-have-to-read-this-entire-blog-post-to-find-out-how/
Types of variables
Many possibilities
• Boolean variables (e.g., satisfiability)
• Finite domain, discrete variables (e.g., colouring)
• Infinite domain, discrete variables (e.g., integers)
• Continuous variables (e.g., reals).
Problem complexity? Ranges from solvable in poly-time (e.g. linear programming) to NP-complete to undecidable.
Types of constraints
• Unary: involve one variable
• Binary: involve two variables
• Higher-order (involve 3 or more variables)
• Relations:
• T1 + d1 ≤ T2 (Task2 has to come after Task1 ) Scheduling • Alldiff (variables in a row), Alldiff (variables in a column),
Alldiff (variables in a 3x3 square). Sudoku
• Preferences (soft constraints): can be represented using
costs and lead to constrained optimization problems.
Real-world CSPs
Often involves allocating limited resources:
• Timetable problems (e.g. which class is offered when,
• Hardware configuration.
• Transportation scheduling. Factory scheduling. Floor planning.
• Puzzle solving (crosswords, Sudoku)
Example: 4 queens problem
• Put 4 queens on 4x4 board so that none attack each other: Partial assignment:
• Formulate this as a CSP by defining:
• Variables and domains • Constraints
4 Queens Problem
Put one queen per column. Let value indicate row of each queen.
• Variables: {Q1, Q2, Q3, Q4}
• Domain (same for all variables): {1, 2, 3, 4}
• Constraints:
Qi Qj (cannot be in same row)
|Qi-Qj| |i - j| (cannot be in same diagonal)
• Can also translate each constraint into set of allowable values for its variables:
• Values for (Q1, Q2): (Q1 =1,Q2 = 3),(Q1 =1,Q2 = 4),(Q1 =2,Q2 = 4) etc.
Example: Sudoku
• Formulate sudoku as a CSP
Sudoku as a CSP
Overview of approaches for solving
• Constructive approach
• State is defined by the set of values assigned so far
• Apply forward search to fill the solution
• General-purpose algorithm which works for all CSPs
• Local search approach
• Start with a broken but complete assignment of values to variables
• Gradually fix broken constraints by re-assigning variables
• Use optimization approaches to decrease # broken constraints (hill- climbing, simulated annealing)
Constructive search for CSPs
• Problem definition:
• State: defined by set of values assigned so far, could be partial
and/or inconsistent assignment
• Initial state: all variables are unassigned.
• Operators: assign a value to an unassigned variable.
• Goal test: all variables assigned, no constraint violated. i.e., complete and consistent assignment
• Problem has deterministic action, fully observable state. Important observation: Depth is limited to the number of variables, n. So we can apply DFS (or depth-limited search)
• Color abstract map so that adjacent countries don’t same color.
• Variables: Countries Ci
• Domains: {Red, Blue, Green}
• Constraints: {C1C2, C1C5, ...}
Standard uninformed search for map coloring
choose 1 of n variables
choose 1 of d values for that variable
Is this complete? Optimal? choose 1 of (n -1)variables
choose 1 of d values for that variable
Is this a practical approach? What is the complexity?
Standard uninformed search for map coloring
choose 1 of n variables
choose 1 of d values for that variable
Is this complete? Optimal? choose 1 of (n -1)variables
choose 1 of d values for that variable
Yes: known solution depth. Yes: If we check the constraints.
Is this a practical approach? What is the complexity?
[n x d] x [(n-1) x d] x [(n-2) x d] x ...... x [2 x d] x d = n! dn
Analysis of the simple approach
Branching factor is very high:
∑i d (i sums over unassigned variables)
BUT: There can be only dn unique complete assignments. More important observations:
• Order in which variables are assigned is irrelevant -> Many paths are equivalent!
• Adding assignments cannot correct a violated constraint!
Backtracking search
At each step, pick a remaining unassigned variable at each level of search tree, then pick a value for that variable
• This way, b=|Di|
Algorithm:
• Select an unassigned variable, X.
• For each value={x1,…, xn} in the domain of that variable
• If the value satisfies the constraints, let X = xi and exit the loop.
• If an assignment was found, move to the next variable.
• If no assignment, go back to preceding variable and try different
• This is the basic uninformed algorithm for CSPs. • Can solve n-queens for n ≈ 25.
Backtracking search
At each step, pick a remaining unassigned variable at each level of search tree, then pick a value for that variable
• This way, b=|Di|
Algorithm:
• Select an unassigned variable, X.
• For each value={x1,…, xn} in the domain of that variable
• If the value satisfies the constraints, let X = xi and exit the loop.
• If an assignment was found, move to the next variable.
• If no assignment, go back to preceding variable and try different value.
Let’s focus on how we order the variables and the values for each variables
Heuristics:
Selecting a Variable
1. Minimum-remaining values: Choose the variable that is the most constrained (i.e., fewest legal values).
2. Degree heuristic: Choose the variable that is involved in the largest number of constraints on other unassigned values
• Use this to break ties from Minimum-remaining value heuristic
Applying this to Sudoku
• Every row, column, 3×3 block must contain exact one instance of a number from 1 to 9.
Selecting a Value
• Heuristic:
• Least-constraining value: Assign the value that rules out the
fewest values for other variables
• Note that we want the variable that is the most constrained with the fewest remaining values (to quickly rule out many possible solutions), but the value that is least constraining, to offer flexibility to find some solution.
To Be Continued
• How to further improve performance of backtracking search?
• Remove obvious inconsistencies in problem
• Other strategies to solve CSPs?
• Local search/optimization algorithms
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com