【MATLAB】應用基因演算法(二):找尋正確字串

  • 1321
  • 0
  • GA
  • 2018-12-26

接續上一篇,我們已經學會該怎麼用 GA 來搜尋 Peaks 函數的最小值。
而本篇主要是介紹該如何使用 GA 來找出目標字串。

一步一步來。
上一篇若是沒看過,以下附上連結:
【MATLAB】應用基因演算法(一):Peaks 函數求極值

假定我們今天要找的字串叫做:

'Hello GA~ >w<'

夏恩先給他一個變數名稱,姑且叫做目標字串(TargStr)吧。

TargStr = 'Hello GA~ >w<';

我們可以先把這個字串可視化,請參閱下圖:

>> plot(double(TargStr), 'LineWidth', 2, 'Color', 'b')

再來是設定一些基本參數。

1. 變數數量

變數的數量就是字串長度。

VarNumber = numel(TargStr);

2. 上下邊界

在我們的設想中,目標字串內的字元的編碼大概是落在 32~127 之間。
呃......夏恩應該不需要把編碼表貼上來對吧!?

好吧,ASCII 邊碼表如下:

圖片來源:Excel-製作ASCII碼對照表

所以我們先對上下邊界進行設定:

% 上下邊界設定
% 注意:空白鍵的代碼是 32 ,所以下邊界從 32 開始。 
lb = zeros(1, VarNumber)+32;
ub = zeros(1, VarNumber)+127;

3. 目標函數

夏恩設計的函數是 比較目標字串與 GA 染色體之間的相似程度,使用向量相減後取絕對值。

function scores = FitnessFcn(x, TargStr)
%% 適應函數

% 把目標字串轉換成 double 一維向量
TS = double(TargStr);

% GA 染色體與目標字串相減取絕對值,作為評分標準。
% 其分數愈接近 0 ,表示愈接近目標字串。
scores = sum(abs(x-TS));

end

請注意這個目標函數,由於我們必須告訴該函數「目標字串」是什麼,這樣才能計算適應值。
於是乎,這裡就需要第二個輸入值。

可是 GA 的目標函數只能有一個 x 作為輸入值不是嗎?

對,所以接著要使用匿名函數來代入參數的技巧,如下。

fitfcn = @(x) FitnessFcn(x, TargStr);

這樣就能保持原本的格式,又能代入所需的參數。

順帶一提,為什麼要用相減取絕對值,而不是用字串比較?像是這樣:

scores = sum( x == TS );

不採用上述方法的原因是:
只給定「對」或「錯」的話,最佳化演算法會不知道該往哪個方向繼續尋找最佳解。
若我們給的是一個距離,演算法就能明確地知道該往哪個方向收斂。

依照夏恩的經驗,給定距離的收斂速度遠大於只判定對錯值喔!

4. 繪圖函數

我們希望能看到最佳化過程中發生了什麼事情,這就需要我們自己設計繪圖函數了。
這件事對大家應該不陌生,畢竟上一篇 GA 文也做過這件事情。

function state = myPlot(options, state, flag, TargStr)
%% 自定繪圖函數,畫出每次迭代的結果。

% 叫出目前最佳的適應函數值
[~, i] = min(state.Score);
X = state.Population(i, :);

% 清空上一張圖
cla

% 繪製目標函數圖形
plot(double(TargStr), 'Color', 'b', 'LineWidth', 2)

% 把目前適應函數值,疊到同一張圖面上
hold on
plot(X, 'Color', 'r', 'LineWidth', 2, 'LineStyle', '--')

% 於標題展示目前最佳化結果
title(['Tar:', TargStr, '  /  Pred:', cellfun(@char, num2cell(X))])

% 坐標軸設定
axis([0, numel(TargStr)+1, 0, 150])

% 即時顯示
drawnow

end

同樣地,這個繪圖函數也需要輸入額外的參數,所以再次使用匿名函數的技巧。

my_plot = @(options, state, flag) myPlot(options, state, flag, TargStr);

5. GA 選項設定

最後一個參數設定就是 GA 的選項,我們直接透過 optimoptions 來完成。

options = optimoptions('ga', ...                       % 最佳化算法
                       'PopulationSize', 50, ...       % 染色體數量
                       'MaxGenerations', 500, ...      % 最大繁衍代數
                       'MaxStallGenerations', 100, ... % 最大停滯代數
                       'PlotFcn', my_plot, ...         % 自定義繪圖函數
                       'Display', 'iter');   

好的,到這邊,參數設定完畢,最後啟動 GA 就可以看到結果了。

6. 執行 GA 

x = ga(fitfcn, VarNumber, [], [], [], [], lb, ub, [], 1:VarNumber, options);

 以下為程式執行結果:

小結

找尋正確字串的功能乍看之下似乎有點不明所以。
若您有相關實作 GA 的經驗,其實這是重複排列的相關命題。

如同本範例,總共有 13 個輸入變數,每個變數的範圍界於 32~127 之間,共 96 個。
於是可以算出來全部有 96^13 種排列方式。

在現實中的重複排列之應用問題,通常不會是數學課本中那種:

郵差有 7 封信要寄送,隨意投入 3 個郵箱,請問有多少種投遞法?
答:我要投訴這個郵差!!!

重複排列常會用在裝車、裝箱、裝櫃的問題上面:

現在有五種貨品要準備上貨櫃,貨櫃內有 20 位置,又每個貨品大小重量皆不同。
請問該怎麼裝哪些貨物,才能達到最大載重?

這才是我們現實中要解決的問題!
好啦,解釋完畢~

下一篇文章來討論直線排列,也就是旅行者問題。
比起重複排列,直線排列更簡單,也更讓人熟悉。

但是愈簡單,也就愈困難,請接著看。
【MATLAB】應用基因演算法(三):高效率的送貨員

附錄

%% GA 範例程式
% 功能:找目標字串
%
% 2018.07.08, Shayne.

TargStr = 'Hello GA~ >w<';
VarNumber = numel(TargStr);

lb = zeros(1, VarNumber)+32;
ub = zeros(1, VarNumber)+127;

fitfcn = @(x) FitnessFcn(x, TargStr);
my_plot = @(options, state, flag) myPlot(options, state, flag, TargStr);

options = optimoptions('ga', ...
                       'PopulationSize', 50, ...
                       'MaxGenerations', 500, ...
                       'MaxStallGenerations', 100, ...
                       'PlotFcn', my_plot, ...
                       'Display', 'iter');   
                   
x = ga(fitfcn, VarNumber, [], [], [], [], lb, ub, [], 1:VarNumber, options);

function scores = FitnessFcn(x, TargStr)
    TS = double(TargStr);
    scores = sum(abs(x-TS));
end

function state = myPlot(options, state, flag, TargStr)
    [~, i] = min(state.Score);
    X = state.Population(i, :);

    cla
    plot(double(TargStr), 'Color', 'b', 'LineWidth', 2)

    hold on
    plot(X, 'Color', 'r', 'LineWidth', 2, 'LineStyle', '--')

    title(['Tar:', TargStr, '  /  Pred:', cellfun(@char, num2cell(X))])
    axis([0, numel(TargStr)+1, 0, 150])
    drawnow
end