Skip to content

EMI-Group/tensoraco

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

27 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

🌟 TensorACO: Tensorized Ant Colony Optimization for GPU Acceleration 🌟

TensorACO Paper on arXiv

Tensorized Ant Colony Optimization (TensorACO) enhances the convergence speed and efficient of large-scale Traveling Salesman Problems (TSP) by incorporating GPU acceleration. By tensorizing the ant system and path, TensorACO capitalizes on GPU parallelism for accelerated computation. Additionally, the Adaptive Independent Roulette (AdaIR) method enhances the performance by a dynamically strategy. TensorACO is compatible with the EvoX framework.

Key Features


  • GPU Acceleration 💻: Leverages GPUs for enhanced computational capabilities.

  • Large-Scale Optimization 📈: Ideal for large ant colony sizes and large city sizes.

  • Real-World Applications 🌐: Suited for TSP, a central challenge in combinatorial optimization, is characterized by the theoretical complexity and practical relevance in routing and logistics.

Requirements


TensorACO requires:

  • Python (version >= 3.7)
  • evox (version >= 0.7.0)
  • JAX (version >= 0.4.16)
  • jaxlib (version >= 0.3.0)
  • (Optional) CUDA and cuDNN for GPU acceleration

Example Usage


import jax
import jax.numpy as jnp
import algorithm
import problem

import evox

if __name__ == '__main__':

    algorithm = algorithm.TensorACO(
        distances=jnp.load('problem/pcb442.npy'),
        node_count=442,
        n_ants=442,
        n_best=100,
        decay=0.5,
        alpha=1,
        beta=2
    )

    problem = problem.TSP(
        jnp.load('problem/pcb442.npy')
    )
    monitor = evox.monitors.StdSOMonitor()

    key = jax.random.PRNGKey(42)

    workflow = evox.workflows.StdWorkflow(
        algorithm=algorithm, 
        problem=problem, 
        monitor=monitor
    )

    state = workflow.init(key)

    for i in range(100):
        state = workflow.step(state)
        monitor.flush()
        print(monitor.get_best_fitness())

Community & Support


Citing TensorACO


If you use TensorACO in your research and want to cite it in your work, please use:

@article{tensoraco,
  title = {{Tensorized} {Ant} {Colony} {Optimization} {for} {GPU} {Acceleration}},
  author = {Yang, Luming and Jiang, Tao and Cheng, Ran},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)},
  year = {2024}
}

Releases

No releases published

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •  

Languages