代写Algorithm程序设计、代做Java程序、Python，c++编程调试

日期：2021-04-04 02:33

Genetic Algorithm - Immutable

Time Estimate: 20 hours

Video

Introduction

You will design and implement a genetic algorithm without using any mutable variables or

state.

The following are banned in your submissions:

● Variables (var)

○ The value at any memory address on the stack or heap cannot

change throughout the execution of your program

○ You can use values (val) to store values

● Any way of directly simulating mutability that is against the spirit of this

assignment. (Ex. Importing a class that has a mutable state variable)

If your submission, including testing, violates this immutability restriction it will not be graded.

Description

Genetic algorithms provide probabilistic solutions to optimization problems. These algorithms

can be thought of as an advanced “guess and check” technique that eventually arrives at an

output that is close to the actual solution without having to know how to compute the solution

directly.

Resources:

● https://en.wikipedia.org/wiki/Genetic_algorithm

● https://www.tutorialspoint.com/genetic_algorithms/index.htm

You will write a generic genetic algorithm of your own design that can find approximate

solutions to optimization problems. This algorithm will be written in such a way that it can be

reused for any application suitable for a genetic algorithm. For each problem, you will need

to provide your genetic algorithm with a cost function to determine how well a potential

solution performs and an incubator function that creates a potential solution from a list of

doubles (Referred to as genes).

Project Structure

1. Download the starter code from UBLearns as a new IntelliJ project

2. Run maven and mark src as the root sources directory

This repository includes a server as its GUI. To run the GUI, run towers.TowerServer then

open towers/static/index.html in your browser.

Objectives

Primary Objective: Genetic Algorithm

Implement a generic genetic algorithm.

In the GeneticAlgorithm object, write a method named geneticAlgorithm with the following

features:

● Takes a type parameter T

○ This is the type of the solution space that you are trying to find. For example,

when computing polynomial regression this type will be Polynomial

● As the first parameter, takes an “incubator” function that takes a List[Double] and

returns an object of type T

○ This function will provide a way to convert a list of genes into an object in the

solution space. Your algorithm will only work with lists of doubles to guess

new solutions and call this incubator to convert the genes into possible

solutions

● As the second parameter, takes a cost function of type T to Double

○ This function takes a potential solution and computes its cost. The goal of

your algorithm is to find a solution with minimal cost. A solution with a cost of

0.0 is considered perfect, though a perfect will not always exist.

● The third, and final, parameter is an Int named size representing the number of

genes in the List[Double] for the incubator function

○ When creating/mutating/crossing lists for the incubator, make sure the lists

have this length

● Returns an object of type T which is the most optimal solution found by the algorithm

Your algorithm will be tested with an unknown application to ensure you implemented the

algorithm generically. Your algorithm will be called 10 times during primary objective testing

to test the efficiency and consistency of your implementation. Be sure your algorithm is

efficient enough to run this many times. Grading will timeout after 5 minutes.

Algorithm Outline: You have a significant amount of freedom in designing your genetic

algorithm. Your only goal is to return a solution that is close to optimal. If you achieve this,

you can complete this assignment. For a little guidance on designing an algorithm, if you

don’t want to design your own from scratch, here are a few steps you can follow.

1. Start by generating a fixed number of random “animals”

a. Each animal is defined by its genes (List of doubles) so this involves

generating random lists of doubles

b. Depending on the rest of your algorithm and applications, the range of these

random values may be important. Ensure that the range is wide enough to

allow any potential solution. (If your genes cover the range -100 to 100 you

will be able to pass the primary objective)

2. Find the best animals

a. Use the incubator function to create a potential solution for each set of genes

b. Use the cost function to compute the cost of each potential solution

c. Sort the animals based on their cost to find the best animals

3. Survival of the fittest

a. Only keep animals with the least costs and say goodbye to the rest

4. Mutations

a. Simulate genetic mutations of the best animals by creating new sets of genes

that are similar to the best ones, but with some random variation

b. Randomness is your friend in this step. You are starting with a pretty good

solution and creating random solutions that are similar to the good one to find

an even better one. Creating several variations of the best solutions with

random changes will help your algorithm to find the best solution

5. Crossover

a. Pair up the top animals and create offspring by combining their genes

b. There are several methods of this, for example averaging their genes or

randomly choosing one parent for each gene

6. More random animals

a. Add more random animals to get back to the original number of animals

7. The next generation

a. Go back to step 2 [with recursion]

b. You can recurse for a fixed number of generations, or until the improvement

from the previous generation is very small. Do not run until the cost is close to

0 since the most optimal solution may have a high cost.

If you follow this outline there are many parameters that are up to you to choose. You should

use the three objectives for testing and adjust your parameters until you have a robust

genetic algorithm. These parameters include:

● How many animals in each generation

● How many generations

● How to mutate genes

● How many mutations to generate and which animals get mutated

● How to crossover two (or more) animals

Testing Note

● Your tests will not be checked by AutoLab for this assignment. Three applications

are setup to assist your testing which you should use to write test suites and test

your genetic algorithm

● If you ask a question in office hours or on Piazza without taking advantage of these

testing opportunities, don’t expect a satisfying answer (Unless your question is

about testing)

Testing Opportunity 1: Single Value

Given a single double to compute, the genetic algorithm should return an instance of

SingleValue containing a double close to this value. This is a simple application that should

be used as a first milestone for your genetic algorithm to reach. The SingleValue object has:

1. A costFunction method

a. This method takes the number to be “guessed” as a parameter and returns a

cost function that takes a SingleValue and return its distance from the number

to be guessed

2. An incubator method

a. This method takes a list of doubles (genes) and returns an instance of

SingleValue from those genes

b. The input List should contain a single Double and this Double will be used

directly as the SingleValues Double

Sample Test Case 1

1. A single value equal to 50.0. This test case is provided with the started code to show

you how the genetic algorithm is used.

Sample Test Case 2

1. A single value equal to 0.0

Sample Test Case 3

1. A single value equal to -50.0

Testing Opportunity 2: Line

Use your genetic algorithm to compute linear regression.

Using SingleValue as an example, complete the Line class and object to be used by your

genetic algorithm to estimate a line fitting a list of points.

The Line class has the same structure as the SingleValue class with:

1. A costFunction method

a. The cost function takes a List of Points and returns a cost function that

computes the cost of a Line object. The cost is the sum of the squared

distances of the points from the polynomial in the y direction.

2. An incubator method

a. The incubator takes a List of Doubles of length 2 and directly uses them as

the coefficients of the Line to be created. The first element of the list is the

slope and the second is the y-intercept.

Sample Test Case 1

1. Points: (-2.0, 1.0), (-1.0, 3.0), (0.0, 5.0), (1.0, 7.0), (2.0, 9.0)

Sample Test Case 2

1. Points: (-4.2, 24.957), (-1.2, 13.453), (-0.3, 11.508), (1.3, 6.088), (2.5, 1.0), (4.0, -3.047), (5.0, -7.839)

2. To ensure that you have the cost function set up properly, check that your algorithm

finds the best fit line of -3.483x + 10.122

Sample Test Case 3

1. Points: (-10.0, -36.4), (-5.1, -17.3), (0.5, -2.2), (1.7, 2.6), (10.0, 26.6)

2. The best fit line is not given for this test case

Testing Opportunity 3: AimBot

Use your genetic algorithm to hit a moving target in a 2d space.

This bot will have a fixed position and must hit a moving target given by its velocity and initial

location. To do this, the genetic algorithm will be used to determine the velocity (direction)

that a projectile should be fired to hit the target.

The cost function will be provided these values as 3 PhysicsVectors and will return a function

that determines the cost of a particular velocity vector.

The returned velocity will have a magnitude of 7.0.

Note: It is not required that you understand all the code in the AimBot class.

This can be tested by running the server, opening the html file, and verifying that the tower

can hit the plate as you move around the screen. The code is already set up to call your

genetic algorithm.

Grading Note

● Because the grader only checks the primary objective it is broken into 4

components

a. Your GA can accurately figure out 2 random hidden numbers 1 time in a

row (2.5 points)

b. Your GA can accurately figure out 2 random hidden numbers 5 times in a

row (2.5 points)

c. Your GA can accurately figure out 2 random hidden numbers 10 times in a

row (2.5 points)

d. Your GA can accurately figure out 2 random hidden numbers 15 times in a

row (2.5 points)