Simple EMOO Problem

This code is an applicatino of EMOO by using Genetic algorithms to solve the following simple constrained problem: Draw the biggest possible circle in a 2D space filled with stars without enclosing any of them.

Author: Wesam ELSHAMY

Electrical Engineering Dept., Cairo University, Egypt

[e-mail]

wesamelshamy.googlepages.com

Contents

• Initializing parameters
• Building the stars
• Cearting initial population
• Initial Population Fitness Assignment
• The Iterations

Initializing parameters

clear;
stars = 30;
iterations = 500;
population = 100;
mutation = 0.7;
mutation_step = 0.8;
grid_size = 10;

Building the stars

for i = 1:stars
    for j = 1:2
        star(i,j) = rand(1)*grid_size;
    end
end
plot(star(:,1),star(:,2),'x')
hold on

Cearting initial population

for i = 1:population
    for j = 1:2
        cit(i,j)= rand(1)*grid_size;
    end
end

Initial Population Fitness Assignment

for j = 1:population
    for k = 1:stars
        d(k) = sqrt((star(k,1)-cit(j,1))^2 + (star(k,2)-cit(j,2))^2);
    end
    d(stars+1) = cit(j,1);
    d(stars+2) = grid_size - cit(j,1);
    d(stars+3) = cit(j,2);
    d(stars+4) = grid_size - cit(j,2);
    d = sort(d);
    cit(j,3) = d(1);
end
cit = sortrows(cit,-3);
cit(1,:)
cit(:,3) = cit(:,3)/cit(1,3);

ans =

    2.6457    7.1843    1.7186

The Iterations

for i = 1:iterations
    %--------------- Mating Selection -----------------
    cit(:,3) = cit(:,3)/cit(1,3);
    pool = [];
    for l = 1:population
        if rand(1)<cit(l,3),pool=[pool;cit(l,:)];,end
    end
    %--------------- Crossover ------------------
    s = size(pool,1);
    if s/2 - round(s/2) ~=0 , pool = pool(1:s-1,:); , s = size(pool,1); , end
    for m = 1:2:s
        pool = [ pool ; [pool(m,1) , pool(m+1,2) , 0]];
        pool = [ pool ; [pool(m+1,1) , pool(m,2) , 0]];
    end
    %--------------- Mutation -------------------
    s = size(pool,1);
    for m = 1:s
        if ((rand < mutation) & (pool(m,1) < grid_size - mutation_step)) , pool(m,1)=pool(m,1)+(2*rand - 1)*mutation_step;,end
        if ((rand < mutation) & (pool(m,2) < grid_size - mutation_step)) , pool(m,2)=pool(m,2)+(2*rand - 1)*mutation_step;,end
    end
    %--------------- Invironmental Selection------------
    temp = [cit ; pool];
    ts = size(temp,1);
    for j = 1:ts
        for k = 1:stars
            d(k) = sqrt((star(k,1)-temp(j,1))^2 + (star(k,2)-temp(j,2))^2);
        end
        d(stars+1) = temp(j,1);
        d(stars+2) = grid_size - temp(j,1);
        d(stars+3) = temp(j,2);
        d(stars+4) = grid_size - temp(j,2);
        d = sort(d);
        temp(j,3) = d(1);
    end
    temp = sortrows(temp,-3);
    cit = temp(1:population,:);
end
xc = cit(1,1);
yc = cit(1,2);
r  = cit(1,3);
x = (xc-r) : 0.05 : (xc+r);
for i = 1:size(x,2)
    y(i) = yc + sqrt(r^2-(x(i)-xc)^2);
end
plot (x,y)
for i = 1:size(x,2)
    y(i) = yc - sqrt(r^2-(x(i)-xc)^2);
end
plot (x,y)
hold off

Published with MATLAB® 7.2