ANt Collony Algorithm

REFRENSI ANT:

XY =

    82    66
    91     3
    12    85
    92    94
    63    68
     9    76
    28    75
    55    39
    96    66
    97    17
    15    71
    98     3
    96    27
    49     4
    80     9
    14    83
    42    70
    92    32
    80    95
    96     3

Sistem akan auto move mencari jarak terdekat untuk melalui semua titik yang ada..

dan ini adalah grafik kecerdasannya...
Iteration 1: Best Cost = 650.2307
Iteration 2: Best Cost = 540.892
Iteration 3: Best Cost = 531.4992
Iteration 4: Best Cost = 483.6564
Iteration 5: Best Cost = 483.6564
Iteration 6: Best Cost = 483.6564
Iteration 7: Best Cost = 483.6564
Iteration 8: Best Cost = 451.971
Iteration 9: Best Cost = 451.9041
Iteration 10: Best Cost = 439.1259
Iteration 11: Best Cost = 439.1259
Iteration 12: Best Cost = 424.478
Iteration 13: Best Cost = 424.478
Iteration 14: Best Cost = 410.1005
Iteration 15: Best Cost = 410.1005
Iteration 16: Best Cost = 410.1005
Iteration 17: Best Cost = 410.1005
Iteration 18: Best Cost = 410.1005
Iteration 19: Best Cost = 410.1005
Iteration 20: Best Cost = 410.1005

Code Aplikasi.m:

model=CreateModel();
CostFunction=@(tour) TourLength(tour,model);

nVar=model.n;
MaxIt=20;      % Maximum Number of Iterations
nAnt=40;        % Number of Ants (Population Size)
Q=1;
tau0=10*Q/(nVar*mean(model.D(:))); % Initial Phromone

alpha=1;        % Phromone Exponential Weight
beta=1;         % Heuristic Exponential Weight

rho=0.05;       % Evaporation Rate

eta=1./model.D;             % Heuristic Information Matrix
tau=tau0*ones(nVar,nVar);   % Phromone Matrix
BestCost=zeros(MaxIt,1);    % Array to Hold Best Cost Values

empty_ant.Tour=[];empty_ant.Cost=[];

ant=repmat(empty_ant,nAnt,1);
BestSol.Cost=inf;

for it=1:MaxIt 
    for k=1:nAnt 
        ant(k).Tour=randi([1 nVar]);
     
        for l=2:nVar
            i=ant(k).Tour(end);
            P=tau(i,:).^alpha.*eta(i,:).^beta;
            P(ant(k).Tour)=0;
            P=P/sum(P);
            j=RouletteWheelSelection(P);
            ant(k).Tour=[ant(k).Tour j];   
        end
        ant(k).Cost=CostFunction(ant(k).Tour);
        if ant(k).Cost<BestSol.Cost
            BestSol=ant(k);
        end
     
    end
 
    % Update Phromones
    for k=1:nAnt
        tour=ant(k).Tour;
        tour=[tour tour(1)];
        for l=1:nVar
            i=tour(l);
            j=tour(l+1);
            tau(i,j)=tau(i,j)+Q/ant(k).Cost;
        end
    end
 
 
    tau=(1-rho)*tau;
    % Store Best Cost
    BestCost(it)=BestSol.Cost;
 
    % Show Iteration Information
    disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
 
    % Plot Solution
    figure(1);
    PlotSolution(BestSol.Tour,model);
    pause(2);%0.01
 
end

%% Results
figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;

++++++++++++++++++++++++

function model=CreateModel()

    x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 80 14 42 92 80 96];

    

    y=[66 3 85 94 68 76 75 39 66 17 71 3 27 4 9 83 70 32 95 3];

    

    n=numel(x);

    

    D=zeros(n,n);

    

    for i=1:n-1

        for j=i+1:n

            

            D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);

            

            D(j,i)=D(i,j);

            

        end

    end

    

    model.n=n;

    model.x=x;

    model.y=y;

    model.D=D;

end

++++++++++++++++++++++++++++++++++++

function L=TourLength(tour,model)

    n=numel(tour);

    tour=[tour tour(1)];

    

    L=0;

    for i=1:n

        L=L+model.D(tour(i),tour(i+1));

    end

end

++++++++++++++++++++++++++++++++++++++

function j=RouletteWheelSelection(P)

    r=rand;

    

    C=cumsum(P);

    

    j=find(r<=C,1,'first');

end

++++++++++++++++++++++++++++++++++++++

function PlotSolution(tour,model)

    tour=[tour tour(1)];

    

    plot(model.x(tour),model.y(tour),'k-o',...

        'MarkerSize',10,...

        'MarkerFaceColor','y',...

        'LineWidth',1.5);

    

    xlabel('x');

    ylabel('y');

    

    axis equal;

    grid on;

    

alpha = 0.1;

    xmin = min(model.x);

    xmax = max(model.x);

    dx = xmax - xmin;

    xmin = floor((xmin - alpha*dx)/10)*10;

    xmax = ceil((xmax + alpha*dx)/10)*10;

    xlim([xmin xmax]);

    

    ymin = min(model.y);

    ymax = max(model.y);

    dy = ymax - ymin;

    ymin = floor((ymin - alpha*dy)/10)*10;

    ymax = ceil((ymax + alpha*dy)/10)*10;

    ylim([ymin ymax]);

    

    

end

++++++++++++++++++++++++++++++++++++++++

GB Phromone 

+++++++++++++++++++++++++++++++++++++++++++++++++++

GB BestRute

+++++++++++++++++++++++++++++++++++++++++++++++++++