FLIght SCheduling OPTimization - a simple optimization library for flight scheduling and related problems in the discrete domain

Overview

Fliscopt

Stars Forks License Issues made-with-python Open Source Love png1 Maintenance PRs Welcome PyPI Tweet Say Thanks!

image

FLIght SCheduling OPTimization πŸ›« or fliscopt is a simple optimization library for flight scheduling and related problems in the discrete domain. The library supports plotting, asynchronous multiprocessing, and unimodal optimization benchmarks. The following repository contains code for the paper "XYZ". The experiments were performed in PyPy3.7 and CPython 3.8.10.

Following algorithms have been implemented and test as of date:

Algorithms:

  • Hill Climbing
  • Random Search
  • Simulated Annealing
  • Genetic Algorithm
  • Genetic Algorithm in Reverse Mode
  • Genetic Algorithm with Reversals
  • Genetic Algorithm with Random Search as a Reversal/Reverse Process
  • Iterated Chaining

Take a look at the docs

Getting Started

Install the library using pip:

pip install fliscopt

Or for unreleased versions:

pip install 'git+https://github.com/Agrover112/fliscopt/[email protected]

Or for development:

git clone https://github.com/Agrover112/fliscopt.git
cd fliscopt
pip install .

Download the flights.txt file from the following link and add it to a data/ directory within your parent directory.

Checkout out the examples in the examples directory or run in Google Collab

For PyPy users

The instructions for setup are mentioned in the setup directory. Alternatively, you can set up using this bash script. A requirements file is provided just in case. The script creates and activates a PyPy Conda environment with all libraries and dependencies.

cd ./setup.sh
source setup.sh

Then install using:

pypy -mpip install fliscopt

Testing

After adding any new algorithm, you can run the tests to check if the code is working properly.

./run_tests.sh

Results

Experimental Results

Results were compared by using the same seeds. The following table shows the results of the experiments. (Will be shortly added)

Accessing results

After running the experiments, the results are stored in the results directory. The results are stored in the following format in subdirectories:

.
β”œβ”€β”€ multi_proc
β”‚   β”œβ”€β”€ ackley_N2
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_results.csv
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_reversed_results.csv
β”‚   β”‚   β”œβ”€β”€ genetic_algorithm_with_reversals_results.csv
β”‚   β”‚   β”œβ”€β”€ hill_climb_results.csv
β”‚   β”‚   β”œβ”€β”€ random_search_results.csv
β”‚   β”‚   └── simulated_annealing_results.csv
β”‚   β”œβ”€β”€ booth/...
|   |
|   |
β”‚   └── zakharov
β”‚       β”œβ”€β”€ genetic_algorithm_results.csv
β”‚       β”œβ”€β”€ genetic_algorithm_reversed_results                  
β”‚       β”œβ”€β”€ genetic_algorithm_with_reversals_results.csv
β”‚       β”œβ”€β”€ random_search_results.csv
β”‚       └── simulated_annealing_results.csv
β”œβ”€β”€ plots
β”‚   β”œβ”€β”€ ackley_N2
β”‚   β”œβ”€β”€ fitness_function
β”‚   β”‚   β”œβ”€β”€ hill_climb.png
β”‚   β”‚   └── random_search.png
β”‚   β”œβ”€β”€ flight_scheduling
β”‚   β”‚   β”œβ”€β”€ simulated_annealing.png
β”‚   β”‚   β”œβ”€β”€ sol_chaining.png
β”‚   β”‚   └── sol_chaining_a1.png
β”‚   └── griewank

References

Read the following for detailed understanding of our project.

[1] Alicea B., Grover A., Lim A. ,Parent J, Unified Theory of Switching. Flash Talk to be presented at: 4th Neuromatch Conference; December 1 - 2, 2021

Contributing Guidelines

Refer Contributing.md and Project Board for mode details. This repository follows conventional commits!

Comments
  • Add message for failed unittests.

    Add message for failed unittests.

    A message indicating a failure for each unit-test, should give the user a small idea of what went wrong in the test. ex: self.assertEqual ( f(values), 0, msg ='HEURISTIC MESSAGE INDICATING WHY TEST CASE FAILED')

    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 12
  • fix:Add docstrings for each algorithm file.

    fix:Add docstrings for each algorithm file.

    Fixing Issue #27 , Please check the added docstrings and if the format is correct, if wrong please help me to correct the mistakes because I am a complete beginner to Google Docstrings and even large Python Codebases. Thank you and have a great day!

    Hacktoberfest Hacktoberfest-accepted 
    opened by subhamgcon 11
  • Add docstrings for each algorithm file.

    Add docstrings for each algorithm file.

    There are few files which contain implementation of the algorithms: [**sa,ga,hc,chaining,rs].py** you need to write the docstring for the classes present in each file using Google Docstring Convention. Refer: algorithms.py on how to write docstrings for functions and similarily refer THIS and THIS link for on getting started on how to write docstrings for the classes. PS : Google Style Guide

    • [ ] chaining.py
    • [ ] ga.py
    • [ ] rs.py
    • [ ] sa.py
    • [ ] hc.py
    documentation good first issue Hacktoberfest 
    opened by Agrover112 6
  •  #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    Creating pr to reference #10

    Docs should also be accessible in main branch (aka master) imo, we can autogenerate docs based on markdown files @Agrover112 inside the module/library

    E.g. let's say you create a doc page in /docs branch called "Why bees can't fly" with the meta tag for doc-tag being bees

    We can setup a script in main branch that when using module in ide, user can type /fliscopt help bees and will find the "intro" meta about the bees entry in the markdown file in /docs branch, as well as a link to view the documentation site

    documentation enhancement 
    opened by Gizmotronn 5
  • Add an Pull Request template

    Add an Pull Request template

    πŸ‘Ž Actual Behavior

    A template for raising a Pullreq.

    πŸ‘ Expected behavior

    same as above

    ✍️ Suggestions to rectify this issue

    Create a .yml template for creating a PR template.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 5
  • fix(readme): Add graphic

    fix(readme): Add graphic

    Closes #11 @Agrover112 I have added a graphic and a logo file in the project, and updated the readme file. I have referred to the above mentioned graphics. Please mention any suggestion or changes to the graphic/logo file. I will look into it and make the necessary changes.

    enhancement Hacktoberfest Hacktoberfest-accepted 
    opened by Anik-Bardhan 5
  • Comparing differences between config files -> #10

    Comparing differences between config files -> #10

    Seems like it's a plugin dependancy issue that's causing the build issues. @Agrover112 Docs should be ready to go, I haven't been able to get the lightweight CMS editor working BUT I'd advise setting this up with GitHub pages by tomorrow and then logging in with prose.io for now UNTIL I can fix the plugin issue

    gem bundle build is the worst thing I can imagine rn.

    bug documentation 
    opened by Gizmotronn 2
  • πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ‘Ÿ Reproduction steps

    Just use the api normally and enter any combination of n_k and number_generations.

    πŸ‘ Expected behavior

    The number of reversals would be = iter/n_k

    πŸ‘Ž Actual Behavior

    Only 1 reversal process takes place , as seen due to default parameters, thus entered parameters are not registering.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 2
  • Add an Pull Request template #39

    Add an Pull Request template #39

    Closes #39

    Renamed PULL_REQUEST.md to to pull_request_template.md following these instructions https://docs.github.com/en/communities/using-templates-to-encourage-useful-issues-and-pull-requests/creating-a-pull-request-template-for-your-repository

    This has been tested as shown in the screenshot. image

    opened by LittleBigProgramming 2
  • Merge this

    Merge this

    What does this PR do?

    Updates README.md with some missing information wrt Results tables.

    Test Plan

    (Write your test plan here. If you changed any code, please provide us with clear instructions on how you verified your changes work.)

    Related PRs and Issues

    (If this PR is related to any other PR or resolves any issue or related to any issue link all related PR and issues here.)

    Have you read the Contributing Guidelines on issues?

    (Write your answer here.)

    opened by So-bonkers 1
  • Add PyPy tests.

    Add PyPy tests.

    Current ./run_tests.sh due to oversight were written and run using python filename.py. In order to appropriately test it , it needs yo be replaced by: pypy filename.py

    opened by Agrover112 1
  • Github Sync Fork action not working

    Github Sync Fork action not working

    πŸ‘Ž Actual Behavior

    Failed to create or merge pull request: HttpError: Validation Failed: {"resource":"PullRequest","field":"head","code":"invalid"}

    πŸ‘ Expected behavior

    Should technically sync forks?

    ✍️ Suggestions to rectify this issue

    I'm currently using secrets.TOKEN, a token which I use for the repo with public_repo permissions enabled. Not sure what is going wrong really. image

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 0
  • πŸ“‹General Issues: Exception handling

    πŸ“‹General Issues: Exception handling

    πŸ‘Ž Actual Behavior

    The Error isn't handled properly.

    πŸ‘ Expected behavior

    Should raise a particular Error (exception) when unintended input is passed to the given fn,etc.

    ✍️ Suggestions to rectify this issue

    Add exception handling for each of the core functions and algorithms

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 0
  • Fix #FIX-NEEDED

    Fix #FIX-NEEDED

    πŸ‘Ÿ Reproduction steps

    Implemented in: mulit_mutattion in ga_utils.py Can be tested by replacing mutation with multi_mutation in ga.py.

    πŸ‘ Expected behavior

    Mulit_mutattion in ga_utils.py should change N bits as selected. [1,2,3,4] for 2 bits could be: [1,3,3,5]

    πŸ‘Ž Actual Behavior

    Mulit_mutattion in ga_utils.py doesn't work as expected. Gives an Index Error when used , since the implementation is not correct.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted good first issue Hacktoberfest 
    opened by Agrover112 5
  • Add more problem functions in fitness.py

    Add more problem functions in fitness.py

    Add more problems rel to current flightscheduling problem. (No matrix problems) Only problems whose solution is of the form: [1,2,3,4] OR [x1,z2..........xn] and corresponding domain : [(-a,b),(-c,-d).......nth-tuple]. Refer fitness.py for existing problems and cost functions and their domains.

    Ideally the isse requires you to add a sample cost function to solve a particular problem, whose inputs are of form 1*n

    enhancement help wanted good first issue Hacktoberfest 
    opened by Agrover112 7
Releases(v0.4.1)
Owner
Humans trying to understand machines...
A simple python application to visualize sorting algorithms.

Visualize sorting algorithms A simple python application to visualize sorting algorithms. Sort Algorithms Name Function Name O( ) Bubble Sort bubble_s

Duc Tran 3 Apr 01, 2022
Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Sorting-Algorithms - All information about sorting algorithm you need and you can visualize the code tracer

Ahmed Hossam 15 Oct 16, 2022
Python sample codes for robotics algorithms.

PythonRobotics Python codes for robotics algorithm. Table of Contents What is this? Requirements Documentation How to use Localization Extended Kalman

Atsushi Sakai 17.2k Jan 01, 2023
Algorithms written in different programming languages

Data Structures and Algorithms Clean example implementations of data structures and algorithms written in different languages. List of implementations

Zoran Pandovski 1.3k Jan 03, 2023
Wordle-solver - A program that solves a Wordle using a simple algorithm

Wordle Solver A program that solves a Wordle using a simple algorithm. To see it

Luc Bouchard 3 Feb 13, 2022
Infomap is a network clustering algorithm based on the Map equation.

Infomap Infomap is a network clustering algorithm based on the Map equation. For detailed documentation, see mapequation.org/infomap. For a list of re

347 Dec 23, 2022
The test data, code and detailed description of the AW t-SNE algorithm

AW-t-SNE The test data, code and result of the AW t-SNE algorithm Structure of the folder Datasets: This folder contains two datasets, the MNIST datas

1 Mar 09, 2022
This application solves sudoku puzzles using a backtracking recursive algorithm

This application solves sudoku puzzles using a backtracking recursive algorithm. The user interface is coded with Pygame to allow users to easily input puzzles.

Glenda T 0 May 17, 2022
Path finding algorithm visualizer with python

path-finding-algorithm-visualizer ~ click on the grid to place the starting block and then click elsewhere to add the end block ~ click again to place

izumi 1 Oct 31, 2021
A Python library for simulating finite automata, pushdown automata, and Turing machines

Automata Copyright 2016-2021 Caleb Evans Released under the MIT license Automata is a Python 3 library which implements the structures and algorithms

Caleb Evans 219 Dec 12, 2022
A collection of Python Scripts made for fun, while exploring Python 🐍

JFF-Python-Scripts A collection of Python Scripts made for fun, while exploring Python 🐍 Inspiration πŸ’‘ Many of the programs in this repository are i

Pushkar Patel 16 Oct 07, 2022
Repository for Comparison based sorting algorithms in python

Repository for Comparison based sorting algorithms in python. This was implemented for project one submission for ITCS 6114 Data Structures and Algorithms under the guidance of Dr. Dewan at the Unive

Devashri Khagesh Gadgil 1 Dec 20, 2021
This repository is not maintained

This repository is no longer maintained, but is being kept around for educational purposes. If you want a more complete algorithms repo check out: htt

Nic Young 2.8k Dec 30, 2022
All algorithms implemented in Python for education

The Algorithms - Python All algorithms implemented in Python - for education Implementations are for learning purposes only. As they may be less effic

1 Oct 20, 2021
Apriori - An algorithm for frequent item set mining and association rule learning over relational databases

Apriori Apriori is an algorithm for frequent item set mining and association rul

Mohammad Nazari 8 Jan 10, 2022
Algorithmic Trading with Python

Source code for Algorithmic Trading with Python (2020) by Chris Conlan

Chris Conlan 1.3k Jan 03, 2023
Distributed algorithms, reimplemented for fun and practice

Distributed Algorithms Playground for reimplementing and experimenting with algorithms for distributed computing. Usage Running the code for Ring-AllR

Mahan Tourkaman 1 Oct 16, 2022
This repository is an individual project made at BME with the topic of self-driving car simulator and control algorithm.

BME individual project - NEAT based self-driving car This repository is an individual project made at BME with the topic of self-driving car simulator

NGO ANH TUAN 1 Dec 13, 2021
Exact algorithm for computing two-sided statistical tolerance intervals under a normal distribution assumption using Python.

norm-tol-int Exact algorithm for computing two-sided statistical tolerance intervals under a normal distribution assumption using Python. Methods The

Jed Ludlow 1 Jan 06, 2022
Nature-inspired algorithms are a very popular tool for solving optimization problems.

Nature-inspired algorithms are a very popular tool for solving optimization problems. Numerous variants of nature-inspired algorithms have been develo

NiaOrg 215 Dec 28, 2022