as3[演算法] 模擬退火 Simulated Annealing

模擬退火 Simulated Annealing

為npc問題

p係指 多項式時間可決定

np則是 非決定性多項式時間

意思就是沒辦法用固定的時間(step)來得到一個問題的答案

而npc是指在np問題中 最困難的情況!

通常這類問題 需要將 參數一個一個帶進去try結果，尋找最佳結果

此模擬退火方法 在真實世界中係指一物體，受高溫後 溫度上升為t ，其內部原子 得到熱能後 形成可遊離狀態

在此可想像成沈積現象 原子會依自身的質能 往理想(比較重的會比較輕的掉到較底的位置)的位置移動 等到溫度降低之後 所有的原子失去動能

此時的各個原子所在的位置 理當比原先較為穩定(就像進行了一次排序) 這就是退火

-----------程式模擬大要------------

對於一個npc問題，給予一個理想大的溫度t，能量e (e與t成正比)，L為程式面搜尋次數

將初始解，就是自已定一個符合答案格式的答案

依照這個初始解，尋找其中一個 原子， 進行 與另一個隨機 "原子" 做交換

若交換結果符合我們的期望，那就交換(以波形來看這是往波谷下降，在所有可能分布波形中，最低的波谷就是最佳解，也稱做穩態(因為再也找不到最好的結果。在程序中起伏已不大，但尚未找到最佳解時 稱為 亞穩態；如果這個程序完整跑完得到的會叫做這次的 最佳解(但卻不能稱為穩態，因為繼續讓他跑下去 可能還是會有起伏 畢竟不可能全部的情況都RUN過)

若交換結果是往上升，那也不會因此否定這個交換，會視目前 能量 做評估，假如目前能量大(也代表T高)的話，就有較大的機會 做交換；

這個機制使得我們的搜尋路線並不會一味的往最低前進，以致於困死於同一條路線，死在一個谷底(而這個谷底 卻又不是整個答案最佳的谷底)

理想的波形會是逐漸向下的震波~

<?xml version="1.0" encoding="utf-8"?>
<s:Application xmlns:fx="http://ns.adobe.com/mxml/2009" 
  xmlns:s="library://ns.adobe.com/flex/spark" 
  xmlns:mx="library://ns.adobe.com/flex/mx" minWidth="955" minHeight="600"
  creationComplete="init();">
<fx:Declarations>
<!-- Place non-visual elements (e.g., services, value objects) here -->
</fx:Declarations>
<fx:Script>
<![CDATA[
public var allP:Array=new Array();
public var len:int=6;
private var T:int=100;//溫度100度
private const dT:int=1;//降溫常數
private var k:int=1;//搜尋次數
private const L:int=100; //搜尋最大次數
private var s:Array=new Array();//能量位址 for this problem，也是結果
private var E:int;//目前能量 也是目前結果的值
public function init():void{
for(var i:int=1;i<=len;i++){
var obj:Object=new Object();
obj.name=i;
obj.x=this['p'+i].x;
obj.y=this['p'+i].y;
allP.push(obj);
}
var tempArr:Array=new Array();
saMul();
}
public function saMul():void
{
s=allP;
E=cal(s);
//初始解
while(T)
{
while(k<=L)
{
var d:Object=nextE();
if(d.E<E)
{
//往波谷方向
s=d.s;
E=d.E;
//交換
}
else
{
var r:Number=Math.random();
var df:Number=d.E-E;
var P:Number=Math.exp(-(df)/(T));
if(r<P)
{
//往波峰方向；機率性交換
s=d.s;
E=d.E;
//交換
}
}
k++;
}
k=1;
trace("T:"+T+",s:"+s[0].name+"-"+
s[1].name+"-"+
s[2].name+"-"+
s[3].name+"-"+
s[4].name+"-"+
s[5].name+"-"+
",E:"+E);
T-=dT;

}
trace("ans:"+s+",E:"+E);
}
private function cal(arr:Array):Number
{
var e:Number=0;
for(var i:int=0;i<arr.length-1;i++)
{
var dx:Number=arr[i].x-arr[i+1].x;
var dy:Number=arr[i].y-arr[i+1].y;
e+=Math.sqrt(Math.pow(dx,2)+Math.pow(dy,2));
}
return e;
}

private function nextE():Object
{
var rObj:Object=new Object();
var s0:int=serachOtherP(s);
var s1:int=serachOtherP(s,s0);

var tempArr:Array=s.slice();
var tempObj:Object;
tempObj=tempArr[s0];
tempArr[s0]=tempArr[s1];
tempArr[s1]=tempObj; 
rObj.s=tempArr;
rObj.E=cal(tempArr);

return rObj;
}
private function serachOtherP(arr:Array,p:int=-1):int
{
if(p==-1)
{
//隨機尋找第一個原子
return Math.floor(Math.random()*arr.length);
}
else
{
while(true)
{
var r:int=Math.floor(Math.random()*arr.length);
if(r!=p)
return r;
}
}
return -1;
}
]]>
</fx:Script>
<mx:Canvas left="100" top="100">
<s:Label x="150" y="20" text="1"/>
<s:Label x="8" y="54" text="2"/>
<s:Label x="130" y="81" text="3"/>
<s:Label x="69" y="132" text="4"/>
<s:Label x="161" y="146" text="5"/>
<s:Label x="200" y="60" text="6"/>

<s:Label id="p1" x="160" y="20" text="●"/>
<s:Label id="p2" x="10" y="60" text="●"/>
<s:Label id="p3" x="130" y="90" text="●"/>
<s:Label id="p4" x="80" y="140" text="●"/>
<s:Label id="p5" x="150" y="150" text="●"/>
<s:Label id="p6" x="200" y="70" text="●"/>
</mx:Canvas>
</s:Application>