1 General Instructions

All submissions for the practical projects should be under version control. Submission procedure remains the same with the first practical project.

The directory under version control for this project should be named as


https://version-control.adelaide.edu.au/svn/aXXXXXXX/2018/s1/adds/project6/


where aXXXXXXX is your student ID.

If you get stuck on one of the hidden test cases and really cannot resolve it yourself, please feel free to ask the practical tutors for hints.

We encourage you to finish your work before the practical session and take the session as consulting time.



2 Problem Description

2.1 Objective

This practical will test your knowledge polymorphism and computational complexity analysis.


2.2 Design

In a file named design.pdf, describe how you are going to solve the problem and test your implementation with the test cases you designed based on the stages below.

Testing Hint: it’s easier if you test things as a small piece of code, rather than building a giant lump of code that doesn’t compile or run correctly. As part of your design, you should also sketch out how you are going to build and test the code.


2.3 Problem

DNA contains the genetic code that defines the structure of every organism on Earth. The information in this DNA is copied and inherited across generations from individual to individual, but may change over generations due to crossover and mutation. A more



successful individual is more likely to survive to breed, increasing the likelihood that it will be able to pass on its particular DNA encoding.

In this practical, we are going to represent an individual with a binary “DNA” strand and mutate it over a number of generations to get a better quality individual. The concepts in this practical are related to Evolutionary Computation, a field of Artificial Intelligence.

Evolutionary computation has been used to solve a number of problems, including mak- ing virtual creatures, reducing race time for athletes, designing strategies for satellite coverage, designing turbines… the list goes on. The following articles provide some kind of overview on evolutionary algorithms. Please have a read if you are interested.

http://www.perlmonks.org/?node_id=298877

http://www.genetic-programming.com/published/usnwr072798.html


2.3.1 Representation of binary strings

In this practical, we use a class called Individual to represent the DNA which can be represented by a list of binary digits. Individual has a variable called binaryString which stores the value of genes.

Your Individual class should at least have the following functions:


string getString(): The function outputs a binary string representation of the bitstring list (e.g.“01010100”).



int getBit(int pos): The function returns the bit value at position pos. It should return -1 if pos is out of bound..



void flipBit(int pos): The function takes in the position of the certain bit and flip the bit value.



int getMaxOnes(): The function returns the longest consecutive sequence of ‘1’ digits in the list (e.g. calling the function on “1001110” will obtain 3).



• int getLength(): The function returns the length of the list.


A constructor that takes in the length of the binary DNA and creates the the binary string. Each binary value in the list should be given a value of 0 by default.



A constructor that takes in a binary string and creates a new Individual with an identical list. Note that this involves creating a new copy of the list.



2.4 Smooth Operator

In order to mutate the DNA, we need a class called Mutator. The Mutator