CS152

Project 6: Searching and Optimization

Now that we have a measure of the impact of darting on the elephant population we can proceed to the next step which is determining what is the optimal darting probability.

To do this we are going to use the Binary Search strategy and “bounce” around in the search space of possible darting probabilities. Of course, since there is no exact solution to this

problem we will also be specifying a tolerance to help us stop the search. Once we get this working we will expand the program so that it can handle optimizing multiple parameters.

Tasks

T1. Write a function to optimize the percent darted

Create a new file called optimize.py. Have the file import the sys, elephant, and random packages. Then create a function called optimize with the following algorithm.

# Executes a search to bring the result of the function optfunc to zero.

# min: minimum parameter value to search

# max: maximum parameter value to search

# optfunc: function to optimize

# parameters: optional parameter list to pass to optfunc

# tolerance: how close to zero to get before terminating the search

# maIterations: how many iterations to run before terminating the search

# verbose: whether to print lots of information or not

def optimize( min, max, optfunc, parameters = None, tolerance =

0.001, maxIterations = 20, verbose=False ):

The optimize function is very similar to the binary search function you wrote in the lab.

1.   Start by assigning to a variable done the value   False.

2.   Start a loop that continues while done is equal to False.

3.   Inside the loop, assign to testValue the average of max and min. This is not (should not be) an integer calculation. If verbose is True, print out testValue.

4.  Assign to result the return value of calling optfunc with testValue

and parameters as the arguments. If verbose is True, print out the result value.

5.   If the result is positive, assign to max the value of  testValue. Else if the result is negative, assign to min the value of testValue. Else, assign to   done the value True.

6.   If max - min is less than the tolerance value, then assign to done the value True.

7.   Decrement maxIterations. If maxIterations is less than or equal to zero, then set done to True.

8.   Outside the loop, return testValue.

Note: Python allows for passing the names of functions as parameters. For example, if target is the name of the function, you can pass target as a parameter and then use that parameter to call the target function. See below.

To test your optimize function, copy the following code into your optimize.py and run it. As noted in the comments, try making tolerance smaller and smaller. You should see that the result gets closer and closer to the target value.

# A function that returns x - target

def target (x, pars):

return x - 0.73542618

# you could also use return x - 1.0 to get close to 1.0

# Tests the binary search using a simple target function.

# Try changing the tolerance to see how that affects the search.

def testTarget ():

res = optimize ( 0.0, 1.0, target, tolerance = 0.01, verbose=True)

print res

if name == " main ":

testTarget ()

T2. Test the optimize function with your elephantSim

The next step is to test the optimize function with your elephantSim function. Create a testEsim function (similar to testTarget above) that calls optimize with a min value of 0.0, a max value of 0.5, and passes it elephant.elephantSim as the target function. You probably want to set

verbose=True as well. As with the testTarget function, assign the return value to a variable and then print the variable. At the bottom of your code, change testTarget() to testEsim() then run optimize.py. Does your optimize function find a value close to 0.43 for the percent darted?

T3. Automate varying a simulation parameter

The next step is to automate the process of evaluating the effects of changing a simulation

parameter across a range of values. This function will let us discover, for example, the effect on the dart probability of changing the calfSurvival rate from 80% to 90% in steps of 1%. The

function definition is given below.

# Evaluates the effects of the selected parameter on the dart

percentage

# whichParameter: the index of the parameter to test

# testmin: the minimum value to test

# testmax: the maximum value to test

# test step: the step between parameter values to test

# defaults: default parameters to use (default value of None)

de f evalParameterEffect ( whichParameter, testmin, testmax, test step,

defaults=None, verbose=False ):

# if defaults is None, assign to simParameters the result of

calling elephant.defaultParameters.

# else, assign to simParameters a copy of defaults  (e.g.

simParameters = defaults [:]

# create an empty list (e.g. results) to hold the results

if verbose:

print "Evaluating parameter %d from %.3f to %.3f with step

%.3f" % (whichParameter, testmin, testmax, test step)

# assign to t the value testmin

# while t is less than testmax

# assign to the whichParameter element of simParameters (e.g.

simParameters [whichParameter]) the value t

# assign to percD art the result of calling optimize with the

appropriate arguments, including simParameters

# append to results the tuple (t, percD art)

if verbose:

print "%8.3f \t%8.3f" % (t, percD art)

# increment t by the value test step

if verbose:

print "Terminating"

# return the list of results

Test your evalParameterEffects function by modifying your top level

code at the bottom of your file to be the following.

if name == " main ":

evalParameterEffect ( elephant.IDXProbAdultSurvival, 0.98, 1.0,

0.001, verbose=True ) Example output:

Evaluating parameter 5 from 0.980 to 1.000 with step 0.001

0.980      0.317

...   # this will keep stepping through from .981 to .998 0.999      0.457

Terminating

T4. Evaluate the effects of varying other parameters

Your final task is to make the following evaluations, showing the effect on the dart percentage of the following parameter sweeps.

Required Elements: Make a table or graph (or both) for each case. These five items should go in your report.

1.  Vary the adult survival probability from 0.98 to 1.0 in steps of 0.001.(example above)

2.  Vary the calf survival probability from 0.80 to 0.90 in steps of 0.01.

3.  Vary the senior survival probability from 0.1 to 0.5 in steps of 0.05.

4.  Vary the calving interval from 3.0 to 3.4 in steps of 0.05.

5.  Vary the max age from 56 to 66 in steps of 2.

While debugging the automation process, you might want to reduce the carrying capacity even further to 200 or 500 elephants.  Only run with 1000 elephants once everything works properly. This will take a while to run with 1000 elephants. Be patient. Example plot for first item:

Required Analysis Interpretation: For full credit, the data outputs (above 1-5)

must be interpreted for the reader in clear sentences within the reflection writeup (below).

Required Follow up Reflection Questions:

1.   What does an import statement do?

2.  What is binary search? How does it work differently than a linear search algorithm?

3.  Why is binary search faster than a linear search (e.g. going page by page to find a word in a dictionary)?

4. For full credit, the data must be interpreted for the reader in clear sentences within the writeup. What do these numbers mean? Why does the darting percentage go up/down when you vary each parameter? How should Kruger National Park use this information?

5.   How might you apply this type of optimized search algorithm approach to something you are really interested in?

Extensions

Extensions are your opportunity to customize your project, learn something else of interest to you, and improve your grade. The following are some suggested extensions, but you are free to choose your own. Be sure to describe any extensions you complete in your report.

●   Automate the graphing process using matplotlib or another graphing package of your choice.

●    Have your program write out proper CSV files with a header line and appropriate commas for the full process.

●    How much variation is there in the average total population for a 200-year elephant simulation across different runs? How stable is the estimate generated by doing 5   simulation runs? Calculating the standard deviation of the population sizes is a reasonable indicator of spread.

●   Check out the os package in Python documentation(import os). What could you do with the os.system function to automate your simulations?

●    Uber-extension: explore varying two parameters simultaneously. For example, if you are  evaluating maximum age from 56 to 64, combine it with a set of values for senior survival rates. If you have five values for maximum age and five values for senior survival rates, there would be 25 unique parameter combinations. The plot of the probability of darting    for a stable population would be a 3D graph with horizontal axes for the two parameter values and a vertical axis indicating the probability of darting.

●    Does the carrying capacity have a significant effect on the probability of darting? Is there a carrying capacity below which the probability of darting goes to zero?

Write your project report

Reports are not included in the compressed file! Please don’t make the graders hunt for your report.

You can write your report in any word processor you like and submit a PDF document in the Google Classroom assignment folder. Or use a Google Document format.

Review the Writeup Guidelines document in the Labs and Projects folder.

Your intended audience for your report is your peers who are not taking CS classes.

From week to week, you can assume your audience has read your prior reports. Your goal should be to explain to peers what you accomplished in the project and to give

them a sense of how you did it. The following is a list and description of the mandatory sections you must include in your report. Do not include the descriptions in your report,  but use them as a guide in writing your report.

● Abstract

A summary of the project, in your own words. This should be no more than a few

sentences. Give the reader context and identify the key purpose of the

assignment. An abstract should define the project's key lecture concepts in your own words for a general, non-CS audience. It should also describe the program's context and output, highlighting a couple of important algorithmic and/or scientific details. Writing an effective abstract is an important skill. Consider the following questions while writing it.

○   Does it describe the CS concepts of the project (e.g. writing well-organized and efficient code)?

○   Does it describe the specific project application (e.g. generating data)?

○   Does it describe your solution and how it was developed (e.g. what code did you write)?

○   Does it describe the results or outputs (e.g. did your code work as expected and what did the results tell you)?

○ Is it concise?

○   Are all of the terms well-defined?

○   Does it read logically and in the proper order?

● Methods

The method section should describe in clear sentences (without pasting any

code) at least one example of your own computational thinking that helped you complete your project. This could involve illustrating how a key lecture concept was applied to creating an image, how you solved a challenging problem, or

explaining an algorithmic feature that is essential to your program as well as why it is so essential. The explanation should be suitable for a general audience who  does not know Python.

● Results

Present your results in a clear manner using human-friendly images or graphs labeled with captions and interpreted for a general audience such as your peers not in the course. Explain, for a general, non-CS audience, what your output means and whether it makes sense.

● Reflection and Follow-up questions

Draw connections between lecture concepts utilized in this project and real-world problems that interest you. How else could these concepts apply to our everyday lives? What are some specific things you had to learn or discover in order to complete the project? Look for a set of short answer questions in this section of the report template.

● Extensions (Required even if you did not do any)

A description of any extensions you undertook, including text output or images demonstrating those extensions. If you added any modules, functions, or other design components, note their structure and the algorithms you used.

● References/Acknowledgements (Required even if there are none)

Identify your collaborators, including TAs and professors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester. Cite any other sources, imported libraries, or tutorials you used to complete the project.

Submit your Code

Turn in your code by zipping the file and uploading it to Google Classroom. When submitting your code, double check the following.

1.   Is your name at the top of each Python file?

2.   Does every function have a docstring (‘’’ ‘’’) specifying what it does?

3.   Is your Lab 06 folder in your Project 06 folder?

4.   Have you checked to make sure you have included all required elements and outputs in your project report?

5.   If you have done an Extension, have you included this information in your report under the Extension heading? Even if you have not done any extensions, include a section in your report where you state this.

6.   Have you acknowledged any help you may have received from classmates, your

instructor, the TAs, or outside sources (internet, books, videos, etc.)? If you received no help at all, have you indicated that under the Sources heading of the report?