Skip to content

A genetic algorithm that solves the pentomino problem (knapsack problem in 2D) in Java from scratch

Notifications You must be signed in to change notification settings

alexandremartens/Genetic-Algorithm_Pentris

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 

Repository files navigation

Genetic-Algorithm_Pentominos

info section explains the behaviour of the algorithm
Using only L,P,T without values? -> Section 1
Using values? -> Section 2
Don't forget to adjust the time limit. this is going to stop the execution
of the program if no solution found

Section 1

Step 1.0: fill L,P,T number of parcels
Step 1.1: set the boolean ValueBoolean = false;
Step 1.2: Add a time-limit of execution in milliseconds.
Step 1.3: RUN the program
Using the bruteforce will modify the way the Simulation method places the parcels. advised to keep it 'True'

info 0.0: Volume total parcels > container volume?
--> try to fill the parcel as best as possible
info 1.0: Volume total parcels <= container volume
info 1.1: Volume total parcels = container volume and all parcels CAN be placed
--> Will find the container, all filled
info 1.2: Volume total parcels < container volume and all parcels CAN be placed
--> Will find the container, with gaps obviously
info 1.3: Volume total parcels < container volume and all parcels CAN't be placed
--> Will remove some pieces and try to get the most pieces placed, will stop with the time-limit

Section 2

Step 2.0: fill L,P,T number of parcels, if 'unlimited', enter
Step 2.1: fill L,P,T's respective weights
Step 2.2: set the boolean ValueBoolean = true;
Step 2.3: Add a time-limit of execution in milliseconds.
Step 2.4: RUN the program

info 0.0: Volume total parcels > container volume?
--> Will stop after the timeLimit and show the best result
info 1.0: Volume total parcels <= container volume
info 1.1: Volume total parcels = container volume and all parcels CAN be placed
--> Will find the container, all filled and show the best result
info 1.2: Volume total parcels < container volume and all parcels CAN be placed
--> Will find the container, with gaps obviously and show the best result
info 1.3: Volume total parcels < container volume and all parcels CAN't be placed
--> Will stop after the timeLimit and show the best result

About

A genetic algorithm that solves the pentomino problem (knapsack problem in 2D) in Java from scratch

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages