Муравьиный алгоритм (ACO) позволяет решать вычислительные задачи способом нахождения хороших путей на графе.
Решаемая задача может быть как "Задачей коммивояжера", так и "О кратчайшем пути", или путем с некими ограничениями (Constrained Shortest Path First).
Первые две задачи решены в данной библиотеке.
Существует множество стратегий и вариаций классического ACO алгоритма.
Библиотека предоставляет реализацию Классического ACO и вариант с использованием Элитных муравьев.
Библиотека гибко расширяется и позволяет вам создать свои алгоритмы из мира ACO, и решать свои задачи.
Исходные данные поступают и в виде матрицы смежности и в виде списка нод (городов, узлов, вершин) с X и Y координатами.
Работа библиотеки протестирована на наборах данных TSPLIB95, для проверки эффективности и производительности.
Кол-во муравьев, все коэффициенты и параматры, настраиваются.
Сейчас мы подготовили веб приложение , которое вы можете установить и запустить локально, чтобы поработать с этим алгоритмом. Смотрите его видео демо для детальной информации.
Решение задачи коммивояжера с помощью ACO:
Второй пример:
Выполните
composer require --prefer-dist mgrechanik/ant-colony-optimization
или добавьте
"mgrechanik/ant-colony-optimization" : "~1.0.0"
в require секцию вашего composer.json файла.
- Создание Менеджера с нужными зависимостями
Manager::__construct(DistanceInterface $distanceStrategy = null, AFinder $finder = null,
MathematicsInterface $mathematics = null, Task $task = null);- По умолчанию Поисковик будет устанавливаться в Классический ACO, а решаемая Задача - в Задачу Коммивояжера
- Загрузка данных в виде матрицы смежности
$manager->setMatrix(array $matrix, int $nameStart = 0) - $nameStart - с какого номера именовать алиас имени ноды, для их внешнего имени-алиаса
- Загрузка данных в виде списка городов
$manager->setCities(City ...$cities) - Данный список городов будет преобразован в матрицу смежности, расстояния вычислены по указанной Менеджеру стратегии.
- Если у города задано свойство name - оно станет его алиасом имени
- Изменение матрицы смежности
$manager->updateMatrix(int $y, int $x, float|int $value, bool $double = true) - Например, можем сделать некий участок непроходимым - $manager->updateMatrix(1, 0, 1000000);
- Запуск вычислительного процесса
$distance = $manager->run(int $iterations = 400) - для небольших графов, число итераций можно уменьшить.
- Вернет найденное расстояние или null если поиск не увенчался успехом
- Получение найденного пути
$path = $manager->getInnerPath() - Найденный путь из номеров нод.
Все ноды внутри именуются числами от 0 до N-1, где N - кол-во нод.
- Получение найденного пути из алиасов
$path = $manager->getNamedPath()- Найденный путь из алиасов имен нод, если вы их задавили.
use mgrechanik\aco\Manager;
$manager = new Manager();
$matrix = [
[ 0, 8, 4, 11],
[ 8, 0, 9, 5 ],
[ 4, 9, 0, 8 ],
[11, 5, 8, 0 ]
];
$manager->setMatrix($matrix);
$distance = $manager->run(20);
var_dump('Distance=' . $distance);
var_dump($manager->getInnerPath())Получим:
Distance=25
Array
(
[0] => 0
[1] => 1
[2] => 3
[3] => 2
[4] => 0
) use mgrechanik\aco\Manager;
use mgrechanik\aco\SppTask;
$task = new SppTask(0, 3);
$manager = new Manager(task : $task);
$matrix = [
[ 0 , 8, 4, 100],
[ 8 , 0, 9, 5 ],
[ 4 , 9, 0, 8 ],
[100, 5, 8, 0 ]
];
$manager->setMatrix($matrix);
$finder = $manager->getFinder();
// increase amount of ants to 6
$finder->setM(6);
$distance = $manager->run(50);
var_dump('Distance=' . $distance);
var_dump($manager->getInnerPath())Получим:
Distance=12
Array
(
[0] => 0
[1] => 2
[2] => 3
)
// for comparison, the direct path [0, 3] is closed by big distance and distance of path [0, 1, 3] is 13use mgrechanik\aco\Manager;
use mgrechanik\aco\City;
$cities = [new City(10,10), new City(50,50), new City(10,50), new City(60,10)];
$manager = new Manager();
$manager->setCities(...$cities);use mgrechanik\aco\Manager;
$matrix = [
[ 0, 8, 4, 11],
[ 8, 0, 9, 5 ],
[ 4, 9, 0, 8 ] ,
[11, 5, 8, 0 ]
];
$manager = new Manager();
$manager->setMatrix($matrix);$finder = new \mgrechanik\aco\elitist\Finder();
$manager = new Manager(finder : $finder);
//...use mgrechanik\aco\Manager;
$matrix = [
[ 0, 8, 4, 11],
[ 8, 0, 9, 5 ],
[ 4, 9, 0, 8 ] ,
[11, 5, 8, 0 ]
];
$manager = new Manager();
$finder = $manager->getFinder();
$manager->setMatrix($matrix);
$manager->run();
var_dump($finder->getHistory());При использовании данной библиотеки мы можем загрузить список городов из картинки, и результат поиска отобразить на результирующей картинке. Визуально будут картинки как на Demo.
Подробнее по подготовке картинки изучайте в описании к той библиотеке, но вкратце - на белом холсте отметьте кружочками диаметром 10 px, вершины графа, и используйте в коде ниже эту картинку.
use mgrechanik\aco\Manager;
use mgrechanik\aco\City;
try {
$imageSearcher = new \mgrechanik\imagepointssearcher\Searcher(
'./images/your_image.jpg',
);
$found = $imageSearcher->run();
if ($found > 1) {
$points = $imageSearcher->getPoints();
$cities = [];
foreach ($points as $point) {
$cities[] = new City($point['x'], $point['y']);
}
$manager = new Manager();
$manager->setCities(...$cities);
if ($res = $manager->run()) {
$innerPath = $manager->getInnerPath();
$imageResult = new \mgrechanik\imagepointssearcher\ImageResult($imageSearcher);
$imageResult->drawLabels();
$imageResult->drawMargins();
$imageResult->drawPath($innerPath);
$imageResult->save('./images/result.jpg');
}
}
} catch (Exception $e) {
//
}Основной настраиваемый обьект - Это поисковик.
Получаем его:
$manager = new Manager();
$finder = $manager->getFinder();
// Настраиваем
//$finder->set...
// ...
//$manager->run();Доступные настройки:
-
Установим величину расстояния, при которой участок между двумя узлами считается непроходимым
->setClosedPathValue(int $value) -
Установим число муравьев
->setM(int $m) -
Установим число муравьев как процент от числа нод. Используется по умолчанию (=40%)
->setMPercent(int $mPercent) -
Устанавливаем коэффициенты для формулы
->setAlpha(float $alpha);
->setBeta(float $beta);
->setP(float $p);
->setC(float $c);
->setQ(int $q);-
Установить стратегию выполнения математических задач
->setMathematics(MathematicsInterface $mathematics) -
Установить текущую выполняемую задачу. TSP, SPP или др.
->setTask(Task $task) -
Установим число элитных муравьев (для поисковика с элитными муравьями)
->setSigma(int $sigma) -
Установим число элитных муравьев как процент от числа регулярных муравьев. Используется по умолчанию (=50%) (для поисковика с элитными муравьями)
->setSigmaPercent(int $sPercent)
Прежде всего отключите XDebug или аналоги, т.к. они могут на порядок влиять на скорость работы
Данный ACO алгоритм находит хорошие пути на графе. И даже лучшие.
Для примера возьмем задачу berlin52.tsp из библиотеки TSPLIB95, где 52 узла у графа.
Решаем задачу кодом ниже:
$cities = TspLibLoader::loadCitiesFromEuc2dFile(__DIR__ . '/images/data/berlin52.tsp');
$finder = new \mgrechanik\aco\elitist\Finder();
$finder->setSigmaPercent(150);
$finder->setMPercent(30);
$finder->setAlpha(0.7);
$manager = new Manager(finder : $finder);
$manager->setCities(...$cities);
$distance = $manager->run(300);
var_dump('Distance=' . $distance);
var_dump($finder->getHistory());Получили вывод:
Distance=7542
Array ...
[85] => Array
(
[distance] => 7542
[inner_path] => 0_21_30_17_2_16_20_41_6_1_29_22_19_49_28_15_45_43_33_34_35_38_39_36_37_47_23_4_14_5_3_24_11_27_26_25_46_12_13_51_10_50_32_42_9_8_7_40_18_44_31_48_0
[iteration] => 85
[time_spent] => 1.94 sec
)
)Данный код, работая на офисном компьютере, за менее чем 2 секунды, смог найти самый лучший путь из известных.
Здесь мы использовали поисковик на основе алгоритма с использования элитных муравьев. Он на практике дает лучшие результаты, чем классический.
Алгоритм вероятностный, каждый раз муравьи будут путешествовать по другому. И очень многое зависит от кол-ва нод, муравьев, настройки всех коэффициентов и параметров, участвующих в формулах.
Библиотека TSPLIB95, содержит множество Задач коммивояжера - исходные данные и решения - лучшие рузультаты, которые были когда либо найдены для этих задач (пути и расстояния).
Библиотека ценна тем, что на ее данных можно протестировать эффективность наших алгоритмов, коэффициентов и параметров.
Библиотека предоставляет множество разных форматов исходных данных. Мы из коробки поддерживаем два из них.
Пример файла с этим форматом - berlin52.tsp . Загружаем из него список нод (городов) и передаем менеджеру:
use mgrechanik\aco\TspLibLoader;
use mgrechanik\aco\Manager;
$fileName = __DIR__ . '/berlin52.tsp';
$cities = TspLibLoader::loadCitiesFromEuc2dFile($fileName);
$manager = new Manager();
$manager->setCities(...$cities);Пример файла с этим форматом - bays29.tsp .
Загружаем из него матрицу смежности и передаем менеджеру:
use mgrechanik\aco\TspLibLoader;
use mgrechanik\aco\Manager;
$fileName = __DIR__ . '/bays29.tsp';
$matrix = TspLibLoader::loadMatrixFromExplicitMatrixFile($fileName);
$manager = new Manager();
// tsplib95 library names nodes starting with "1"
$manager->setMatrix($matrix, 1);Adjacency Matrix - Матрица смежности, задает расстояния между узлами графа. Это базовая структура, с которой начинает работать алгоритм.
Если граф представлен как Города с координатами, то эта информация сначала переводится в матрицу смежности