文章目錄

01 內容概要

本資料集合了多種數學建模和優化算法的常用代碼資源，旨在為參與美國大學生數學建模競賽（MCM/ICM，簡稱美賽）的參賽者提供實用的編程工具和算法實現。這些算法包括BP神經網絡、CT圖像重建、Floyd算法、Topsis算法、層次分析法、分支定界法、灰色預測、粒子群算法、模擬退火算法（特別適用于TSP和背包問題）、人口增長模型以及搜索和遺傳算法。這些算法覆蓋了從機器學習到優化問題的廣泛領域，為解決復雜問題提供了多樣化的方法。

02 各種算法基本原理

1. BP神經網絡

• 基本原理：BP神經網絡是一種按誤差反向傳播訓練的多層前饋網絡，其算法稱為BP算法。基本思想是梯度下降法，利用梯度搜索技術，以期使網絡的實際輸出值和期望輸出值的誤差均方差為最小。基本BP算法包括信號的前向傳播和誤差的反向傳播兩個過程。即計算誤差輸出時按從輸入到輸出的方向進行，而調整權值和閾值則從輸出到輸入的方向進行。正向傳播時，輸入信號通過隱含層作用于輸出節點，經過非線性變換，產生輸出信號，若實際輸出與期望輸出不相符，則轉入誤差的反向傳播過程。誤差反傳是將輸出誤差通過隱含層向輸入層逐層反傳，并將誤差分攤給各層所有單元，以從各層獲得的誤差信號作為調整各單元權值的依據。通過調整輸入節點與隱層節點的聯接強度和隱層節點與輸出節點的聯接強度以及閾值，使誤差沿梯度方向下降，經過反復學習訓練，確定與最小誤差相對應的網絡參數（權值和閾值），訓練即告停止。此時經過訓練的神經網絡即能對類似樣本的輸入信息，自行處理輸出誤差最小的經過非線形轉換的信息。
  2. CT圖像重建
• 基本原理：CT圖像重建是通過投影數據重建物體內部結構的過程。常用的算法包括濾波反投影（FBP）算法。FBP算法通過在頻域對投影函數乘上一個高通濾波器來抵消直接反投影算法帶來的誤差，然后進行反投影重建。隨著科技的發展，CT重建算法大致分為傳統重建算法、迭代重建算法和深度學習算法三類。傳統重建算法基于FBP，迭代重建算法根據實時采集到的探測器數據對預測圖像進行迭代優化，而深度學習算法則利用深度學習技術來提高圖像質量和降低輻射劑量。
  3. Floyd算法
• 基本原理：Floyd算法是一種利用動態規劃思想尋找給定加權圖中多源點之間最短路徑的算法。它通過不斷“插點”的方式，更新節點之間的最短路徑。對于節點i和j，若d[i][k] + d[k][j] < d[i][j]，則更新節點i、j之間的距離。該算法適用于APSP（All Pairs Shortest Paths，多源最短路徑），是一種動態規劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法，也要高于執行|V|次SPFA算法。
  4. Topsis算法
• 基本原理：Topsis算法是一種多準則決策分析方法，通過計算每個方案與理想解和負理想解的相對接近度來進行排序。理想解是各指標的最優值，負理想解是各指標的最差值。相對接近度越大，方案越優。
  5. 層次分析法
• 基本原理：層次分析法是一種將復雜問題分解為不同層次，并通過成對比較來確定權重的決策分析方法。它將目標、準則和方案分為不同層次，構建判斷矩陣，并通過特征向量法計算權重，進行一致性檢驗。
  6. 分支定界法
• 基本原理：分支定界法是一種搜索問題的解空間的算法，通過分支和定界來剪枝，避免不必要的搜索。它適用于組合優化問題，能夠找到全局最優解。
  7. 灰色預測
• 基本原理：灰色預測是一種基于灰色系統的預測方法，通過生成灰色模型（如GM(1,1)）來預測系統行為。它適用于小樣本、貧信息的預測問題。
  8. 粒子群算法
• 基本原理：粒子群算法是一種基于群體智能的優化算法，模擬鳥群覓食行為。粒子在搜索空間中飛行，調整自己的位置和速度，向全局最優解靠攏。
  9. 模擬退火算法
• 基本原理：模擬退火算法是一種基于物理退火過程的優化算法，通過模擬金屬退火過程來尋找全局最優解。它允許一定程度的“爬坡”，以跳出局部最優解。
  10. 人口增長模型
• 基本原理：人口增長模型用于描述人口隨時間的增長過程，常見的有指數增長模型和邏輯斯蒂增長模型。指數增長模型假設人口增長率恒定，而邏輯斯蒂增長模型考慮了環境承載力的影響。
  11. 搜索結果和遺傳算法
• 基本原理：遺傳算法是一種基于自然選擇和遺傳機制的優化算法，通過選擇、交叉和變異操作來進化種群，尋找最優解。搜索算法則是一類通過搜索解空間來尋找問題解的算法，包括廣度優先搜索、深度優先搜索等。

03 部分代碼

%BP神經網絡的公路運量的預測 P121  %未debug完
clc  %清屏
clear all;  %清楚內存以加快運算速度
close all;   %關閉當前所有figure圖像
SamNum=20; %樣本的輸入數量為20
TestSamNum=20;%測試樣本數量為20
ForcastSamNum=2; %預測樣本數量為2
HiddenUnitNum=8;%中間層隱節點數量取8
InDim=3;%網絡輸入維度為三
OutDim=2;%網絡輸出為維度為2
%原始數據
%人數（萬人）
sqrs=[20.55 22.44 25.37 27.13 29.45 30.10 30.96 34.06 36.42 38.09 39.13 39.99 41.43 44.59 47.30 52.89 55.73 56.76 79.17 60.63];
%機動車數（萬輛）
sqjdcs=[0.6 0.75 0.85 0.9 1.05 1.35 1.45 1.6 1.7 1.85 2.15 2.2 2.25 2.35 2.5 2.6 2.7 2.85 2.95 3.1];
%公路面積（萬平方千米）
sqglmj=[0.09 0.11 0.11 0.14 0.20 0.23 0.23 0.32 0.32 0.34 0.36 0.36 0.38 0.49 0.56 0.59 0.59 0.67 0.69 0.79];
%公路客運量（萬人）
glkyl=[5126 6217 7730 9145 10460 11387 12353 15750 18304 19836 21024 19490 20433 22598 25107 33442 36836 40548 42927 43462];
%公路貨運量（萬噸）
glhyl=[1237 1379 1385 1399 1663 1714 1834 4322 8132 8936 11099 11203 10524 11115 13320 16762 18673 20724 20803 21804];
p=[sqrs;sqjdcs;sqglmj]; %輸入數據矩陣
t=[glkyl;glhyl];         %目標數據矩陣
[SamIn,minp,maxp,tn,mint,maxt]=premnmx(p,t); %原始樣本對（輸入與輸出）初始化rand('state',sum(100*clock));        %依據系統時鐘種子產生隨機數
NoiseVar=0.01;                       %噪聲強度為0.01（添加噪聲的原因是防止網絡過度擬合）
Noise=NoiseVar*randn(2,SamNum);     %生成噪聲
SamOut=tn+Noise;                  %將噪聲加到輸出樣本上TestSamIn=SamIn;TestOut=SamOut;MaxEpochs=50000;
lr=0.035;
E0=0.65*10^(-3);
W1=0.5*rand(HiddenUnitNum,InDim)-0.1;
B1=0.5*rand(HiddenUnitNum,1)-0.1;
W2=0.5*rand(OutDim,HiddenUnitNum)-0.1;
B2=0.5*rand(OutDim,1)-0.1;
ErrHistory=[];for i=1:MaxEpochsHiddenOut=logsig(W1*SamIn+repmat(B1,1,SamNum));NetWorkOut=W2*HiddenOut+repmat(B2,1,SamNum);Error=SamOut-NetWorkOut;SSE=sumsqr(Error)ErrHistory=[ErrHistory SSE];if SSE<E0,break,endDelta2=Error;Deltal= W2'* Delta2.*HiddenOut.*(1-HiddenOut);dW2=Delta2*HiddenOut';dB2=Delta2*ones(SamNum,1);dW1=Deltal*SamIn';dB1=Deltal*ones(SamNum,1);W2=W2+lr*dW2;B2=B2+lr*dB2;W1=W1+lr*dW1;B1=B1+lr*dB1;
endHiddenOut=logsig(W1*SamIn+repmat(B1,1,TestSamNum));
NetworkOut=W2*HiddenOut+repmat(B2,1,TestSamNum);
a=postmnmx(NetworkOut,mint,maxt);
x=1990:2009;
newk=a(1,:);
newh=a(2,:);
figure;
subplot(2,1,1);plot(x,newk,'r-o',x,glkyl,'b--+');
legend('網絡輸出客運量','實際客運量');
xlabel('年份');ylabel('客運量/萬人');
title('源程序神經網絡客運量學習和測試對比圖');
title('源程序神經網絡貨運量學習和測試對比圖');
subplot(2,1,2);plot(x,newh,'r-o',x,glhyl,'b--+');
legend('網絡輸出貨運量','實際貨運量');
xlabel('年份');ylabel('貨運量/萬噸');%利用訓練好的網絡進行測試
pnew=[73,39  75.55  3.9635  4.097 0.9880  1.0268];
pnewm=tramnmx(pnew,minp,maxp);HiddenOut=logsig(W1*pnew+repmat(B1,1,ForcastSamNum));
anewn=W2*HiddenOut+repmat(B1,1,ForcastSamNum);anew=postmnmx(anewn,mint,maxt);

04 代碼下載

提供了MATLAB的實現代碼，使得用戶可以根據自己的需求進行調整和應用。
MATLAB代碼下載地址