赞
踩
1.在选择的过程中,选择多少次,会不会造成种群的减少,选到重复的怎么办?
选择次数没有限制,即然是选择肯定就会有没选上的,因此会造成种群数量减少,选到重复的个体舍弃重新选择。建议选择的次数少于种群数量,因为不重复,因此当次数为种群数量时即全部选择了,这样就失去了选择的意义。舍弃重复的是因为重复的个体对种群的差异化没有帮忙(试想极端情况下全是重复个体,那么交叉后全是一样的,没有意义)。
2.即然计算出了种群中每个个体的适应度,为什么不直接选择适应度高的,舍弃适应度低的,而要用其他算法来选择?
适应度低的个体也可能存在优质基因。现实生活中的例子:一对傻子生了个聪明儿子。
3.交叉的过程是随机交叉还是两两交叉,交叉多少次合适?
随机或两两交叉都可以,交叉次数大于或等于初始种群中个体数量/2。因为交叉一次产生两个新个体,而第3步的变异不产生新个体,因此为保证种群中个体的数量不致于越来越少(人口负增长), 交叉次数大于或等于初始种群中个体数量/2。
JAVA实现的遗传算法:http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3
使用GA求解TSP问题:http://www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5
基因算法教程:http://www.w3ii.com/genetic_algorithms/default.html
1.模拟退火算法可以分解为解空间、目标函数和初始解三部分。
2.模拟退火的基本思想:
(1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L
(2) 对k=1, …, L做第(3)至第6步:
(3) 产生新解S′
(4) 计算增量ΔT=C(S′)-C(S),其中C(S)为代价函数
(5) 若ΔT<0则接受S′作为新的当前解,否则以概率exp(-ΔT/T)接受S′作为新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解,结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少,且T->0,然后转第2步。
demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2
from sko.SA import SA
sa = SA(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, L=300, max_stay_counter=150)
best_x, best_y = sa.run()
print('best_x:', best_x, 'best_y', best_y)
# best_x: [-2.09849560e-05 5.00075424e-02 2.40334265e-06] best_y 5.030317095901513e-10
import matplotlib.pyplot as plt
import pandas as pd
plt.plot(pd.DataFrame(sa.best_y_history).cummin(axis=0))
plt.show()
而且,scikit-opt提供了3种类型的模拟退火:快速,玻尔兹曼,柯西。查看更多SA
import sys import numpy as np from scipy import spatial import matplotlib.pyplot as plt file_name = 'nctu.txt' points_coordinate = np.loadtxt(file_name, delimiter=',') num_points = points_coordinate.shape[0] distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean') distance_matrix = distance_matrix * 111000 # 1 degree of lat/lon ~ = 111000m 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)])
from sko.SA import SA_TSP
sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)
best_points, best_distance = sa_tsp.run()
print(best_points, best_distance, cal_total_distance(best_points))
# %% Plot the best routine from matplotlib.ticker import FormatStrFormatter fig, ax = plt.subplots(1, 2) best_points_ = np.concatenate([best_points, [best_points[0]]]) best_points_coordinate = points_coordinate[best_points_, :] ax[0].plot(sa_tsp.best_y_history) ax[0].set_xlabel("Iteration") ax[0].set_ylabel("Distance") ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], marker='o', markerfacecolor='b', color='c', linestyle='-') ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f')) ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f')) ax[1].set_xlabel("Longitude") ax[1].set_ylabel("Latitude") plt.show()
# %% Plot the animation import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation from matplotlib.ticker import FormatStrFormatter best_x_history = sa_tsp.best_x_history fig2, ax2 = plt.subplots(1, 1) ax2.set_title('title', loc='center') line = ax2.plot(points_coordinate[:, 0], points_coordinate[:, 1], marker='o', markerfacecolor='b', color='c', linestyle='-') ax2.xaxis.set_major_formatter(FormatStrFormatter('%.3f')) ax2.yaxis.set_major_formatter(FormatStrFormatter('%.3f')) ax2.set_xlabel("Longitude") ax2.set_ylabel("Latitude") plt.ion() p = plt.show() def update_scatter(frame): ax2.set_title('iter = ' + str(frame)) points = best_x_history[frame] points = np.concatenate([points, [points[0]]]) point_coordinate = points_coordinate[points, :] plt.setp(line, 'xdata', point_coordinate[:, 0], 'ydata', point_coordinate[:, 1]) return line ani = FuncAnimation(fig2, update_scatter, blit=True, interval=25, frames=len(best_x_history)) plt.show() ani.save('sa_tsp.gif', writer='pillow')
下载链接:https://pan.baidu.com/s/18OySLiJx3E9_53TA2PO3Sw 提取码:06gq
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。