2. Genetic Programming
Maximum Points: 30
DUE: UPDATED Monday November 6, 2023 at 11:55pm; submitted on MOODLE.
This is the Monday of reading week
Y’all asked for this
If the fact that it’s reading week bothers you, then submit it before the original due date
Warning
Claiming that objectives/tasks/enhancements were complete within the report when in reality they were not is (a) a serious form of academic misconduct — falsifying results — and (b) against the student code of conduct.
These violations are subject to severe penalty. All violations will be reported and investigated fully.
2.1. Base Task
The base task is to implement Genetic Programming (GP) for Symbolic Regression.
2.2. Marking Details
A total of 30 points may be obtained on this assignment. Although it is not required to complete all portions of the assignment (one may choose to only try to obtain, for example, 20 points), all portions must be completed correctly and effectively to receive all 30 points.
Below is a high-level overview of how points will be awarded. Details on each task are provided later in the assignment description.
A total of 5 points will be awarded for having a working implementation of GP for Symbolic Regression
A total of 5 additional points may be awarded for adding enhancements to the GP implementation
Using GP for a typed problem may award an additional 5 points
Generating an effective visualization for evolution/solutions may award up to 2 additional points
A complete report will award up to 5 points
Using LaTeX to generate the report will award an additional 2 points
Including proper references/citations awards an additional 2 points
Including figures and tables awards an additional 2 points
Performing an effective statistical analysis will award an additional 2 points
Note
A working GP implementation is required in order to obtain any points for the additional tasks described within the assignment.
2.3. Provided Files
Files containing CSV formatted instances can be found on the github repository
All instances are made up of tabular data where the rows are observations and columns are the variables. The dependant variable is always the last column.
Each of these instances were generated by some function and normally distributed noise was added to each data point to make the problems more difficult. The goal is to find the function that was used to generate each instance.
Warning
Many of these instances are more than two or three dimensions. This will make visualizing and plotting the data difficult.
A more creative way to visualize the data may be required.
2.4. Implementing Genetic Programming
The first portion of the assignment is to implement GP for symbolic regression. It does not matter how the GP is implemented as long as the high-level framework of the algorithm is followed.
Feel free to start from the GP implementations available on the GitHub repository. Being creative and experimental is encouraged, and further, this creativity will provide plenty of content to discuss in the report.
Do not feel compelled to use the existing implementations of the GP that are in the repository. Additionally, the language used does not particularly matter; however, if you would like to use a language other than C, C++, C#, Java, or Python, please ask first for approval.
Assuming the GP implementation is working and there are no serious issues, 5 points will be awarded.
2.4.1. Enhancements and Modifications
A total of 5 additional points may be awarded for enhancing and modifying the GP implementation. In general, each enhancement/modification will award 1 additional point, but depending on the complexity of the enhancement/modification, additional or fewer points may be awarded. To be safe, do not aim to put in minimal effort to obtain these marks if the goal is to obtain all 5 additional points.
The enhancements/modifications must be made clear to the marker as they will not dig through the implementation to try to find what was done. If choosing not to write a report, at least provide a text file containing a description of what was done. If writing a report, add a section within the report outlining what was done. If the enhancements/modifications are not clear, points may not be awarded.
Below is a short list of possible enhancement/modifications
Elitism
New or modified genetic operators
New or modified selection
Adding additional heuristics to the search
Adding a new operation to the algorithm
2.4.2. Visualization
Generating a visualization of results may provide an additional 2 points. How this is done is up to each individual, but ensure it is interesting, effective, clear, and well presented to ensure the points are awarded. The more creative the better.
2.4.3. Typed Problems
An additional 5 points may be awarded if GP is effectively used on a typed problem. No data will be provided, thus finding an interesting problem and related data will be required. It must be made clear to the marker that GP was sufficiently applied to the problem and that the problem is interesting enough to earn the additional points.
Problems/data that are used for tutorial implementations of typed GP for the used GP system will not be eligible for the additional points. For example, one of the tutorials for DEAP used typed GP for spam detection. Thus, spam detection is a problem that is not eligible for receiving additional points.
If struggling to find a problem, check out the UCI Machine Learning Repository.
2.5. Report
Writing a simple report will award up to 5 additional points; however, a total of 13 points may be obtained by completing all portions of the report sufficiently.
Warning
Writing a report is non-trivial and will likely take much longer than implementing the algorithm.
The base report will consider spelling, grammar, prose, etc. for marking, thus, the marker will be analysing the report both quantitatively and qualitatively.
There is no right way to write a report, nor is there a definitive structure. The most correct way is to write a report that most effectively communicates what needs to be communicated.
Below is a list of things to consider including in the report. This list is a collection of suggested ideas to consider and is not intended to be the standard template.
Introduction
What is the problem?
Small literature review
What have other people done in the past that worked
Problem description
What is symbolic regression?
If applicable, what is the typed problem?
Algorithm description
How was GP implemented?
Can someone follow the description to recreate your work?
What enhancements/modifications were included?
Why were they done?
How were they done?
Explain how the results will be analysed
What is being compared?
How will the comparison be done?
Mean
Distribution comparison
Probability values?
Explains the results and discuss
What happened?
How would this compare to random?
How would this compare to other algorithms?
How were the results compared to the best known?
Did any of the implemented modifications or enhancements improve the results?
Conclusions and possible future directions
What are the major takeaways?
How good was it?
What else could be done as next steps for continuing the analysis?
Bibliography
References, if included
2.5.1. LaTeX
An additional 2 points may be obtained if the report is written in LaTeX.
LaTeX is powerful software for writing and typesetting documents. Everything is written in plain text with various tags that LaTeX will use to format the document nicely.
Although it is possible to download, write, and build everything locally on a personal computer, it is highly recommended to use Overleaf. Overleaf is an online editor that takes care a lot of tedious setup and it automatically backs up all work.
If using LaTeX, it is recommended that the report be written with the IEEE conference template. Overleaf makes it simple to start using the template.
Although it is possible to write the bibliography in the document with \bibitem, it is far simpler to use
BibTeX.
Although LaTeX and BibTeX is not being taught, it should not be too difficult to get used to it with the help of tutorials and examples available online.
2.5.2. References and Citations
Including effective and proper references/citations may award an additional 2 points.
There is no correct number of references to include as that depends on the report itself.
LaTeX and BibTeX makes references and citations relatively simple. Further, with Google Scholar, getting references correct is trivial.
2.5.3. Figures and Tables
Effectively including figures, tables, etc. in the report may award an additional 2 points. Examples include an algorithm flow diagram, a table of parameter settings, tables of results, result visualization, learning curves, distributions of results, etc.
Note
The tables and figures must effectively communicate relevant information. For example, a giant table of results is difficult to interpret. Instead, think of how the data can be represented succinctly and clearly.
2.5.4. Statistical Analysis
Including proper statistical comparisons of results may award an additional 2 points.
Typically, different results will be obtained every time the algorithm is run. This is due to the stochastic nature of these algorithms. For this reason, it is not possible to run these algorithms once to compare the results. Instead, distributions of results need to be obtained and these distributions are then compared to one another.
In evolutionary computation, it is common to see 30 runs of each algorithm to obtain the distributions (30 runs of the same algorithm with the same setup and hyperparameters).
It is not possible to say which statistical methods should be used for the analysis as that depends on what the goal is. Below is a general guideline.
General summary statistics for each distribution
Mean, standard deviation, etc.
Comparing distributions
Student t-test or Mann-Whitney U
Measuring the difference between distributions (effect)
Cohen’s D test
2.6. What to Submit to Moodle
Warning
Completing a requirement does not guarantee that the corresponding points will be awarded. Each requirement must be completed to the satisfaction of the marker.
Submit everything via Moodle by 11:55pm on the due date
Include the full implementation of GP along with any special running instructions if necessary
Include the report
Include anything else the marker may need for effectively evaluating the work