Comments (5)
这是我实验跑出来的结果:
48 capitals of the US (Padberg/Rinaldi)
Simulated annealing Best distance: 33899.903615127725
Simulated annealing Average distance: 34430.13375274746
Genetic Algorithm Best distance: 87771.26994701447
Genetic Algorithm Average distance: 93383.70990490801
Ant Colony Alogorithm Best distance: 34956.61325328256
Ant Colony Alogorithm Average distance: 35598.34244140098
Solution distance: 33523.70850743559
GA算法跟其他算法跑出来的结果相差甚远,其他数据库也是类似,scikit的遗传算法解TSP问题效果不太理想
from scikit-opt.
Now we have a better update using UDF
step1: define your problem (data is from your url)
import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt
points_coordinate = np.array(
[
[6734, 1453], [2233, 10], [5530, 1424], [401, 841], [3082, 1644], [7608, 4458], [7573, 3716], [7265, 1268],
[6898, 1885], [1112, 2049], [5468, 2606], [5989, 2873], [4706, 2674], [4612, 2035], [6347, 2683], [6107, 669],
[7611, 5184], [7462, 3590], [7732, 4723], [5900, 3561], [4483, 3369], [6101, 1110], [5199, 2182], [1633, 2809],
[4307, 2322], [675, 1006], [7555, 4819], [7541, 3981], [3177, 756], [7352, 4506], [7545, 2801], [3245, 3305],
[6426, 3173], [4608, 1198], [23, 2216], [7248, 3779], [7762, 4595], [7392, 2244], [3484, 2829], [6271, 2135],
[4985, 140], [1916, 1569], [7280, 4899], [7509, 3239], [10, 2676], [6807, 2993], [5185, 3258], [3023, 1942]]
)
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
num_points = points_coordinate.shape[0]
def cal_total_distance(routine):
'''The objective function. input routine, return total distance.
cal_total_distance(np.arange(num_points))
'''
num_points, = routine.shape
return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
step2: make up UDF and run
from sko.GA import GA_TSP
def reverse(self):
for i in range(self.size_pop):
if np.random.rand() < self.prob_mut:
n1, n2 = np.random.randint(0, self.len_chrom - 1, 2)
if n1 >= n2:
n1, n2 = n2, n1 + 1
self.Chrom[i, n1:n2] = self.Chrom[i, n1:n2][::-1]
return self.Chrom
def run(self, max_iter=None):
self.max_iter = max_iter or self.max_iter
for i in range(self.max_iter):
Chrom_old = self.Chrom.copy()
self.X = self.chrom2x()
self.Y = self.x2y()
self.ranking()
self.selection()
self.crossover()
self.mutation()
# put parent and offspring together and select the best size_pop number of population
self.Chrom = np.concatenate([Chrom_old, self.Chrom], axis=0)
self.X = self.chrom2x()
self.Y = self.x2y()
self.ranking()
selected_idx = np.argsort(self.Y)[:self.size_pop]
self.Chrom = self.Chrom[selected_idx, :]
# record the best ones
generation_best_index = self.FitV.argmax()
self.generation_best_X.append(self.X[generation_best_index, :])
self.generation_best_Y.append(self.Y[generation_best_index])
self.all_history_Y.append(self.Y)
self.all_history_FitV.append(self.FitV)
global_best_index = np.array(self.generation_best_Y).argmin()
global_best_X = self.generation_best_X[global_best_index]
global_best_Y = self.func(global_best_X)
return global_best_X, global_best_Y
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
ga_tsp.register('mutation', reverse). \
register('run', run)
best_points, best_distance = ga_tsp.run()
step3: plot the result
fig, ax = plt.subplots(1, 1)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax.plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
plt.show()
plt.figure(2)
plt.plot(ga_tsp.generation_best_Y)
Looks great! May better set those as default.
The old answer:
prob_mut
不宜过大,这个概率代表的是每个基因变异的概率,而不是整条染色体变异的概率。
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=300, max_iter=800, prob_mut=0.001)
distance: 47864.13182497867
有所改进,但效果还是比其它算法差。
对于较长的路径,GA需要有一些改进策略,这是最近打算做的。
from scikit-opt.
version 0.5.3 has set the above as default GA_TSP
from scikit-opt.
Thank You!
from scikit-opt.
感谢你提交的bug,是否允许在未来的正式版本 scikit-opt 1.0 把你列为 contributor 呢?
from scikit-opt.
Related Issues (20)
- 没有连续域蚁群算法的实现
- crossover.py文件中crossover_2point_bit算子起作用吗
- How to change crossover rate? HOT 1
- 请问GA在做整数规划的时候怎么设置才能保证每次n个变量间不重复 HOT 1
- Allow users to set number of process pool workers/threads
- 如何在初始化阶段将表现良好的个体加入种群?
- 规定GA起始点
- 约束条件不生效
- 请教多进程模式下,如何释放占用内存 HOT 3
- ACA算法发生除0问题
- 请问模拟退火算法出自于哪里?
- 希望增加进度条
- 如何设置遗传算法优化函数最大化?提供的一些demo都是目标函数最小化问题求解
- 请问,如何解决一个简单的VRP问题?
- 如何用已知的较好参数初始化种群 HOT 2
- 默认优化目标最大还是最小
- solve the problem that use grid route
- 计算加速
- 非优化参数的传入 HOT 2
- BUG: array shape mismatch between Y and pbest_y in PSO, error raised in update_pbest HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from scikit-opt.