Question

Please if you can help question (i) at least, which would be very helpful.

Assume that a wireless channel can transmit up to 30 Mbps and can be divided between any number of admitted users. There are 7 users in total with the data rate as shown in vector R [rl (R[5, 11, 3, 2, 7, 15, 10]) in Mbps. The profit of a service provider will depend on the number of admitted users as well as the allocated data rate to that users, i.c. profi: for iving service to the, usor x is pi ảne is equal to: pi 1.2* r10/ ri. Service provider's objective is to maximise their profit Model this problem as a Knapsack problem; use greedy approximation and find out which users will be [5 marks] given service. i Model the problem with the genetic algorithm, starting with the population of five chromosomes, and continue for five iterations Use five bits binary for representing the chromosomes Assume cross-over probability is 0.5 and mutation probability is 1 Define your cross-over and mutation operators yourself (use the same operation for all the five iterations) Write all steps of computing the five sets of populations. Based on the fifth population, which users will be allocated service? If you make any further assumptions, explain them. 10 marks]

Answer 1

Ans (i) In the Knapsack Problem Weights, Values, Items are required to solve the problem; in which given Weights and values of n items are putted into a knapsack of capacity W to get the maximum total value in the knapsack.

Here Items are users which are I[1-7], Weights are data rate i.e. wt[5,11,3,2,7,15,10] and values are the profit calculated val[8.14.1,6.9,7.4,9.8].

This is wight and value table above

here comparing W=30 with total wight and highest values .

here we are taking two weights

18 (V 6.9t 18 6 95.5 W35 Ws 15+2-22, (Vs 186+8,8-28. Ч ) Hou wu Can See that 10 ,V( 8+14-1+13ニは5:11

similarly all weights are calculated and compared

in last weight=11+2+3+10 with value =14.1+6.9+7.4+13=41.4 is highest profit gained with weight upto 30 Mbps.User 2,3,4,7 will be given service.

Here is the program for same in C programming Language

#include<stdio.h>

// function that returns maximum of two integers

int max(int a, int b) { return (a > b)? a : b; }

int main()

{

    int val[] = {60, 100, 120};

    int wt[] = {10, 20, 30};

    int W = 50;

    int n = sizeof(val)/sizeof(val[0]);

    printf("%d", knapsack(W, wt, val, n));

    return 0;

}

int knapsack(int W, int wt[], int val[], int n)

{

   int i, w;

   int K[n+1][W+1];

  

   // Build table K[][] in bottom up manner

   for (i = 0; i <= n; i++)

   {

       for (w = 0; w <= W; w++)

       {

           if (i==0 || w==0)

               K[i][w] = 0;

           else if (wt[i-1] <= w)

                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

           else                    

                 K[i][w] = K[i-1][w];

       }

   }