使用值編碼的遺傳算法初始種子多樣性C＃

Question

我想知道以下內容： 如何使用值編碼有效地初始生成具有高度多樣性的染色體？ 一種方法是網格初始化，但速度太慢。直到現在，我一直使用.NET中的隨機類來選擇值編碼中的隨機值，但儘管值是均勻分佈的，但從這些染色體計算得到的適應度函數值卻不是。下面是染色體的初始化代碼：

public Chromosome(Random rand) 
     { 
      Alele = new List<double>(); 
      for (int i = 0; i < ChromosomeLength; i++) 
      { 
       Alele.Add(rand.NextDouble() * 2000 - 1000); 
      } 
     } 

所以，我開發了計算來自新的，隨機做出染色體（上代碼）的健身功能，如果健身是類似於任何其他已經在染色體，一個列表新的染色體是隨機生成的，他的適應度被計算出來，並且這個過程重複進行，直到他的適應度與列表中已有的適應度相差不足。

下面是這部分的代碼：

private bool CheckSimilarFitnes(List<Chromosome> chromosome, Chromosome newCandidate) 
    { 
    Boolean flag=false; 
    double fitFromList, fitFromCandidate; 
    double fitBigger,fitSmaller; 

    foreach (var listElement in chromosome) 
     { 
     fitFromList = listElement.CalculateChromosomeFitness(listElement.Alele); 
     fitFromCandidate = newCandidate.CalculateChromosomeFitness(newCandidate.Alele); 
     fitBigger = fitFromList >= fitFromCandidate ? fitFromList : fitFromCandidate; 
     fitSmaller = fitFromList < fitFromCandidate ? fitFromList : fitFromCandidate; 

      if ((fitFromList/fitFromCandidate) < 1.5) 
       return false 
     } 

    else return true; 

    } 

但是，更多的染色體我有需要更長的時間來添加一個新的列表，還設有健身是從別人已經在那裏足夠的不同。

那麼，有沒有辦法讓這個網格初始化更快，需要幾天時間來製作80個這樣的染色體？

Answer 1

這裏有一些代碼可能有幫助（我剛剛寫道）：GA for ordering 10 values spaced by 1.0。它從100個完全隨機的等位基因開始，這正是您的代碼開始的方式。

我給GA解決的目標是按遞增順序對值進行排序，間隔爲1.0。它在適應函數Eval_OrderedDistance中通過計算每對樣本的標準偏差從1.0開始。當適應度趨於0.0時，等位基因應開始按順序出現。

0代的最適合的染色體是完全隨機的，其餘的染色體也是如此。你可以看到鍛鍊價值是非常高的（即壞）：

GEN: fitness (allele, ...) 
    0: 375.47460 (583.640, -4.215, -78.418, 164.228, -243.982, -250.237, 354.559, 374.306, 709.859, 115.323) 

隨着世代延續，健身（標準差1.0）下降，直到它幾乎是完美的一代100000：

100: 68.11683 (-154.818, -173.378, -170.846, -193.750, -198.722, -396.502, -464.710, -450.014, -422.194, -407.162) 
    ... 
10000: 6.01724 (-269.681, -267.947, -273.282, -281.582, -287.407, -293.622, -302.050, -307.582, -308.198, -308.648) 
    ... 
99999: 0.67262 (-294.746, -293.906, -293.114, -292.632, -292.596, -292.911, -292.808, -292.039, -291.112, -290.928) 

代碼的有趣的部分是適應度函數：

// try to pack the aleles together spaced apart by 1.0 
// returns the standard deviation of the samples from 1.0 
static float Eval_OrderedDistance(Chromosome c) { 
    float sum = 0; 
    int n = c.alele.Length; 
    for(int i=1; i<n; i++) { 
     float diff = (c.alele[i] - c.alele[i-1]) - 1.0f; 
     sum += diff*diff; // variance from 1.0 
    } 

    return (float)Math.Sqrt(sum/n); 
} 

而突變。我用一個簡單的交叉和一個「完全變異一個等位基因」：

Chromosome ChangeOne(Chromosome c) { 
    Chromosome d = c.Clone(); 
    int i = rand.Next() % d.alele.Length; 
    d.alele[i] = (float)(rand.NextDouble()*2000-1000); 
    return d; 
} 

我用精英主義始終保持最好的染色體的一個完全相同的副本。然後使用突變和交叉產生100個新的染色體。

這聽起來像是你正在計算健身的方差，當然這會告訴你，你的人口的適合度都差不多。我發現它是非常重要重要的是你如何定義你的健身功能。適應度函數越精細，就越能區分染色體。顯然，由於你的gen 0返回的適應性方差爲68e-19，所以你的適應度函數返回的是完全不同的染色體的相似值。

你能分享你的健身計算嗎？或者您要求GA解決什麼問題？我認爲這可能會幫助我們幫助你。

[編輯：添加顯式健身共享/小生境]

我重新考慮這一點，並updated my code。如果你想保持獨特的染色體，你必須比較它們的內容（如其他人所提到的）。一種方法是計算它們之間的標準偏差。如果它低於某個閾值，則可以認爲它們相同。來自類染色體：

// compute the population standard deviation 
public float StdDev(Chromosome other) { 
    float sum = 0.0f; 
    for(int i=0; i<alele.Length; i++) { 
     float diff = other.alele[i] - alele[i]; 
     sum += diff*diff; 
    } 
    return (float)Math.Sqrt(sum); 
} 

我認爲Niching會給你你想要的。它比較人羣中的所有染色體以確定它們的相似性，併爲每個染色體分配一個「利基」值。然後使用稱爲顯式健身分享的技術來對屬於利基的染色體進行「處罰」。適應值除以每個生態位中的染色體數量。因此，如果您有三個小組（A，A，A），而不是該小生選擇的可能性的3倍，則將其視爲單個實體。

我比較了我的示例與顯式健身共享的開啓和關閉。最大STDDEV爲500，Niching爲OFF時，大約有18-20個生態位（基本上每100個人口中有5個重複項）。隨着Niching開啓，大約有85個壁龕。這就是人口中85％獨特的染色體。在我的測試輸出中，您可以看到diversity after 17000 generations。

這裏的小生境代碼：

// returns: total number of niches in this population 
// max_stddev -- any two chromosomes with population stddev less than this max 
//    will be grouped together 
int ComputeNiches(float max_stddev) { 
    List<int> niches = new List<int>(); 

    // clear niches 
    foreach(var c in population) { 
     c.niche = -1; 
    } 

    // calculate niches 
    for(int i=0; i<population.Count; i++) { 
     var c = population[i]; 
     if(c.niche != -1) continue; // niche already set 

     // compute the niche by finding the stddev between the two chromosomes 
     c.niche = niches.Count; 
     int count_in_niche = 1; // includes the curent Chromosome 
     for(int j=i+1; j<population.Count; j++) { 
      var d = population[j]; 
      float stddev = c.StdDev(d); 
      if(stddev < max_stddev) { 
       d.niche = c.niche; // same niche 
       ++count_in_niche; 
      } 
     } 
     niches.Add(count_in_niche); 
    } 

    // penalize Chromosomes by their niche size 
    foreach(var c in population) { 
     c.niche_scaled_fitness = c.scaled_fitness/niches[c.niche]; 
    } 

    return niches.Count; 
} 

[編輯：安東的代碼後的分析和更新]

我知道這可能不是解決家庭作業問題的適當論壇，但因爲在做這件事之前我做了一些努力，而且我做了很多樂趣，所以我認爲這隻對Anton有幫助。

Genotip.cs，Kromosom.cs，KromoMain.cs

此代碼保持良好的多樣性，以及我能在一個運行獲得「原始適應」下調至47，這是你的情況的均方誤差。那非常接近！

正如我在評論中指出的那樣，我想嘗試在編程中幫助你，而不僅僅是幫助你做家庭作業。請閱讀這些工作分析。

1. 正如我們預料的那樣，從一開始就沒有必要創造一個「更多元化」的人口。只需生成一些完全隨機的染色體。

2. 你的突變和交叉是非常具有破壞性的，你只有其中的幾個。我添加了幾個新的運營商，似乎更好地解決了這個問題。

3. 你扔掉了最好的解決方案。當我的代碼只運行錦標賽選擇時，會有一個Kromo比其他所有的都好99％。選擇錦標賽時，最有價值的東西很可能會被遺忘。我加了一點「精英主義」，爲下一代保留了這個價值的副本。

4. 考慮面向對象技術。比較我寫給你的原始代碼的重寫。

5. 請勿複製代碼。您有兩個不同類別的採樣參數。

6. 保持您的代碼清潔。有幾個未使用的代碼部分。特別是在向SO提交問題時，儘量縮小範圍，刪除未使用的代碼並進行一些清理。

7. 評論您的代碼！我已經評論重新工作。我知道這是塞爾維亞語，但即使是一些評論也會幫助別人瞭解你在做什麼以及你打算做什麼。

8. 總的來說，不錯實施一些像錦標賽選擇了更復雜的事情

9. 身高雙[]數組，而不是名單。開銷較少。此外，您的幾個List temp變量甚至不需要。你的結構

   List temp = new List（）;對於（...）{ temp.add（value）; } 用於（在每個溫度值）{ 總和+ =值 } 平均=總和/ temp.Count

可以很容易地被寫爲：

sum = 0 
for(...) { 
    sum += value; 
} 
average = sum/count; 

1. 在幾個地方你忘了初始化一個循環變量，這可能很容易加到你的問題中。這樣的事情會引起嚴重的問題，並且這是在你的代碼以及其他一個或兩個地方

   雙擬合= 0; （每個染色體）{ //你應該初始化適合於這裏內部 LOOP （對於每個等位基因）{ fit + = ...; } fit/= count; }

祝您好運！

Answer 2

如果您需要true您的應用程序的隨機數字，我建議您查看Random.org。他們有一個免費的HTTP API，並且clients for just about every language。

隨機性來自大氣噪聲，它對於許多目的比計算機程序中通常使用的僞隨機數算法更好。

（我與Random.org無關，雖然我確實貢獻了PHP客戶端）。

Answer 3

這裏的基本問題是大多數隨機生成的染色體具有相似的適應性，對嗎？沒關係;這個想法並不適合你的初始染色體具有非常不同的適應性;這對染色體本身來說是不同的，可能它們是。事實上，由於尚未運行算法，因此您應該期望大多數第一代的初始適應度接近於零。

這就是爲什麼你的代碼太慢了。假設第一個候選人很糟糕，基本上沒有適應能力。如果第二個必須是1.5倍不同，那真的意味着它必須要好1.5倍，因爲它不會變得更糟。然後下一個比那個好1.5倍，等等達到80.所以你真正在做的是通過生成完全隨機的染色體並將它們與你所擁有的進行比較來尋找越來越好的染色體。我敢打賭，如果你記錄了進展，你會發現找到後續候選人需要越來越多的時間，因爲很難找到真正好的染色體。但是尋找更好的染色體是GA的目標！基本上你所做的是在手工優化一些染色體之前，嗯，實際上是優化它們。

如果你想確保你的染色體是多樣的，比較它們的內容，不要比較它們的適應性。比較健身是阿爾戈的工作。

Answer 4

我認爲你的問題在於你的健身功能以及你如何選擇候選人，而不是隨機值如何。你的過濾過於嚴格，甚至可能無法接受足夠的元素。

樣品

• 值：隨機浮點0-10000。
• 適應度函數平方根（n）的
• 期望健身的分佈 - 的距離至少爲1。

線性利用該適應度函數你會很快得到採取的多數1全「點」的（因爲你最多有100個地方），所以下一個會花費更長的時間。在某些時候，還會有幾個小範圍，大部分結果都會被拒絕，更糟糕的是，當你得到大約50個數字時，下一個很可能無法適應。

Answer 5

我打算在此迅速擺動，但艾薩克非​​常正確。您需要讓GA完成工作。你有一代人（染色體，無論），他們在健身方面的規模都很大（或者他們都完全相同）。

你選擇一些好的變異（自己）和交叉（彼此）。你可能會使用前10％來產生另一個完整的人口，並將最低的90％。也許你總是保持着頂尖人物（精英主義）。

您在此迭代了一段時間，直到您的GA停止改進，因爲這些人都非常相似。你的人口中多元化程度很低。

什麼可能會幫助你1）讓你的突變更有效，2）找到一個更好的方法來選擇突變的個體。在我的評論中，我建議AI Techniques for Game Programmers。這是一本很棒的書。非常容易閱讀。

要列出從書中的一些標題，你要尋找的東西：

選擇技術，如Roulette Selection (on stackoveflow)（上wikipedia）和Stochastic Universal Sampling，其控制如何您選擇的個體。我一直喜歡輪盤賭選擇。你設定了一個人將被選中的概率。這不僅僅是簡單的白噪聲隨機採樣。

我在遺傳算法之外用這個隨機選擇羅馬字母表中的4個字母。我爲每個字母分配了一個從0.0到1.0的值。每次用戶（孩子）都會正確選擇該字母，我會將該值降低0.1，即0.1。這會增加選擇其他字母的可能性。如果在10次之後，用戶選擇了正確的字母，則該值將是0.0，並且將幾乎（幾乎）不會再次顯示該字母。

Fitness Scaling像Rank Scaling，Sigma Scaling和Boltzmann Scaling (pdf on ftp!!!)這樣的技術可以讓您修改原始適應值以適應調整後的適應值。其中一些是動態的，如玻爾茲曼縮放，它允許您設置隨時間變化的「壓力」或「溫度」。增加的「壓力」意味着選擇了更適合的人。壓力下降意味着可以選擇人口中的任何個人。

我想這樣：你正在通過多維空間尋找解決方案。你打到一個「高峯」，並按照你的方式進入它。適合的壓力非常高。你直接進入當地的最大值。現在你的健康不能改變。你的突變並沒有讓你走出高峯。所以你開始減少壓力，只是，哦，隨機選擇項目。你的健康水平開始下降，這是好的一段時間。然後你開始再次增加壓力，並且感到驚訝！你已經跳出了本地最大值，並找到了一個可愛的新本地最大值進入。再次增加壓力！

Niching（我從來沒有用過，但似乎是一種將相似的人聚集在一起的方法）。假設你有兩個相當不錯的人，但他們完全不同。他們一直在選擇。他們保持微微的變化，並沒有變得更好。現在你有一半的人口是A的次要變體，而你的人口的一半是B的小變量。這似乎是一種說法，嘿，整個A羣的平均適應度是多少？以及對於B？而對於其他所有的利基你有什麼。然後根據每個利基的平均適應度進行選擇。選擇你的利基，然後從該利基中選擇一個隨機的個人。畢竟，我可能會開始使用它。我喜歡！

希望你找到一些有用的！