Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования
Факультет физико-математический

Кафедра математического моделирования


Курсовая работа

          Применение муравьиных алгоритмов

            при решении задач оптимизации
2009г.


Содержание          Введение..................................................................................................................3

Глава 1. Муравьиные алгоритмы.

1. Биологические принципы поведения муравьиной колонии.................5

2. Истории создания муравьиных алгоритмов...........................................7

3. Концепция муравьиных алгоритмов.................................. …………....9

4. Обобщённый алгоритм............................................... ...........................11

5. Этапы решения задачи при помощи муравьиных алгоритмов...........13

6. Достоинства и недостатки муравьиных алгоритмов...........................14

6.1. Достоинства:.........................................................................................14

6.2. Недостатки:...........................................................................................14

Глава 2. Применение муравьиных алгоритмов при решении задач оптимизации.

1.1. Применение муравьиных алгоритмов для задачи

коммивояжёра..............................................................................................16

1.2. Муравьиный алгоритм для задачи коммивояжёра в псевдокоде..............................................................................................................25

     2.1.  Задача оптимального распределения файлов      в    компьютерной сети……………………………………………………………………….…...28

2.2  Муравьиный алгоритм для задачи распределения файлов

в компьютерной сети  в псевдокоде…………………………..…………29

Заключение………………...................................................................................32

Список использованной литературы...................................................................33

Приложение……………………………………………………………………....35

         Введение

Актуальность работы. В последние годы интенсивно разрабатывается научное направление с названием «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных  механизмов принятия решений. Эти механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении нескольких миллионов лет.

Среди так называемых “Soft computing techniques”, разработанных за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся

• Генетические алгоритмы  - основываются на естественном отборе и генетике.

• Муравьиные алгоритмы (Ant Colony Optimization – ACO, Ant Systems – AS) –моделируют поведение муравейника.

Цель работы.  Изучение работы муравьиных алгоритмов, решение задач оптимизации с помощью данного алгоритма и реализация его с помощью языка программирования Delphi.   

          Задачи работы.

·       Изучить теоретические основы  муравьиных алгоритмов.

·        Описать решение муравьиными алгоритмами задач оптимизации.

·        Проанализировать применения муравьиных алгоритмов.

Практическая ценность. В ходе выполнения дипломной работы был создан программный продукт реализации муравьиного алгоритма, который  

 

      можно успешно применять в различных областях для решения сложных задач оптимизации.

       Новизна работы. Задачи выбора оптимальных решений составляют в настоящее время   обширную область актуальных практических и теоретических приложений. В работе излагаются результаты исследования возможности применения одного из  таких  алгоритмов – алгоритм моделирования    поведения муравьиных колоний для решения задач оптимизации.

Содержание работы.

     Дипломная работа состоит из введения, двух глав, заключения,

списка литературы и приложений.

В первой главе рассмотрены биологические принципы поведения муравьиной колонии, история создания, концепция и принцип работы муравьиных алгоритмов.

Во второй главе  решены задачи оптимизации (задача коммивояжера и задача оптимального распределения файлов в компьютерной сети) с помощью муравьиных алгоритмов. Приведен сравнительный анализ  результатов  решения задачи коммивояжера с помощью муравьиного и генетических алгоритмов.

В приложении приведены листинги программ реализации задач оптимизации на языке программирования Delphi. 

2.Листинг программы  решения задачи распределения файлов в компьютерной сети в среде
Delphi
.

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids;
type

  TForm1 = class(TForm)

    Button1: TButton;

    Memo1: TMemo;

    StringGrid1: TStringGrid;

    Label1: TLabel;

    Memo2: TMemo;

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;
var

  Form1: TForm1;
implementation
{$R *.dfm}

 label metka;

const m=5;

const n=3;
var t,i,k,j,number:integer;

    pk,gk:string;

    log,log1:boolean;

    q,g,d,c_f,rec,sx,ps,ro,s,stay:real;

    x,xrez,f:array[1..m,1..n] of integer;

    p:array[1..m,1..n] of real;

    fhelp,tay,b:array[1..n] of real;

    v:array[1..n] of integer;

 procedure TForm1.Button1Click(Sender: TObject);

begin
randomize;

t:=1; d:=100;

rec:=0.001;

ro:=0.01;

for j:=1 to n do begin

tay[j]:=0.01;

b[j]:=random(150);end;

{b[1]:=1000;b[2]:=1;b[3]:=1;}

for i:=1 to m do

for j:=1 to n do  begin

f[i,j]:=random(10);

x[i,j]:=0;end;
for i:=1 to m do v[i]:=random(40)+1;

for j:=1 to n do begin

fhelp[j]:=0;

for i:=1 to m do

fhelp[j]:=fhelp[j]+f[i,j];end;

{-----------------methods begin--------------------------}

while (t<50) do

 begin

 for i:=1 to m do

 for j:=1 to n do

 x[i,j]:=0;

 memo1.lines.add('t='+inttostr(t));{readln;}  
  {---------razmeshenie faila--------------}

  memo1.Clear;

  for i:=1 to m do

  begin

   s:=0;

   for j:=1 to n do

   s:=s+fhelp[j]*tay[j];

   ps:=0;

   for j:=1 to n do

    begin

     p[i,j]:=(tay[j]*fhelp[j])/(s);

     str(p[i,j]:3:3,pk);

     memo1.lines.add(pk);     

     ps:=ps+p[i,j]*100;

    end;

   {generation g}

   log:=false;

   while (log=false) do begin

   g:=(random(99)+1);

   memo1.lines.add('g='+floattostr(g));  

   number:=0;

   q:=p[i,1]*100;  {writeln('qb',q:4:2);}

   if (g>0)and(g<q) then begin number:=1;log:=true;end;

   for j:=1 to n-1 do

   begin

    if (g>q)and(g<(p[i,j+1]*100+q)) then

      begin

         number:=j+1;log:=true;

     end;

    q:=q+p[i,j+1]*100;

    {writeln('q=',q:4:2);}

   end;

   x[i,number]:=1;

   log1:=true;

   for j:=1 to n do

   begin

    sx:=0;

    for k:=1 to m do sx:=sx+v[k]*x[k,j];

    if (sx>b[j]) then log1:=false;

   end;

   if (log1=false) then

   begin log:=false; x[i,number]:=0;end;

memo1.lines.add('num='+inttostr(number));    /////////////////

   {readln;}

   end;{-------------end generation g----------}

   //writeln('-------------');

   x[i,number]:=1;

   tay[number]:=(1-ro)*tay[number]+tay[number]/d;

   stay:=0;

   for j:=1 to n do stay:=stay+tay[j];

   for j:=1 to n do tay[j]:=(1-ro)*tay[j]+stay/d;

 end;{---------------end i----------------------}
 c_f:=0;

 for k:=1 to m do

 for j:=1 to n do

 c_f:=c_f+(f[k,j]*v[k]*x[k,j]);

 if c_f>rec then begin

 for k:=1 to m do

 for j:=1 to n do

 xrez[k,j]:=x[k,j];

 rec:=c_f;end;

 memo1.lines.add('c_f='+floattostr(c_f));

 t:=t+1;

 end;

  stringgrid1.ColCount:=n+1;

  stringgrid1.RowCount:=m+1;

for i:=1 to m do    begin

 for j:=1 to n do

 form1.StringGrid1.Cells[j,i]:=floattostr(xrez[j,i])

 //memo1.lines.add(floattostr(xrez[i,j]));

 end;

 memo2.lines.add('-----------------ves faila---------------------');

 for i:=1 to m do

 //i:=1;

 memo2.lines.add('ves ' + inttostr(i) + ' faila='+floattostr(v[i]));

 memo2.lines.add('------------------ves yzla---------------------');

 for j:=1 to n do

 //j:=1;

memo2.Lines.Add('ves ' + inttostr(j) + ' yzla=' + floattostr(b[j]));

   memo2.lines.add ('c_f='+floattostr(rec));

end;

end.