代做Algorithm|Assignment|代写Java : 这是一个基于java语言的进行算法代写的题目，重点考察算法本身的理解
Programming in Java
Fundamentals of Programming in Java
assignment 2
Evolutionary Algorithms
Marks available: 100
Submit your work by the deadline above. The accepted submission format is a zip archive. Submit only java source files in your archive. Place all of the files in the same zip. Do NOT submit .class files. Pleasedo not submit Eclipse (or other IDE) projects.
Please make sure that the following package declaration is the first line of your Java files: package com.bham.pij.assignments.a2a; Do not output anything to the console unless explicitly asked to. You may, of course, use console outputto debug your programs. Just make sure that you comment out or delete such debug statements when you submit. Where applicable, your class for each of the exercises must have the name shown in the exercise heading. In each of these exercises, you are not restricted to only creating therequired methods. If you want to, you can create others. However, you must createat leastthe required methods. Do not use any input method (such asScanner) in any method that is required by this specification.
Introduction
For this assignment you will implement agenetic algorithm(GA), which is a type of evolutionary algorithm.
As discussed in the lecture, the genetic Algorithm is a search algorithm that is inspired by natural evo-lution. Two key processes are adopted: genetic mutationandcrossover. These processes are described below. Using these two processes, the GA proceeds from an initial collection of random solutions to findsome desired solution. The critical component that determines the success or otherwise of the search is called thealgorithm to decide which ones are the fittest, i.e. the best. You do not need to know anything aboutfitness measure. The fitness measure assigns a numerical fitness to each solution, enabling the biology to implement this assignment. This assignment is partly an implementation exercise but is also a design exercise. The design that youchoose will affect your mark. You should seek to utilise the object-oriented principles that we have been discussing in lectures since week 3.
Algorithm overview
The GA starts with a collection of random individuals. This collection is usually of a fixed size, for ex- ample, 100. An individual is an attempted solution of the particular problem. Since all initial individualsare random, none of them probably represents a particularly good solution. It will usually be the case, however, that even though they are random, some individuals will be better than others. Each individual has achromosome. A chromosome is a collection ofgenesof fixed size. Each gene on a chromosome can have one value from a set of values. For example, in a text-based task, each gene mighthave the value of one of the alphabetic characters (like the weasel example we discussed). So, a decision must be taken about what are the legal values of a gene. In a task involving binary numbers, for example,gene values can only be 1 or 0. No other values will be legal.
The GA follows the following steps. Please note that other implementations of the GA might follow a different process. This is the process that we are adopting, however. (1) The first step of the GA is to create apopulationof random individuals. Each individual has a chro- mosome that will have been initialised to random values from the range of legal values. The populationhas a fixed size, e.g. 100.
(2) The mutation operation is then applied to the whole population. Mutation is discussed in more detail below. (3) The GA then assesses the fitness of the population. This means it must decide which are the bestindividuals in the population. To do this afitness measureis required. The GA applies a fitness measure to each individual and assigns each individual its own fitness value. The fitness measure depends entirely on the purpose of the search. For example, to search for a binary string that consists only of ones, wewould use a fitness measure that rewards how many ones there are in a string: the more the better. It is a good idea to sort the population according to this fitness measure. (4) The next step involves the creation of(for example, 20 out of a population of 100). We then select the best individuals from the population sonewindividuals. We decide how many new individuals we want that they can be used in areproductionprocess to create the new individuals. For example, we might choose 10 of the best individuals. These are called thehas been sorted for fitness, this step is easy. We then randomly select a pair of individuals from these bestparents. If the population 10 and take the following steps with them.
(5) We create two new individuals (This is described in more detail below.children) from each pair of parents by using the crossover operation.
(6) Once we have performed these operations and have our new 20 individuals (from doing this repeatedly), we prepare to put them into the general population. To maintain the population size, we remove the 20worstindividuals and add the new 20 individuals.
(7) We then return to step (2) and continue with this process until we reach the desired goal or until a certain number ofgenerationshave been processed.
Crossover
The crossover operation is a simple array copying exercise. Assuming an individual chromosome is stored in some kind of array then we do the following to perform crossover. Assume we have selected two parents: parent1 and parent2. We randomly select a crossover point. This needs to be somewhere between the start and the end of thechromosome. Technically, we view the crossover point as lyingbetweentwo genes. We then create two new chromosomes (hence, individuals). The first new chromosome is created by copying the gene values from parent1 up to the crossover point and from parent2 after the crossover point. The second new chromosomeis created by copying the gene values from parent2 up to the crossover point and then from parent 1 after it.
Consider the following example that uses binary strings: parent1 = [1,0,1,1,0,1,1,0] parent2 = [0,0,0,1,1,0,1,1] Select a random crossover point, e.g. 3. We will assume, therefore, that the crossover occurs between genes 3 and 4. child1 = [1,0,1,1,1,0,1,1]child2 = [0,0,0,1,0,1,1,0]
Note that crossover is not always performed. Crossover occurs according to some (low) probability. If crossover doesnew children. See the section on parameters.notoccur for a particular pair of parents then each of them is simply copied to create the
Mutation
Mutation involves changing the value of a gene. Of course, its new value must come from the legal set ofvalues. For binary strings, for example, we simply change 0 to 1 and vice versa.
Consider individual1 and individual2 below. We choose a random mutation point for individual1, e.g. 5. We then mutate the gene value at that position. individual1 = [1,0,1,1,1,1,1,1]
We choose a random mutation point for individual2, e.g. 0. We then mutate the gene value at that position. individual2 = [1,0,0,1,0,1,1,0] We do this for the entire population. Again, mutation of any gene value is not always performed. It is performed according to some (low)probability. Each gene is independently mutated or not mutated. That means there is a high chance that no gene will be mutated but also a very small chance that more than one will be mutated. See the sectionon parameters.
Parameters
The GA requires that some parameters be specified. Not command line parameters, but some constantsthat it uses to dictate the operation of the algorithm. These parameters are largely down to you but there are some guidelines below. Size of population:if you get better results.You should start out with a population size of 100. You can vary this value to see
Number of parents:vary this to see its effect.This should start at something like 10% of the population size. Again, you can
Number of children: This will be the same as the previous parameter. Each pair of parents has two children. Crossover probability:has a very low chance of being involved in the crossover operation. Again, experiment with this value toThis should be set to a low value, e.g. 0.02. This means that each pair of parents see its effect. Mutation probability: This should be set to a low value, e.g. 0.01. This means that each gene has a very probability of being mutated. Again, experiment with this value to see its effect.
Implementation
You need to implement the following classes.
Individual
This class represents an individual in the GA. It must have the following methods: public double getFitness() This method returns the current fitness of this individual. public String toString() This method returns athis must be a string containing the chromosome but as a single string of characters.Stringrepresentation of the individual. For any individual that uses characters,
GAApplication
This class is the base class for all types of GA. It must contain the following methods: public void run() This method processesmutation operations, crossover operations, etc. for one iteration of the algorithm.onegeneration of the GA. This means that in this method you must perform the
public Individual getBest() This method returns the current best individual.
BinaryMaximiser[50 marks]
TheBinaryMaximiserclass represents a GA that will maximise a binary string of arbitrary length. This class extendsGAApplication. It must have a constructor that receives an integer: the length of the binary string to maximise. This application seeks a binary string that contains only ones. Thus, the fitness measure should be a countof the number of ones in a string. The mutation operation should change a zero to a one and and a one to a zero. The binary string should be represented as a0. Stringfor ease. Thus, each character will be 1 or
Weasel[25 marks]
TheWeaselclass represents a GA that can find an arbitrary search string. This class extendsGAApplication. It must have a constructor that receives aString: the string to find. The fitness measure for this application requires a little more thought. It seems right that the closer to the target string a string is, the fitter it is. This naturally gives ashould consider how you will deal with this. lower number for a higher fitness. You
The mutation operation should change the value of each alphabetic character either up or down. For example, a B becomes a C or an A. What should an A become if it is mutated downwards? Thisdepends on what alphabet you select for your strings. There is no need to restrict the strings to only the alphabetic characters (plus space), apart from the fact that it will find the solution more quickly if youdo. If you look at the ASCII table, it is actually convenient to use the space character as the lower limit of the legal value. You should, however,excludeall of the control characters (lower than ASCII value 32).
Maths[25 marks]
Thematical expression.Mathsclass represents a GA that can find an integer target that is greater than zero from a mathe-
This class extends GAApplication. This class should have a constructor that receives two parameters: one being an integer representing a valueexpressions greater that than will zero, be created.that will be the target; the other being an integer representing the length of the
Thismetic application operators. worksThere by are creating no brackets strings in that the representexpressions mathematical but the correct expressions order ofusing operations the four shouldarith-
besuitable respected. range (^) ofAgain, values. since You this will applicationclearly need uses to include strings, the you arithmetical need to look operators at the andASCII digits table in theto (^) range.find a The fitness measure is the result of evaluating the expressions. An expression that has a result that is closerpopulation to the is desiredrandomly integer generated is fitter. and Notethe GA that operations some strings might will result be impossible in impossible to evaluate. operations. The In initialthese cases you should evaluate the strings to have the lowest possible fitness. You can decide what that is.
Gene value ranges
Asplication. you have read above, you need to select appropriate gene value ranges for the individuals in each ap-
Forcharacters BinaryMaximiser not numbers). the range is easy. Each gene can only have the value 0 or 1 (remember: these are
Forhave Weasel values youless canthan use 32). most The of more the ASCIIcharacters codes. you You include should in excludethe range, the the control longer characters it will take though to find (they the (^) targeta soup string. of characters. This is OK, though. And its a bit more interesting to watch your target string emerge from ForJust Maths try and, you include can also the usearithmetical the same operators alphabet andas for the Weasel digits 0 but to I9. recommend restricting it a bit more.
Hint
Theyou mostbest wayof the to thingsapproach you this need problem to know is toby implementinitially creating the whole the BinaryMaximiserassignment. class. This will teach