(5/5)

Goal: Showcase your understanding of Genetic Algorithms (GA) and prepare a technical report examining the algorithm’s performance in a given problem.

Task: This assignment has 3 parts. First, you must implement a GA system as described in lecture. Next, you must perform a number of experiments with your GA system and collect data regarding its performance. The final step will be preparing a technical report to present your findings. Specific details regarding the requirements of the GA implementation, the experiments to be performed, and the format and content of the report follow.

As a reminder, the basic procedure of a GA is as follows: Read problem instance data

Set GA parameters

Generate a random initial population, POP, of size popSize

for gen=1 to MAXGEN do:

evaluate fitness of each individual in POP

select a new population using a selection strategy apply crossover and mutation

end for

A GA could have the following components:

• Initial Population Initializer: Creates a population of size popSize of randomized individuals as described in class

• Chromosome: A chromosome encodes a solution to the problem being solved. In our case each chromosome must represent a sequence of distinct integers. The simplest representation to use is an integer array, mutation and crossover can then be performed on the elements of the array, although other representations are possible. The array should contain each of the integers 0,1,2,.,n−1 in some order. No integer should be present more than once, and all integers from 0 up to and including n − 1 should be included, where n is the size of the array.

• Reproduction: Use Tournament Selection (remember K = 2, 3, 4 or 5)

• Crossover: Given two individuals, a crossover creates two offspring. Implement your GA using the following crossover strategies independently:

• Order Crossover

• A crossover of your choice for example: Uniform Order Crossover or Partially Mapped Crossover

• Mutator: Given an individual, a mutator creates a mutated individual. Implement your GA using a mutation operator of your choice (from those discussed in class)

• Fitness evaluation function: The fitness function should take an individual and produce a real number describing the suitability of the solution encoded in the individual. In our case the fitness function will attempt to describe how much an unshredded document looks like English. One possible fitness evaluation function is provided, but feel free to experiment with other options. With the provided fitness function smaller numbers indicate a more fit solution.

• Genetic algorithm system: The implementation of the GA system. This file should glue together the various components of your system.

• User parameters: Population size, maximum generation span, probability of (crossover, mutation, etc.). Your GA program should permit the user to easily define his/her own genetic parameters and data (e.g., crossover rate, mutation rate, population size, maximum generation span etc ).

Using your GA implementation perform the following experimentation:

• Run your GA to compare the performance of the two crossover operators mentioned above by using the following parameters (and include elitism in all cases):

a) Crossover rate = 100 %, mutation = 0%

b) Crossover rate = 100 %, mutation = 10%

c) Crossover rate = 90 %, mutation 0%

d) Crossover rate = 90 %, mutation 10%

e) Determine your own best parameter settings

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of