Genetic Algorithm For Optical Spectrum Defragmentation

Author(s): Bassem Essam

Originally published on Towards AI.

Genetic Algorithm For Optical Spectrum Defragmentation

Bassem Essam

·

Follow

Published in

·9 min read·1 hour ago

Listen

Share

The genetic algorithm has many applications in real-world problems. It works well in many optimization problems due to its simplicity and speed. The genetic algorithm is inspired by the evolution theory. It uses the randomness of generating new instances and the “survival to the fittest” concept to generate the optimal solution.

In this blog, the main idea and concepts of the genetic algorithm will be explained. They will be illustrated with the traveling salesman problem to clear the mechanisms of the algorithm with a practical example. Afterward, the optical spectrum fragmentation problem will be explained briefly, and why the genetic algorithm is a good solution for this problem. Finally, we will go through the application of the genetic algorithm to solve the spectrum fragmentation problem.

What is Genetic Algorithm?

The genetic algorithm mimics the concepts of the evolution theory. If we have a generation of a specific animal species and their pairs are mated, the resultant individuals will inherit the genes from both parents. The next generation of this species will have the individuals with the best genes inherited from the best parents and others with weak genes. After generations, the weak genes will disappear since the individuals who are carrying these genes will not be fit enough to survive and pass their genes to the next generations.

In optimization problems usually, we are trying to find the optimal solution from a large space of solutions, and we keep track of the different solutions to know if we are approaching the optimal solution or not. If we use the same concepts of evolution in our problem, we can find a semi-optimal solution in a reasonable time. The genetic algorithm goes into the same stages as happens with genes moving through the generations. At the beginning the population initialization, then the mating, the selection, and the mutation stage to explore larger search space. At this point, the concepts are still not clear, so we can explore the traveling salesman problem as an example and see how a genetic algorithm can find a solution to it in less time.

The Traveling Salesman Problem

The traveling salesman problem (TSP) is a famous NP-Hard problem that can be solved in exponential time. Let’s assume that a salesman has to visit 5 cities and return to the city where he started. What is the shortest path to go to all cities without passing by the same city twice? The straightforward approach is to calculate the distances of all possible solutions and choose the one with the lowest distance. This approach is good but it’s very time-consuming and not scalable as the number of cities increases the time complexity increases. In our example, the five cities have 5! possible paths, which is 120 paths, what if we have 100 cities, the possible paths are 36828800, so another approximate solution can be developed to find the near-optimal solution. One of the algorithms is the greedy algorithm, in which you choose the nearest unvisited city to the current city as the next destination city until you are done with all the cities. This algorithm is very good in the sense of the reduction of the time complexity which is reduced to n instead of n! The greedy algorithm is really fast but the solution is not optimal especially when the number of cities (n) is high. Here the genetic algorithm comes to play a role.

First, let’s assume that we take a sequence of cities randomly and calculate the total distances between these cities. Again, we keep randomizing this set and hopefully, we get the minimum distance. Here, we still have a chance to hit the optimal solution (the minimum total distances between the cities). The challenge is to select the best random solution and keep track of how you are approaching the optimal solution. Now let’s see how the genetic algorithm helps solve these challenges.

When we generate a set of cities, we will call it a chromosome and the total distances between cities in this set will be the chromosome fitness. Here our goal is to minimize the fitness of the chromosome as much as possible. Let’s generate thousands of chromosomes (combinations of cities) and call them the population. The next step is to mate the individuals in the population somehow and crossover their chromosomes. This means that we take the first half of the sequence from the first chromosome and the second half from the second chromosome. Afterward, we calculate the fitness of the individuals in the population. We select the best individuals (the chromosome with the minimum fitness score) then, move them to the next generation and repeat these steps for each generation until we solve with the best fitness when the algorithm converges. Till this point, we missed a very important step which is the mutation, in this step, we make some changes to the generated chromosomes at a very low rate to help the algorithm explore other areas in the search space. Without mutation, the algorithm will keep searching in the possible variations of the cities and might end up without getting any optimal solution.

Optical Spectrum Fragmentation

The optical spectrum fragmentation problem is very common in DWDM networks. The fragmented spectrum is the spectrum that is not efficiently utilized. In DWDM networks, the wavelengths are multiplexed together in one fiber core to be sent to the far-end site. In the C band, there are traditionally 88 X 50GHz channels in one link. If we have a complex optical network, the wavelengths are routed between sites to fulfill the traffic matrix needs of the customers. In the example shown in Figure (3), we need to avail a wavelength between site 1 to site 3 through link1, link2 but in the fragmented spectrum, the only available bandwidth between site 1 and site 3 is one wavelength. Without doing any correction actions to the existing wavelengths, you have to deploy new links between site 1 and site 3, which wastes the available resources and introduces more costs. The de-fragmentation process is simply migrating the already-existing wavelengths to one side of the spectrum to avail more portion of the spectrum for the new requests of traffic and optimize the available links. The correction actions needed for de-fragmentation of the spectrum are very expensive since they need planned outage windows and long planning activities to plan and execute the correction actions. Hence, one of the important aspects of spectrum optimization is to keep the modifications minimum to reduce the cost implied in the changes.

Genetic Algorithm in Spectrum de-fragmentation

Now, we understand the concepts of the genetic algorithm and how to apply it in TSP. The question is how to apply the algorithm to solve the fragmentation problem. First, we need to represent the allocation of the different wavelengths in the spectrum as a chromosome to generate the population and continue the other steps. The spectrum allocation map can help us in representing the distribution of the wavelengths. Figure (4) shows a toy example in which a wavelength is tagged by a unique ID, the rows represent the links and the columns represent the wavelengths in the spectrum. Any free slot in the spectrum is represented by 0.

Fitness Function

The fitness function is a key element in the algorithm since it determines how to fit the chromosome and tells us if we are going in the right direction. A spectrum that is fully utilized is a spectrum of all services that occupy the minimum number of wavelengths in the spectrum, so the fitness function in this problem consists of three components. The first component is the percentage of free lambdas in the spectrum which have no channels created on. The table with more empty columns is more optimized. The second component is the utilization of each lambda (The number of occupied slots in a lambda/ The total number of frequency slots). The third component is the number of changes applied between the original version of the table and the chromosome table that the fitness function applied to.

The optimization of the fitness function is to minimize the fitness of the individuals and select the best individuals. F1, F2 and F3 are factors to give different weights to each component of the fitness score.

Fitness score = F1 * free lambdas + F2 * lambda utilization + F3 * number of changes

Population Initialization

We have an initial version of our spectrum allocation map. We need to generate many random versions of it to initialize the population. In our case, we have restrictions and guidelines to make sure that the individual (one version of the spectrum allocation map) is valid. The first guideline is that we are not going to re-route a wavelength (Och) to free a portion of the spectrum. The reason is that re-routing the Och implies the calculation of the OSNR of the new wavelength. This is another task with a lot of details and complexities. Hence, The Ochs will move horizontally on the same links but with changing the channel frequency. The second guideline is that no multiple Ochs can occupy the same frequency slot in any of the common links between the Ochs. Finally, we need to randomize the generation of the initial version of the table to get a wide variance of individuals in the population.

Crossover

The crossover in our problem here is to combine two individuals, half from one parent and half from the other parent to produce a new individual (a spectrum allocation table). The main challenge here is that the allocation of the Ochs in both parents can be overlapped, so the approach to achieve a successful crossover function is to generate a random number as a separator of a range between 1 and the number of Och IDs in the spectrum. For Ochs with ID less than the separator ID, The locations of the Ochs will be taken from the first parent, and for all Och IDs higher than the separator ID will be taken from the second parent. In case of overlapping of Och IDs in both parents, the Och ID is allocated in the first available positions (the Och will be moved horizontally until it fits in a free position). In Figure (5) the Och ID 4 is used as a crossover separator, and if there is an overlapping in the Och locations, it moves to the first fit allocation (Child 2).

Selection

There are many selection techniques to select the best individuals for the next generation. One of the techniques is k-tournament selection. K random individuals are selected and the fittest individual is chosen. The good thing about K-tournament selection is that it selects from a low number of candidates therefore, the randomness of the output selection is kept, which means that selection will still have some weak chromosomes that make the search space wide.

Mutation

The mutation process is very important to discover new spaces in the search spaces moving from one generation to the other. In the de-fragmentation problem, the mutation is flipping two random columns with each other.

Conclusion

The Genetic algorithm is very effective in optimization problems. It is inspired by the evolution theory using randomness to generate many versions of the problem and mate these versions to produce fitter individuals led by a fitness function to reach the best solution. We went through the genetic algorithm to solve the traveling salesman problem to view the concepts of the algorithm.

One of the problems in the optical networks is the fragmentation in the optical spectrum. This problem is that the spectrum is not well utilized which blocks the network operators from availing new services. The genetic algorithm can offer a good solution to solve the problem and optimize the spectrum. The algorithm is applied to the spectrum de-fragmentation by designing a fitness function, crossover, selection, and mutation process to find the best solution that represents the optimized spectrum.

Thank you for reading my blog. For any questions and queries, please contact me on my LinkedIn profile:

https://www.linkedin.com/in/bassemessam/

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI