Searching for… something?
GA屬於AI的搜索(search)或優化(optimisation)類別，一般而言，人工神經網絡不能使用。 當然，它們可以用作求解一部分(例如，根據其內容對網頁進行分類)。 但是，進行搜索或優化一組參數的並不適用於ANN的架構。
這是因為人工神經網絡基本上是統計驅動(statistically-driven)的輸入輸出映射(input-output mapping)機器。 放入圖像，人工神經網絡可以告訴你它是不是貓(如果你在網路上找到圖片，很可能是肯定的)。 但是試著讓人工神經網絡在網路上找到一隻貓，你就會陷入困境。 什麼是輸入/輸出？ 你將如何訓練它？ 當問題如此不明確以至於你不確定你正在尋找什麼時，或者當搜索的選項數量不合理地增加時(Google搜索'貓'返回75億個結果，這超過了地球上的人口)，這個問題會變得更糟。
The knapsack problem
接下來我們用搜索/優化問題的典型例子來說明這個問題：背包問題(knapsack problem)。
背包問題是這樣的：假設你是一個旅行的銷售人員，他把你所有的商品都放在你可靠的背包裡。 當然，您希望通過在您的回合中獲取最有價值的商品來確保您當天賺到最多的錢。 但你有一個問題 - 你只能攜帶這麼多，否則你的bag將會破裂！ 每天早上，你需要找到最好的物品組合放在你的bag裡，這樣可以最大化你攜帶的價值，但不要超過bag的容量，這樣就會破壞。
讓我們開始來解決這個問題：
Search space - 約束一種搜索的抽象參數。
States - 空間中的位置或多組條件。
Goal state - 理想的結果或解決方案。
背包問題中的search space是放入包中的每種可能的物品組合。 每個項目都有一個相關的value和weight，並且背包本身俱有最大capacity。 單個state是包中物品的組合之一，goal state是一個單一的組合，可以在不超過行李capacity的情況下最大化價值。
Search space - 約束一種搜索的抽象參數。
States - 空間中的位置或多組條件。
Goal state - 理想的結果或解決方案。
背包問題中的search space是放入包中的每種可能的物品組合。 每個項目都有一個相關的value和weight，並且背包本身俱有最大capacity。 單個state是包中物品的組合之一，goal state是一個單一的組合，可以在不超過行李capacity的情況下最大化價值。
A brute force solution
使用暴力法解決背包是一個非常簡單的問題。 在此代碼段中，我們遍歷bag中所有可能的項目組合，並測試每個項目的value和weight。
import random
from itertools import combinations
from time import time
class Item:
value = 0
weight = 0
def __init__(self, value, weight):
self.value = value
self.weight = weight
def __repr__(self):
return "Item(value={}, weight={})".format(self.value, self.weight)
def getRandomItem(min=1, max=30):
return Item(
random.randrange(min, max),
random.randrange(min, max)
)
def getCombinations(items, capacity):
# get all combinations
combi = []
for i in range(1, len(items)):
c = list(combinations(items, i))
if len(c[0]) > capacity:
# early stop - we don't need *all* the combinations
break
combi += c
return combi
def bruteForceKnapsack(items, capacity):
# find all combinations
allCombinations = getCombinations(items, capacity)
numCombinations = len(allCombinations)
print(numCombinations, "combinations")
bestCombination = None
bestWeight = 0
bestValue = 0
for i in range(numCombinations):
thisCombination = allCombinations[i]
weight = sum([i.weight for i in thisCombination])
if weight <= capacity:
value = sum([i.value for i in thisCombination])
if value > bestValue:
bestValue = value
bestWeight = weight
bestCombination = thisCombination
return bestCombination, bestValue, bestWeight
if __name__ == "__main__":
# record the entry point time
t1 = time()
# the number of possible items to put in the knapsack
numItems = 10
# the items themselves
# this will generate a random set of items, from 1-30 in value and weight
items = [getRandomItem() for x in range(numItems)]
# the target capacity
capacity = 10 * numItems
print("Number of items:", numItems)
print("Capacity: ", capacity)
bestCombination, bestValue, bestWeight = bruteForceKnapsack(items, capacity)
print("Found best combination")
print("{} items with {} value and {} weight:".format(len(bestCombination), bestValue, bestWeight))
print(bestCombination)
print("Took ", time() - t1)
運行此代碼表明我們確實找到了解決方案，對於此示例中的10個項目，我們可以非常快速地找到解決方案。 但是，如果有更多項目需要搜索，會發生什麼？ 有10個項目，我們只需要搜索大約1000種組合，我的機器需要大約7毫秒。 但是有20個項目，組合數量增加到大約1,000,000，需要2.5秒。 只有五(25)個項目可以產生大約3300萬種組合，大約需要2分鐘才能完成搜索。 這種趨勢顯示背包問題具有指數(O(2^n))複雜度，這意味著對於較大的n值，它很快變得不切實際。
GAs: a different kind of search
讓我們想一個更好的方法來搜索大量空間的背包問題。我們面臨的問題在於，當我們增加項目數量時，組合數量呈指數增長。如果不是像前面用暴力法搜索bag中的每個可能的項目組合，我們有fixed number of states，evaluate their value，然後以某種方式更改它們以探索search space的話會如何。
這正是GA背後的直覺。受自然進化的啟發 - 通過自然選擇使一個簡單的有機體變得更加複雜並且更好地適應其環境的過程--GAs評估一組states(GA術語中的人口)的fitness並且在下一代中evolve出最佳解(“fittest“)。最終，人口的整體適應性將會提高，並找到最佳解。
下次我們將更多地了解GA搜索過程的機制。現在，讓我們關注GA中的一些基本概念，所有這些概念都受到自然進化的啟發：基因(genes)，染色體(chromosomes)，表現型(phenotypes)和適應函數(fitness functions)。
您可以將phenotype視為與一般AI術語中的search state類似。在生物學中，你是一個活體phenotype，你的基因定義了你的表現方式。如果您有棕色眼睛的基因，那麼您的phenotype眼睛也會變成棕色。類似地，在GA中，基因是一種抽象參數，用來編碼其中一種phenotype。chromosome是基因的集合，它們以抽象的方式完全代表phenotype。最後，fitness函數是一種特定於應用程序的評估方法，它從chromosome建立phenotype並且計算solution的好壞程度。
這正是GA背後的直覺。受自然進化的啟發 - 通過自然選擇使一個簡單的有機體變得更加複雜並且更好地適應其環境的過程--GAs評估一組states(GA術語中的人口)的fitness並且在下一代中evolve出最佳解(“fittest“)。最終，人口的整體適應性將會提高，並找到最佳解。
下次我們將更多地了解GA搜索過程的機制。現在，讓我們關注GA中的一些基本概念，所有這些概念都受到自然進化的啟發：基因(genes)，染色體(chromosomes)，表現型(phenotypes)和適應函數(fitness functions)。
您可以將phenotype視為與一般AI術語中的search state類似。在生物學中，你是一個活體phenotype，你的基因定義了你的表現方式。如果您有棕色眼睛的基因，那麼您的phenotype眼睛也會變成棕色。類似地，在GA中，基因是一種抽象參數，用來編碼其中一種phenotype。chromosome是基因的集合，它們以抽象的方式完全代表phenotype。最後，fitness函數是一種特定於應用程序的評估方法，它從chromosome建立phenotype並且計算solution的好壞程度。
The knapsack as a chromosome
在我們的背包範例中，我們已經說過，single search stat - 一種phenotype - 是bag中物品的一種可能組合。 將其編碼到chromosome中就像創建二進制列表一樣簡單，其中長度是放入bag中的可能項目的數量。 如果單個基因的值為1，則包含在bag中。
為了說明這一點，下面是一些建立隨機chromosome並將其轉換為一個phenotype的範例代碼。
為了說明這一點，下面是一些建立隨機chromosome並將其轉換為一個phenotype的範例代碼。
import random
class Item:
value = 0
weight = 0
def __init__(self, value, weight):
self.value = value
self.weight = weight
def __repr__(self):
return "Item(value={}, weight={})".format(self.value, self.weight)
def getRandomItem(min=1, max=30):
return Item(
random.randrange(min, max),
random.randrange(min, max)
)
def getPhenotype(chromosome, items):
return [v for i, v in enumerate(items) if chromosome[i] == 1]
if __name__ == "__main__":
# the number of possible items to put in the knapsack
numItems = 10
# the items themselves
# this will generate a random set of items, from 1-30 in value and weight
items = [getRandomItem() for x in range(numItems)]
# A potential solution to the knapsack problem as a binary chromosome
# A list for every potential item, 1 = it's in the bag 0 = it isn't
# Here I'll just create a random one
chromosome = [1 if random.random() > 0.5 else 0 for x in range(numItems)]
print("Chromosome:")
print(chromosome)
phenotype = getPhenotype(chromosome, items)
print("Phenotype ({} items):".format(len(phenotype)))
print(phenotype)
It’s in the bag
這就是我們將在本週留下的地方。 我們已經介紹了機器學習和人工神經網絡的一些局限，以及對某些AI問題的更廣泛觀點的需求。 我們還引入了遺傳算法作為搜索複雜空間的替代方法，以及GAs，基因，染色體，表現型和適應函數中的一些基本概念。
沒有留言:
張貼留言