B2-實作：二維爬山演算法

前述的簡易爬山演算法，函數 f(x) 只有一個變數，因此只能調整 x 值的大小，但是對於兩個變數的 f(x,y) 而言，除了調整 x 以外，還可以調整 y ，因此程式就必須要修改。

固定調整法

如果我們《上下左右》的調整方法都試一遍，就可以將程式修改如下：

import random

def hillClimbing(f, x, y, h=0.01):
    while (True):
        fxy = f(x, y)
        print('x={0:.3f} y={1:.3f} f(x,y)={2:.3f}'.format(x, y, fxy))
        if f(x+h, y) >= fxy:
            x = x + h
        elif f(x-h, y) >= fxy:
            x = x - h
        elif f(x, y+h) >= fxy:
            y = y + h
        elif f(x, y-h) >= fxy:
            y = y - h
        else:
            break
    return (x,y,fxy)

def f(x, y):
    return -1 * ( x*x - 2*x + y*y + 2*y - 8 )

hillClimbing(f, 0, 0)

執行結果

PS D:\ccc\course\ai\python\02-optimize> python .\hillClimbing2.py
x=0.000 y=0.000 f(x,y)=8.000
x=0.010 y=0.000 f(x,y)=8.020
x=0.020 y=0.000 f(x,y)=8.040
x=0.030 y=0.000 f(x,y)=8.059
x=0.040 y=0.000 f(x,y)=8.078
...
x=1.000 y=-0.960 f(x,y)=9.998
x=1.000 y=-0.970 f(x,y)=9.999
x=1.000 y=-0.980 f(x,y)=10.000
x=1.000 y=-0.990 f(x,y)=10.000
x=1.000 y=-1.000 f(x,y)=10.000

隨機調整法

import random

def hillClimbing(f, x, y, h=0.01):
    failCount = 0
    while (failCount < 10000):
        fxy = f(x, y)
        dx = random.uniform(-h, h)
        dy = random.uniform(-h, h)
        if f(x+dx, y+dy) >= fxy:
            x = x + dx
            y = y + dy
            print('x={0:.3f} y={1:.3f} f(x,y)={2:.3f}'.format(x, y, fxy))
        else:
            failCount = failCount + 1
    return (x,y,fxy)

def f(x, y):
    return -1 * ( x*x -2*x + y*y +2*y - 8 )

hillClimbing(f, 0, 0)

執行結果

PS D:\ccc\course\ai\python\02-optimize> python hillClimbing2r.py
x=0.009 y=0.003 f(x,y)=8.000
x=0.011 y=-0.004 f(x,y)=8.012
x=0.018 y=-0.008 f(x,y)=8.031
x=0.020 y=-0.016 f(x,y)=8.051
x=0.019 y=-0.022 f(x,y)=8.071
x=0.017 y=-0.027 f(x,y)=8.081
...
x=1.000 y=-1.001 f(x,y)=10.000
x=1.000 y=-0.999 f(x,y)=10.000
x=1.000 y=-1.000 f(x,y)=10.000
x=1.000 y=-1.000 f(x,y)=10.000

Edit on GitHub