Scribd
Upload
4 views2 pages

BASE Algorithm

The document outlines an algorithm for an ant colony optimization process, detailing the initialization phase where ants are assigned starting cities and the sets of unvisited cities. It describes the tour-building phase where ants select their next cities and update pheromone levels, followed by a global update phase that computes tour lengths and updates pheromone based on the best tour found. The process continues until a specified end condition is met, at which point the shortest tour length is printed.

Uploaded by

yasseralhusain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
4 views2 pages

BASE Algorithm

The document outlines an algorithm for an ant colony optimization process, detailing the initialization phase where ants are assigned starting cities and the sets of unvisited cities. It describes the tour-building phase where ants select their next cities and update pheromone levels, followed by a global update phase that computes tour lengths and updates pheromone based on the best tour found. The process continues until a specified end condition is met, at which point the shortest tour length is printed.

Uploaded by

yasseralhusain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1- //initialization phase [4-6]

For each pair(r,s) τ (r,s)= τₒ end_for (τₒ=1/n*lrs )


For k=1 to m //(m: No. of ant)
Let rk1 be the starting city for ant k
Jk (rk1) = {1,……………,n} – rk1
//Jk(rk1) is the set of yet to be visited cities for ant k in city rk1
rk = rk1 //rk is the city where ant k is located
End_for

2-// this is the phase in wich ants bulid their tours the tour of ant k is stored in tour k
For i=1 to n
If i<n
Then
For k=1 to m
Choose the next city sk according to (2) and (1)
Jk(sk) = Jk(rk) – sk
Tourk(i) = (rk , sk)
End_for
Else
For k=1 to m
// in this cycle all ants go back to thr initial city rk1
Sk=rk1
Tourk(i) = (rk , sk)
End_for
End_if
// in this step local updating occurs and pheromone is update using
For k =1 to m
τ (rk , sk) =(1-p) τ (rk, sk) + p τₒ
rs = sk //new city for ant k
End_for
End_for
3-// in this phase global update accurs and pheromone is update
For k=1 to m
Compute lk // lk the length of tour of tour done by ant k
End_for

Compute l best
//update edges belonging to lbest
For each edge(r,s)
τ (rk,sk)= (1- α) τ (rk,sk)+ α * 1/ (lbest)
End_for

4- if (End_condition = true)
Then print shortest of lk
Else goto 2

(2)

Where qₒ =0.9 , β=2 , α=p=0.1 , τₒ=1/n*lrs , n No. of city


M(No. of ants)=10

You might also like