遺傳算法：自然選擇的搜索和優化

什麼是遺傳算法？

在過去的幾年裡，人工智能 (AI) 引起了極大的轟動。 谷歌、蘋果和微軟等大公司正在積極研究這個話題。 事實上，人工智能是一個涵蓋許多目標、方法、工具和應用程序的保護傘。 遺傳算法 (GA) 只是通過許多可能的解決方案進行智能搜索的工具之一。

遺傳算法是一種基於自然進化原理的元啟發式搜索和優化技術。 它屬於更大的一類進化算法。

GA 維護著一組染色體——一組解決該問題的潛在解決方案。 這個想法是，“進化”將在連續幾代之後找到問題的最佳解決方案——類似於自然選擇。

遺傳算法模擬三個進化過程：選擇、基因交叉和突變。

與自然選擇類似，遺傳算法選擇的核心概念是適應度。 更適合的染色體有更好的生存機會。 適應度是衡量由染色體表示的解的質量的函數。 本質上，種群中的每條染色體都代表輸入參數。 例如，如果您的問題包含兩個輸入參數，例如交易價格和交易量，則每個染色體在邏輯上將由兩個元素組成。 元素如何在染色體中編碼是一個不同的話題。

在選擇過程中，染色體形成一對父母進行繁殖。 每個孩子都從父母那裡獲得特徵。 基本上，孩子代表了來自其父母的特徵的重組：一些特徵來自一個父母，一些來自另一個父母。 除了重組之外，一些特徵還可以發生變異。

因為更健康的染色體會產生更多的孩子，所以後代的每一代都會有更好的適應度。 在某些時候，一代將包含一個染色體，它代表了我們問題的足夠好的解決方案。

GA 功能強大且廣泛適用於復雜問題。 有一大類優化問題很難用傳統的優化技術解決。 遺傳算法是有效的算法，其解決方案是近似最優的。 眾所周知的應用包括調度、運輸、路由、組技術、​​佈局設計、神經網絡訓練等等。

付諸實踐

我們將看到的示例可以被認為是 GA 的“Hello World”。 這個例子最初是由 J. Freeman 在Simulating Neural Networks with Mathematica中給出的。 我從 Mitsuo Gen 和 Runwei Cheng 的《遺傳算法和工程設計》中得到它。

單詞匹配問題試圖用遺傳算法進化一個表達式。 最初，該算法應該從隨機生成的字母列表中“猜測”“成為或不是”短語。

由於列表中 13 個位置 [不包括空格] 中的每一個都有 26 個可能的字母，因此我們以純隨機方式得到正確短語的概率為 (1/26)^13=4.03038×10-19，大約為[quintillion] 中的兩次機會（Gen & Chong, 1997）。

我們將在這裡更廣泛地定義問題，使解決方案更加困難。 假設我們不限於英語或特定短語。 我們最終可以處理任何字母，甚至任何一組符號。 我們對語言一無所知。 我們甚至不知道是否有任何語言。

假設我們的對手想到了一個任意的短語，包括空格。 我們知道短語的長度和字母表中符號的數量。 這是我們僅有的知識。 每次猜測後，我們的對手都會告訴我們有多少個字母。

每條染色體都是字母表中符號的索引序列。 如果我們談論的是英文字母，那麼“a”將由 0 表示，“b”由 1 表示，“c”由 2 表示，依此類推。 因此，例如，單詞“be”將表示為[4, 1] 。

我們將通過 Java 代碼片段演示所有步驟，但理解每個步驟並不需要 Java 知識。

遺傳算法核心

我們可以從遺傳算法的一般實現開始：

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

這是每個 GA 或多或少包含的一組簡單步驟。 在初始化步驟，我們生成初始的短語群。 人口的大小由populationSize決定。 短語如何生成取決於supplier的實施。

在迭代步驟中，我們進化種群，直到在while循環的測試中滿足終止條件。 終止條件可以包括代數和群體中短語之一的精確匹配。 termination封裝了一個精確的實現。

在每次迭代中，我們執行典型的 GA 步驟：

1. 根據染色體適應度對種群進行選擇。
2. 通過交叉操作產生新的“一代”。
3. 對某些短語中的某些字母進行重組。

該算法的核心非常簡單且與領域無關。 所有問題都是一樣的。 您需要調整的是遺傳算子的實現。 接下來，我們將仔細研究前面提到的每個 GA 算子。

選擇

正如我們已經知道的那樣，選擇是尋找當前染色體的繼任者的過程——這些染色體更適合我們的問題。 在選擇過程中，我們需要保證適應度更好的染色體有更好的生存機會。

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

這個實現背後的想法如下：人口被表示為數字軸上的結果範圍。 總人口在 0 和 1 之間。

染色體所佔據的範圍與其適應度成正比。 這導致更適合的染色體獲得更大的塊。 然後我們隨機查看一個介於 0 和 1 之間的數字，並找到一個包含該數字的範圍。 顯然，更大的範圍有更高的機會被選擇，因此更適合的染色體有更好的生存機會。

因為我們不知道適應度函數的細節，所以我們需要對適應度值進行歸一化。 適應度函數由fitness表示，它將染色體轉換為表示染色體適應度的任意雙精度值。

在代碼中，我們找到了種群中所有染色體的適應度，我們還找到了總適應度。 在for循環中，我們對按總適應度縮小的概率進行累積求和。 從數學上講，這應該導致最終變量的值為 1。由於浮點的不精確性，我們不能保證這一點，所以我們將其設置為 1 只是為了確定。

最後，對於等於輸入染色體數的次數，我們生成一個隨機數，找到一個包含該數字的範圍，然後選擇對應的染色體。 您可能會注意到，可能會多次選擇同一染色體。

分頻器

現在我們需要染色體來“繁殖”。

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

使用預定義的概率crossoverProbability ，我們選擇父母進行育種。 選擇的父母被洗牌，允許任何組合發生。 我們採用一對父母並應用crossover算子。 我們對每一對應用兩次操作符，因為我們需要保持種群大小相同。 孩子們在人口中取代了他們的父母。

突變

最後，我們對特徵進行重組。

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

使用預定義的概率mutationProbability ，我們對染色體執行“突變”。 突變本身由mutation定義。

特定問題的算法配置

現在讓我們看看我們需要為我們的通用實現提供什麼類型的問題特定參數。

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

參數分別為：

1. 交叉算子
2. 交叉概率
3. 健身功能
4. 變異算子
5. 突變概率
6. 人口規模
7. 初始種群的染色體供應商
8. 終止功能

這是我們問題的配置：

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

交叉算子和概率

private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

交叉的概率為 0.25，因此我們預計平均 25% 的染色體將被選擇用於交叉。 我們為一對染色體的交叉執行了一個簡單的程序。 我們從[0..length]範圍內生成一個隨機數n ，其中length是染色體的長度。 現在我們通過從一個染色體中取出前n字符和從第二個染色體後的剩餘字符來配對選定的對。

健身功能

private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

適應度函數只是計算目標短語和給定染色體之間的匹配次數。

變異算子和概率

private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

變異操作在每條染色體上獨立進行。 突變的概率為 0.05，因此我們預計平均 5% 的人口會發生突變。 我們通過選擇一個隨機字母位置並將其值替換為字母表中的一個隨機字母來進行變異。 我們對每個突變的染色體做兩次。

供應商

private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

供應商通過從字母表中獲取隨機字母來生成隨機短語。 每個短語都有一個恆定的預定義長度。

終止函數

private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

終止函數計算調用次數，如果完全匹配或生成計數達到 3,000，則返回true 。

執行

現在我們準備測試我們的算法。 如果您多次運行它，您會注意到並非所有運行都成功。 每次迭代的次數都會不同。 這是由於算法的概率性質。 該算法有幾個可以改進的地方。 你可以玩交叉和變異概率。

降低數字將導致穩定但緩慢的解決方案。 較少數量的染色體將受到遺傳算子的影響，因此解決方案將需要更多的迭代。

增加數字會加快算法的速度，但也會使解變得不穩定。 適合的染色體不僅會被保留，還會受到遺傳算子的影響。 因此，他們將失去他們的“好”基因。

找到一個好的平衡點很重要。 增加迭代次數將使算法有更多機會找到解決方案，但另一方面，這將花費更多時間。 您還可以應用不同的交叉和變異方法。 這些運算符的良好選擇將大大提高解決方案的質量。

接下來是什麼？

我們在這裡只介紹了冰山一角。 我們舉了一個只有一個輸入的例子，輸入可以很容易地表示為一條染色體。 遺傳算子簡單明了。

處理一個現實世界的問題並將遺傳算法應用於它是非常有趣的。 您將發現編碼真實輸入數據的不同方法以及不同的交叉和變異實現。

如果一個問題可以通過一組參數來表達，我們必須猜測這些參數來優化一個度量，我們可以快速設置一個我們可以用來解決它的 GA。

最有趣的問題之一是教授人工神經網絡。 我們可以將可優化參數設置為突觸強度，並將適應度指標設置為我們的神經網絡給出正確答案的輸入百分比。 之後，我們可以坐下來讓我們的神經網絡演變成我們想要的理想解決方案。 或者至少在我們得到足夠好的東西之前，因為進化需要時間。