04 最优化方法

推荐书籍：

《最优化方法》 李元科

基本概念：

目标函数     无约束优化   约束优化 

 迭代下降法 

1）图解法：

 2）迭代下降法

导数是函数在一个点上变化率的描述 。 偏导数是函数在一点沿坐标方向的变化率 ，方向导数是函数在一点沿任意方向的变化率 ，梯度则是函数在一个点上变化率最大的方向导数 。 函数在一个点上沿任意方向的方向导数等于函数在该点的梯度在该方向上的投影 。

方向导数：

 梯度定义：

无约束优化 ： 

约束优化： 

梯度下降法（看一阶导数）：

牛顿法（二阶导数）：

启发式算法：

遗传算法：模拟退火算法：蚁群算法：

模拟退火算法：

参看：
http://www.cnblogs.com/ranjiewen/p/6084052.html

from random import randint

def flip(segs, pos):

    return segs[:pos] + str(1-int(segs[pos])) + segs[pos+1:]

def flip_n(segs, n):

    for i in range(n):

        segs = flip(segs, randint(0, len(segs)-1))

    return segs

def anneal(text, segs, iterations, cooling_rate):

    temperature = float(len(segs))

    while temperature > 0.5:

        best_segs, best = segs, evaluate(text, segs)

        for i in range(iterations):

            guess = flip_n(segs, int(round(temperature,0)))

            score = evaluate(text, guess)

            if score < best:

                best, best_segs = score, guess

        score, segs = best, best_segs

        temperature = temperature / cooling_rate

        print(evaluate(text, segs), segment(text, segs))

    print()

    return segs

运行示例：

text = "doyouseethekittyseethedoggydoyoulikethekittylikethedoggy"

seg1 = "0000000000000001000000000010000000000000000100000000000"

anneal(text, seg1, 5000, 1.2)