锐客网

  1. 首页 > it技术 > >

浅谈Genetic Algorithm

算法

【浅谈Genetic Algorithm】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...
● https://www.tutorialspoint.co...
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.
  3. 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)
  4. 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
  5. Survival of the fittest
    a. Only keep animals with the least costs and say goodbye to the rest
  6. 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
  7. 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
  8. More random animals
    a. Add more random animals to get back to the original number of animals
  9. 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
  10. 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:
  11. 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
  12. 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
  13. 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
  14. A single value equal to 0.0
    Sample Test Case 3
  15. 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:
  16. 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.
  17. 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
  18. 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
  19. 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)
  20. 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
  21. Points: (-10.0, -36.4), (-5.1, -17.3), (0.5, -2.2), (1.7, 2.6), (10.0, 26.6)
  22. 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)

    推荐阅读


    上一篇：【算法】前缀树

    下一篇：在小程序当中渲染树