組合優(yōu)化問(wèn)題與現(xiàn)代優(yōu)化算法

組合優(yōu)化問(wèn)題與仿生優(yōu)化算法數(shù)學(xué)建模培訓(xùn)

組合最優(yōu)化（combinatorialoptimization)是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等。所研究的問(wèn)題涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、通信網(wǎng)絡(luò)等領(lǐng)域。該問(wèn)題可用數(shù)學(xué)模型描述為：“組合優(yōu)化問(wèn)題”存在于生活中的方方面面

田忌賽馬，投資組合“組合優(yōu)化”是通過(guò)“優(yōu)化某種順序排列方式”實(shí)現(xiàn)的

何謂組合優(yōu)化問(wèn)題？0-1背包問(wèn)題設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為ai

(i=1,2,…,n),價(jià)值分別為ci(i=1,2,…,n)的物品，如何以最大的價(jià)值裝包？經(jīng)典的組合優(yōu)化問(wèn)題——背包問(wèn)題旅行商問(wèn)題

一個(gè)推銷員欲到n個(gè)城市推銷商品，每?jī)蓚€(gè)城市i和j之間的距離為dij，如何選擇一條道路使得推銷員每個(gè)城市正好走一遍后回到起點(diǎn)且所走路徑最短。經(jīng)典的組合優(yōu)化問(wèn)題——旅行商問(wèn)題一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題——旅行商問(wèn)題數(shù)學(xué)模型旅行商問(wèn)題的應(yīng)用領(lǐng)域

旅行商問(wèn)題要從圖G的所有旅行路線中求取最小成本的旅行路線，而從初始點(diǎn)出發(fā)最終回到初始點(diǎn)的周游路線一共有n!條，即等于除初始結(jié)點(diǎn)外的n個(gè)結(jié)點(diǎn)的排列數(shù)，因此旅行商問(wèn)題是一個(gè)排列問(wèn)題。可用于：指導(dǎo)交通規(guī)劃，以減輕交通擁堵；指導(dǎo)物流節(jié)點(diǎn)的布局規(guī)劃，物流路徑的合理選擇，以減少物流成本；指導(dǎo)互聯(lián)網(wǎng)環(huán)境中節(jié)點(diǎn)的設(shè)置，以更好地讓信息流動(dòng)。一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題——旅行商問(wèn)題從n!條周游路線中找出一條具有最小成本的旅行路線，如果用枚舉的方法尋找，就是把每一個(gè)旅程的成本都計(jì)算一次，再比較大小，顯然需要計(jì)算n!次；當(dāng)n不斷的變大，問(wèn)題的求解會(huì)呈現(xiàn)出一種組合爆炸的狀態(tài)。所以，尋求有效的算法是解決組合問(wèn)題的關(guān)鍵。旅行商問(wèn)題的解勤勞的小蜜蜂英國(guó)倫敦大學(xué)皇家霍洛韋學(xué)院等機(jī)構(gòu)的研究人員報(bào)告：在花叢中飛來(lái)飛去的小蜜蜂顯示出了輕而易舉破解旅行商問(wèn)題的能力。人們利用人工控制的假花進(jìn)行了實(shí)驗(yàn)，結(jié)果顯示，不管怎樣改變花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵間飛行的最短路徑。螞蟻覓食單只螞蟻的能力和智能非常簡(jiǎn)單，但它們通過(guò)相互協(xié)調(diào)、分工、合作完成筑巢、覓食、遷徙等復(fù)雜行為，比如螞蟻在覓食過(guò)程中能夠通過(guò)相互協(xié)作找到食物源和巢穴之間的最短路徑。其它的動(dòng)物如蟑螂，魚(yú)，細(xì)菌，鳥(niǎo)等都能夠利用群智能，采取合理的行動(dòng)進(jìn)行覓食，人們仿照這些動(dòng)物的覓食行為構(gòu)造了相應(yīng)的仿生算法。仿生優(yōu)化算法——群智能算法仿生優(yōu)化算法——粒子群算法

粒子群優(yōu)化算法(PSO)是一種集群智能方法的演化計(jì)算技術(shù),PSO的基本概念源于對(duì)鳥(niǎo)群捕食行為的研究.1995被Kennedy和Eberhart于1995年提出。PSO算法的思想是跟蹤最好點(diǎn)，并逐步向最好點(diǎn)靠近。粒子（潛在的解）在解空間跟蹤最優(yōu)的粒子進(jìn)行搜索。每個(gè)尋優(yōu)的問(wèn)題解都被想象成一只鳥(niǎo)，我們也稱為“Particle”。所有的Particle都有一個(gè)fitnessfunction以判斷目前的位置之好壞。每一個(gè)Particle必須賦予記憶性，能記得所搜尋到最佳位置。每一個(gè)Particle還有一個(gè)速度以決定飛行的距離與方向。仿生優(yōu)化算法——粒子群算法仿生優(yōu)化算法——粒子群算法第i個(gè)粒子的“飛翔”速度也是一個(gè)D維的向量，記為假設(shè)在一個(gè)D維的目標(biāo)搜索空間中，有m個(gè)粒子組成一個(gè)群落，其中第i個(gè)粒子表示為一個(gè)D維的向量i=1,2,…m.每個(gè)粒子的位置就是一個(gè)潛在的解。將其帶入一個(gè)目標(biāo)函數(shù)就可以計(jì)算出其適應(yīng)值，根據(jù)適應(yīng)值的大小衡量其優(yōu)劣。記第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為記整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為仿生優(yōu)化算法——粒子群算法基本思路：初始化一群隨機(jī)粒子（隨機(jī)解）每次迭代中，粒子通過(guò)跟蹤兩個(gè)極值更新自己：

——粒子本身找到的歷史最好解（個(gè)體極值點(diǎn)pbest）

——整個(gè)種群目前找到的最好解（全局極值點(diǎn)gbest）需要計(jì)算粒子的適應(yīng)值（目標(biāo)函數(shù)值），以判斷粒子位置距最優(yōu)點(diǎn)的距離。每次迭代中，根據(jù)適應(yīng)值更新pbest和gbest。迭代終止條件：設(shè)置最大迭代次數(shù)或全局最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值。

仿生優(yōu)化算法——粒子群算法每個(gè)粒子如何迭代？c1,c2—學(xué)習(xí)因子，經(jīng)驗(yàn)值取c1=c2=2，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng)rand（）—隨機(jī)數(shù)，取值范圍（0，1），以增加搜索隨機(jī)性仿生優(yōu)化算法——粒子群算法開(kāi)始初始化粒子群計(jì)算每個(gè)粒子的適應(yīng)度根據(jù)適應(yīng)度更新pbest、gbest，更新粒子位置速度結(jié)束noyes達(dá)到最大迭代次數(shù)或全局最優(yōu)位置滿足最小界限？基本粒子群優(yōu)化算法流程圖仿生優(yōu)化算法——粒子群算法分布式搜尋具記憶性組件較少，容易實(shí)現(xiàn)適合在連續(xù)性的范圍內(nèi)搜尋粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題Schwefel'sfunction初始化粒子群位置粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題迭代5次后粒子群位置迭代10次后粒子群位置粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題迭代20次后粒子群位置粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題迭代100次后粒子群位置粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題迭代500次后粒子群位置粒子群優(yōu)化算法求解最優(yōu)化問(wèn)題粒子群優(yōu)化算法求解車輛路徑問(wèn)題車輛路徑問(wèn)題車輛路徑問(wèn)題可以描述為：有一個(gè)中心倉(cāng)庫(kù)，擁有k輛車，車場(chǎng)向L個(gè)客戶送貨，第i個(gè)客戶貨運(yùn)量為gi（i=1,2,……,L）,中心與客戶、客戶與客戶兩兩間的廣義運(yùn)輸費(fèi)用為cij，車場(chǎng)編號(hào)為0，客戶編號(hào)為i=1，2，……，L，送貨卡車裝載容量為qk（qk>gi,i=0,1,……,L），車輛不允許超載。要求指派運(yùn)輸車輛，并確定每輛車的運(yùn)輸路線，使得總運(yùn)輸費(fèi)用z最低。粒子群優(yōu)化算法求解車輛路徑問(wèn)題

各發(fā)貨點(diǎn)坐標(biāo)及貨運(yùn)量序號(hào)01234567坐標(biāo)(18,54)(22,60)(58,69)(71,71)(83,46)(91,38