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
- Оптимизация на колонията на мравки (това)