Skip to main content

Introduction to Evolutionary Computation 進化計算導論

Aims of the module 模塊的目標​

  • Provide an interdisciplinary introduction into Evolutionary Computation within a broader picture of Nature-Inspired Computing and Non-Standard Computation 在更廣泛的自然啟發計算和非標準計算的範圍內提供對進化計算的跨學科介紹
  • Provide a clear understanding how Genetic and Evolutionary Algorithms work 清楚地了解遺傳和進化算法的工作原理
  • Introduce the main concepts, techniques and applications in the field of randomised search heuristics and nature-inspired computing with a focus on (but not limited to) optimisation 介紹隨機搜索啟發式和自然啟發計算領域的主要概念、技術和應用，重點是（但不限於）優化
  • Give students some experience on when such techniques are useful, how to use them in practice & how to implement them 給學生一些經驗，當這些技術有用時，如何在實踐中使用它們以及如何實現它們
  • Provide theoretical foundations on the computational complexity of these algorithms, to guide their educated application 提供這些算法的計算複雜度的理論基礎，以指導他們的受教育應用

Learning outcomes (official version) 學習成果（官方版本）​

  • LO1 Describe, and apply the principles of evolutionary computation LO1 描述並應用進化計算的原理
  • LO2 Explain and compare different evolutionary algorithms LO2 解釋和比較不同的進化算法
  • LO3 Design and adapt evolutionary algorithms for non-trivial problems LO3 設計和調整非平凡問題的進化算法
  • LO4 (level 4/M) Demonstrate an awareness of the current literature in this area LO4（4 級/M）展示對該領域當前文獻的認識

Learning outcomes (longer version) 學習成果（更長的版本）​

  • LO1 Demonstrate a good understanding of different evolutionary algorithms and nature-inspired design techniques and how they are applied to solve real world problems LO1 很好地理解不同的進化算法和受自然啟發的設計技術，以及它們如何應用於解決現實世界的問題
  • LO2 Demonstrate an understanding of the relations, similarities and differences between the most important heuristics and nature-inspired algorithms presented in the module and other search and optimisation techniques LO2 展示對模塊中介紹的最重要的啟發式算法和自然啟發算法與其他搜索和優化技術之間的關係、異同的理解
  • LO3 Design and adapt evolutionary algorithms including operators, representations, fitness functions and potential hybridisations for non-trivial problems LO3 設計和調整進化算法，包括運算符、表示、適應度函數和針對非平凡問題的潛在混合
  • LO4 (level 4/M) Describe, use, analyse and discuss recent research literature in evolutionary computation and demonstrate a critical understanding of these methods LO4（4 級/M）描述、使用、分析和討論進化計算方面的最新研究文獻，並展示對這些方法的批判性理解

What will be covered (this may be evolving!) 會涵蓋的內容（這可能會不斷變化！）​

  • Algorithms 算法
    • Randomized Search Heuristics 隨機搜索啟發式
    • Evolutionary Algorithms: Genetic Algorithms, Genetic Programming, Evolutionary Programming, Differential Evolution and Evolution Strategies 進化算法：遺傳算法、遺傳編程、進化編程、差分進化和進化策略
    • Game Theory (optimisation), and: Evolutionary Game Theory (dynamics) 遊戲理論（優化）和：進化遊戲理論（動態）
    • Particle Swarm Optimiser & Ant Colony Optimisation 粒子群優化器和螞蟻群優化
    • Artificial Immune System (time permitting) 人工免疫系統（時間允許）
  • Theory 理論
    • Schema Theorem 圖式定理
    • Convergence and Convergence Rate 收斂和收斂率
    • Computational Complexity 計算複雜度
    • No Free Lunch Theorem 無免費午餐定理
    • Fitness Landscape 適應度景觀
    • Boolean Networks 布爾網絡
    • Cellular Automata (including Game of Life) 細胞自動機（包括生命遊戲）

What will not be covered 不會涵蓋的內容​

  • (Other) Nonstandard Computation （其他）非標準計算
    • Analog computing 模擬計算
    • Fuzzy logic devices 模糊邏輯器件
    • Mechanic, computing 機械師，計算
    • Neural (and memristive) computing, ML (→separate modules) 神經（和記憶抵抗）計算，ML（→ 獨立模塊）
    • Quantum Computation (→separate module) 量子計算（→ 獨立模塊）

Questions and answers 題目和答案​

  • Q: What is Nature Inspired Optimisation? 自然啟發優化是什麼？

  • A: The study of computational systems that use ideas inspired from natural evolution, e.g., the principle of survival of the fittest 自然啟發優化是一種研究計算系統的方法，該系統使用自然演化的想法，例如，生存的原則

  • Q: Why should we study it? 為什麼我們應該研究它？

  • A: It provides a general method for solving 'search for solutions' type of problems, such as optimisation, learning, and design. 它為解決"搜索解決方案"類型的問題提供了一種通用方法，例如優化、學習和設計。

  • Q: What is Evolutionary Computation? 什麼是進化計算？

  • A: The study of computational systems that use ideas inspired from natural evolution, e.g., the principle of survival of the fittest 進化計算是一種研究計算系統的方法，該系統使用自然演化的想法，例如，生存的原則

  • Q: Why should we study it? 為什麼我們應該研究它？

  • A: It provides a general method for solving 'search for solutions' type of problems, such as optimisation, learning, and design. 它為解決"搜索解決方案"類型的問題提供了一種通用方法，例如優化、學習和設計。

Cool example 1: NASA's Evolved antenna NASA 的進化天線​

  • Satellite antenna evolved fully designed by an evolutionary algorithm 完全由進化算法設計的衛星天線
  • Used for a 2006 NASA mission called Space Technology 5 (ST5) 用於 2006 年 NASA 任務 Space Technology 5（ST5）
    • The mission consists of three satellites that will take measurements in Earth's magnetosphere. 這個任務由三顆衛星組成，將在地球磁場中進行測量。
    • Each satellite has two communication antennas to talk to ground stations. 每顆衛星都有兩個通信天線，用於與地面站通信。
    • The mission successfully launched on March 22, 2006 任務於 2006 年 3 月 22 日成功發射
  • It is the the world's first artificially-evolved object to fly in space 這是世界上第一個人工進化的物體，它將在太空中飛行
  • Youtube video

Cool example 2: Evolutionary robotics 進化機器人​

  • Evolutionary robotics: a methodology that uses evolutionary computation to design, develop and control autonomous robots. 進化機器人：一種使用進化計算來設計、開發和控制自主機器人的方法。
  • One of the famous example: The Golem Project 一個著名的例子：Golem 計劃
    • Genetically Organized Lifelike Electro Mechanics 基因組織的栩栩如生的機電
    • H. Lipson and J. B. Pollack (2000), "Automatic design and Manufacture of Robotic Lifeforms", Nature 406, pp. 974-978
    • Evolutionary Computation + 3D printing = Evolutionary Robots 進化計算 + 3D 打印 = 進化機器人
  • Youtube video
  • Youtube video of new evolving soft robots

Cool example 3: Blondie24 - Evolved master checkers player 進化的大師棋手​

  • Blondie24: an artificial intelligence checkers-playing computer program Blondie24：人工智能跳棋計算機程序
  • The most special feature: learn playing checkers by itself 這個程序最特別的特點是：自學跳棋
  • How: given the checkers rules, co-evolve artificial neural networks as opponent players, the wining players will be selected and breed the next generation 給定跳棋規則，進化人工神經網絡作為對手，贏得比賽的對手將被選中並繁殖下一代
  • Did it work? Rated as Expert on Microsoft's Gaming Zone as claimed by the authors. 這個程序是否有效？根據作者的說法，它在微軟的遊戲區被評為專家。
  • Video

Cool example 4: Automated Invention Machine 自動發明機​

  • An ambitious goal: To automate creativity 一個雄心勃勃的目標：使創造力自動化
  • How: use evolutionary computation, especially Genetic Programming (GP) 進化計算，特別是遺傳編程（GP）
  • A case study: invent/re-invent electronic circuits by Genetic Programming 遺傳編程發明/重新發明電子電路
  • Reinvented 21 Previously Patented Inventions 進化計算重新發明了 21 個以前被專利的發明
  • Invented 2 new patentable inventions 進化計算發明了 2 個新的可專利的發明
  • John Koza's website

Cool example 5: Evolutionary art 進化藝術​

What is a Genetic Algorithm (GA)? 什麼是遺傳算法？​

  • Observation: Natural Evolution has evolved many complex systems (e.g., brain) and "solved" many bioengineering problems 觀察：自然進化已經進化出許多複雜的系統（例如大腦）並"解決"了許多生物工程問題
  • Idea: Mimic the idea of Darwinian Evolution to optimize some objective... 模仿達爾文進化的理念來優化某些目標...
  • ... where the objective can be defined by any fitness function. ...目標可以通過任何適應函數來定義。
  • A GA then is (more details and examples to follow!) 一個 GA 是（更多細節和例子將跟隨！）
    • a set of possible configurations (genotype) "code" (also called genes or chromosomes) 一組可能的配置（基因型）"代碼"（也稱為基因或染色體）
    • a mapping from genotype to phenotype (the sought solution or configuration) 從基因型到表型的映射（所求解的解或配置）
    • a function from genotype to the real numbers, defining the fitness of each possible configuration 基因型到實數的函數，定義每個可能配置的適應性
    • an algorithmic framework for the evolution of a population of genes / chromosomes (includes initial population, population size, selection, reproduction, mutation, and criteria for termination of algorithm) 一個演化基因/染色體群體的算法框架（包括初始群體、群體大小、選擇、繁殖、突變和算法終止標準）

Mini-exercise: Smallest Sudoku - fitness function? 迷你練習：最小的數獨 - 適應函數？​

  • Standard Sudoku has a 9×9 board to be filled with 9 different symbols (integers) 標準數獨有一個 9×9 的棋盤，用 9 個不同的符號（整數）填充
  • What is the smallest possible Sudoku? Let's pick a 2× 2 version 最小的數獨是什么？讓我們選擇一個 2× 2 版本
  • Fill a 2×2 board (a 2×2 matrix) with symbols 0 and 1, such that in each row and in each column each symbol appears only once. 填滿一個 2×2 的棋盤（一個 2×2 的矩陣），用符號 0 和 1，使得每一行和每一列中的每個符號只出現一次。
  • Wrong: (1101)\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right) Right: (1001)\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)
  • Task: Formulate (mathematically) a fitness function! 任務：形成（數學上）一個適應函數！