COSC 4426 Topics in

Download
Share  Add to  Flag Embed
Uploaded from authorPOINTLite
Views:
 
Category: Entertainment
     
 
License:   All Rights Reserved

Presentation Description

No description available.

Comments

Presentation Transcript

COSC 4426 Topics in Computer Science II Discrete Optimization: 

COSC 4426 Topics in Computer Science II Discrete Optimization Good results with problems that are too big for people or computers to solve completely http://mathworld.wolfram.com/TravelingSalesmanProblem.html

Difficult problems: 

Difficult problems hard to represent (what information, what data structures) no known algorithms no known efficient algorithms this course: discreet variable problems

Examples: 

Examples practical examples scheduling (transportation, timetables,…) puzzles crosswords, Sudoku, n Queens classic examples SAT: propositional satisfiability problem (independent parameters) CSP: constraint satisfaction problem (dependent parameters) TSP: travelling salesman problem (permutations)

SAT: propositional satisfiability problem: 

SAT: propositional satisfiability problem n propositions, P1, P2, P3, …, Pn What combination of truth values makes a sentence true? Table has 2n rows. n=50, 250 = 1,125,899,906,842,624 n=2; 22 = 4 rows

CSP: constraint satisfaction problem: 

CSP: constraint satisfaction problem example – map colouring n countries – 4 possible colours constraints: adjacent countries different colours 4n combinations n=13; 413 = 67,108,864 combinations; 25 constraints

TSP: traveling salesman(sic) problem: 

TSP: traveling salesman(sic) problem n cities: what is shortest path visiting all cities, C1, C2, C3, …, Cn once? (n-1)! routes from home city on complete graph n = 16; (n-1)! = 1,307,674,368,000 C1 n = 5; (n-1)! = 24

Silly Example – one variable: 

Silly Example – one variable mark in class based on hours attended number of hours, h, is between 0 and 36 find optimal attendance (best h) if mark m is m = 3h - 8 mark m is m = 20h - h2 mark m is m = (5h/9 – 10)2 mark m is m = h3 mod 101 mark m is m = markarray[h]

Slide8: 

m = 3h - 8

Slide9: 

m = 3h – 8 m = 20h - h2 m = (5h/9 – 10)2 global optimum

Slide10: 

m = h3 mod 101 local optimum

Slide11: 

m = h3 mod 101 m = markarray[h]

Problem description: 

Problem description fitness function (optimization function, evaluation) – e.g., m = h3 mod 101 constraints (conditions) – e.g., 0 ≤ h ≤ 36 find global optimum of fitness function without violating constraints OR getting stuck at local optimum small space: complete search large space: ?????

Large problems: 

Large problems more possible values more parameters, n = {n1, n2, n3, …} more constraints more complex fitness functions - takes significant time to calculate m = f(n)  too big for exhaustive search

Searching without searching everywhere: 

Searching without searching everywhere How to search intelligently/efficiently using information in the problem: -hill climbing -simulated annealing -genetic algorithms -constraint satisfaction -A* - …

Focusing search: 

Focusing search assumption – some pattern to the distribution of the fitness function finding the height of land in a forest - can only see ‘local’ structure - easy to find a hilltop but are there other higher hills?

Fitness function distribution: 

Fitness function distribution convex – easy – start anywhere, make local decisions

Fitness function distribution: 

Fitness function distribution many local maxima make local decisions but don’t get trapped

Course outline: 

Course outline textbook – Michalewicz and Fogel (reasonable price, valuable book) lectures, notes and ppt presentations evaluation assignments project tests final exam