Function Optimization

Function Optimization 

Some of the problems we need to find maximum or minimum of different d structures for a function. If data structure is a set of points on space, then the function can be assumed as landscape over a space.

    These type of space related problems can be solved using a technique called Hill climbing, In this technique we traverse by moving from one point to adjacent point which having highest elevation.

Hill Climbing Procedure: Look at all immediate successor of current state 'n'.  If there exists a successor 'n' such that the f(n) > f(m) and f(n) > = f(n) or f(n) ≥ f(t) for all the successors 't' of 'm' then move from 'm' to 'n'. Else, halt at 'm'. Looks one step ahead to determine, any successor is better than the current state, if there is one then move to best successor the bill climbing technique usually does not  allow back tracking or jumping to an alternative path since there is no nodes list of other candidate granter nodes from which the search could be resumed or continued. Not complete, because of the certain constraints such as sense, the search terminates at the 'local maxima', 'plateaux' and 'ridges'. Therefore these drawbacks are always problematical.

Local maxima: A local maxima is a peak which is lower than the highest peak in the state space on a local maxima, will climbing hill halt, though inspite of better solution. . 

Plateaux: It is an area of state space where the evaluation function is flat. It is flat local maxima, from which no uphill exists (or) shoulder. Therefore it could not make progress. The same is depicted in the diagram as shown graphically in the below Figure,

Fig: State Space Correspond to an Objective Function 

Ridge: Ridge is area of search space that is higher than surrounding areas and that itself has a slope. But orientation of high region compared to or set of available moves, makes it impossible to traverse a ridge. 

Algorithm for Hill-Climbing 

Function Hill_Climbing (problem) returns a solutions state.

Inputs: problem, a problem

State: current, a problem next, a node 

current ← make_node (initial_state [problem]) 

loop do 

next ← a highest valued successor of a current node. 

if value [next] < value [current] then return current 

current ← next 

Hill climbing is similar to the DFS, in which the most promising child node is selected for expansion at each point, a successor node that appears to lead most quickly to the top of the hill, i.e., the goal is selected for exploration.

1. Evaluate the initial. If it is a goal state then return it and quit. Else, continue. with the initial state and name it as the current state. 
2. Loop until a solution is found or until there are no new operators to be applied. . 
• i) Select an operator that has not yet been applied to the current state and apply it to produce a new one node state. 
• ii) Evaluate this new state node, and
• If it is not the goal state, then return it and quit 
• If it is not the goal state but better than the current stat than make the new state as the current state.
• If it is not better than the current state then simply resume or continue in the loop.

Disadvantages

1. Local Maxima: It a state which is better than all its neighbors but is not better than some others states which are further away. At this point, all moves appear to make things worse. They are hence also called foot hills.
2. A Plateaux: It is a flat area of the search space in which a' whole set of neighboring states have the same value. Here it is not possible to determine the best direction in which to move.
3. A Ridge: It is a special kind of local maximum. It is an area of the search space that is higher than the surrounding area. But the orientation of higher region, compared to the set of available moves and the directions in which they move, makes it impossible to traverse a ridge by a single moves.

Simulate Annealing: Is a variation of hill climbing technique and we describe it as valley descending. Here we use the term objective or informative which aims at minimizing the value. The objective is also called goal simulated annealing is patterned after the physical process of annealing in which physical substances such as metals are melted and then gradually cooled until some solid state is reached.

The goal is to produce a minimal energy final state. There is some probability that a transition to a higher state will occur probability is given as, 

        P = e^-ΔE/KT

Where the ΔE is the positive change in the energy level. 

        T is the temperature, 

        K is Boltzman constant.

The rate at which the system is cooled is called the 'Annealing Schedule'. T    he variable k describes the correspondence between the units of temperature and the units of energy, Since, in analogous process, the units for both E and T are artificial, it makes no sense to include k into T, selecting values for T that produce desirable behavior in the algorithms. Therefore, we revise probability formula as, 

        P' = e^-ΔE/T

The three points that makes simulated annealing different from simple hill climbing are, 

1. The annealing schedule must be maintained. 
2. Moves to the worse states must be considered. 
3. We need to maintain the best state found so far, in case the final state worse than the earlier state, then earlier state, will be still available.