优化算法

优化技术特别擅长处理：受多种变量的影响，存在许多种可能的解的问题，以及结果因这些变量的组合而产生很大变化的问题。比如组团旅游问题，宿舍分配问题等。
优化问题需要明确什么是最重要的因素，找到最重要的因素，需要组合在一起形成一个值，即成本函数。有了成本函数，下面介绍几种常用优化算法。

随机搜索（Random searching）

随机搜索算法不是一个非常好的优化算法，但是它使我们更易理解别的算法，也是评估其它算法的baseline。比较低效，没有利用已发现的优解。

def randomoptimize(domain,costf):
  best=999999999
  bestr=None
  for i in range(0,1000):
    # Create a random solution
    r=[float(random.randint(domain[i][0],domain[i][1])) 
       for i in range(len(domain))]
    
    # Get the cost
    cost=costf(r)
    
    # Compare it to the best one so far
    if cost<best:
      best=cost
      bestr=r 
  return r

爬山法（hill climbing）

从一个随机解开始，然后在其临近的点的解集中寻找更好的解集。容易陷入局部最优解，可以使用随机重复爬山法，爬山法以随机生成的多个初始值为起点运行若干次。

局部最优

def hillclimb(domain,costf):
  # Create a random solution
  sol=[random.randint(domain[i][0],domain[i][1])
      for i in range(len(domain))]
  # Main loop
  while 1:
    # Create list of neighboring solutions
    neighbors=[]
    
    for j in range(len(domain)):
      # One away in each direction
      if sol[j]>domain[j][0]:
        neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
      if sol[j]<domain[j][1]:
        neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])

    # See what the best solution amongst the neighbors is
    current=costf(sol)
    best=current
    for j in range(len(neighbors)):
      cost=costf(neighbors[j])
      if cost<best:
        best=cost
        sol=neighbors[j]

    # If there's no improvement, then we've reached the top
    if best==current:
      break
  return sol

模拟退火算法（simulated annealing）

受物理领域的启发，不仅仅接收更优的解，也接收表现较差的解。随着退火过程的不断进行，算法越来越不可能接收较差的解，直到最后，只会接收更优的解，被接受的概率公式如下：

接受概率

刚开始温度比较高，概率接近于1，随着温度的降低，高成本值和低成本值的差值越来越重要，差异越大，概率越低，因此算法倾向于较差的值，不会是非常差的值。

def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
  # Initialize the values randomly
  vec=[float(random.randint(domain[i][0],domain[i][1])) 
       for i in range(len(domain))]
  
  while T>0.1:
    # Choose one of the indices
    i=random.randint(0,len(domain)-1)

    # Choose a direction to change it
    dir=random.randint(-step,step)

    # Create a new list with one of the values changed
    vecb=vec[:]
    vecb[i]+=dir
    if vecb[i]<domain[i][0]: vecb[i]=domain[i][0]
    elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]

    # Calculate the current cost and the new cost
    ea=costf(vec)
    eb=costf(vecb)
    p=pow(math.e,(-eb-ea)/T)

    # Is it better, or does it make the probability
    # cutoff?
    if (eb<ea or random.random()<p):
      vec=vecb      

    # Decrease the temperature
    T=T*cool
  return vec

该算法在减少执行时间方便也表现不俗。

遗传算法（genetic algorithm）

受自然科学的启发。该算法运行前要先随机生成一组解，称为种群（population）。

题解及成本序列

先对题解进行排序，把当前最顶端的题解加入其所在的新种群中，该方法称为精英选拔法（elitism）。新种群中余下的部分是通过变异和交叉得到。

变异（mutation）

对一个即有解进行微小的、简单的、随机的变化。

变异示例

交叉（crossover）

选取最优解中的两个解，然后按照某种方式组合得到。

交叉示例

def geneticoptimize(domain,costf,popsize=50,step=1,
                    mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
  def mutate(vec):
    i=random.randint(0,len(domain)-1)
    if random.random()<0.5 and vec[i]>domain[i][0]:
      return vec[0:i]+[vec[i]-step]+vec[i+1:] 
    elif vec[i]<domain[i][1]:
      return vec[0:i]+[vec[i]+step]+vec[i+1:]
  
  # Crossover Operation
  def crossover(r1,r2):
    i=random.randint(1,len(domain)-2)
    return r1[0:i]+r2[i:]

  # Build the initial population
  pop=[]
  for i in range(popsize):
    vec=[random.randint(domain[i][0],domain[i][1]) 
         for i in range(len(domain))]
    pop.append(vec)
  
  # How many winners from each generation?
  topelite=int(elite*popsize)
  
  # Main loop 
  for i in range(maxiter):
    scores=[(costf(v),v) for v in pop]
    scores.sort()
    ranked=[v for (s,v) in scores]
    
    # Start with the pure winners
    pop=ranked[0:topelite]
    
    # Add mutated and bred forms of the winners
    while len(pop)<popsize:
      if random.random()<mutprob:

        # Mutation
        c=random.randint(0,topelite)
        pop.append(mutate(ranked[c]))
      else:
      
        # Crossover
        c1=random.randint(0,topelite)
        c2=random.randint(0,topelite)
        pop.append(crossover(ranked[c1],ranked[c2]))
    
    # Print current best score
    print scores[0][0]
    
  return scores[0][1]

详细内容参见集体智慧。