Max Polygon Packing with Genetic Algorithm

Project Overview

This project implements a Genetic Algorithm to solve the Max Polygon Packing problem. The objective is to maximize the value of polygons packed within a container without overlapping and without allowing rotations. The algorithm uses a JSON input format that specifies the shapes, their coordinates, values, and the container's dimensions.

Algorithm Explanation

The core of this project is a Genetic Algorithm that evolves a population of solutions over multiple generations. Here's a brief overview of how it works:

1. Initialization:

   • The algorithm starts with a random population of solutions. Each solution is a specific arrangement of shapes in the container.

2. Selection:

   • The best solutions are selected based on their fitness, which is determined by the total value of shapes successfully placed in the container.

3. Crossover:

   • New solutions are generated by combining parts of two parent solutions, mimicking biological crossover.

4. Mutation:

   • Changes are introduced to some solutions to maintain diversity in the population and avoid local optima.

5. Termination:

   • The algorithm continues to evolve the population until a predefined number of generations is reached or a satisfactory solution is found.

Project Structure

The project is organized as follows:

• main.py: The entry point for running the algorithm. It parses arguments, sets up logging, and initializes the algorithm.
• algo.py: Contains the base classes and utility functions used by the genetic algorithm.
• genetic_algo.py: Implements the specific genetic algorithm used to solve the problem.
• Container.py: Defines the container where the shapes will be packed.
• Shape.py: Defines the shapes that need to be packed.
• Solution.py: Represents a solution, including the arrangement of shapes within the container.
• utils.py: Contains utility functions for loading input files and other helper methods.
• requirements.txt: Lists the Python packages required to run the project.

Installation

To set up the environment for this project, follow these steps:

1. Clone the repository:

   git clone https://github.com/yourusername/max-polygon-packing.git
   cd max-polygon-packing

2. Create a virtual environment (optional but recommended):

   python3 -m venv venv
   source venv/bin/activate

3. Install the required packages:

   pip install -r requirements.txt

Usage

To run the algorithm, use the following command:

python main.py --instance path/to/instance.json --pop_size 4 --gens 5 --tries 10

Arguments:

• --instance: Path to the JSON file containing the problem instance.
• --pop_size: (Optional) Population size for the genetic algorithm. Default is 4.
• --gens: (Optional) Number of generations for the genetic algorithm. Default is 5.
• --tries: (Optional) Number of tries for random creation. Default is 10.

Example

You can run an example instance as follows:

python main.py --instance data/example.json --pop_size 10 --gens 100 --tries 20

Examples

Example JSON instances are provided in the data directory. You can modify these or create new ones to test different scenarios.