評論(0

不動點演算法

標籤: 暫無標籤

針對標準遺傳演算法收斂精度不高的缺陷,把不動點理論引入遺傳演算法.將種群中的個體視為剖分中的點,通過對解空間進行J1剖分和整數標號得到個體承載單純形的頂點標號信息;利用該信息指導演算法進行最優化搜索和收斂性判斷.當種群個體的承載單純形全部轉化為全標單純形時,演算法中止,得出全局最優解.算例結果表明,該演算法具有很高的計算效率和穩定性.

1 不動點演算法 -不動點演算法

 

2 不動點演算法 -正文

  又稱固定點演算法。所謂不動點,是指將一個給定的區域A,經某種變換ƒ(x),映射到A時,使得x=ƒ(x)成立的那種點。最早出現的不動點理論是布勞威爾定理(1912):設ARn中的一緊緻凸集, ƒ為將A映射到A的一連續函數,則在A中至少存在一點x,使得x=ƒ(x)。其後,角谷靜夫於1941年將此定理推廣到點到集映射上去。設對每一xA,ƒ(x)為A的一子集。若ƒ(x)具有性質:對A上的任一收斂序列xix0,若yi∈ƒ(xi)且yiy0,則有y0∈ƒ(x0),如此的ƒ(x)稱為在A上半連續,角谷靜夫定理:設ARn中的一緊緻凸集,對於任何xA,若ƒ(x)為A的一非空凸集,且ƒ(x)在A上為上半連續,則必存在x不動點演算法A,使x不動點演算法∈ƒ(x不動點演算法)。J.P.紹德爾和J.勒雷又將布勞威爾定理推廣到巴拿赫空間。
  不動點定理在代數方程、微分方程、積分方程、數理經濟學等學科中皆有廣泛的應用。例如,關於代數方程的基本定理,要證明ƒ(x)=0必有一根,只須證明在適當大的圓│x│≤R內函數ƒ(x)+x有一不動點即可;在運籌學中,不動點定理的用途至少有二:一為對策論中用來證明非合作對策的平衡點的存在和求出平衡點;一為數學規劃中用來尋求數學規劃的最優解。對於一個給定的凸規劃問題:min{ƒ(x)│gi(x)≤0,i=1,2,…,m},在此,ƒ和g1,g2,…,gm皆為Rn中的凸函數。通過適當定義一個函數φ,可以證明:若上述問題的可行區域非空,則φ的不動點即為該問題的解。
  在1964年以前,所有不動點定理的證明都是存在性的證明,即只證明有此種點存在。1964年,C.E.萊姆基和 J.T.Jr.豪森對雙矩陣對策的平衡點提出了一個構造性證明。1967年,H.斯卡夫將此證法應用到數學規劃中去。其後,不動點定理的構造性證明有了大的發展和改進。
  H.斯卡夫的證明是基於一種所謂本原集,後來的各種發展皆基於某種意義下的三角剖分。現以n維單純形Sn為例來說明這一概念,在此,不動點演算法不動點演算法。對每一i, 將區間0≤xi≤1依次分為m1,m2…等分,m1<m2<…,mi不動點演算法,是給定的一列正整數。對於固定的i,過分點不動點演算法不動點演算法依次作平行於xi=0的平面。 這些平面將Sn分成若干同樣大小的n維三角形。它們的全體作成的集Gi,稱為Sn的一三角剖分。設ƒ(x)為SnSn的一連續函數,x=(x1,x2,…,xn+1),ƒ(x)=(ƒ1x),ƒ2x),…,ƒn+1x))。定義不動點演算法不動點演算法。由於ƒ(x)和x皆在Sn上,若有不動點演算法則顯然有ƒ(x不動點演算法)=x不動點演算法,即x不動點演算法為ƒ(x)的一不動點。
  對每一點ySn賦與標號l(y)=k=min{jyCj,且yj>0}。由著名的施佩納引理,在Gi中必存在一三角形σi,它的n+1個頂點yi(k)的標號分別為k(k=1,2,…,n+1)於是可得一列正數ij(j不動點演算法),使得不動點演算法(k)→yk,k=1,2,…,n+1。根據σi的作法,當ij不動點演算法時,不動點演算法收斂成一個點x不動點演算法。故yk=x不動點演算法,k=1,2,…,n+1。因不動點演算法(k)的標號為k,故ykCk,因而不動點演算法x不動點演算法為所求的不動點。因此,求ƒ(x):SnSn 的不動點問題就化為求 σi(i=1,2,…) 的問題。為了計算上的效果,除了上述的標號法之外,還有標準整數標號法、向量標號法等等。關於如何求σi,有變維演算法、三明治法、同倫演算法、變維重始法等等,通過適當定義,可將上之Sn改為RnRn中之一凸集。求一凸函數在一凸集上的極值問題也可化為求不動點問題。一般說來,這條途徑適用於維數不高但問題中出現的函數較為複雜的情況。
  參考書目
 A.J.J.TalmanVariable Dimension Fixed Point Algorithms and Triangulations, Mathematisch Centrum, Amsterdam, 1980.

 

3 不動點演算法 -配圖

 

4 不動點演算法 -相關連接

相關評論

同義詞:暫無同義詞