Оптимизация на колонията на мравки с пример за Java

Програмиране

1. Въведение

Целта на тази поредица е да обясни идеята за генетичните алгоритми и да покаже най-известните реализации .

В този урок ще опишем концепцията за оптимизация на колонията мравки (ACO), последвана от примера на кода.

2. Как работи ACO

ACO е генетичен алгоритъм, вдъхновен от естественото поведение на мравка. За да разберем напълно алгоритъма ACO, трябва да се запознаем с основните му понятия:

  • мравките използват феромони, за да намерят най-краткия път между дома и източника на храна
  • феромоните се изпаряват бързо
  • мравките предпочитат да използват по-къси пътища с по-плътен феромон

Нека покажем прост пример за ACO, използван в Проблема на пътуващия продавач. В следващия случай трябва да намерим най-краткия път между всички възли в графиката:

Следвайки естествено поведение, мравките ще започнат да изследват нови пътища по време на изследването. По-синият син цвят показва пътищата, които се използват по-често от останалите, докато зеленият цвят показва текущия най-кратък път, който е намерен:

В резултат на това ще постигнем най-краткия път между всички възли:

Хубавият GUI-базиран инструмент за тестване на ACO можете да намерите тук.

3. Внедряване на Java

3.1. ACO параметри

Нека обсъдим основните параметри за алгоритъма ACO, декларирани в класа AntColonyOptimization :

private double c = 1.0; private double alpha = 1; private double beta = 5; private double evaporation = 0.5; private double Q = 500; private double antFactor = 0.8; private double randomFactor = 0.01;

Параметър c показва първоначалния брой пътеки в началото на симулацията. Освен това алфата контролира важността на феромоните, докато бета контролира приоритета на разстоянието. Като цяло бета параметърът трябва да е по-голям от алфа за най-добри резултати.

След това променливата на изпарение показва процента колко феромонът се изпарява при всяка итерация, докато Q предоставя информация за общото количество феромон, оставено на пътеката от всяка мравка , а antFactor ни казва колко мравки ще използваме на град.

И накрая, трябва да имаме малко случайност в нашите симулации и това се покрива от randomFactor .

3.2. Създайте мравки

Всеки мравка ще може да посети определен град, да запомни всички посетени градове и да следи дължината на пътеката:

public void visitCity(int currentIndex, int city) { trail[currentIndex + 1] = city; visited[city] = true; } public boolean visited(int i) { return visited[i]; } public double trailLength(double graph[][]) { double length = graph[trail[trailSize - 1]][trail[0]]; for (int i = 0; i < trailSize - 1; i++) { length += graph[trail[i]][trail[i + 1]]; } return length; }

3.3. Настройка мравки

В самото начало трябва да инициализираме изпълнението на ACO кода, като предоставим матрици на пътеки и мравки:

graph = generateRandomMatrix(noOfCities); numberOfCities = graph.length; numberOfAnts = (int) (numberOfCities * antFactor); trails = new double[numberOfCities][numberOfCities]; probabilities = new double[numberOfCities]; ants = new Ant[numberOfAnts]; IntStream.range(0, numberOfAnts).forEach(i -> ants.add(new Ant(numberOfCities)));

След това трябва да настроим матрицата на мравките , за да започне с произволен град:

public void setupAnts() { IntStream.range(0, numberOfAnts) .forEach(i -> { ants.forEach(ant -> { ant.clear(); ant.visitCity(-1, random.nextInt(numberOfCities)); }); }); currentIndex = 0; }

За всяка итерация на цикъла ще изпълняваме следните операции:

IntStream.range(0, maxIterations).forEach(i -> { moveAnts(); updateTrails(); updateBest(); });

3.4. Премести мравки

Нека започнем с метода moveAnts () . Трябва да изберем следващия град за всички мравки, като помним, че всяка мравка се опитва да следва пътеките на други мравки:

public void moveAnts() { IntStream.range(currentIndex, numberOfCities - 1).forEach(i -> { ants.forEach(ant -> { ant.visitCity(currentIndex, selectNextCity(ant)); }); currentIndex++; }); }

Най-важната част е да изберете правилно следващия град за посещение. Трябва да изберем следващия град въз основа на вероятностната логика. Първо, можем да проверим дали Ant трябва да посети произволен град:

int t = random.nextInt(numberOfCities - currentIndex); if (random.nextDouble()  i == t && !ant.visited(i)) .findFirst(); if (cityIndex.isPresent()) { return cityIndex.getAsInt(); } }

Ако не сме избрали произволен град, трябва да изчислим вероятностите за избор на следващия град, като си спомним, че мравките предпочитат да следват по-силни и по-кратки пътеки. Можем да направим това, като съхраним вероятността за преместване във всеки град в масива:

public void calculateProbabilities(Ant ant) { int i = ant.trail[currentIndex]; double pheromone = 0.0; for (int l = 0; l < numberOfCities; l++) { if (!ant.visited(l)){ pheromone += Math.pow(trails[i][l], alpha) * Math.pow(1.0 / graph[i][l], beta); } } for (int j = 0; j < numberOfCities; j++) { if (ant.visited(j)) { probabilities[j] = 0.0; } else { double numerator = Math.pow(trails[i][j], alpha) * Math.pow(1.0 / graph[i][j], beta); probabilities[j] = numerator / pheromone; } } }

След като изчислим вероятностите, можем да решим до кой град да отидем, като използваме:

double r = random.nextDouble(); double total = 0; for (int i = 0; i = r) { return i; } }

3.5. Актуализиране на пътеки

В тази стъпка трябва да актуализираме пътеките и левия феромон:

public void updateTrails() { for (int i = 0; i < numberOfCities; i++) { for (int j = 0; j < numberOfCities; j++) { trails[i][j] *= evaporation; } } for (Ant a : ants) { double contribution = Q / a.trailLength(graph); for (int i = 0; i < numberOfCities - 1; i++) { trails[a.trail[i]][a.trail[i + 1]] += contribution; } trails[a.trail[numberOfCities - 1]][a.trail[0]] += contribution; } }

3.6. Актуализирайте най-доброто решение

Това е последната стъпка от всяка итерация. Трябва да актуализираме най-доброто решение, за да запазим препратката към него:

private void updateBest() { if (bestTourOrder == null) { bestTourOrder = ants[0].trail; bestTourLength = ants[0].trailLength(graph); } for (Ant a : ants) { if (a.trailLength(graph) < bestTourLength) { bestTourLength = a.trailLength(graph); bestTourOrder = a.trail.clone(); } } }

След всички повторения крайният резултат ще посочи най-добрия път, намерен от ACO. Моля, обърнете внимание, че с увеличаване на броя на градовете вероятността за намиране на най-краткия път намалява.

4. Заключение

Този урок представя алгоритъма за оптимизация на колонията на мравки . Можете да научите за генетичните алгоритми без каквито и да било предварителни познания в тази област, като имате само основни умения за компютърно програмиране.

Пълният изходен код за кодовите фрагменти в този урок е достъпен в проекта GitHub.

За всички статии от поредицата, включително други примери за генетични алгоритми, разгледайте следните връзки:

  • Как да проектирам генетичен алгоритъм в Java
  • Проблемът с пътуващия продавач в Java
  • Оптимизация на колонията на мравки (това)