بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

Relaxed problems
مسائل تعديل شده

  • A problem with fewer restrictions on the actions is called a relaxed problem
    The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem
  • If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution
  • If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution
  • تركيب هيوريستيك ها: h(n)=max(h1(n), h2(n), .. hm(n))
  • اگر همه hiها قابل قبول باشند h(n) هم قابل قبول و اگر همه سازگار باشند h(n) هم سازگار خواهد بود

اسلاید 2 :

Local search algorithms

  • In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution, such as 8 queens problem
  • State space = set of "complete" configurations
  • Find configuration satisfying constraints, e.g., n-queens
  • In such cases, we can use local search algorithms
  • keep a single "current" state, try to improve it

اسلاید 3 :

Example: n-queens

  • Put n queens on an n × n board with no two queens on the same row, column, or diagonal

اسلاید 4 :

مزاياي جستجوي محلي

  • استفاده از حافظه بسيار كم تقريبا ثابت
  • امكان استفاده در فضاهاي حالت بزرگ و نا متناهي (پيوسته)

مناسب برای مسائل بهینه سازی.

اسلاید 5 :

Hill-climbing search

  • "Like climbing Everest in thick fog with amnesia”
  • همسايه هاي مجاور(توليد شده توسط تابع پسين) را بررسي مي كند و اگر حالتي بهتر است آن را جايگزين حالت فعلي ميكند

اسلاید 6 :

Hill-climbing search

  • Problem: depending on initial state, can get stuck in local maxima

اسلاید 7 :

Properties of simulated annealing search

  • One can prove: If T decreases slowly enough, then simulated annealing search will find a global optimum with probability approaching 1
  • Widely used in VLSI layout, airline scheduling, etc

اسلاید 8 :

Local beam search
جستجوي پرتوي محلي

  • Keep track of k states rather than just one
  • Start with k randomly generated states
  • At each iteration, all the successors of all k states are generated
    If any one is a goal state, stop; else select the k best successors (or randomly) from the complete list and repeat.

اسلاید 9 :

Genetic algorithms

  • Start with k randomly generated states (population)
  • A state is represented as a string over a finite alphabet (often a string of 0s and 1s)
  • Evaluation function (fitness function). Higher (sometimes lower) values for better states.
  • Produce the next generation of states by selection, crossover, and mutation
  • A successor state is generated by combining two parent states
  • A suitable GUI for GA in MATLAB: gatool

اسلاید 10 :

  • Fitness function: number of non-attacking pairs of queens (min = 0, max = 8 × 7/2 = 28)
    24/(24+23+20+11) = 31%
    23/(24+23+20+11) = 29% etc
در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید