Several mathematical functions take multiple parameters and, for some defined domain, can have widely varying generated values.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Function Optimization

Several mathematical functions take multiple parameters and, for some defined domain, can have widely varying generated values.

To optimize a function is to find a set of parameters that aims to approximate the global minimum or maximum

(depending on what you're searching for) of that function.

 

For example, if you wish to minimize a simple function like y=x2, for a domain of -5 ≤ x ≤ 5, there's a clear global minimum of x=0.

 

However, several more complicated functions have numerous local minima, and those minima (combined with a more complicated function) can make it trickier to easily identify the true global minimum.

 

To some extent, discretization (remember our third lab exercise?) can help us here. However, typical discretization will scan the entire domain with uniform spacing. Conversely, if we find a potentially good area within the domain, we'd actually want to further study that area with a far higher precision (possibly ignoring the rest of the domain entirely).

 

Naturally, all of this also applies to maximization; it's just the direction that changes.

 

The Egg Holder function is an interesting one. The generalized formula is scalable for multiple dimensions, and is written as:

𝑚−1

𝑓(𝑥) = ∑[−(𝑥𝑖+1 + 47)sin√|𝑥𝑖+1 + 𝑥𝑖⁄2 + 47| − 𝑥𝑖sin√|𝑥𝑖 − (𝑥𝑖+1 + 47)|]

𝑖=1

 

However, since we really just want two axes (x and y), we can more simply write it as:

𝑓(𝑥, 𝑦) = −(𝑦 + 47)sin(√| 𝑥⁄2 + 𝑦 + 47|) − 𝑥sin(√|𝑥 − 𝑦 − 47|)

 

The domain we'll use is -512 ≤ x,y ≤ +512.

 

Hill-Climbing

Let's consider a hypothetical local search. A local search is a basic mathematical search that, when presented with different possible moves in some search space, picks the move that appears to yield an improved outcome.

 

For example, if we were minimizing y=x2, and our current guess was x=0.2, then two potential new guesses might be 0.15 or 0.23. Since 0.15 would yield a preferable y value, that is what we would choose. We call it hill-climbing because, if we were trying to maximize, it would always choose the short-term decision that offered the highest immediate height.

 

Hill-climbers are very susceptible to local minima, so you typically need some additional tricks for them to be useful.

 

Parallel Hill-Climbers

Since a single hill climber isn't very intelligent, we can achieve better results by allowing multiple hill climbers to search in parallel. We'll achieve this by assigning a thread to each climber.

 

Thus, we shall formalize our hill-climbing algorithm as follows:

• We shall have a global concept of “best answer so far”

◦ This will include the lowest minimum found so far, as well as the x and y that yielded that value

◦ You may want to initialize this lowest minimum to something artificially high, and leave it to the climbers to immediately initialize it properly for you

• The user will be presented with a menu, asking for the number of climbers (threads) to run simultaneously

◦ You can assume a maximum of 8 climbers/threads (avoid taxing sandcastle while testing)

◦ If the user selects 0, the program exits

• Each climber has a current position (with corresponding current calculated height)

• Each climber will generate, at each step, 4 possible moves

◦ The best possible move (i.e. the one that generates the lowest calculated value) is the possible next move for that climber

◦ If the generated value would improve on the climber's current calculated height, make the move

▪ Otherwise, randomize the position of the climber, within the established [-512..+512] domain, and recalculate its height

• Whenever any climber finds a new global best minimum, it updates the global “best answer so far”

◦ Of course, this will require some form of mutual exclusion

• When the user presses ctrl+c, execution suspends, and the user is presented with the menu again

◦ If the user chooses to pick a number of threads to try again, the “global best” thus far is not forgotten

• At the very least, whenever the user presses ctrl+c to suspend, you must show the “global best” height (and corresponding x and y) thus far. You may wish to also include support for SIGUSR1, to display the current progress without suspending the search

 

 

Attachments:

Expert's Answer

680 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of