C best ,vớ i best hoặc là độ dài của hành trình tốt nhất tại vòng lặp hiện tại, hoặc là độ dài của hành trình tốt nhất từ khi bắt đầu tìm kiếm MMAS sẽ thực hiện cập nhật luân phiên
double[] over =new double[numCities];
3.2.4. Biểu diễn thông tin kiến
Ban đầu, một con kiến khởi tạo ngẫu nhiên một hành trình và để lại một lượng vệt mùi Δτ trên các cạnh nó đã đi qua. Làm được điều này, một con kiến phải có khả năng: (1) lưu hành trình nó đã đi qua, (2) xác định thành phố tiếp theo để đi tại mỗi thành phố, (3) tính toán và lưu giá trị của các giải pháp mà nó tìm ra.
(1) Lưu hành trình nó đã đi qua
Mảng của mảng ants được sử dụng để lưu hành trình của mỗi kiến. Hành trình này bao gồm tất cả các thành phố, đi qua mỗi thành phố một lần.
int[][] ants
Trong đó, chỉ số hàng i là số thứ tự của kiến thứ i (với i=0…số kiến-1), chỉ số cột j là số thứ tự của thành phố thứ j (với j=0…số thành phố-1). kiến-1), chỉ số cột j là số thứ tự của thành phố thứ j (với j=0…số thành phố-1).
Tại mỗi thành phố, một con kiến xác định thành phố kế tiếp để đi dựa vào xác suất được tính như sau:
− Xác xuất tại thành phố i =giá trị over tại thành phố i / tổng các giá trị over
tại tất cả các thành phố (chỉ xét với các thành phố kề cận với thành phố hiện tại đang xét, các thành phố đã có mặt trên con đường đang xét sẽ có xác suất là 0).
− Tổng các xác suất là 1 tức: ∑
i=0
n−1
pi=1. Các xác suất này sẽ được lưu trong một mảng một chiều probs.
− Bước tiếp theo của thuật toán là phải đưa ra quyết định thành phố nào sẽ được lựa chọn để đi tiếp dựa vào các xác suất đã tính. Thuật toán ACO được trình bày ở đây sử dụng một kỹ thuật gọi là kỹ thuật lựa chọn bánh xe xổ số. Theo đó, một mảng được đặt tên là cumulprob được tạo ra nhằm lưu xác suất tích lũy. Kích thước của mảng cumulprob này lớn hơn mảng probs
một phần tử, và phần tử ở vị trí 0 được gán giá trị là 0.0. Mỗi phần tử trong
cumulprob có giá trị bằng tổng giá trị của phần tử probs và cumulprob ở vị trí ngay trước nó. (hay cumulprob[i] = probs[i-1]+cumulprob[i-1]).
− Sau khi mảng cumulprob đã được tạo ra, một số p ngẫu nhiên từ 0.0 và 1.0 sẽ được phát ra. Giá trị p rơi vào khoảng giá trị của 2 phần tử i và j nào đó trong mảng cumulprob, thì phần tử đầu tiên của khoảng giá trị này (tức thành phố i) sẽ được chọn là thành phố kế tiếp trong hành trình đang xét. Trong quá trình xây dựng hành trình của mỗi kiến, mỗi kiến sẽ được gán cho một mảng một chiều visited có kiểu dữ liệu là kiểu logic đúng hoặc sai để hành trình tạo ra không chứa các thành phố trùng lặp và một mảng trail để lưu hành trình mà nó đã hoàn thành. Giá trị của visited[i]=true nếu thành phố i đã được thăm và
visited[i]=false nếu ngược lại.
Đặc tả cho các mảng probs, cumulprob, trail, visited như sau: