Your task is to implement a Genetic algorithm (GA) to optimize the cost of an

overlay network of 25 nodes. In order to get you started the design of the chromosome representation, crossover and mutation operators are given to you. Essentially an overlay network consists of links, which are either active or inactive.

Every individual in a population encodes a complete network (as shown above),

where each link is either active or inactive. A text file network.txt contains the link

information of all possible network connections in the following form: The first link in the table connects node 1 with node 2 and has a cost of 85.19, and so on. For the first step of the GA you have to initialize your population of chromosomes. You have to randomly generate new overlay networks, by either assigning a link or not between any two given nodes (1 for active, 0 for inactive). One possible network configuration could be the following:

Once the initial population is generated, the fitness of each network needs to be calculated (use the fitness function provided). We use the following fitness function

to calculate an overlay networks fitness in terms of cost: where is the cost of the overlay network, and is the total cost of a fully connected network. Afterwards, a selection method needs to be implemented. You are asked to implement the tournament selection method. Tournament selection involves running k tournaments among a few chromosomes chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Then, the crossover method needs to be implemented and the figure below shows how this can be done using two-point crossover. If crossover happens based on the probability choose two randomly chosen points within the chromosome and swap the middle part.

Once the crossover method is done, the mutation method needs to be implemented as such: if mutation happens based on the probability choose one bit of the chromosome randomly and flip it.

The following GA parameters should be used for the initial run of the

implementation:

Population size: 100

Crossover rate: 70%

Mutation rate: 0.1%

Maximum number of iterations: 1,000

Selection method: Tournament (K=2)

Genetic Algorithm Description:

1. [Start] Generate random population of n chromosomes.

2. [Fitness] Evaluate the fitness f(x) of each chromosome x in

the population.

3. [New population] Create a new population by repeating the

following steps until the new population is complete:

1. [Selection] Select two parent chromosomes from the

population according to their fitness (the better, the

greater the chance to be selected).

2. [Crossover] With a crossover probability cross over the

parents to form new offspring (children). If no

crossover is performed, both offspring are an exact copy

of their parents.

3. [Mutation] For each chromosome and with a mutation

probability mutate new offspring at one position in

chromosome. If no mutation is performed, offspring is

an exact copy of the parent.

4. [Replace] New population replaces old population.

5. [Test] If the maximum number of iterations is satisfied, stop,

and return the best solution in current population.

6. [Loop] Go to Step 2.

Description Your task is to implement a Genetic algorithm (GA) to optimize the cost of an overlay network of 25 nodes. In order to get you started the design of the chromosome representation, crossover and mutation operators are given to you. Network Bapresentation Overny Encoding -1,1,1,0,0,0 Encoding- Underlying Physical Network Essentially an overlay network consists of links, which are either active or inactive. Every individual in a population encodes a complete network (as shown above). where each link is either active or inactive. A text file network.txt contains the link information of all possible network connections in the following form: Node Node Cost 2 85.19 105.98 100.36 88.73 1 6 103.73 7 124.07 1 1 1 1 3 4 5 1 The first link in the table connects node 1 with node 2 and has a cost of 85.19, and so on. For the first step of the GA you have to initialize your population of chromosomes. You have to randomly generate new overlay networks, by either assigning a link or not between any two given nodes (1 for active, O for inactive). One possible network configuration could be the following: Once the initial population is generated, the fitness of each network needs to be calculated (use the fitness function provided). We use the following fitness function to calculate an overlay network's fitness in terms of cost: F-1-6) CN where c is the cost of the overlay network, and en is the total cost of a fully connected network. Afterwards, a selection method needs to be implemented. You are asked to implement the tournament selection method. Tournament selection involves running k tournaments among a few chromosomes chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Then, the crossover method needs to be implemented and the figure below shows how this can be done using two-point crossover. If crossover happens based on the probability choose two randomly chosen points within the chromosome and swap the 'middle' part. Two Point Crossover Pent Paret Encoding-st. 1.01.000,0 Encoding-0.18. 11, Encoding Underlying Physical Network Essentially an overlay network consists of links, which are either active or inactive. Every individual in a population encodes a complete network (as shown above). where each link is either active or inactive. A text file network.txt contains the link information of all possible network connections in the following form: Node Node Cost 2 85.19 105.98 100.36 88.73 1 6 103.73 7 124.07 1 1 1 1 3 4 5 1 The first link in the table connects node 1 with node 2 and has a cost of 85.19, and so on. For the first step of the GA you have to initialize your population of chromosomes. You have to randomly generate new overlay networks, by either assigning a link or not between any two given nodes (1 for active, O for inactive). One possible network configuration could be the following: Once the initial population is generated, the fitness of each network needs to be calculated (use the fitness function provided). We use the following fitness function to calculate an overlay network's fitness in terms of cost: F-1-6) CN where c is the cost of the overlay network, and en is the total cost of a fully connected network. Afterwards, a selection method needs to be implemented. You are asked to implement the tournament selection method. Tournament selection involves running k tournaments among a few chromosomes chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Then, the crossover method needs to be implemented and the figure below shows how this can be done using two-point crossover. If crossover happens based on the probability choose two randomly chosen points within the chromosome and swap the 'middle' part. Two Point Crossover Pent Paret Encoding-st. 1.01.000,0 Encoding-0.18. 11, Encoding