# [psdm] メタヒューリスティクス
###### tags: `2022-4Q` `東工大` `psdm`

**heuristic**，啟發法。
**metaheuristic**，[元啟發算法](https://zh.wikipedia.org/zh-tw/%E5%85%83%E5%90%AF%E5%8F%91%E7%AE%97%E6%B3%95)。

[toc]
## 多スタート局所探索法
**multi-start local search**; MLS

**給多個初期解**，各自套用**局部探索法**得出多組局部最佳解，再從其中找出值最佳的 local minimum。

- 透過**隨機生成**的解的初期值來實行的，稱為 **randomized multi-start local search**。
- 進一步的，考慮光是隨機生成初期解的話，選到的常會是品質低劣的解（e.g. 要畫什麼賺流量？隨機生成的答案：畫蘋果），所以套用**貪婪算法**並生成複數個初期解，這稱為 **greedy randomized adaptive procedure(GRASP)**。
- 和其他方法相比
- 不參考過去的探索經歷，而是以當下生成的初期解為起點開始探索
- 傾向：經過一定次數的迭代之後，暫定解會變得較難更新

## 反復局所探索法
**iterated local search**; ILS

- 取**先前的探索之中所得出的良解**為初期值，加上隨機值（或隨機函數稍微擾動它的位置）去變形它（i.e. 改變它的值），再套用局部探索法去收斂到一個新的最佳解。
- 變形策略：
- **可變近旁探索法**（**variable neighbor search**; VNS）：適應性地調整暫定解「附近」的範圍定義，以取得合適的（不會收斂回起點的暫定解的）隨機值的手法。隨機值從小取到大，直到出來的解不會再收斂回起點，便更新暫定解。
## アニーリング法
退火法，[焼きなまし法](https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95)，simulated annealing; SA

## タブー探索法(tabu search)
[**禁忌搜索**](https://zh.wikipedia.org/zh-tw/%E7%A6%81%E5%BF%8C%E6%90%9C%E7%B4%A2)，[タブーサーチ](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%96%E3%83%BC%E3%82%B5%E3%83%BC%E3%83%81)，TS。
- 精神：
- 用來跳脫局部最佳解的搜索方法
- ？

## Marine-Predators-Algorithm

- Random walk strategy
- [Lévy flight](https://en.wikipedia.org/wiki/L%C3%A9vy_flight)/walk: 在獵物稀缺的狩獵場的移動模式。單向 travel 比較遠，較少折返回去過的地方。因為獵物少，所以走得比較遠（還是比較快？）。
- PDF: 

- https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2516217/
- Brownian movement: 獵物豐腴的獵場的移動模式。比較兜圈子，反覆徘徊在獵物聚集的這個場域的感覺。
- [介紹與分析此 motion 的參考書（？）](https://www.stat.berkeley.edu/~aldous/205B/bmbook.pdf)
- probability density function: https://stats.libretexts.org/Bookshelves/Probability_Theory/Probability_Mathematical_Statistics_and_Stochastic_Processes_(Siegrist)/18%3A_Brownian_Motion/18.01%3A_Standard_Brownian_Motion
> Lévy behaviour to be associated with less productive waters (sparser prey) and Brownian movements to be associated with productive shelf or convergence-front habitats (abundant prey).
- The family of such search strategies describes a movement, characterized by many small steps associated with longer relocations which are drawn from a probability distribution with a **power-law** tail
- 記住掠食成功的區域
- 考慮海流（Eddy）跟人類的影響（FADs effect）
- [Matlab](https://jp.mathworks.com/matlabcentral/fileexchange/74578-marine-predators-algorithm-mpa)
- paper: https://www.sciencedirect.com/science/article/abs/pii/S0957417420302025
- [GitHub](https://github.com/afshinfaramarzi/Marine-Predators-Algorithm)

### 特徵
- Non-Gradient Based Optimization: [含相關介紹的論文](https://www.researchgate.net/publication/348732530_Non-Gradient_Based_Optimization)

### 應用例子
- [工程力學](https://zh.wikipedia.org/wiki/%E5%B7%A5%E7%A8%8B%E5%8A%9B%E5%AD%A6)
- 2021, [Marine predators' algorithm: Application in applied mechanics](https://www.researchgate.net/publication/355974118_Marine_predators%27_algorithm_Application_in_applied_mechanics)
- 可用的最佳化例：pressure vessel optimization（壓力容器優化）, cantilever beam optimization（懸臂樑優化）, cone clutch optimization（錐形離合器優化） and speed reducer optimization（減速器優化）
### Algorithm
0. 初期值設定
1) 要放出幾隻掠食者，獵到最多獵物的會是 Top predator
2)
1. 迭代的前、中、後期，分別用以下 random walk 模式來決定步長，以尋找最佳解：
1) phase 1: 全是以 Levy 模式移動。
2) phase 2: 半 Levy 半 Brownian。
3) phase 3: 全 Brownian。

:::warning
解如何收斂？
:::
2. 擾動：洋流和人類影響解（狩獵者）的所在位置。
3. 記憶：儲存目前找到的 best solution（Top predator position）不過儲存下來如何利用？
4. 停止條件：迭代次數到達上限，或得到滿足給定條件的可行解。
5. 輸出：
- Top predator position (i.e. best solution)
- corresponding fitness (`Top_predator_fit`)：最佳掠食者的適應性評分。（是什麼的值？）
- convergence curve (`Convergence_curve`)：收斂曲線。（這是啥）

### 變數名稱意義
- `ub`: upper bound
- `lb`: lower bound
- `fitness`: 適應性函數。用來評價 search agent 的所在位置（i.e. 解）的好壞，其實就是代入了 `Prey` 的 objective function 值。
- `Prey`：search agent 的位置。可以想成他們的位置就相當於（他們正在咀嚼的）獵物的位置。
- `fobj`：目標函數。

### `MPA.m`

%_________________________________________________________________________
%  Marine Predators Algorithm source code (Developed in MATLAB R2015a)
%
%  programming: Afshin Faramarzi & Seyedali Mirjalili
%
% paper:
%  A. Faramarzi, M. Heidarinejad, S. Mirjalili, A.H. Gandomi, 
%  Marine Predators Algorithm: A Nature-inspired Metaheuristic
%  Expert Systems with Applications
%  DOI: doi.org/10.1016/j.eswa.2020.113377
%  
%  E-mails: [e-mail]            (Afshin Faramarzi)
%           [e-mail]                   (Mohammad Heidarinejad)
%           [e-mail]    (Seyedali Mirjalili) 
%           [e-mail]               (Amir H Gandomi)
%_________________________________________________________________________
function [Top_predator_fit,Top_predator_pos,Convergence_curve]=MPA(SearchAgents_no,Max_iter,lb,ub,dim,fobj)
Top_predator_pos=zeros(1,dim);
Top_predator_fit=inf; 
Convergence_curve=zeros(1,Max_iter);
stepsize=zeros(SearchAgents_no,dim);
fitness=inf(SearchAgents_no,1);
Prey=initialization(SearchAgents_no,dim,ub,lb);
  
Xmin=repmat(ones(1,dim).*lb,SearchAgents_no,1);
Xmax=repmat(ones(1,dim).*ub,SearchAgents_no,1);
         
Iter=0;
FADs=0.2;
P=0.5;
while Iter<Max_iter    
     %------------------- Detecting top predator -----------------    
 for i=1:size(Prey,1)  
        
    Flag4ub=Prey(i,:)>ub;
    Flag4lb=Prey(i,:)<lb;    
    Prey(i,:)=(Prey(i,:).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb;                    
        
    fitness(i,1)=fobj(Prey(i,:));
                     
     if fitness(i,1)<Top_predator_fit 
       Top_predator_fit=fitness(i,1); 
       Top_predator_pos=Prey(i,:);
     end          
 end
     
     %------------------- Marine Memory saving ------------------- 
    
 if Iter==0
   fit_old=fitness;    Prey_old=Prey;
 end
     
  Inx=(fit_old<fitness);
  Indx=repmat(Inx,1,dim);
  Prey=Indx.*Prey_old+~Indx.*Prey;
  fitness=Inx.*fit_old+~Inx.*fitness;
        
  fit_old=fitness;    Prey_old=Prey;
     %------------------------------------------------------------   
     
 Elite=repmat(Top_predator_pos,SearchAgents_no,1);  %(Eq. 10) 
 CF=(1-Iter/Max_iter)^(2*Iter/Max_iter);
                             
 RL=0.05*levy(SearchAgents_no,dim,1.5);   %Levy random number vector
 RB=randn(SearchAgents_no,dim);          %Brownian random number vector
           
  for i=1:size(Prey,1)
     for j=1:size(Prey,2)        
       R=rand();
          %------------------ Phase 1 (Eq.12) ------------------- 
       if Iter<Max_iter/3 
          stepsize(i,j)=RB(i,j)*(Elite(i,j)-RB(i,j)*Prey(i,j));                    
          Prey(i,j)=Prey(i,j)+P*R*stepsize(i,j); 
             
          %--------------- Phase 2 (Eqs. 13 & 14)----------------
       elseif Iter>Max_iter/3 && Iter<2*Max_iter/3 
          
         if i>size(Prey,1)/2
            stepsize(i,j)=RB(i,j)*(RB(i,j)*Elite(i,j)-Prey(i,j));
            Prey(i,j)=Elite(i,j)+P*CF*stepsize(i,j); 
         else
            stepsize(i,j)=RL(i,j)*(Elite(i,j)-RL(i,j)*Prey(i,j));                     
            Prey(i,j)=Prey(i,j)+P*R*stepsize(i,j);  
         end  
         
         %----------------- Phase 3 (Eq. 15)-------------------
       else 
           
           stepsize(i,j)=RL(i,j)*(RL(i,j)*Elite(i,j)-Prey(i,j)); 
           Prey(i,j)=Elite(i,j)+P*CF*stepsize(i,j);  
    
       end  
      end                                         
  end    
        
     %------------------ Detecting top predator ------------------        
  for i=1:size(Prey,1)  
        
    Flag4ub=Prey(i,:)>ub;  
    Flag4lb=Prey(i,:)<lb;  
    Prey(i,:)=(Prey(i,:).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb;
  
    fitness(i,1)=fobj(Prey(i,:));
        
      if fitness(i,1)<Top_predator_fit 
         Top_predator_fit=fitness(i,1);
         Top_predator_pos=Prey(i,:);
      end     
  end
        
     %---------------------- Marine Memory saving ----------------
    
 if Iter==0
    fit_old=fitness;    Prey_old=Prey;
 end
     
    Inx=(fit_old<fitness);
    Indx=repmat(Inx,1,dim);
    Prey=Indx.*Prey_old+~Indx.*Prey;
    fitness=Inx.*fit_old+~Inx.*fitness;
        
    fit_old=fitness;    Prey_old=Prey;
     %---------- Eddy formation and FADs� effect (Eq 16) ----------- 
                             
  if rand()<FADs
     U=rand(SearchAgents_no,dim)<FADs;                                                                                              
     Prey=Prey+CF*((Xmin+rand(SearchAgents_no,dim).*(Xmax-Xmin)).*U);
  else
     r=rand();  Rs=size(Prey,1);
     stepsize=(FADs*(1-r)+r)*(Prey(randperm(Rs),:)-Prey(randperm(Rs),:));
     Prey=Prey+stepsize;
  end
                                                        
  Iter=Iter+1;  
  Convergence_curve(Iter)=Top_predator_fit; 
       
end

> 來源：https://jp.mathworks.com/matlabcentral/fileexchange/74578-marine-predators-algorithm-mpa

:::spoiler ChatGPT 的解讀：
各個段落：
1. Detecting top predator：identifying the best solution in the population of search agents (Prey).
- 評價每個 search agent 的適應性（fitness），並和當前最佳 `Top_predator_fit` 做比較。
- 如果一隻 search agent 有比當前最高分更高分的適應性，則它會成為 Top predator。其位置與適應性分別更新到 `Top_predator_pos` 和 `Top_predator_fit`

2. Marine Memory saving：a mechanism to remember the best solutions found so far.
- If `Iter` is equal to 0, the fitness and position of each search agent is stored in fit\_old and Prey\_old, respectively.
- In subsequent iterations, the better solutions between the current iteration and the previous iteration are selected and stored in Prey and fitness.

3. Eddy formation and FADs effect：updates the position of each search agent.
- 根據洋流與人類影響更新 search agent 的位置（給原位置加上某種擾動）
- CF
- 計算各個維度的步長。
- `FADs`：控制搜尋過程中的環境效果。

各個函數：
1. "`fitness=inf(SearchAgents_no,1);`" 創造一個 SearchAgents\_no 行，1 列的矩陣，每一個元素都是無限大 (inf)。
2. "`Convergence_curve=zeros(1,Max_iter)`;" 創造一個 1 行，Max\_iter 列的矩陣，每一個元素都是 0。Convergence\_curve 被用來記錄收斂曲線。
3. "Xmin=repmat(ones(1,dim).\*lb,SearchAgents\_no,1); Xmax=repmat(ones(1,dim).\*ub,SearchAgents\_no,1);" 創造了兩個矩陣：Xmin 和 Xmax。Xmin 是一個 SearchAgents\_no 行，dim 列的矩陣，每一個元素都等於 lb。Xmax 是一個 SearchAgents\_no 行，dim 列的矩陣，每一個元素都等於 ub。
4. "`repmat`" 函數的功用是重複複製一個矩陣的每一行或每一列。
5. "`fitness(i,1)=fobj(Prey(i,:));`" 呼叫 `fobj` 函數，並用回傳值更新 fitness 矩陣的第 i 行第一列的元素。

:::