優化算法通常用來處理問題最優解的求解--這個問題有多個變量共同決定的，舉一個例子比如有這樣一張 人員關系表，需要繪制一張SOSO華爾茲(一種socialnetwork， http://tag.soso.com/)，比如：
繪制方法有很多種，我們希望能夠最終展現給使用者的繪制是比較好閱讀的，比如交叉線比較少，每個人的點排的比較開等等。
我們利用以下一個資料格式來描述最終的一個解，即一個向量包含每個人的坐标，假設：通常我們用一個 向量來表示解x， x =[a1,a2,….]
這個矩陣也很多值，那這個繪制方法可能很多，優化算法就是用來尋找和評估其中比較好的一種繪制的結果的解。那這裡就要回答一個很關鍵的問題，什麼樣的解是好的解，這就需要一個方法來評估一個解的好壞程度，也就是優化算法當中要 定義的 成本函數(Cost Function)，在這個案例中就是有一個函數輸入是 每個人的坐标，輸出是評價這種畫法或者說分布品質如何。
常用有4種優化算法:
1 随機搜尋
2 爬山法
3 退火法
4 遺傳算法
下面該給出各種算法的實作說明，通過程式解釋各種求解實作和思想，為了便于了解，先介紹下 資料儲存格式：
Python code：
people=['劉翔','姚明','陳道明','郭晶晶','霍啟剛','紀偉','羅伯斯','孫海平','史冬鵬','葉莉']
links=[('劉翔', '姚明'),
('劉翔', '陳道明'),
('劉翔', '郭晶晶'),
('劉翔', '紀偉'),
('劉翔', '羅伯斯'),
('劉翔', '孫海平'),
('劉翔', '史冬鵬'),
('姚明', '葉莉'),
('陳道明', '霍啟剛'),
('郭晶晶', '霍啟剛'),
('紀偉', '羅伯斯'),
('孫海平', '史冬鵬'),
1 随機搜尋：主要 依賴于随機函數，每一次求解，都是不确定的變化趨勢(更好還是更壞)
#domain 表示解空間，domain
[0] 表示向量x第i個維的最小值，domain[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
[0],domain[1]))
# 計算 成本
cost=costf(r)
# 是否更優，成本小為更優
if cost
best=cost
bestr=r
return r
2 爬山法 ，搜尋沿着某一個更優方向搜尋直到一個極值(如下圖的波谷)
以下是python 的一個實作：
#domain 表示解空間，domain
[0] 表示向量x第i個維的最小值，domain[1] 表示向量x第i個維的最大值。
# costf ：成本函數(Cost Function)
def hillclimb(domain,costf):
# 從一個随機解開始
sol=[random.randint(domain
[0],domain[1])
#搜尋解過程
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]
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=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
[0],domain[1]))
while T>0.1:
# 随機選擇一個次元
i=random.randint(0,len(domain)-1)
# 選擇一個搜尋方向
dir=random.randint(-step,step)
# 在搜尋方向上生成新解
vecb=vec[:]
vecb
+=dir
elif vecb>domain[1]: vecb=domain[1]
ea=costf(vec)
eb=costf(vecb)
#重新計算系統穩定性-機率p，退火算法核心
p=pow(math.e,(-eb-ea)/T)
# 更優解将替換目前解，在系統早期，溫度很高，系統很不穩定，非更優解也可能替換目前解，這樣做的目的，是避免過快陷入局部最優解，更大範圍搜尋最優解。
if (eb
vec=vecb
# 減低溫度
T=T*cool
return vec
4 遺傳算法：這個搜尋過程基于一個假設認為全局最優解很可能 存在于目前 最優解種群中的下一代，這個下一代通常由目前最優解種群，通過解空間的某些維的交叉或者變異産生(這裡有很多機率：變異範圍機率P1，交叉還是變異的機率p2……)，新産生的一代中，重新計算成本，保留一定數量最優解，作為目前最優解種群，如此循環經過幾代遺傳，最終在最後一代最優解種群中選擇解。計劃這個算法在另外文章中再詳細介紹。
為了熟悉這些算法，是以實驗了這個案例。除了以上算法，我們還需要編寫一個成本函數，這個非常關鍵，這裡列出一種計算方法，通過計算解所描述的圖上點之間的距離和線交叉情況，來評估該圖分布是否均衡合理(比如：交叉少便于閱讀)，
代碼如下：
def crosscount(v):
loc=dict([(people
,(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
[0]],loc[links[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
],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
[1],(result[1])) for i in range(0,len(people_queue))])
pos_values=[]
for i in range(0,len(people)):
pos_values.append(pos[people
][0])
pos_values.append(pos[people][1])
return pos_values
優化的一個結果：
由于時間關系，沒有做再多的實驗。。。幾個算法優化結果都差不多，退火和下山稍微比随機好一點。
總結：
優化算法的一個特點往往給出的是一個局部最優解，不是絕對的最優解，或者說全局最優解。一種優化算法是否有用很大程度取決問題本身，如果問題解本身就是比較無序的，或許随機搜尋是最有效的。如以下這種情況，最優解可能位于一個狹小的空間，算法通常很難找到這個最優解的途徑，因為任何解決的解成本都很高，都很有可能被排除在外。
那是否能夠事先給出一個比較優的初始解，再在這個基礎在利用優化算法，是否可以得到較優解，我想可能是存在的，在以上的這個例子當中，我做了下嘗試，效果感覺不是很明顯，當然也有很有可能是我方法不對。後來分析覺得 實際系統應該是使用類似 mass and spring 算法，這個算法也 模拟自然界中 球和彈簧的運動模型來的：各個節點施力企圖遠離對方，而節點間的連線又企圖拉近其連結的2個節點。
附：
SOSO華爾茲是騰訊(TM)旗下搜尋門戶SOSO(搜搜)于2009年8月起新增的一項搜尋功能。在這個頁面裡我們可以看到許多明星人物肖像被做成小圖示，一個圖示所連結的頁面就是關于此圖檔人物的熱門關聯及其相關熱門搜尋。
SOSO華爾茲的特點在于：能夠把與你要搜尋的人物相關的其他人物都連成一個關系網，按照熱門程度來進行相關聯，您可以在這個頁面中發現此人與其相關聯人物之間的關系，以及在什麼時候發生了什麼事情等等。通過點選檢視詳細，更可以看到關聯此事件的網頁新聞，部落格，搜吧，圖檔等等。讓人非常友善的直接找到關注點以及所關聯的人與事。
以上内容是 個人的一些學習筆記，資料大多源于網際網路，有很多也是個人的了解，不一定正确，供大家參考。
if vecb