演化式計算

Evolutionary Computation
EE-6950, Fall 2023
Lecture # 1 - Introduction
Outline
I. Class Overview, Books, Grading

II. Brief Introduction to Evolutionary Computation (EC)

III. Homework – don't worry, easy! 🤓

2
I. Class Overview, Books, Grading
Introductions

• Instructor:
Lindor Henrickson (林道)
Email: [email protected]
O ce: EE Building Room 817

• TA:
張昆湧
Email: [email protected]

4
ffi
Class Details

• Lectures will be taught in English

• Programming language: Python
• Classroom: EE-207
• Time: Thurs 1:10-4:00pm
• O ce hours:
- Usually available before class or right after class ends
- You can also email me to arrange an appointment

5
ffi
Primary goals of this class

• Learn the foundations of Evolutionary Computation

• Apply Python to computational EC programming problems

• Learn advanced applications of EC

• Have some fun! ☺

6
Textbooks

• Primary textbook for this class:

- “Introduction to Evolutionary Computing”, 2nd Ed.

A.E. Eiben and J.E. Smith, Springer, 2015

- I have a few spare copies of this book I can loan out

7
Textbooks

• Another useful EC book (optional):

- “Evolutionary Computation”, K.A. De Jong, MIT

Press, 2006

- I have a few spare copies of this book I can loan out

8
Textbooks

• A good book on Python programming:

[Note: There are also plenty of free tutorials online at
http://www.Python.org]

- “Learning Python”, 5th Ed., Mark Lutz, O’Reilly,

2013

- This book is massive! Don’t worry, you don’t need

to read the whole thing to get started in Python!

9
Brief Course outline

• Introduction to EC
• Python programming & Production software techniques
• Components of EC
• Problem solving & representations for EC
• Multi-objective/constrained EC’s
• Parallel processing EC’s
• Advanced Applications:
- Evolutionary Electronics: IC Design & layout
- Interactive & Hybridized EC
- Evolution of things/robots
- Reinforcement learning, ML & neural networks
10
Grading & Projects

• This class will be project based:

- No written exams…yay!
- Series of smaller Python-based projects for homework
- Final project at end of semester:
• See next slide for details…

• Grading breakdown (tentative):

- Homework 60% (#1 or #2)
- (#1. Attendance 70% + HW criteria 30%)
- (#2. HW criteria 100%)
- Final project 40%

11
HW & Attendance

• The following will result in HW grade of 0:

- HW not submitted by deadline
- Code that was copied

• Attendance taking will be strictly closed by 1:30pm

• If you have a legitimate reason for missing class or a HW deadline, please let
me know (preferably ahead of time, if possible). I am a reasonable person ☺

12
Final Projects

• Python coding project: Choose an EC problem and then solve it with hands-
on code implementation

• You will also be required to give a presentation of your nal project to the
class.

• Note:
• Projects/presentations must be done in English
• TBD, depending on class size: Individual or team-based projects

13
NCHU iLearning Portal

• There will be an iLearning portal for this class

- https://lms2020.nchu.edu.tw/

• I will post all lecture notes (pdf) and supplemental materials there, typically at
least one day in advance [pdf pwd]

• We will also use this for homework/project submissions

Programming Survey

• What programming languages do you already know?

• Any experience with Python?

• Any background in object-oriented (OO)? (C++, Java, Python, etc.)

• Any background in computational, numerical, or algorithmic coding?

15
Python Programming

• We will spend a lecture or so for an introduction and review of Python and

production programming best practices

• 注意: For this class it is expected that you already have some background in
programming, since we will be writing our own algorithms from scratch

16
II. Brief Introduction to EC
So, what are Evolutionary Algorithms?

• Evolutionary algorithms are stochastic search algorithms inspired by the ideas

of genetic propagation and Darwinian evolution and selection.

• They are extremely powerful computational algorithms that have had much
success in the areas of global optimization, ML, RL, modeling and
classi cation.

18
fi
Common features of EA’s

• Population of individuals

• Individuals have a tness (a measure of quality)

• Stochastic Variation operators:

• Crossover, mutation  Push towards novelty (exploration)

• Selection towards higher tness  “survival of the ttest”

19
fi
fi
Basic Evolutionary Algorithm

20
Basic EC Pseudo-Code

21
A few notable strengths of EA’s
• Stochastic population -> Global search capability, doesn’t stall on local optima, failed points or constraints

• Population-based
• Many parallelization possibilities intrinsic to algorithm
• Can elegantly handle multiple objectives/constraints

• Arbitrary and exible data types – no derivatives or continuity required

• Can be hybridized to incorporate partial knowledge, local search, etc. Can ne-tune balance between local,
heuristic and global search.

• Can self-adaptively solve for it’s own “strategy” parameters

• Can be used interactively, if desired

22
fl
Example EA in Action - 1-D optimization

Initial Generation Intermediate Generation Final Generation

One Global Minimum

Many local minima

Note: Multiple local minima can “trap” simple hill-climbing algorithms

23
Many applications…

• See following slides for some examples…

24
Example: Automated IC layout & optimization

• Large combinatorial search space (so-called ”

NP-complete” problem)

• Specialized problem representation (Slicing, SP)

• Fitness: Minimize layout area and routing

25
Example: Evolving structure – NASA satellite

• Optimized satellite designs for NASA to

maximize vibration isolation

• Evolving: design structures

• Fitness: vibration resistance

26
Example: Evolution of Things/Robots

• Evolving population of robot’s “brains”

• Evolving: ANN controllers

• Fitness: better task performance

27
Example: Multi-objective engineering design

• Multi-objective optimization

• Evolving: multi-variate design parameter

space (e.g., analog IC design parameters,
transistor sizes, etc.)

• Fitness: seek optimal design criteria

(power, space, frequency, etc.)

28
Example: Evolving models

• Evolve creditability model to predict loan

paying behavior of new applicants

• Evolving: prediction models

• Fitness: model accuracy on historical data

29
Example: Search/games – 8 Queens problem

• Given an 8-by-8 chessboard and 8 queens

• Place the 8 queens on the chessboard without any

con ict

• Two queens con ict if they share same row,

column or diagonal

30
fl
fl
Example: Reinforcement Learning, Policy Search

• Evolve optimal game-playing "policy"

using Evolution Strategies approach (ES)

• Recently used to evolve AI agents to

play Atari video games

• P. Chrabaszcz , et al. Neural &

Evolutionary Computing, 2/2018

31
Example: Reinforcement Learning, Policy Search

• Evolve optimal Tetris AI agent using

Evolutionary Computation and feature-
based policy function

• N. Bohm, et al. MIC2005, 8/2005

32
Example: Neural-network Structure Evolution

• Evolve the structure of neural networks

• Example: Discover optimal RNN cell

structure representation

• A. Ororbia, et al. arXiv 2/2019

33
Example: Evolving software programs

• So-called “Genetic Program”

• Seek optimal program to solve given task

(e.g., symbolic regression)

34
Example: Simulating evolving artificial societies

• Simulating trade, economic competition, etc.

• Use models to optimize strategies and policies

• Evolutionary agents

• Survival of the ttest

35
fi
III. Homework
Your first Homework assignment
1. Download and install Python interpreter version 3.x (latest is 3.11.5)
https://www.python.org

[Note: If you prefer to use Anaconda or other Python framework, that is also ne,
but I will be using the standard version of Python from python.org]

37
Your first Homework assignment
2. Install the following Python libraries:
- PyYAML (yaml parser)
- NumPy (high-performance matrix library)
- Matplotlib (data visualization)
- PyTorch, aka “torch” (tensor & neural network library)
- OpenAI Gym, aka “gym” (RL environment simulation library)
- Also need: pygame & imageio- mpeg (for OpenAI video rendering)

[Note: If you prefer Tensor ow or a di erent data visualization library for your
own code, that’s ne, however my code examples will require the above
libraries]

38
fi
ff
fl
ff
Next week…
Introduction to Python