aco元启发式的python3实现
ACO-Pants的Python项目详细描述
蚁群优化元启发式的python3实现
概述
pants提供快速确定如何 访问互连节点的集合,以便完成的工作 最小化。节点可以是任意的数据集合,而边缘 表示在两个节点之间移动所需的“工作量”。 因此,pants是解决旅行推销员问题的工具。
世界是由一个节点列表和一个负责 返回任意两个给定节点之间的边的长度。长度 函数不需要返回实际长度。相反,“长度”指的是 从第一个节点移动到第二个节点所涉及的“工作量” 节点-不管“工作”是什么。对于一个愚蠢的,随机的例子,它可以 甚至是一个人在上下一道菜之前必须洗的菜的数量 至少站在洗碟机比赛。
通过迭代过程找到解。在每次迭代中, 有几个蚂蚁可以找到一个解决方案,可以“访问” 世界。每边信息素的量根据 所用溶液的长度。蚂蚁 最小距离被认为是局部最优解。如果当地人 解决方案与以前的任何解决方案相比都有较短的距离 迭代之后,它就成为全局最优解。精英蚂蚁 然后将它们的信息素沉积在全局最优解的路径上 为了进一步加强它,这个过程会重复。
您可以阅读有关Ant Colony Optimization on Wikipedia的更多信息。
安装
通过pip
安装$ pip3 install ACO-Pants
用法
使用pants很简单。这里的例子使用欧几里德距离 在具有(x, y)坐标的2d节点之间,但没有实数 对任何类型节点数据的要求。
导入pants(以及您需要的任何其他包)。
importpantsimportmathimportrandom
创建数据点;这些数据点成为节点。在这里我们创造了一些 随机二维点。对节点的唯一要求是 可与所有其他节点区分。
nodes=[]for_inrange(20):x=random.uniform(-10,10)y=random.uniform(-10,10)nodes.append((x,y))
定义长度函数。此函数必须接受两个节点 返回他们之间的“工作量”。在这种情况下,欧几里德 距离很好。
defeuclidean(a,b):returnmath.sqrt(pow(a[1]-b[1],2)+pow(a[0]-b[0],2))
从节点和length函数创建World。
world=pants.World(nodes,euclidean)
创建Solver。
solver=pants.Solver()
用Solver求解World。提供了两种方法 正在查找解决方案:solve()和solutions()。前者 返回找到的最佳解决方案,而后者返回每个 如果是目前为止最好的解决方案。
solution=solver.solve(world)# orsolutions=solver.solutions(world)
检查溶液。
print(solution.distance)print(solution.tour)# Nodes visited in orderprint(solution.path)# Edges taken in order# orbest=float("inf")forsolutioninsolutions:assertsolution.distance<bestbest=solution.distance
运行演示
其中包括一个33“城市”演示脚本,可以从命令行运行。
user@host:~$ pants-demo -h usage: pants-demo [-h] [-V] [-a A] [-b B] [-l L] [-p P] [-e E] [-q Q] [-t T] [-c N] [-d D] Script th;at demos the ACO-Pants package. optional arguments: -h, --help show this help message and exit -V, --version show program's version number and exit -a A, --alpha A relative importance placed on pheromones; default=1 -b B, --beta B relative importance placed on distances; default=3 -l L, --limit L number of iterations to perform; default=100 -p P, --rho P ratio of evaporated pheromone (0 <= P <= 1); default=0.8 -e E, --elite E ratio of elite ant's pheromone; default=0.5 -q Q, --Q Q total pheromone capacity of each ant (Q > 0); default=1 -t T, --t0 T initial amount of pheromone on every edge (T > 0); default=0.01 -c N, --count N number of ants used in each iteration (N > 0); default=10 -d D, --dataset D specify a particular set of demo data; default=33 For best results: * 0.5 <= A <= 1 * 1.0 <= B <= 5 * A < B * L >= 2000 * N > 1 For more information, please visit https://github.com/rhgrant10/Pants. user@host:~$ pants-demo Solver settings: limit=100 rho=0.8, Q=1 alpha=1, beta=3 elite=0.5 Time Elapsed Distance -------------------------------------------------- 0:00:00.017490 0.7981182992833705 0:00:00.034784 0.738147755518648 0:00:00.069041 0.694362159048816 0:00:00.276027 0.6818083968312925 0:00:00.379039 0.6669398280432167 0:00:00.465924 0.6463548571712562 0:00:00.585685 0.6416519698864324 0:00:01.563389 0.6349308484274142 -------------------------------------------------- Best solution: 0 = (34.02115, -84.267249) 9 = (34.048194, -84.262126) 6 = (34.044915, -84.255772) 22 = (34.061518, -84.243566) 23 = (34.062461, -84.240155) 18 = (34.060461, -84.237402) 17 = (34.060164, -84.242514) 12 = (34.04951, -84.226327) 11 = (34.048679, -84.224917) 8 = (34.046006, -84.225258) 7 = (34.045483, -84.221723) 13 = (34.051529, -84.218865) 14 = (34.055487, -84.217882) 16 = (34.059412, -84.216757) 25 = (34.066471, -84.217717) 24 = (34.064489, -84.22506) 20 = (34.063814, -84.225499) 10 = (34.048312, -84.208885) 15 = (34.056326, -84.20058) 5 = (34.024302, -84.16382) 32 = (34.118162, -84.163304) 31 = (34.116852, -84.163971) 30 = (34.109645, -84.177031) 29 = (34.10584, -84.21667) 28 = (34.071628, -84.265784) 27 = (34.068647, -84.283569) 26 = (34.068455, -84.283782) 19 = (34.061281, -84.334798) 21 = (34.061468, -84.33483) 2 = (34.022585, -84.36215) 3 = (34.022718, -84.361903) 4 = (34.023101, -84.36298) 1 = (34.021342, -84.363437) Solution length: 0.6349308484274142 Found at 0:00:01.563389 out of 0:00:01.698616 seconds. user@host:~$
已知错误
我现在都不知道。如果你发现 否则。
故障排除
学分
- 罗伯特·格兰特rhgrant10@gmail.com
许可证
平均绩点