rhgrant10 / acopy Goto Github PK
View Code? Open in Web Editor NEWA Python implementation of the Ant Colony Optimization Meta-Heuristic
Home Page: https://acopy.readthedocs.io
License: Other
A Python implementation of the Ant Colony Optimization Meta-Heuristic
Home Page: https://acopy.readthedocs.io
License: Other
There is no setter/getter for t0
Was trying to run the acopy solver for fully connected graphs and it works fine but throws a key error whenever the graph is not fully connected.
It doesn't make sense for the pheromone laid down by elite ants (in _trace_elite
) to be done long after the main pheromone update (in _update_scent
). Probably _update_scent
should call _trace_elite
.
Sometimes I want the solver to return the best path from each iteration (local best) but other times I want the solver to simply return the best path from all iterations (global best). Can this be made into an option?
Also, it would be handy if the solver only yielded better and better solutions.
I think the methods attractiveness
and trail_level
should be renamed to something more generic. priori
and posteriori
would work well in my opinion. These are better descriptions of what the ant is trying to do in general, independent of the implementation, and therefore will work better for users trying to subclass Ant
.
I'd like to keep the code as tidy as possible. Please keep lines under 80 chars (<=79).
There is not a single @property
that has a docstring. Fix this soon.
import acopy
import networkx as nx
g = nx.Graph()
g.add_edge(0, 1, weight = 2)
g.add_edge(1, 2, weight = 2)
g.add_edge(2, 3, weight = 2)
g.add_edge(3, 0, weight = 2)
g.add_edge(0, 2, weight = 1)
g.add_edge(1, 3, weight = 1)
solver = acopy.Solver(rho=.03, q=1)
colony = acopy.Colony(alpha=1, beta=3)
tour = solver.solve(g, colony, limit=100)
ValueError: The truth value of a DataFrame is ambiguous. Use a.empty, a.bool(), a.item(), a.any() or a.all().
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/workspaces/optimisation_shortest_path/notebooks/Clusterization.ipynb in
2 colony = acopy.Colony(alpha=1, beta=3)
3
----> 4 tour = solver.solve(tmp_g, colony, limit=100)
/usr/local/lib/python3.7/site-packages/acopy/solvers.py in solve(self, *args, **kwargs)
/usr/local/lib/python3.7/site-packages/acopy/solvers.py in optimize(self, graph, colony, gen_size, limit)
/usr/local/lib/python3.7/site-packages/acopy/solvers.py in find_solutions(self, graph, ants)
/usr/local/lib/python3.7/site-packages/acopy/solvers.py in (.0)
/usr/local/lib/python3.7/site-packages/acopy/ant.py in tour(self, graph)
/usr/local/lib/python3.7/site-packages/acopy/ant.py in choose_destination(self, graph, current, unvisited)
/usr/local/lib/python3.7/site-packages/acopy/ant.py in get_scores(self, graph, current, destinations)
/usr/local/lib/python3.7/site-packages/acopy/ant.py in score_edge(self, edge)
/usr/local/lib/python3.7/site-packages/pandas/core/generic.py in __nonzero__(self)
1477 def __nonzero__(self):
1478 raise ValueError(
-> 1479 f"The truth value of a {type(self).__name__} is ambiguous. "
1480 "Use a.empty, a.bool(), a.item(), a.any() or a.all()."
1481 )
ValueError: The truth value of a DataFrame is ambiguous. Use a.empty, a.bool(), a.item(), a.any() or a.all().
I want to be able to use my csv files with pants. Pipes, file paths on the command line, etc.etc. You know the drill. I hate writing boilerplate code :-(
Would you please consider bumping the version of click to the 8th major version?
Line 15 in ff074ae
I have tested the following configuration in a vritual environment:
'click~=8.0'
Tests ran fine.
I want to be able to create the world from an existing distance matrix. The problem with accepting only a list of coordinates is that it makes the assumption that ants can reach each coordinate from every other coordinate, but sometimes I'd like to restrict that assumption.
Your code is pretty clean but that main method at the bottom is a right mess! Clean that up man!
Some of the variables are specified differently in different places. For example, the World
constructor takes arguments a
and b
, but the properties that hold those values have names alpha
and beta
. This potential confusion hurts readability and therefore maintainability.
Currently, there are no unit tests. Although there is some test data, it is simply a global variable. It needs to be placed in its own module with a battery of unit tests.
There are many use cases when starting node is fixed. The city to start the visiting is already given and according to that the route needs to be defined. Can this use case be solved with ACO using this library?
#enhancement
I would like to use pants as a shell script by pointing it to a list of coordinates or some kind of file that describes a world. rho
, Q
, t0
, alpha
, beta
, niters
, and ant_count
should be implemented as command line options.
uname -a
: Linux AquaRing 4.19.44 #1-NixOS SMP Thu May 16 17:41:32 UTC 2019 x86_64 GNU/Linux
I was trying to run a solver over a noncomplete graph. I expected this to work, but it didn't.
Alternatively, I would expect it to say loud and clear in the docs that this only works on complete graphs.
Minimal failing example:
import acopy
import networkx as nx
import random
random.seed(0)
G = nx.cycle_graph(4)
for edge in G.edges:
G.edges[edge]['weight'] = 1
solver = acopy.Solver()
colony = acopy.Colony()
tour = solver.solve(G, colony, limit=100)
Traceback:
Traceback (most recent call last):
File "Untitled-1.py", line 15, in <module>
tour = solver.solve(G, colony, limit=100)
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 193, in solve
for solution in self.optimize(*args, **kwargs):
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 225, in optimize
solutions = self.find_solutions(state.graph, state.ants)
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 259, in find_solutions
return [ant.tour(graph) for ant in ants]
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 259, in <listcomp>
return [ant.tour(graph) for ant in ants]
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/ant.py", line 58, in tour
solution.add_node(node)
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 75, in add_node
self._add_node(node)
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/acopy/solvers.py", line 83, in _add_node
data = self.graph.edges[edge]
File "/nix/store/9yfdaw94lxrygpqqph8ry0vv2zd5dvqg-python3-3.7.3-env/lib/python3.7/site-packages/networkx/classes/reportviews.py", line 930, in __getitem__
return self._adjdict[u][v]
KeyError: 2
(Sorry for the mangled paths, that's NixOS for ya)
I like that you implemented an elite ant system, but it's rather rigid. I want to be able to choose whether the local best or global best solution is traced by the elite ants, as well as specify a particular number of them.
It seems to me that for a world with N
coordinates, each ant will always move N
times. Thus they will all finish at the same time.
When I clone an ant, it still has the same UID as the one from which I cloned it.
Now, acopy's ant can move on the complete graph certainly.
If the graph is a little sparse,
ant.py
def tour(self, graph):
"""Find a solution to the given graph.
:param graph: the graph to solve
:type graph: :class:`networkx.Graph`
:return: one solution
:rtype: :class:`~acopy.solvers.Solution`
"""
solution = self.initialize_solution(graph)
unvisited = self.get_unvisited_nodes(graph, solution)
while unvisited:
node = self.choose_destination(graph, solution.current, unvisited)
solution.add_node(node)
unvisited.remove(node)
solution.close()
return solution
solution doesn't have all vertexes, because current node's adjacent nodes will be involved only.
And, If this process run, we try to get a edge which doesn't exist.
def tour(self, graph):
"""Find a solution to the given graph.
:param graph: the graph to solve
:type graph: :class:`networkx.Graph`
:return: one solution
:rtype: :class:`~acopy.solvers.Solution`
"""
V = len(graph)
solution = None
while True:
try:
solution = self.initialize_solution(graph)
while len(solution.nodes) < V:
unvisited_nodes = self.get_unvisited_nodes(graph, solution)
node = self.choose_destination(graph, solution.current, unvisited_nodes)
solution.add_node(node)
solution.close()
break
except IndexError as e:
print(e)
continue
except Exception as e:
print(e)
continue
return solution
Above code is so ugly and not beautiful, but can handle the sparse graph.
Would you plan to create functions for sparse graphs, like above code(above code is not good...)?
Sorry, for bad english.
Thank you.
There is no implementation of __copy__
or __deepcopy__
for Ants
and Worlds
.
Currently (or as an isolated problem on my system), installing the package with pip does not also install the utils folder, which is required for the package to properly function.
My makeshift fix was simply moving the utils folder from this project into the site-packages folder where the package was stored. So far, this has solved/suppressed all errors, so it seems like the imported package is simply missing utils.
If the problem is unsolvable/unimportant/known, then this issue can be closed immediately, but I just wanted to bring it up in case it inconvenienced anyone.
In terminal:
pip install acopy
In the python interpreter:
>>> import acopy
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/local/lib/python3.7/site-packages/acopy/__init__.py", line 2, in <module>
from .ant import Ant # noqa: F401
File "/usr/local/lib/python3.7/site-packages/acopy/ant.py", line 7, in <module>
from . import utils
ImportError: cannot import name 'utils' from 'acopy' (/usr/local/lib/python3.7/site-packages/acopy/__init__.py)
Moving acopy/utils
from this repository into /usr/local/lib/python3.7/site-packages/acopy
causes the above to give no error.
Hello.
I try to use acopy in the graph which was made by networkx.
For example
import acopy
import tsplib95
import networkx as nx
import random
import matplotlib.pyplot as plt
solver = acopy.Solver(rho=.03, q=1)
colony = acopy.Colony(alpha=1, beta=3)
// try to use graph made by networkx
G = nx.fast_gnp_random_graph(10, 0.9)
for (u, v) in G.edges():
G.edges[u, v]['weight'] = random.randint(1, 1000)
tour = solver.solve(G, colony, limit=100)
nx.draw_networkx(G)
plt.show()
print(tour.cost)
print(tour.path)
But when I run this code, the error occured below.
Traceback (most recent call last):
File "/Users/students/Desktop/keras_aco/main.py", line 15, in <module>
tour = solver.solve(G, colony, limit=100)
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/solvers.py", line 193, in solve
for solution in self.optimize(*args, **kwargs):
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/solvers.py", line 225, in optimize
solutions = self.find_solutions(state.graph, state.ants)
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/solvers.py", line 259, in find_solutions
return [ant.tour(graph) for ant in ants]
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/solvers.py", line 259, in <listcomp>
return [ant.tour(graph) for ant in ants]
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/ant.py", line 57, in tour
node = self.choose_destination(graph, solution.current, unvisited)
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/ant.py", line 110, in choose_destination
scores = self.get_scores(graph, current, unvisited)
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/acopy/ant.py", line 125, in get_scores
edge = graph.edges[current, node]
File "/Users/students/.pyenv/versions/keras_aco_env/lib/python3.6/site-packages/networkx/classes/reportviews.py", line 930, in __getitem__
return self._adjdict[u][v]
KeyError: 0
I think that acopy's ant tried to use the edge which doesn't exists.
So, error occured.
Can acopy deal with the network which isn't a complete graph?
And, Can I change the code
if Ant can't make a Hamiltonian path , then Ant trys to make a Hamiltonian path again.
Thank you, and sorry for bad english.
I tried to run the algorithm on a larger tsp graph like att532.tsp
but the algorithm diverge from the solution and is really slow.
acopy solve att532.tsp --formt tsplib95 --limit 50
How should I configure the parameter rho
, q
, alpha
and beta
foe better adaptation to the graph ? And make it faster ?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.