色婷婷中文在线观看视频,青青草原视频精品在线免费观看,亚洲中文在线字幕,亚洲AV无码国产综合专区,成人蜜桃av,777国产偷窥盗摄精品,麻豆蜜桃成人免费视频,东京热一二三区

遺傳算法 - 簡(jiǎn)書(shū)

遺傳算法的理論是根據(jù)達(dá)爾文進(jìn)化論而設(shè)計(jì)出來(lái)的算法: 人類(lèi)是朝著好的方向（最優(yōu)解）進(jìn)化，進(jìn)化過(guò)程中，會(huì)自動(dòng)選擇優(yōu)良基因，淘汰劣等基因。

遺傳算法（英語(yǔ)：genetic algorithm (GA) ）是計(jì)算數(shù)學(xué)中用于解決最佳化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)的，這些現(xiàn)象包括遺傳、突變、自然選擇、雜交等。

搜索算法的共同特征為：

首先組成一組候選解
依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度
根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解
對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解

遺傳算法的一般步驟

my_fitness函數(shù) 評(píng)估每條染色體所對(duì)應(yīng)個(gè)體的適應(yīng)度
升序排列適應(yīng)度評(píng)估值，選出 前 parent_number 個(gè) 個(gè)體作為 待選 parent 種群（適應(yīng)度函數(shù)的值越小越好）
從 待選 parent 種群 中隨機(jī)選擇 2 個(gè)個(gè)體作為父方和母方。
抽取父母雙方的染色體，進(jìn)行交叉，產(chǎn)生 2 個(gè)子代。（交叉概率）
對(duì)子代（parent + 生成的 child）的染色體進(jìn)行變異。（變異概率）
重復(fù)3,4,5步驟，直到新種群（parent_number + child_number）的產(chǎn)生。

循環(huán)以上步驟直至找到滿意的解。

名詞解釋

交叉概率：兩個(gè)個(gè)體進(jìn)行交配的概率。例如，交配概率為0.8，則80%的“夫妻”會(huì)生育后代。
變異概率：所有的基因中發(fā)生變異的占總體的比例。

GA函數(shù)

function [best_fitness, elite, generation, last_generation] = my_ga( ...
    number_of_variables, ...    % 求解問(wèn)題的參數(shù)個(gè)數(shù)
    fitness_function, ...       % 自定義適應(yīng)度函數(shù)名
    population_size, ...        % 種群規(guī)模（每一代個(gè)體數(shù)目）
    parent_number, ...          % 每一代中保持不變的數(shù)目（除了變異）
    mutation_rate, ...          % 變異概率
    maximal_generation, ...     % 最大演化代數(shù)
    minimal_cost ...            % 最小目標(biāo)值（函數(shù)值越小，則適應(yīng)度越高）
)

% 累加概率
% 假設(shè) parent_number = 10
% 分子 parent_number??1 用于生成一個(gè)數(shù)列
% 分母 sum(parent_number??1) 是一個(gè)求和結(jié)果（一個(gè)數(shù)）
%
% 分子 10     9     8     7     6     5     4     3     2     1
% 分母 55
% 相除 0.1818    0.1636    0.1455    0.1273    0.1091    0.0909    0.0727    0.0545    0.0364    0.0182
% 累加 0.1818    0.3455    0.4909    0.6182    0.7273    0.8182    0.8909    0.9455    0.9818    1.0000
%
% 運(yùn)算結(jié)果可以看出
% 累加概率函數(shù)是一個(gè)從0到1增長(zhǎng)得越來(lái)越慢的函數(shù)
% 因?yàn)楹竺婕拥母怕试絹?lái)越小（數(shù)列是降虛排列的）
cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); % 1個(gè)長(zhǎng)度為parent_number的數(shù)列

% 最佳適應(yīng)度
% 每一代的最佳適應(yīng)度都先初始化為1
best_fitness = ones(maximal_generation, 1);

% 精英
% 每一代的精英的參數(shù)值都先初始化為0
elite = zeros(maximal_generation, number_of_variables);

% 子女?dāng)?shù)量
% 種群數(shù)量 - 父母數(shù)量（父母即每一代中不發(fā)生改變的個(gè)體）
child_number = population_size - parent_number; % 每一代子女的數(shù)目

% 初始化種群
% population_size 對(duì)應(yīng)矩陣的行，每一行表示1個(gè)個(gè)體，行數(shù)=個(gè)體數(shù)（種群數(shù)量）
% number_of_variables 對(duì)應(yīng)矩陣的列，列數(shù)=參數(shù)個(gè)數(shù)（個(gè)體特征由這些參數(shù)表示）
population = rand(population_size, number_of_variables);

last_generation = 0; % 記錄跳出循環(huán)時(shí)的代數(shù)


% 后面的代碼都在for循環(huán)中
for generation = 1 : maximal_generation % 演化循環(huán)開(kāi)始
    
    % feval把數(shù)據(jù)帶入到一個(gè)定義好的函數(shù)句柄中計(jì)算
    % 把population矩陣帶入fitness_function函數(shù)計(jì)算
    cost = feval(fitness_function, population); % 計(jì)算所有個(gè)體的適應(yīng)度（population_size*1的矩陣）

    % index記錄排序后每個(gè)值原來(lái)的行數(shù)
    [cost, index] = sort(cost); % 將適應(yīng)度函數(shù)值從小到大排序

    % index(1:parent_number) 
    % 前parent_number個(gè)cost較小的個(gè)體在種群population中的行數(shù)
    % 選出這部分(parent_number個(gè))個(gè)體作為父母，其實(shí)parent_number對(duì)應(yīng)交叉概率
    population = population(index(1:parent_number), :); % 先保留一部分較優(yōu)的個(gè)體
    % 可以看出population矩陣是不斷變化的

    % cost在經(jīng)過(guò)前面的sort排序后，矩陣已經(jīng)改變?yōu)樯虻?/span>
    % cost(1)即為本代的最佳適應(yīng)度
    best_fitness(generation) = cost(1); % 記錄本代的最佳適應(yīng)度

    % population矩陣第一行為本代的精英個(gè)體
    elite(generation, :) = population(1, :); % 記錄本代的最優(yōu)解（精英）

    % 若本代的最優(yōu)解已足夠好，則停止演化
    if best_fitness(generation) < minimal_cost; 
        last_generation = generation;
        break; 
    end
    
    % 交叉變異產(chǎn)生新的種群

    % 染色體交叉開(kāi)始
    for child = 1:2:child_number % 步長(zhǎng)為2是因?yàn)槊恳淮谓徊鏁?huì)產(chǎn)生2個(gè)孩子
        
        % cumulative_probabilities長(zhǎng)度為parent_number
        % 從中隨機(jī)選擇2個(gè)父母出來(lái)  (child+parent_number)%parent_number
        mother = find(cumulative_probabilities > rand, 1); % 選擇一個(gè)較優(yōu)秀的母親
        father = find(cumulative_probabilities > rand, 1); % 選擇一個(gè)較優(yōu)秀的父親
        
        % ceil（天花板）向上取整
        % rand 生成一個(gè)隨機(jī)數(shù)
        % 即隨機(jī)選擇了一列，這一列的值交換
        crossover_point = ceil(rand*number_of_variables); % 隨機(jī)地確定一個(gè)染色體交叉點(diǎn)
        
        % 假如crossover_point=3, number_of_variables=5
        % mask1 = 1     1     1     0     0
        % mask2 = 0     0     0     1     1
        mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];
        mask2 = not(mask1);
        
        % 獲取分開(kāi)的4段染色體
        % 注意是 .*
        mother_1 = mask1 .* population(mother, :); % 母親染色體的前部分
        mother_2 = mask2 .* population(mother, :); % 母親染色體的后部分
        
        father_1 = mask1 .* population(father, :); % 父親染色體的前部分
        father_2 = mask2 .* population(father, :); % 父親染色體的后部分
        
        % 得到下一代
        population(parent_number + child, :) = mother_1 + father_2; % 一個(gè)孩子
        population(parent_number+child+1, :) = mother_2 + father_1; % 另一個(gè)孩子
        
    end % 染色體交叉結(jié)束
    
    
    % 染色體變異開(kāi)始
    
    % 變異種群
    mutation_population = population(2:population_size, :); % 精英不參與變異，所以從2開(kāi)始
    
    number_of_elements = (population_size - 1) * number_of_variables; % 全部基因數(shù)目
    number_of_mutations = ceil(number_of_elements * mutation_rate); % 變異的基因數(shù)目（基因總數(shù)*變異率）
    
    % rand(1, number_of_mutations) 生成number_of_mutations個(gè)隨機(jī)數(shù)(范圍0-1)組成的矩陣(1*number_of_mutations)
    % 數(shù)乘后，矩陣每個(gè)元素表示發(fā)生改變的基因的位置（元素在矩陣中的一維坐標(biāo)）
    mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 確定要變異的基因
    
    % 被選中的基因都被一個(gè)隨機(jī)數(shù)替代，完成變異
    mutation_population(mutation_points) = rand(1, number_of_mutations); % 對(duì)選中的基因進(jìn)行變異操作
    
    population(2:population_size, :) = mutation_population; % 發(fā)生變異之后的種群
    
    % 染色體變異結(jié)束
   
end % 演化循環(huán)結(jié)束

適應(yīng)度函數(shù)

適應(yīng)度函數(shù)由解決的問(wèn)題決定。舉一個(gè)平方和的例子。

求函數(shù)的最小值，其中每個(gè)變量的取值區(qū)間都是 [-1, +1]。問(wèn)題的最優(yōu)解：每個(gè) x_i 都等于0。

function y = my_fitness(population)
% population是隨機(jī)數(shù)[0,1]矩陣，下面的操作改變范圍為[-1,1]
population = 2 * (population - 0.5); 
y = sum(population.^2, 2); % 行的平方和

測(cè)試

clear; 
close all;

% 調(diào)用 my_ga 進(jìn)行計(jì)算
% 求解問(wèn)題的參數(shù)個(gè)數(shù)         10
% 自定義適應(yīng)度函數(shù)名         my_fitness
% 種群規(guī)模                  100
% 每一代中保持不變的數(shù)目     50 (即交叉率0.5)
% 變異概率                  0.1 (1/10的個(gè)體發(fā)生變異)
% 最大演化代數(shù)              10000 10000代
% 最小目標(biāo)值                1.0e-6 個(gè)體適應(yīng)度函數(shù)值 < 0.000001結(jié)束
[best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);


% 輸出后10行
% disp(best_fitness(9990:10000,:));
% disp(elite(9990:10000,:))
% 這樣是不合適的，因?yàn)镚A常常在中間就跳出循環(huán)了

% 這樣才是合適的輸出
disp(last_generation); 
i_begin = last_generation - 9;
disp(best_fitness(i_begin:last_generation,:));
% 將elite值轉(zhuǎn)化為問(wèn)題范圍內(nèi)
my_elite = elite(i_begin:last_generation,:);
my_elite = 2 * (my_elite - 0.5);
disp(my_elite);

% 最佳適應(yīng)度的演化情況
figure
loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
xlabel('Generation','fontsize',15);
ylabel('Best Fitness','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

% 最優(yōu)解的演化情況
figure
semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
xlabel('Generation','fontsize',15);
ylabel('Best Solution','fontsize',15);
set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);

輸出

注意：這些值都是不確定的。

>> test_ga
        2035 // last_generation 跳出循環(huán)

   // best_fitness 后10行
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.268244559363828
   0.063540829423325

  // elite 后10行，最后一行為想要的解
  Columns 1 through 7

  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849
  -0.000383439136218  -0.000401508032900   0.000097444596325   0.000337256996077  -0.000064973174152   0.000120384223563   0.000117039829849

  Columns 8 through 10

  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.001433818552852   0.000176675571817
  -0.000362645135942  -0.000093799483467   0.000176675571817