Assuma a cell phone company needs to setup antennas to cover a rectangular m × n area. Company has k different type of antenna. c_i is the cost of a i typed antenna. r_i is the coverege radius of a i typed antenna. Antennas are installed at grid positions. When the euclidian distance between the antenna and the point is less than or equal to r_i, that point is covered by that antenna. A point is considered covered when at least one antenna covers it.

Company can install up to s antennas. However they want to cover as much of the m×n grid as possible with minimum cost.

You are asked to design and implement a genetic algorithm for the problem. m, n, s, k, c_i and r_i  i = 1,k are given as input. The fitness value f to maximize and summary of parameters are given as:

As default encoding, use an array of size s as your genotype. Each allele is a triple (i,x,y). i is a number in [0,k]. 0 means antenna is not installed, otherwise i is the type of antenna. x is an integer in [0,m] and y is an integer in [0,n] denoting the position of the antenna. In this way, you expect to find the positions and types of antennas to install in the grid. Also use the following parameters in the default implementation:

• random initialization of each integer value. Only valid triples.
• population size 100
• tournament selection
• 5% mutation probability. Randomly set one of the elements of the triple.
• One point crossover
• 1% elitism. Replace worst offspring with best parent in the next generation.

Then make an experiment with different parameter setups. Here are some parameters for experiment:

• different crossover operators (arithmetic crossovers etc.)
• different selection mechanisms/pressures
• another possible encoding or another idea you have (just ask me before)

Choose at least 3 parameter setups. Repeat experiment for each setup for at least 10 times and collect results for best and average fitnesses for each generation and number of moves required to guess the number. Plot average (of 20 experiments) charts for:

• generation vs best fitness for 3 setups
• generation vs average fitness for 3 setups

You can use GALib (http://lancet.mit.edu/ga/) or any library of your choice. You shall submit your code with an experiment report with the following template:

Topic: Antenna placement problem
Name surname:       Id:      

GA Parameters: (mark the difference in 3 setups)

Population size:
Crossover/mutation rates:
Type of crossover/mutation:
Selection mechanism:
% of Elitism:
Fitness function:

Results

..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........ ..... ..... .......... ......... .......... .......... ........

Please do not ask homework related questions by email unless it is personal. Use newsgroup so that all can share the answers.

I will post the input data in couple of days.