啟發(fā)式算法-2012課件

1、啟發(fā)式算法四川大學(xué)數(shù)學(xué)學(xué)院譚英誼Email: 一、組合優(yōu)化問題二、啟發(fā)式算法三、模擬退火算法四、遺傳算法解決離散的優(yōu)化問題運(yùn)籌學(xué)分支。通過數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。一.組合優(yōu)化問題1.1 組合優(yōu)化問題的基本概念一般模型目標(biāo)函數(shù)約束函數(shù)0-1背包問題（Knapsack Problem）加工調(diào)度問題（Scheduling Problem）旅行商問題（Travelling Salesman Problem-TSP）裝箱問題（Bin Packing Problem）圖著色問題（Graph Colori

2、ng Problem）經(jīng)典的組合優(yōu)化問題：0-1背包問題一個(gè)旅行者要從n種物品中選取b公斤重的物品，每個(gè)物品至多選一件。問這個(gè)旅行者應(yīng)該怎樣選取，是所選物品的總價(jià)值最大。旅行商問題給定n個(gè)城市和每兩個(gè)城市間的距離。一個(gè)貨郎自某一城市出發(fā)巡回售貨，問這個(gè)貨郎應(yīng)該如何選擇路線，使每個(gè)城市經(jīng)過一次且僅一次，并且路徑長度最短。距離矩陣，路徑，目標(biāo)函數(shù)例：TSP的近似算法：最近鄰法、最近插入法、最小支撐樹法、局部搜索法等算法（最近鄰法）：(1)任選一個(gè)城市c1為出發(fā)點(diǎn)；(2)根據(jù)與出發(fā)城市最近的原則，在c1以外的n-1個(gè)城市中選取第二個(gè)經(jīng)過城市；(3)再以c2為出發(fā)城市，在尚未經(jīng)過的按最近鄰原則選取c3

3、，如此重復(fù)，直至所有城市都被經(jīng)過，最后到達(dá)的城市是cn；（4）從cn返回c1，構(gòu)成一條路徑。例：0-1背包問題：貪婪算法每一步只在可選輸入中選取一個(gè)滿足約束條件的輸入來構(gòu)造一個(gè)可行解，實(shí)現(xiàn)某個(gè)優(yōu)化測度（目標(biāo)函數(shù)或別的測度）下的最優(yōu)。后繼步對前趨步的結(jié)果進(jìn)行擴(kuò)充，直到滿足約束條件的輸入選完，不能再擴(kuò)充為止。1.3 鄰域結(jié)構(gòu)與局部最優(yōu)1.4 局部搜索算法改善局部搜索算法性能的途徑：(1)對大量初始解執(zhí)行算法，再從中選優(yōu)(2)引入更復(fù)雜的鄰域結(jié)構(gòu)，使算法能對解空間的更大范圍進(jìn)行搜索(3)改變局部搜索算法只接受優(yōu)化解迭代的準(zhǔn)則，在一定限度接受惡化解。3.2 模擬退火算法流程：1）隨機(jī)產(chǎn)生一個(gè)初始解 ，

4、令 ，并計(jì)算目標(biāo)函數(shù)值2）設(shè)置初始溫度 t=T(0)，終止溫度 降溫系數(shù)3）while tTmini)for j=1:kii)對當(dāng)前最優(yōu)解 按照某一鄰域函數(shù),產(chǎn)生一新的解 計(jì)算新的目標(biāo)函數(shù)值 并計(jì)算目標(biāo)函數(shù)值的增量iii) 如果 則iv）如果 則如果否則v）end for4）降溫5）end while6）輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束。3.3 模擬退火算法要素1）狀態(tài)空間與狀態(tài)生成函數(shù)（鄰域函數(shù)）搜索空間（狀態(tài)空間）：由經(jīng)過編碼的可行解的集合所組成狀態(tài)生成函數(shù)（鄰域函數(shù)）應(yīng)盡可能保證產(chǎn)生的候選解遍布全部解空間。通常由兩部分組成，即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布候選解一般采用按照某一概率密度函

5、數(shù)對解空間進(jìn)行隨機(jī)采樣來獲得概率分布可以是均勻分布、正態(tài)分布、指數(shù)分布等等2）狀態(tài)轉(zhuǎn)移概率（接受概率）p狀態(tài)轉(zhuǎn)移概率是指從一個(gè)狀態(tài)xold（一個(gè)可行解）向另一個(gè)狀態(tài)xnew（另一個(gè)可行解）的轉(zhuǎn)移概率通俗的理解是接受一個(gè)新解為當(dāng)前解的概率它與當(dāng)前的溫度參數(shù)T有關(guān)，隨溫度下降而減小一般采用Metropolis準(zhǔn)則3.4 模擬退火算法實(shí)驗(yàn)性能分析：1）模擬退火法與局部搜索算法的差異2）優(yōu)點(diǎn)：高效、健壯、通用、靈活3）不足：返回一個(gè)高質(zhì)量近似解的時(shí)間花費(fèi)較多，當(dāng)問題規(guī)模不可避免增大時(shí)，難于承受的運(yùn)行時(shí)間將使算法喪失可行性。如何改進(jìn)？3.5 模擬退火算法的matlab實(shí)現(xiàn)利用模擬退火算法求函數(shù)極?。簾o約

6、束或有界約束x = simulannealbnd(fun,x0)x = simulannealbnd(fun,x0,lb,ub)x = simulannealbnd(fun,x0,lb,ub,options)x,fval = simulannealbnd(.)x,fval,exitflag = simulannealbnd(.)x,fval,exitflag,output = simulannealbnd(.)dejong5fcnx0 = 0 0;x,fval = simulannealbnd(dejong5fcn,x0)Optimization terminated: change in b

7、est function value less than options.TolFun.x = 0.0216 -31.9955fval = 2.9821Optimization terminated: change in best function value less than options.TolFun.x = -15.9669 -31.9749fval = 1.9920exitflag = 1output = iterations: 1608 funccount: 1621 message: 1x80 char randstate: 625x1 uint32 randnstate: 2

8、x1 double problemtype: unconstrained temperature: 2x1 double totaltime: 0.8268x,fval,exitflag,output = simulannealbnd(dejong5fcn,0,0)x0 = 0 0;lb = -64 -64;ub = 64 64;x,fval = simulannealbnd(dejong5fcn,x0,lb,ub)Optimization terminated: change in best function value less than options.TolFun.x = -32.01

9、69 -31.9879fval = 0.9980fun = (x) 3*sin(x(1)+exp(x(2);x = simulannealbnd(fun,1;1,0 0)Optimization terminated: change in best function value less than options.TolFun.x = 896.9234 0.0000options = saoptimset(PlotFcns,saplotbestf,saplottemperature,saplotf,saplotstopping);simulannealbnd(dejong5fcn,x0,lb,

10、ub,options);options = saoptimset(InitialTemperature,300 50);options = saoptimset(options,TemperatureFcn,temperaturefast);options = saoptimset(options,ReannealInterval,50);options = saoptimset(options,Display,iter,DisplayInterval,400);options = saoptimset(options,TolFun,1e-5);inputcities = 1150.0 630

11、.0 40.0 750.0 750.0 1030.0 1650.0 1490.0 . 790.0 710.0 840.0 1170.0 970.0 510.0 750.0 1280.0 230.0 460.0 . 1040.0 590.0 830.0 490.0 1840.0 1260.0 1280.0 490.0 1460.0 . 1260.0 360.0; 1760.0 1660.0 2090.0 1100.0 2030.0 2070.0 650.0 . 1630.0 2260.0 1310.0 550.0 2300.0 1340.0 700.0 900.0 1200.0 . 590.0

12、860.0 950.0 1390.0 1770.0 500.0 1240.0 1500.0 790.0 . 2130.0 1420.0 1910.0 1980.0;2）計(jì)算總距離的函數(shù)該函數(shù)根據(jù)給定路徑計(jì)算該路徑對應(yīng)總路程。function d = distance(inputcities)% d = distance(inputcities)計(jì)算TSP問題中n個(gè)城市間某路徑的總路程% 輸入?yún)?shù)為2*n數(shù)組，其中n為城市數(shù)目，列為對應(yīng)城市坐標(biāo) d = 0; for n = 1 : length(inputcities) if n = length(inputcities) d = d + no

13、rm(inputcities(:,n) - inputcities(:,1); else d = d + norm(inputcities(:,n) - inputcities(:,n+1); end end3）繪制路線的函數(shù)function f = plotcities(inputcities)% plotcities(inputcities)從inputcities參數(shù)中繪制城市的位置%輸入?yún)?shù)為2*n數(shù)組，其中n為城市數(shù)目，列為對應(yīng)城市坐標(biāo)temp_1 = plot(inputcities(1,:),inputcities(2,:),b*);set(temp_1,erasemode,no

14、ne);temp_2 = line(inputcities(1,:),inputcities(2,:),Marker,*);set(temp_2,color,r);x = inputcities(1,1) inputcities(1,length(inputcities);y = inputcities(2,1) inputcities(2,length(inputcities);x1 = 10*round(max(inputcities(1,:)/10);y1 = 10*round(max(inputcities(2,:)/10);if x1 = 0 x1 = 1;endif y1 = 0

15、y1 = 1;endaxis(0 x1 0 y1);temp_3 = line(x,y);set(temp_3,color,r);dist = distance(inputcities);distance_print = sprintf(.The roundtrip length for %d cities is % 4.6f units. ,length(inputcities),dist);text(x1/15,1.05*y1,distance_print,fontweight,bold);drawnow;4）交換城市的函數(shù)% s = swapcities(inputcities,n) n

16、個(gè)城市隨機(jī)的交換返回一組m個(gè)城市s = inputcities;for i = 1 : n city_1 = round(length(inputcities)*rand(1); if city_1 1 city_1 = 1; end city_2 = round(length(inputcities)*rand(1); if city_2 1 city_2 = 1; end temp = s(:,city_1); s(:,city_1) = s(:,city_2); s(:,city_2) = temp;end5）執(zhí)行模擬退火的函數(shù)function s = simulatedannealin

17、g(inputcities,initial_temperature,.cooling_rate,threshold,numberofcitiestoswap)% s = simulatedannealing (inputcities,initial_temperature,cooling_rate,)通過% n 個(gè)城市的TSP問題的最優(yōu)解返回一個(gè)新的城市構(gòu)型。global iterations;temperature = initial_temperature;initial_cities_to_swap = numberofcitiestoswap;iterations = 1;comple

18、te_temperature_iterations = 0;while iterations threshold previous_distance = distance(inputcities); temp_cities = swapcities(inputcities,numberofcitiestoswap); current_distance = distance(temp_cities); diff = abs(current_distance - previous_distance);if current_distance = 10 temperature = cooling_ra

19、te*temperature; complete_temperature_iterations = 0; endnumberofcitiestoswap = round(numberofcitiestoswap*exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end iterations = iterations + 1; complete_temperature_iterations = complete_temperature_iterations + 1;

20、else if rand(1) exp(-diff/(temperature) inputcities = temp_cities; plotcities(inputcities); numberofcitiestoswap = round(numberofcitiestoswap*exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end complete_temperature_iterations = complete_temperature_iteration

21、s + 1; iterations = iterations + 1; end end clc fprintf(tttIterations = %dn,iterations); fprintf(tttTemperature = %3.8fn,temperature); fprintf(tttIn current temperature for %d timesn,complete_temperature_iterations);endprevious_distancesimulatedannealing(inputcities,2000,0.97,2000,2)四. 遺傳算法4.1 遺傳算法簡

22、介19世紀(jì)60年代 Holland一族通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法遺傳算法是一種概率搜索算法，它是利用某種編碼技術(shù)作用于稱為染色體的二進(jìn)制數(shù)串，其基本思想是模擬由這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織地然而是隨機(jī)的信息交換來重新結(jié)合那些適應(yīng)性好的串，在每一代中，利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和段來生成一個(gè)新的串的群體；作為額外添加，偶爾也要在串結(jié)構(gòu)中嘗試用新的位和段來替代原來的部分。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個(gè)染色體進(jìn)行評價(jià)，并基于適應(yīng)值來選擇染色體，是適應(yīng)性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。遺傳算法利用簡單的編碼

23、技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，從而解決非常困難的問題。特別是它不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性、導(dǎo)數(shù)存在、單峰等假設(shè)，以及其固有的并行性。2）初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器 t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始種群P(0)5 2 1 4 3 52 4 3 1 5 23 4 2 1 5 31 4 5 2 3 1例如：1）編碼：將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)；4.2 遺傳算法流程3）個(gè)體評價(jià)：計(jì)算種群P(t)中各個(gè)個(gè)體的適應(yīng)度4）選擇運(yùn)算：將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操

24、作是建立在群體中個(gè)體的適應(yīng)度評估基礎(chǔ)上的。經(jīng)典的選擇算子：輪盤賭被選中的概率為：5）交叉運(yùn)算：將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子5 2 | 1 4 | 3 52 4 | 3 1 | 5 23 4 | 2 1 | 5 31 4 | 5 2 | 3 1例：有序雜交法：將個(gè)體兩兩配對，并以交叉概率Pc把配對的父代個(gè)體加以替換重組而生成新個(gè)體5 2 | 3 1 | 3 52 4 | 1 4 | 5 2倘若交換基因后出現(xiàn)了重復(fù)，則將該城市取代字串B1與A1中的城市具有相同位置的新城市，直到與字串A1中的城市均不重復(fù)

25、為止。5 2 | 3 1 | 1 52 4 | 1 4 | 5 25 2 | 3 1 | 4 52 4 | 1 4 | 5 26）變異運(yùn)算：將變異算子作用于群體。即是對群體中的個(gè)體串的某些基因座上的基因作變動(dòng)。以變異概率Pm對群體中個(gè)體串某些基因位上的基因值作變動(dòng)，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則，仍保留父代染色體。例：5 2 | 3 1 | 4 55 2 | 1 3 | 4 5群體P(t)經(jīng)過選擇、交叉和變異運(yùn)算之后得到下一代群體P(t+1)7）終止條件判斷：若t=T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。4.3 遺傳算法的matlab實(shí)現(xiàn)x

26、 = ga(fitnessfcn,nvars)x = ga(fitnessfcn,nvars,A,b)x = ga(fitnessfcn,nvars,A,b,Aeq,beq)x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)x, fval = ga(.)x, fval, exitflag, output, population, scores =

27、ga()A = 1 1; -1 2; 2 1;b = 2; 2; 3;lb = zeros(2,1);x, fval, exitflag = ga(lincontest6,2,A,b,lb)Optimization terminated: average change in the fitness value less than options.TolFun.x = 0.7904 1.2094fval = -8.0180exitflag = 1function y = simple_fitness(x) y = 100 * (x(1)2 - x(2) 2 + (1 - x(1)2;functi

28、on c, ceq = simple_constraint(x) c = 1.5 + x(1)*x(2) + x(1) - x(2); -x(1)*x(2) + 10; ceq = ;ObjectiveFunction = simple_fitness;nvars = 2; % Number of variablesLB = 0 0; % Lower boundUB = 1 13; % Upper boundConstraintFunction = simple_constraint;x,fval = ga(ObjectiveFunction,nvars,LB,UB, ConstraintFu

29、nction)Optimization terminated: average change in the fitness value less than options.TolFun and constraint violation is less than options.TolCon.x = 0.8122 12.3122fval = 1.3578e+004gatoolFitness function：ackleyfcnNumber of variables：10選中Plots中的Best fitnessX = gamultipoj(fitnessfcn,nvars,A,b,Aeq,beq

30、,lb,ub,options)可以處理線性不等式約束、線性等式約束和有界約束解多目標(biāo)規(guī)劃function y = simple_multiobjective(x) y(1) = (x+2)2 - 10; y(2) = (x-2)2 + 20;FitnessFunction = simple_multiobjective;numberOfVariables = 1;x,fval = gamultiobj(FitnessFunction,numberOfVariables);Optimization terminated: average change in the spread of Paret

31、o solutions less than options.TolFun.size(x)ans = 15 1size(fval)ans = 15 24.4 遺傳算法對TSP的應(yīng)用load(usborder.mat,x,y,xx,yy);plot(x,y,Color,red); hold on;cities = 40;locations = zeros(cities,2);n = 1;while (n = cities) xp = rand*1.5; yp = rand; if inpolygon(xp,yp,xx,yy) locations(n,1) = xp; locations(n,2) = yp; n = n+1; endendplot(locations(:,1),locations(:,2),bo);distances = zeros(cities);for count1=1:cities, for count2=1:count1, x1 = locations(count1,1); y1 = locations(count1,2); x2 = loca