NO IMAGE

 

 

文/騰訊soso 林世飛

 

    優化演算法通常用來處理問題最優解的求解–這個問題有多個變數共同決定的,舉一個例子比如有這樣一張 人員關係表,需要繪製一張SOSO華爾茲(一種socialnetwork,http://tag.soso.com/),比如:

    繪製方法有很多種,我們希望能夠最終展現給使用者的繪製是比較好閱讀的,比如交叉線比較少,每個人的點排的比較開等等。

    我們利用以下一個資料格式來描述最終的一個解,即一個向量包含每個人的座標,假設:通常我們用一個 向量來表示解x, x =[a1,a2,….]

    這個矩陣也很多值,那這個繪製方法可能很多,優化演算法就是用來尋找和評估其中比較好的一種繪製的結果的解。那這裡就要回答一個很關鍵的問題,什麼樣的解是好的解,這就需要一個方法來評估一個解的好壞程度,也就是優化演算法當中要 定義的 成本函式(Cost Function),在這個案例中就是有一個函式輸入是 每個人的座標,輸出是評價這種畫法或者說分佈質量如何。

    常用有4種優化演算法:

    1 隨機搜尋

    2 爬山法

    3 退火法

    4 遺傳演算法

 

    下面該給出各種演算法的實現說明,通過程式解釋各種求解實現和思想,為了便於理解,先介紹下 資料儲存格式:

Python code:

people=[‘劉翔’,’姚明’,’陳道明’,’郭晶晶’,’霍啟剛’,’紀偉’,’羅伯斯’,’孫海平’,’史冬鵬’,’葉莉’]

links=[(‘劉翔’, ‘姚明’),

       (‘劉翔’, ‘陳道明’),

       (‘劉翔’, ‘郭晶晶’),

       (‘劉翔’, ‘紀偉’),

       (‘劉翔’, ‘羅伯斯’),

       (‘劉翔’, ‘孫海平’),

       (‘劉翔’, ‘史冬鵬’),

       (‘姚明’, ‘葉莉’),

       (‘陳道明’, ‘霍啟剛’),

       (‘郭晶晶’, ‘霍啟剛’),

       (‘紀偉’, ‘羅伯斯’),

       (‘孫海平’, ‘史冬鵬’),

       (‘羅伯斯’, ‘孫海平’)]

 

    1  隨機搜尋:主要 依賴於隨機函式,每一次求解,都是不確定的變化趨勢(更好還是更壞)

#domain 表示解空間,domain[i][0] 表示向量x第i個維的最小值,domain[i][1] 表示向量x第i個維的最大值。

# costf :成本函式(Cost Function)

def randomoptimize(domain,costf):

  best=999999999

  bestr=None

 

 # 求解 1000次

 for i in range(0,1000):

    # 建立一個隨機的解

    r=[float(random.randint(domain[i][0],domain[i][1]))

       for i in range(len(domain))]

 

    # 計算 成本

    cost=costf(r)

 

    # 是否更優,成本小為更優

    if cost<best:

      best=cost

      bestr=r

  return r

 

    2 爬山法 ,搜尋沿著某一個更優方向搜尋直到一個極值(如下圖的波谷)

 

    以下是python 的一個實現:

#domain 表示解空間,domain[i][0] 表示向量x第i個維的最小值,domain[i][1] 表示向量x第i個維的最大值。

# costf :成本函式(Cost Function)

 

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)):

      # 解向量 第j維 在解空間,向上或者向下 變化步長1(所以叫鄰居解 )

      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:])

 

    # 在這一批尋找最優解

    current=costf(sol)

    best=current

    for j in range(len(neighbors)):

      cost=costf(neighbors[j])

      if cost<best:

        best=cost

        sol=neighbors[j]

# 當沒有更優解出現時候,認為達到某個區域性最優解,搜尋過程結束

    if best==current:

      break

  return sol

 

    3 退火法

    前面的2個優化演算法,都是簡單往一個更優方向搜尋最優解,這樣如果遇到下面這種情況,這樣很可能陷入一個區域性最優解(Local optimum),最終搜尋的解可能不是全域性最優解(Goal optimum),為了避免這個情況,我們希望搜尋過程一定程度允許一些差的解存在,因為這些解很可能存在通往最優解的方向上。

 

    為了實現這個想法,退火法在系統早期允許差解存在,存在概率為P,這個概率越來越小,因為還是要找最優解,所以系統後期基本不接受差的解,這個過程很像 物體退火降溫的過程,溫度越高時候,分子運動雜亂無章,系統越不穩定,即可以接受差的解,當物體冷卻以後,系統趨於穩定,即只接受更優解,我們用這個公式模擬這個過程:

    求解過程如下(個人感覺直接看程式 更好理解):

 

    附:模擬退火法( Simulated Annealing;SA) 最早的想法是由N.Metropolis 等人於1953 年所提出,在當時並沒有受到重視。直到1983 年由Kirkpatrick et al. 提出蒙地卡羅模擬(MonteCarlo Simulated)概念的隨機搜尋技巧,利用此方法來求解的組合最佳化問題時,才使此演演算法受到重視。

    以下是python 的一個實現:

def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):

 

 # 從一個隨機解開始

  vec=[float(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)

 

    # 選擇一個搜尋方向

    dir=random.randint(-step,step)

 

    # 在搜尋方向上生成新解

    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]

 

    ea=costf(vec)

eb=costf(vecb)

 

#重新計算系統穩定性-概率p,退火演算法核心

    p=pow(math.e,(-eb-ea)/T)

 

# 更優解將替換當前解,在系統早期,溫度很高,系統很不穩定,非更優解也可能替換當前解,這樣做的目的,是避免過快陷入區域性最優解,更大範圍搜尋最優解。

 

    if (eb<ea or random.random()<p):

      vec=vecb     

 

    # 減低溫度

    T=T*cool

  return vec

 

    4 遺傳演算法:這個搜尋過程基於一個假設認為全域性最優解很可能 存在於當前 最優解種群中的下一代,這個下一代通常由當前最優解種群,通過解空間的某些維的交叉或者變異產生(這裡有很多概率:變異範圍概率P1,交叉還是變異的概率p2……),新產生的一代中,重新計算成本,保留一定數量最優解,作為當前最優解種群,如此迴圈經過幾代遺傳,最終在最後一代最優解種群中選擇解。計劃這個演算法在另外文章中再詳細介紹。

 

    為了熟悉這些演算法,所以實驗了這個案例。除了以上演算法,我們還需要編寫一個成本函式,這個非常關鍵,這裡列出一種計算方法,通過計算解所描述的圖上點之間的距離和線交叉情況,來評估該圖分佈是否均衡合理(比如:交叉少便於閱讀),

 

程式碼如下:

def crosscount(v):

  loc=dict([(people[i],(v[i*2],v[i*2 1])) for i in range(0,len(people))])

 

  total=0

 

  # Loop through every pair of links

  for i in range(len(links)):

    for j in range(i 1,len(links)):

 

      # 計算線交叉情況

      (x1,y1),(x2,y2)=loc[links[i][0]],loc[links[i][1]]

      (x3,y3),(x4,y4)=loc[links[j][0]],loc[links[j][1]]

 

      den=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)

 

      if den==0: continue

 

      ua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den

      ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den

 

      if ua>0 and ua<1 and ub>0 and ub<1:

        total =1

 

    #計算點互相的距離

    for i in range(len(people)):

      for j in range(i 1,len(people)):

        (x1,y1),(x2,y2)=loc[people[i]],loc[people[j]]

 

        dist=math.sqrt(math.pow(x1-x2,2) math.pow(y1-y2,2))

        if dist<50:

          total =(1.0-(dist/50.0))

 

  return total

 

效果如下:

 

>>> sol=optimization.annealingoptimize(socialnetwork.domain,socialnetwork.crossc

ount,step=100,cool=0.99)

>>> socialnetwork.crosscount(sol)

 

    總體感覺效果不是很好,這個可能和我們的成本函式也有關,成本函式需要比較好的評價每個解的好與壞。

    後來想,是否可以從一個比較好初始狀態開始,再利用優化演算法進行簡單的優化,於是寫了一個函式 ,根據人數量,先平均切割塊,把關係多的人放在位於中間的聯通性比較好的塊,這個解作為搜尋的初始值:

 

def init_pos(peoples,height=400):

    result =[]

    pos_len= round(1 math.sqrt(len(peoples)))

    pos_unit=int(height/pos_len)

    helf_unit=int(pos_unit/5)

 

    #生成初始位置列表

    for i in range(1,pos_len 1):

        for j in range(1,pos_len 1):

            result.append((pos_weigh(i*pos_unit,j*pos_unit,height),(i*pos_unit-helf_unit,j*pos_unit-helf_unit)))

 

    result.sort()

    result.reverse()

 

    #計算每個人的權重

    people_weigh={}

    for link in links:

        people_weigh.setdefault(link[0],0)

        people_weigh[link[0]] =1

        people_weigh.setdefault(link[1],0)

        people_weigh[link[1]] =1

 

    people_queue=[]

    for item in people_weigh:

        people_queue.append((people_weigh[item],item))

 

    people_queue.sort()

    people_queue.reverse()

    #放置人,根據權重大小先後放置

 

    pos=dict([(people_queue[i][1],(result[i][1])) for i in range(0,len(people_queue))])

    pos_values=[]

 

    for i in range(0,len(people)):

        pos_values.append(pos[people[i]][0])

        pos_values.append(pos[people[i]][1])

 

    return pos_values

 

    優化的一個結果:

    由於時間關係,沒有做再多的實驗。。。幾個演算法優化結果都差不多,退火和下山稍微比隨機好一點。

 

    總結:

    優化演算法的一個特點往往給出的是一個區域性最優解,不是絕對的最優解,或者說全域性最優解。一種優化演算法是否有用很大程度取決問題本身,如果問題解本身就是比較無序的,或許隨機搜尋是最有效的。如以下這種情況,最優解可能位於一個狹小的空間,演算法通常很難找到這個最優解的途徑,因為任何解決的解成本都很高,都很有可能被排除在外。

    那是否能夠事先給出一個比較優的初始解,再在這個基礎在利用優化演算法,是否可以得到較優解,我想可能是存在的,在以上的這個例子當中,我做了下嘗試,效果感覺不是很明顯,當然也有很有可能是我方法不對。後來分析覺得  實際系統應該是使用類似  mass and spring 演算法,這個演算法也 模擬自然界中 球和彈簧的運動模型來的:各個節點施力企圖遠離對方,而節點間的連線又企圖拉近其連結的2個節點。

 

附:

    SOSO華爾茲是騰訊(TM)旗下搜尋門戶SOSO(搜搜)於2009年8月起新增的一項搜尋功能。在這個頁面裡我們可以看到許多明星人物肖像被做成小圖示,一個圖示所連結的頁面就是關於此圖片人物的熱門關聯及其相關熱門搜尋。

    SOSO華爾茲的特點在於:能夠把與你要搜尋的人物相關的其他人物都連成一個關係網,按照熱門程度來進行相關聯,您可以在這個頁面中發現此人與其相關聯人物之間的關係,以及在什麼時候發生了什麼事情等等。通過點選檢視詳細,更可以看到關聯此事件的網頁新聞,部落格,搜吧,圖片等等。讓人非常方便的直接找到關注點以及所關聯的人與事。

 

    以上內容是 個人的一些學習筆記,資料大多源於網際網路,有很多也是個人的理解,不一定正確,供大家參考。