Ant system initial parameters distribution

Abstract

The paper presents some preliminary results on distributing initial parameter values among ants in Ant System. Two cases are studied, one with uniform distribution of heuristic information sensitivity values among ants and other with Gaussian distribution. Experimental analysis is performed by comparing behavior of Ant System with possible parameter values from the range to distributed parameter values solving Traveling Salesman Problem. Minimum mean error found, number of optimal solutions found and convergence speed are used as main indicators of Ant System performance evaluation. Uniform distribution proved to have minimum mean error difference from optimal value not more than 2 % with similar convergence speed. Number of optimal solutions found is from 2 to 5 times worse than in case of optimal parameter value due to small number of ants with parameter set close to optimal. Distribution of initial parameter values proved to be competitive when system complexity increase is not possible and initial values are not known.

Straipsnyje pateikiami pirminiai pradinių parametrų verčių paskirstymo skruzdėms skruzdžių sistemoje rezultatai. Analizuojami du parametrų paskirstymo atvejai: vienas tolydaus skirstinio, kitas – Gausso. Eksperimentiniu tyrimu sprendžiama keliaujančio prekeivio užduotis, lyginant skruzdžių sistemos elgseną esant skirtingoms parametrų vertėms iš intervalo ir skruzdėms paskirstytoms vertėms. Minimali vidutinė klaida, surastų optimalių sprendinių skaičius ir konvergavimo greitis naudojami kaip skruzdžių sistemos našumo indikatoriai. Tolydus parametro verčių paskirstymas leido pasiekti minimalią vidutinę klaidą, kai skirtumas ne daugiau kaip 2 % nuo optimalios parametro vertės esant panašiam konvergavimo greičiui. Rastų optimalių sprendinių skaičius nuo 2 iki 5 kartų mažesnis nei esant optimaliai parametro vertei, nes, esant paskirstytoms parametro vertėms tik nedidelis skaičius skruzdžių turi parametrų rinkinį, artimą optimaliam. Paskirstyti pradinio parametro vertes tikslinga, kai neįmanoma didinti sistemos sudėtingumo ir pradinės parametrų vertės nėra žinomos.