COIT20277 Introduction to Computational Intelligence
Assignment 1 – Evolutionary Computation
Due date: Week 5 Tuesday (13 August XXXXXXXXXX:59 pm AEST ASSESSMENT
Weighting: 20% 1
Objectives
Model and design solution to the given problem applying principles of Genetic Algorithms
Develop source code and implement designed solution.
Follow co
ect procedure for implementing a Genetic Algorithm.
Test software implementations to ensure co
ectness and maintainability.
The Knapsack Problem (KP)
The Knapsack Problem is an example of a combinatorial optimization problem, which seeks for a best
solution from among many other solutions. It is concerned with a knapsack that has a specific volume
(or capacity) V. There are a number of distinct items I that may potentially be placed in the knapsack.
Each item has a positive number volume v and positive integer benefit b. The goal is to place as the
items into the Knapsack to maximize the total benefit, while the total volume of the items is not
exceeding the volume V of the knapsack. Note that we cannot have more than one copy of an item in
the knapsack.
Example:
Suppose we have a knapsack that has a capacity of 13 cubic inches and three potential items (labeled
‘A,’ ‘B,’ ‘C’), whose volume and benefit are as follows:
Item # A B C
Benefit 4 3 5
Volume 6 7 8
We want to include in the knapsack only these items that will have the greatest total benefit within the
constraint of the knapsack’s capacity. Each item is only selected once. There are 23 = 8 possible ways
(subsets) to place these items into the knapsack as in the table (next page).
An index 0 or 1 is used to indicate if the co
esponding item is selected nor not. We can see that the
optimal solution is to select only item A and B not C XXXXXXXXXXto place into the knapsack, which result in
highest benefit of 7, and total volume of 13 satisfying the capacity constraint of the knapsack.
A B C
Total
Volume
Total
Benefit
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX --
XXXXXXXXXX
XXXXXXXXXX --
XXXXXXXXXX
XXXXXXXXXX --
Assessment Task
A. Programming
You are required to write a Java Application that implements a genetic algorithm to solve the
Knapsack Problem for any number of items with different volumes and benefits.
You can use the following class descriptions as a guideline for your design.
1. Item class
This class is to store the item value and benefit in integers. Write the necessary accesso
and mutator methods to and get the value and benefit values. You should also write the
parameterised constructor that takes the values and creates the Item object, a default
constructor.
2. Individual class
The purpose of this class is to create an individual and store required values. In this
problem, the chromosome is an a
ay of binary integers, each integer being the index of an
item (0 or 1) to indicate if an item is selected or not. The chromosome length or the a
ay
size is the number of available item to be considered. This class should have:
Two parameterised constructors, one taking the chromosome as a parameter, and
the other taking the chromosome length as a parameter.
Accessor and mutator methods to set and get chromosome, set and get a particula
gene within a chromosome, set and get fitness of the individual. Fitness is the
total benefit of selected items.
toString() method to display the genes (item indices) contained in the
chromosome.
3. Population class
As in any GA, this class is used to create as many individuals as per the given population
size where each individual will have a different item index and therefore, different fitness.
This class stores the a
ay of individuals and the population fitness which is the total
individual fitness. This class should have:
Two parameterised constructors, one taking the population size as a parameter,
and the other taking the population size and chromosome length as parameters.
Accessor and mutator methods to set and get the parameters of population size,
population fitness, individuals, a specific individual at a given index, the fittest
individual of the population.
This class also should have a shuffle method to organise the individuals of the
population at a random order.
4. Genetic Algorithm class
This class stores the GA parameters of population size, mutation rate, crossover rate,
elitism count, knapsack volume. This class should have:
A parameterised constructor that takes the above parameters and creates the
object.
An initPopulation method to create the first generation of the population.
A method to test whether termination condition has reached.
A method to calculate and return the individual’s fitness.
A method to evaluate population by calculating and setting the individual fitness
and then calculating the population fitness.
A method to select parent for the crossover using roulette wheel selection.
A method to crossover using two-points cross-over and create new population.
A method to mutate population leading to evolution.
5. Packaging Main class
This class will create items with random values and benefits using objects of the above
classes and execute the application creating the required number of generations and
displaying the optimal solution for items in knapsack.
You use the algorithmic steps given below to implement this class
public class Packaging{
public static int maxGenerations =
initialize to given generations
public static void main(String[] args) {
int numItems =
initialize number of items
int populationSize =
double mutationRate =
double crossoverRate =
double knapsack_capacity =
initialize capacity for knapsack
int elitism_count = 1;
Number of best individuals to retain.
Item items[] = new Item[numItems];
Loop to create Items with random Volumne and Benefit.
for (int itemIndex = 0; itemIndex < numItems; itemIndex++) {
int volumne = (int) (10 * Math.random()+1);
int benefit = (int) (10 * Math.random()+1);
items[itemIndex] = new Item(volumne, benefit);
}
Initial GA
GeneticAlgorithm ga = new GeneticAlgorithm(
Use Appropriate Parameters);
Initialize population
Population population = ga.initPopulation(items.length);
TODO: Evaluate population
Keep track of cu
ent generation
int generation = 1;
Start evolution loop
while (ga.isTerminationConditionMet(generation, maxGenerations) == false) {
TODO: Apply Select Paren Population
TODO: Apply crossover
TODO: Apply mutation
TODO: Evaluate population
TODO: Increment the cu
ent generation
TODO: Display appropriate output for each iteration.
}
TODO: Display results
}
}
You will write and submit source code in java for the implementation of the application. As you
can see many of the classes and methods can be coded following the generic pattern given in
weekly examples. Sample outputs of an implemented program is provided in “Assignment 1 -
Example Output.pdf” for your reference.
You can build your application using the NetBeans, TextPad Editor or any other suitable IDE for
software development.
Run and test your program with the following parameter settings:
Maximum Generations: 50
Number of Items : 10
Population Size : 10
Mutation Rate : 0.1
Crossover Rate : 0.7
Knapsack Volume Constraint = 40
Elitism = 1
B. Report
As part of the assessment you should submit a report that contains the UML class diagrams for the
classes. Your report should also contain an explanation of the implementation of the given
methods of crossover and mutation to show the strategical approach used to improve the
population fitness, generation after generation. Include a
ief note on how such strategy can be
used in solving optimization problems. Take screenshots and explain the outputs of your
implemented program.
Assessment Submission
You should submit one zip file containing the following files using the Moodle online submission
system, by the due date:
Item.java – Source code for the Item class as given above
Individual.java – Source code for the Individual class
Population.java – Source code for the Population class
GeneticAlgorithm.java – Source code for the Genetic Algorithm class
PackagingMain.java– Source code for the Packaging Main class
Report.docx – A document file containing details as outline above.
Assessment criteria - Assignment 1 marking guide
Note:
1. If your program doesn’t compile or run, partial marks will be allocated by inspection of the source
code.
2. Your understanding of the algorithm and problem solving approach used will be examined using the
detailed java doc comments inserted in your source code file.
3. Please clarify any doubts you have by one of the means of discussing with your tutor, posting a
query in the Q& A forum, or discussing with your colleagues or contacting the unit coordinator.
4. Please do not share your source code files or report with your colleagues which may lead to
plagiarism. Please do not search and use source code available elsewhere which may also lead to
plagiarism