项目作者: erfanMhi

项目描述 :
量子启发遗传算法为k均值聚类纸提出的量子启发式遗传算法的实现。
高级语言: Jupyter Notebook
项目地址: git://github.com/erfanMhi/A-quantum-inspired-genetic-algorithm-for-k-means-clustering.git


Quantum-Inspired Genetic Algorithm for K-means Clustering 🧬🔬

Python 3.9+
Poetry
License: MIT
Tests
Code style: black

A Python implementation combining quantum computing concepts with evolutionary algorithms to optimize cluster assignments, offering improved convergence over traditional methods.

✨ Features

  • 🧬 Quantum-Inspired Evolution: Uses quantum principles for better exploration
  • 🎯 Optimized Convergence: Faster convergence than traditional genetic algorithms
  • 📊 Multiple Datasets: Support for various synthetic datasets (SDA1, SDA2, SDA3)
  • 📈 Visualization Tools: Built-in plotting utilities for cluster analysis

🧪 Algorithm Overview

The QIGA represents cluster centroids using quantum-inspired bits (qubits) in superposition:

  1. |ψ⟩ = cos(θ)|0 + sin(θ)|1

Key components:

  • Quantum Rotation: Updates quantum angles based on the best solutions
  • Quantum Mutation: Introduces diversity through random angle perturbations
  • K-means Objective: Minimizes within-cluster sum of squared errors

QIGA Architecture

🚀 Quick Start

Prerequisites

Installation

  1. # Clone the repository
  2. git clone https://github.com/erfanmiahi/A-quantum-inspired-genetic-algorithm-for-k-means-clustering.git
  3. cd A-quantum-inspired-genetic-algorithm-for-k-means-clustering
  4. # Install dependencies with Poetry
  5. poetry install

Basic Usage

  1. from qiga_kmeans.algorithms import QIGA
  2. from qiga_kmeans.utils import generate_sda_dataset
  3. # Generate synthetic data
  4. X = generate_sda_dataset(1) # SDA1 dataset
  5. # Initialize and run QIGA
  6. qiga = QIGA(
  7. n_clusters=3,
  8. population_size=20,
  9. max_generations=50,
  10. mutation_prob=0.01,
  11. crossover_prob=0.8
  12. )
  13. labels, sse = qiga.fit(X)

🧪 Testing

  1. # Run all tests with coverage
  2. poetry run pytest --cov=src/qiga_kmeans
  3. # Run specific test modules
  4. poetry run pytest tests/unit/algorithms/ # Test all algorithms
  5. poetry run pytest tests/unit/utils/ # Test utilities

📁 Project Structure

  1. src/qiga_kmeans/
  2. ├── algorithms/ # Core algorithm implementations
  3. ├── qiga.py # Quantum-inspired genetic algorithm
  4. ├── genetic.py # Traditional genetic algorithm
  5. └── kmeans.py # Base k-means implementation
  6. ├── utils/ # Helper utilities
  7. ├── data_generator.py # Synthetic dataset generation
  8. └── preprocessing.py # Data preprocessing utilities
  9. ├── data/ # Data management
  10. └── visualization/ # Plotting tools

📝 Citation

If you use this implementation in your research, please cite:

  1. @software{qiga_kmeans,
  2. author = {Erfan Miahi},
  3. title = {A Quantum-Inspired Genetic Algorithm for K-means Clustering},
  4. year = {2024},
  5. url = {https://github.com/erfanmiahi/A-quantum-inspired-genetic-algorithm-for-k-means-clustering}
  6. }

📄 Implementation Status

Note: The current implementation exists in two forms:

  1. Original implementation in implementation.ipynb - This is the working reference implementation
  2. Package implementation in src/ directory - This is a work in progress conversion from the notebook and needs proper testing

The code in the src/ directory is currently being refactored from the notebook format and requires:

  • Complete test coverage
  • Validation against original results
  • Performance optimization
  • Documentation improvements

Please refer to implementation.ipynb for the current working implementation.

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.



Made with ❤️ by Erfan Miahi