Skip to content

Latest commit

 

History

History
86 lines (58 loc) · 3.29 KB

README.md

File metadata and controls

86 lines (58 loc) · 3.29 KB

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.