Due date: Monday, January 6, 2003.
This project is worth 20% of the total marks in the course.
Choose one of the following problems for your project.
Problem 1. An investigation of the method of Simulated Annealing. This project will require you to investigate the method of Simulated Annealing. This will initially involve a summary of the algorithms based on this concept. The method will then be applied to several examples to illustrate the detailed working of the method including the progress of the algorithm at each stage. Computer programs will be available but may have to be modified. An initial reference for this method is Numerical Recipes, second edition, §10.9. Code for the programs listed in Numerical Recipes are available upon request.
Problem 2. A study and use of the Genetic Algorithm in optimization problems. This topic is also referred to as Evolutionary Algorithms. You should provide a summary of the method and apply it to several examples to assess the effectiveness of the method. Include a copy of the code you used and detailed results, preferrably in graphical form. The following texts which are available in the library are suggested as references:
ˇ The simple genetic algoritm - foundations and theory, Michael D Vose (eresource)
ˇ Practical handbook for genetic algorithms, Lance Chambers QA402.5 P73 1995 v.3
ˇ Handbook of genetic algorithms, Lawrence Davis QA402.5 H36
ˇ An introduction to genetic algorithms for scientists and engineers David A Coley QA76.618 C65 1999 (this book has a disk with a QBASIC code for the genetic algorithm and links to various websites including one supplying FORTRAN codes).
The texts will be placed on three day reserve in the Steacie Library.
Problem 3. An extension of our study of Padé approximants including the use of continued fractions to evaluate the approximants and the Chebyshev form of rational approximants. A summary of existing theoretical results should be given for these methods. Include an analysis of the computational efficiency of the continued fraction form as well as algorithms for producing such continued fractions. Also carry out a comparison of the accuracy of the polynomial versus the Chebyshev forms of rational approximants.
Your report should include a number of numerical examples with a comparison of the results in graphical form.
Problem 4: An alternative source of FORTRAN programs which implement a large number of numerical routines can be found at www.netlib.org/slatec. Compare this suite of programs with the IMSL set you have been using. Choose 3 main topics which are covered in this course. Within each topic choose 2 different algorithms which have routines in both IMSL and this alternative source. Write programs which use these routines and test them on a sample of non-trivial problems. Compare the two sources on the following basis:
- quality of write up of the routines;
- ease of use;
- running time;
- output format.
Finally provide a general overview of these two sources of numeriical software. Comment on the range of programs available and your general reaction to them.
Problem 5: You may suggest your own problem. It must be based on topics studied in this course. It could involve alternate methods that we have not studied and must include applications to numerical examples. Alternatively, you could apply one of the methods from the course to a non-trivial problem. In the latter case, the problem must arise from a specific situation which must be described. If you wish to do this you must hand in a written description of the problem you propose to solve along with an outline of the method of solution by the date listed below.
You must indicate email (firstname.lastname@example.org) by Tuesday, Dec.3 which problem you wish to solve for your project.
You will be required to give a 25 minute talk on your project in January. You should plan to use transparencies, including those illustrating your results, in presenting your project.
The completed project will consist of a write-up, the numerical output, plots of the results and program listings . The marks will be based on the material handed in plus the talk. In assigning marks, emphasis will be placed on clarity of the write-up and a critical evaluation of the problem. If you are dealing with alternate methods, the strength and weaknesses of the methods should be discussed in relation to the standard methods. If you are doing a numerical problem, accuracy of the results and the way in which these are determined will be a factor. The talk will be used to judge your understanding of the problem and the style of the delivery will not be a major factor. You should be prepared to answer questions on the talk.
A preliminary assessment of your project will be available before your talk is scheduled.