rlog58
commented
1 year ago Промежуточно. По некоторому seed был построен случайный граф (100 вершин, 1265 ребер). Делалось 10 запусков на каждом из фреймворков. Точки на графике одного цвета отображают наборы парето-фронтов к некоторому времени. У меня это было (0мин, 1мин, ..., 6 мин). На первом графике в задаче неизвестно число вершин, на втором число вершин зафиксировано. Цветовую гамму поправлю, сделаю градиентной, а не набором цветов. Мои промежуточные выводы такие:
- На графах мелкой размерности (до 20 вершин) сравнивать неинтересно, оба фреймворка, как правило, у меня находят оптимум за 1-2 минуты.
- Пока у фреймворков не заметна сильная деградация глобального поиска (позапускаю ещё часовые запуски), т.е некоторое улучшение со временем всё же есть
- У голема нет нужного набора операторов, как я понял, для поиска графа фиксированной размерности. В основном мутации связаны с изменением числа вершин. Поэтому на втором графике видим, что поиска толком-то и нет.
- Если же разрешить использование операторов изменения числа вершин, то голем в среднем быстрее сходится. Это я могу объяснить тем, что все мутации имеют смысловую интерпретацию (добавление вершины, изменение поддерева, и т.д.). В то время как у pymoo из коробки только базовые мутации и они не отображают смысловые действия над графом.
Сейчас я планирую добавить в голем мутацию удаления ребра, а также произвести часовые запуски фреймворков, чтобы была видна сходимость к оптимуму. Боксплоты допиливаю
maypink
Possible synthetic task for comparison is evolving graphs to match target graphs by some distance metric, like edit distance of adjacency matrix. In DEAP/pymoo this can be implemented as evolution of graph matrices.
Compare results:
Having this comparison, we could understand where we're better or worse in simple tasks and where GOLEM can be improved. If the results are positive, they could be used in papers.
Implementation of graph search in GOLEM is in this file