本文共 4671 字，大约阅读时间需要 15 分钟。

最优化算法的思想在于，我们往往并不需要得到最优解，而是得到一个近似最优解，来节省时间的开销。

• 爬山算法

  随机算法没有逻辑可寻，成本较低，但是效果较差。而爬山算法利用了数据的内在规律。就像爬山一样，为了，爬到上的最顶部，在到达一个点后，我们总是环顾四周，寻找比当前位置高的地方，然后继续往上爬。即比较当前位置的邻近值。

• 模拟退火

  很显然，爬山算法有个缺陷，比如，如果我们的当前位置是E，当取A，D两个值作比较时，会排除D点，这样结果将陷入到局部最大值A。为了避免在最开始就陷入局部最大值，所以，我们引入了一个概率PP = exp[-（newcost - oldcost）/ T ]，即在温度很高时或者之后的值与第一个值相差不大时，会更可能不排除在外。越往后，随着温度的降低，将越来越接近爬山算法。这样在最初就不会排除D，从而可以顺利找到B

• 遗传算法

  遗传算法类似于人类进化论，即物种总是朝着最优秀的方向进化，进化的方式有重组和变异，重组及优秀个体交换信息，变异即优秀个体内部改变元素。选择即我们通过成本函数进行排序，选择更好的值。

""" @author: zoutai@file: optimization.py @time: 2018/04/22 @description: """import randomimport timeimport mathpeople = [('Seymour', 'BOS'),          ('Franny', 'DAL'),          ('Zooey', 'CAK'),          ('Walt', 'MIA'),          ('Buddy', 'ORD'),          ('Les', 'OMA')]# newyork的Laguardia机场destination = 'LGA'# 第一步，以出发地-目的地为key，以具体的航班信息为value，做字典映射flights = {}for line in open('schedule.txt'):    origin, dest, departTime, arriveTime, price = line.strip().split(',')    flights.setdefault((origin, dest), [])    # 多趟航班，使用append    flights[(origin, dest)].append((departTime, arriveTime, int(price)))# 返回时间的分钟表示def getminutes(t):    x = time.strptime(t, '%H:%M')    return x[3] * 60 + x[4]def printschedule(r):    for d in range(len(r) // 2):        name = people[d][0]        origin = people[d][1]        go = flights[(origin, dest)][r[d * 2]]        back = flights[(dest, origin)][r[d * 2 + 1]]        print('%10s%10s，%5s-%5s，%3s，%5s-%5s，%3s'              % (name, origin, go[0], go[1], go[2], back[0], back[1], back[2]))s = [1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]printschedule(s)# 成本函数=等待时间+机票+出租车def schedulecost(sol):    totalcost = 0    earliestDep = 24 * 60    latestArrive = 0    for d in range(len(sol) // 2):        name = people[d][0]        origin = people[d][1]        go = flights[(origin, dest)][int(sol[d * 2])]        back = flights[(dest, origin)][sol[int(d * 2 + 1)]]        totalcost += go[2] + back[2]        if latestArrive < getminutes(go[1]):            latestArrive = getminutes(go[1])        if earliestDep > getminutes(back[0]):            earliestDep = getminutes(back[0])    totalWait = 0    for d in range(len(sol) // 2):        go = flights[(origin, dest)][sol[d * 2]]        back = flights[(origin, dest)][sol[d * 2 + 1]]        totalWait += (latestArrive - getminutes(go[1]))        totalWait += (getminutes(back[0]) - earliestDep)    # 出租车50/天    if latestArrive < earliestDep:        totalcost += 50    return totalcost + totalWaitprint("默认初始化值：",schedulecost(s))domain = [(0, 9)] * (len(people) * 2)# 1、随机法def randomoptimize(domain, costf):    best = 999999999    # bestRs = None    iterNum = 1000    for i in range(iterNum):        r = [random.randint(domain[i][0], domain[i][1]) for i in range(len(domain))]        cost = costf(r)        if cost < best:            best = cost            # bestRs = best    return r, bestr, best = randomoptimize(domain,schedulecost)print("随机法：",best)# 2、爬山法# 对于每一个未知数，搜索维度方向上的邻近节点，取最小值，直到最小值不变，退出def hillClimb(domain,costf):    # 创建随机解-初始化    sol = [random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]    # 循环    while 1:        # 创建邻接-表：二维的，即左右两个        neighbors = []        # 这里面的邻接区并不完全对，应该再加上一个维度循环，即单独固定一个变量变化        for j in range(len(domain)):            if sol[j]>domain[j][0]:                neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])            if sol[j]
   
    cost:                best=cost                sol = neighbors[j]        # 整个邻接区都没有更好的，则终止循环        if best==current:            break;    return sol,bestsol,best = hillClimb(domain,schedulecost)print("爬山法：",best)# 3、模拟退火# 原理相对于爬山法，为了避免陷入局部最小值，在初期的时候，对于不符合的结果，暂时不排除# T:初始温度，cool:冷却因子，step方向步长def annealingoptimize(domain,costf,T=10000,cool=0.95,step=1):    # 初始化随机值    vec = [random.randint(domain[i][0],domain[i][1]) for i in range(len(domain))]    while T > 0.1:        # 随机选择一个方向        i = random.randint(0,len(domain)-1)        director = random.randint(-step,step)        vecb = vec[:]        vecb[i]+=director # 偏移        # 防止出界        if vecb[i]
    
     domain[i][1]:            vecb[i]=domain[i][1]        costCur = costf(vec)        costB = costf(vecb)        if (costB
     
      costCur,也不用保留之前的vec，因为，温度下降后，会再返回到当前值        # 降低温度        T = T * cool    return vec,costf(vec)sol,best = annealingoptimize(domain,schedulecost)print("模拟退火算法：",best)# 4、遗传算法def geneticoptimize(domain,costf,popsize=50,step=1,mutprob=0.2,elite=0.2,mixiter=100):    # 变异    def mutate(vec):        i = random.randint(0,len(domain)-1)        # 随机数什么用？        if random.random()<0.5 and vec[i]>domain[i][0]:            return vec[:i]+[vec[i]-step]+vec[i+1:]        elif vec[i]
     
    
   

转载地址：http://ihepi.baihongyu.com/