In this homework you will solve
- – Sorting optimization problem, and
- – Minimum spanning tree (MST) problem
using
- – Tabu Search (TS), and
- – Genetic Algorithms (GA).
- Design and implement TS based algorithm for both problems (MST and sorting optimization problem).
- Design and implement GA based algorithm for both problems (MST and sorting optimization problem).
- Write a report about your work. In your report, you should
- – give the rigorous and in detailed definition of the optimization problems that you used to design
your algorithms.
- – give explanation of your design. If there are alternatives for a design decision, explain why you
choose the one in your design. Write pseudo-code of your algorithms.
- – explain non-trivial implementation details in your code.
- – present the theoretical run-time analysis
- – present the results of experimental analysis. Run your algorithms for several benchmark
problems (of various complexities and sizes) and present their performance. Draw figures and tables.
- – give the rigorous and in detailed definition of the optimization problems that you used to design
Note that you will work with the same (or very similar) problems for future homework assignments and design algorithms using following design techniques, as well.
- – Particle Swarm Optimization
- – Ant Colony Optimization
