This assignment aims to broaden students’ understanding about different types of optimization techniques. The assignment focuses on swarm intelligence and provides hands-on with the Ant-Colony optimization technique to solve the Graph Coloring problem.
Q-1 – Coloring Graphs using ACO
Graph coloring is a classic problem in Computer Science in which you are required to color the vertices of a graph (vertex coloring) with minimum colors such that no two adjacent vertices are of same color (as shown in the image below).
In this question, you will implement Ant-Colony Optimization (ACO) technique to solve the vertexcoloring problem. Several problem instances are available here from where you can download the data file (gcol1.txt) for your testing.
You can start with the following values for different parameters (No. of ants, Q, α, β,) and are required to fine-tune these values to come up with the best set of parameters for the given problem:
- α: 0.8 - β: 0.8
- : 0.8
- No. of ants: 20
You also need to plot a graph to show the behavior of your implementation during the optimization process:
- Iteration vs Best fitness so far
- Iteration vs avg fitness so so far
The grading will be based on the following components:
Problem Formulation
Properly formulating ACO to address Graph coloring problem
25%
Implementation
Correct implementation of the algorithm and the proposed formulation
40%
Results
Fine-tuning of parameters, Convergence behavior, Final outcome, Graph plotting
15%
Report
Quality of Writing, Clarity
20%
The report will cover the details of Problem formulation and results and their analysis.
Q-2 Know more about Optimization
a) Read the following article thoroughly to understand the heuristic and metaheuristic optimization and get a general idea of different techniques of optimization.
Based on above two readings, answer the following questions:
1. What is metaheuristic optimization?
2. What are the situations in which gradient based optimization techniques do not work?
3. Briefly explain any one swarm based algorithm that we have NOT discussed in the class.
