Give an overview over optimization problems

Optimization Problem

An optimization problem is one where all states/nodes can be a solution (to different degrees) but the target is to find the state that optimizes (min, max, ...) the solution according to an objective function. I.e., finding "best" states; there are no (explicit) goal state and also no path (costs).

Objective/Evaluation Function (Zielfunktion)

tells how good a state is, also in comparison to other states

either minimized or maximized depending on the optimization problem

Key Terminologies in Local Search

Global Optimum

A global optimum is the extremum (minimum or maximum) of the objective function for the entire input search space.

Local Optimum

A local optimum is the extremum (minimum or maximum) of the objective function for a given region of the input space, e.g., a basin in a minimization problem.

Local Search Algorithms in General

Local Search

Local search algorithms traversing only a single state rather than saving multiple paths in memory. It modifies its state iterative, trying to improve a criteria

-> In many optimization problems the sequence of actions and costs are irrelevant

-> goal is to find a state fulfilling all goal constraints not the path to reach it!

Advantages:

Uses a very little/constant amount of memory

Find a reasonable solution in very large state spaces (where systematical approaches fail)

Disadvantages:

No guarantees for completeness or optimality

What are design considerations for Local Search Algorithms?

Describe the Climbing Hill/ Greed Local Search!

Expand current state (all Neighbors)

Move to highest Evaluation

Repeat until reached a maximum

Problem:

might not be optimal (plateaus, ridges..)

The Climbing Hill Algorithm might not find the optimum. What can be done to get closer to the gobal optimum.

Last changed7 months ago