解決與遺傳算法，健身，突變縱橫字謎

我努力做一個實驗室的學校。我正在嘗試使用遺傳算法解決縱橫字謎。問題是，這不是很好（它仍然是過於隨機）我會嘗試給我現在如何執行我的程序的簡短說明：解決與遺傳算法，健身，突變縱橫字謎

如果我有困惑（＃是塊，0是空的空間）

#000 
00#0 
#000

以及這個拼圖的解決方案的候選詞的集合。我的DNA只是作爲一維數組的矩陣。

我的第一套個人從我的單詞包含的字母池中隨機生成DNA。

我使用輪盤賭選擇做選擇。關於組合和突變的機率有一些參數，但如果突變會發生，那麼我將總是改變25％的DNA。我從我的信池中隨機字母改變它（這可能有負面影響，因爲突變可以破壞已經形成的話）

現在的適應度函數：我都horizontaly和verticaly遍歷矩陣：如果我找到一個詞，然後健身+ = word.lengh +1

如果我找到一個字符串是一個字的一部分，然後健身+ = word.length /（puzzle_size * 4）。無論如何，它應該給出一個介於0和1之間的值。因此，它可以從「tool」和廣告X中找到「FITNESS」，然後在「tool」中找到「too」並將另一個Y添加到FITNESS。

我的這代人實際上並沒有隨着時間而改善。他們顯得隨機。所以即使經過400代1000-2000的池（這些數字並不重要），當解決方案應該有6個單詞時，我會得到1-2個字（2或3個字母）的解決方案。

來源

2011-05-02 Blitzkr1eg

我認爲你的健身功能可能不明確。我會設置這個，所以每一行都有一個二進制適應度。一行是合適的，否則它不合適。（例如，行是一個單詞，或者它不是一個單詞）那麼解決方案的整體適應性將會是#fit rows/total rows（橫向和縱向）。此外，你可能會改變太多的DNA，我會做出這個變量，並試驗。

來源

2011-05-02 16:50:34

一行可能包含多於1個單詞，如：＃tool＃pink – Blitzkr1eg 2011-05-02 17:47:35

然後，健身可能是＃行中正確的單詞/每行可能的單詞數量。我認爲字長是無關緊要的 – 2011-05-02 18:02:34

您的健身功能對我來說看起來還不錯，儘管沒有更多的細節，但很難獲得您所做的事情的真實情況。

你沒有指定變異概率，但是當你變異時，25％是非常高的變異。此外，輪盤選擇適用批次的選擇壓力。你經常看到的是，算法很早就發現了一個比所有其他算法好得多的解決方案，輪盤選擇導致算法選擇它的可能性很高，以致於你很快就會得到一個完整的副本那個。在那一點上，除了偶爾偶然的幸運突變之外，搜索暫停，並且由於你的突變非常大，所以你不可能發現一個改進的移動而不破壞染色體的其餘部分。

我會嘗試二元比賽的選擇，和一個更明智的變異算子。通常啓發式的人用於突變是（平均）翻轉每個染色體的一個「位」。但是，您不希望每次都確定一個字母更改。例如：

for(i=0; i<chromosome.length(); ++i) { 
    // random generates double in the range [0, 1) 
    if(random() < 1.0/chromosome.length()) { 
     chromosome[i] = pick_random_letter(); 
    } 
}

來源

2011-05-02 21:26:53 deong

解決與遺傳算法，健身，突變縱橫字謎

回答

相關問題