593413198 / genetic_algorithm Goto Github PK

• Hill-climbing

• 基本**：在追求效率的条件下尽可能寻找局部最优解

• 它可能陷入局部的山峰，但这不是全局意义上的山峰

• 三个要点： startpoint（决定从哪里开始搜索）、step（决定每次搜索的步长,决定邻域的大小和算法的时间）、range(不能超出搜索范围，哪怕它的结果更优)

• 两种爬法： 首次爬山法（邻域找到第一个更优的直接爬）、最陡爬山法（找完邻域找出最优的再爬）

  def evaluate(): ------------ 评价函数，返回某个解的价值

  def yield_start(): ---------- 产生起点 startpoint

  def neigh(node,step): --- 根据指定步长返回node的领域

  def climb(node,step): ---- 找到node领域内最优的邻居并递归,一旦找不到更优则认为达到局部最优解并返回

• data以csv格式存放了200万个0到100之间的二维坐标数据，找出离他们距离和最小的一个点

  1. 经测试，每计算一个点到这200万个点的距离，需要1s左右的时间；
  2. 如果采取暴力所有，哪怕精度为1，也需要100*100大约10000s的时间，接近3个小时

测试结果：

暴力搜索： --- 10单位精度，60s，425560
           ---  1单位精度，约100min，可以忽略
爬山算法： --- 10单位精度，10s，426860
           ---  1单位精度，75s，423730

规律总结：