Artificial Intelligence INC 551 Lecture 4 Iterative Improvement Algorithms &

INC 551 Artificial

Intelligence

Lecture 4 Iterative Improvement Algorithms & Constraint Satisfaction Problems (CSP)

Deliberative Agent Agent

Action Make Decision

Environment World Model

Sense, Perceive

State-Action nodes or others

World Model Best action? (Black Box)

What is the best action? Similar to optimization problem

Search for Best Solution

Input 1 2 3 4 5 6 :

System

Output 23 12 192 175 34 16 :

Iterative Improvement Algorithms (Optimality Search) • Hill Climbing

• Simulated Annealing • Genetic Algorithms

Comparison มีจิงโจ้ ตาบอดทีต่ ้ องการพาตัวเองกระโดดขึน้ ไปบนยอดสู งสุ ดของยอดเขา • Hill Climbing จิงโจ้ ลองหย่ อนขาไปในทิศต่ างๆ ถ้ าสู งขึน้ ก็จะยอมก้ าว • Simulated Annealing จิงโจ้ กนิ เหล้ าเข้ าไปก้ าวผิดก้ าวถูก แต่ พอผ่ านไปก็จะสร่ างเมาแล้ วก้ าวถูกมากๆขึน้ • Genetic Algorithms ใช้ วธิ ีออกลูกหลานมากๆ แล้ วเรายิงจิงโจ้ ทอี่ ยู่ต่าๆทิง้ ไปเรื่ อยๆ จนในทีส่ ุ ด จะหวังว่ าจิงโจ้ ทเี่ หลืออยู่คือตัวทีอ่ ยู่สูงๆ

Hill Climbing ข้ อเสี ย สามารถติดอยู่ที่ local minima

“ลองก้ าว” ถ้ าสู งกว่ าเดิมก็ไป

8-queen problem

วาง queen 8 ตัวให้ ไม่ สามารถกินกันได้

Thinking

ชนกัน = 5 คู่

ชนกัน = 3 คู่

ชนกัน = 1 คู่

Traveling Salesman Problem

หาเส้ นทางทีส่ ้ั นทีส่ ุ ดทีเ่ ชื่ อมเมืองเป็ น chain

Thinking

ระยะทางรวม = 230

ระยะทางรวม = 110

Simulated Annealing

คล้าย hill-climbing แต่ จะเดินลงเขาด้ วย ด้ วย probability

T ลดลงเรื่ อยๆเมื่อเวลาผ่ านไปจนเป็ น 0

e E / T

Evolutionary Algorithms

• Genetic Algorithms (GA)

• Evolutionary Strategies (ES) • Evolution Programming (EP)

Objective of the Algorithms Finding a Maximum or minimum

(numerical way) เหมาะสาหรับปัญหาทีไ่ ม่ ทราบอะไรเกีย่ วกะมันเลย รู้แค่ มี input อย่ างนี้ output ออกมาเป็ นอย่ างนี้

Evolutionary Algorithm 1. 2. 3. 4. 5.

Initial Population Representation Evaluation Selection Crossover Mutation

8-Queen Crossover Example

Heuristics of Evolutionary Algorithms

Input 1 2 3 4 5 6 :

System

แถวๆนีน้ ่ าจะดี ลองเยอะๆหน่ อย โดยลองค่ าทีม่ าจากคุณสมบัติ ของ 2 ค่ านีเ้ ช่ น 3.6

Output 23 12 192 175 34 16 :

Evolutionary Algorithms

Input 1 2 3 4 5 6 : Population

System

Fitness Function

Output 23 12 192 175 34 16 :

Evaluation

1 2 3 4 5 6

(Mutation, Recombination)

Breeding

Initial Population

Selection

1 2 3 4 5 6

2.1 3.2 4.3 5.4 5.2 6.4

Evaluation

Add offsprings

3.2 3 4.3 4 5 5.2 New population in the next era

Procedure of Evolutionary Algorithms

Create initial random population Evaluate fitness of each individual Termination criteria satisfied ?

yes

no

Select parents according to fitness Recombine parents to generate offspring Mutate offspring Replace population by new offspring

stop

Constraint Satisfaction Problems Variables – X1,X2,X3,…. Constraints – C1,C2,C3,…. ต้ องการหาค่ า X1,X2,X3,… ที่ satisfy C1,C2,C3,…. ปัญหาแบบนีส้ ามารถแก้ได้ ด้วยวิธีการ search

Example

Constraint Graph

Nodes คือ variables Link คือ constraints

Variables อันไหนเชื่ อมกันแสดงว่ ามี constraint ต่ อกัน

Example

Cryptarithmetic

Sudoku

Sudoku is a CSP problem.

Types of Constraints • Unary (เกีย่ วกับ 1 ตัวแปร เช่ น WA ≠ red) • Binary (เกีย่ วกับ 2 ตัวแปร เช่ น WA ≠ Q) • High-order (เกีย่ วกับ 2 ตัวแปร เช่ นใน Cryptarithmetic) • Preference (เป็ น soft constraint ทีเ่ กีย่ วกับ optimization เช่ น red < green)

Search Formulation Initial State = Empty set (no assignment to any variables) Successor function = Assign 1 value to 1 variable Goal = All constraints are satisfied

Search Choices

• Breadth – first

• Depth - first

Depth-first ที่ expand node ตาม constraint เรียก Backtracking search

• Breadth – first ได้ solution ที่ depth n อาจได้ solution ซ้ากันถ้ าคาตอบสลับกันได้ • Depth – first Depth จากัด = n ใช้ เนื้อทีแ่ ละเวลาน้ อย

Backtracking Search

Depth-first เป็ น uninformed search เราสามารถเพิม่ ประสิ ทธิภาพได้ จากการจัดลาดับ หรื อ ขจัด solution ทีไ่ ม่ น่าป็ นไปได้ จัดเป็ น informed search ด้ วย heuristics

Most-constraint Heuristic หรื อ minimum remaining values heuristic จะเลือก assign variable ทีม่ ี set of value น้ อยทีส่ ุ ดก่ อน หรื อ variable ทีม่ ี constraints มากสุ ดก่ อน

Least-constraint Heuristic จะเลือก assign variable ให้ มี constraints กับ variables ทีเ่ หลือน้ อยทีส่ ุ ด

Forward checking Heuristic จะ keep track ค่ าทีเ่ ป็ นไปได้ ของแต่ ละ variable จะ backtrack เมื่อ variable ใดอันหนึ่งไม่ มคี ่ าทีจ่ ะเป็ นไปได้

Constraint Propagation Method Idea: การนาเอา constraints มาประกอบกันจะช่ วยให้ ลดจานวน node ได้

Arc Consistency Heuristic เป็ นวิธีการ propagate constraints แบบหนึ่ง จะมี list ของ constraints ทั้งหมดไว้ โดยทัว่ ไป จะเป็ น Queue แล้ วจะทาการ check ทีละอัน หลังจากนั้นจะทาการขจัด domain ของ variable ที่เป็ นไปไม่ ได้ ทงิ้ วิธีนีจ้ ะทาให้ ทราบล่ วงหน้ าเมื่อ variable assignment ใช้ ไม่ ได้

กฏ for every value of X, some value of Y must be true

OK!

กฏ for every value of X, some value of Y must be true

NSW = blue ทาให้ SA = ?? ดังนั้นตัด NSW = blue ออก

Blue ใน NSW ไป รัฐที่มี constraints ต้ องมา check ใหม่

พบว่ า detect error ได้ ก่อน forward checking ธรรมดา

Arc Consistency Algorithm (AC3)

Tree-Structure CSPs Problem ทีม่ ี constraint graph เป็ น tree (ไม่ เป็ น loop) จะมีข้นั ตอนการ solve ทีแ่ น่ นอนตายตัว

จะทาให้ ลดเวลาในการคิดอย่ างมาก

Nearly Tree-Structured CSPs

จะทาได้ โดยให้ ค่า SA fix ไปเลย แล้ วตัดออกไป ถ้ าไม่ ได้ กล็ องเปลีย่ นค่ า SA ใหม่