教程 | 基於遺傳算法的拼圖遊戲解決方案

 2017-11-12 14:30:00.0

原標題:教程 | 基於遺傳算法的拼圖遊戲解決方案

選自GitHub

參與:林川、劉曉坤

這是一個GitHub項目,介紹了一種基於遺傳算法的帶有板塊尺寸自動檢測功能的拼圖遊戲解決方案。

GitHub鏈接:https://github.com/nemanja-m/gaps

安裝

把 repo 下載到本地

$ git clone https://github.com/nemanja-m/gaps.git$ cdgaps

安裝要求

$ pip install -r requirements.txt$ sudo apt-get install python-tk

以可編輯模式安裝項目:

$ pip install -e .

從圖像中創建拼圖

使用 create_puzzle腳本從圖像中創建拼圖。

亦即

$ create_puzzle images/pillars.jpg --size=48 --destination=puzzle.jpg[SUCCESS] Puzzle created with 420 pieces

將從 images/pillars.jpg 創建分割成 420 塊的拼圖,每塊拼圖像素爲 48x48px。

運行 create_puzzle --help可以獲得詳細幫助。

注意:我們創建出來的拼圖尺寸可能會比原圖小,這取決於設置的拼圖塊的大小。最大的可能是以矩形從原始圖像隨機裁剪出來。

解決拼圖問題

爲了解決這個拼圖問題,我們會用到 gaps 腳本。

亦即

$ gaps --image=puzzle.jpg --generations=20 --population=600

這將啓動初始羣體爲 600 個(populations)和 20 代(generations)的遺傳算法。

提供下列選項:

Option Deion
--image 指向拼圖的路徑
--size 拼圖塊的像素尺寸
--generations 遺傳算法的代的數量
--population 個體數量
--verbose 每一代訓練結束後展示最佳結果
--save 將拼圖還原爲圖像

運行 gaps --help獲得詳細幫助。

尺寸檢測

如果你不能明確的給 gaps提供 --size的參數,拼圖塊尺寸將自適應。

其實給 gaps提供 --size的具體參數總是可行的:

$ gaps --image=puzzle.jpg --generations=20 --population=600 --size=48

注意:尺寸檢測功能適用於大多數圖像,但是在某些邊緣情況下尺寸檢測會失效,並給出一個錯誤的尺寸。在這種情況下,你可以明確的給定一個尺寸。

終止條件

遺傳算法的終止條件對於確定它的運行何時結束是很重要的。人們觀察到在最初的時候,遺傳算法進展非常快,每幾次迭代都會產出更好的解決方案,但是在後期的改進非常小的時候,往往會趨於飽和。

gaps將終止的情況:

  • 當經過 X 次迭代在全量中沒有改善的時候

  • 當它演化到了某個絕對的代(generations)數的時

文章來源:機器之心