• 검색 결과가 없습니다.

Chapter 1

N/A
N/A
Protected

Academic year: 2021

Share "Chapter 1"

Copied!
13
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

Chapter 1

Introduction to Evolutionary Algorithms

Dae-Ki Kang

(2)

Notice and disclaimer!

• Most contents of these slides are simple and

literal translation of the Korean lecture slides of the following book.

▫ 쉽게 배우는 유전 알고리즘/문병로/한빛미디어

• These slide are made simply because there are no English lecture slides for the original lecture slides, i.e. purely educational purpose.

• Any form of the reuse of the materials should be done only after the permission of the original

author (문병로)

(3)

Objectives of this class

• Check the history of evolutionary algorithms

• Understand the basic architecture of

evolutionary algorithms and their operators

• Understand that evolutionary algorithms are not always suitable for all problems.

(4)

Evolutionary Algorithms

• Genetic Algorithm= GA

• Problem solution space search method using the evolution principle of entities in population

genetics

• One field of “Evolutionary Computation”

• key features - natural selection, crossover, mutation, population, etc.

(5)

Brief of the history

During 1950’s and 1960’s : Independent studies (without communication) by some researchers

Genetic Algorithm(John Holland)

Evolutionary Programming (Fogel, Owens, Walsh) – crossover was not used

Evolution Strategy (Rechenberg) – Start with single thread. Similar to current GA

1975, John Holland, 「Adaptation in Natural and Artificial Systems」

1984, due to Holland , SantaFe Institute changes research direction from Complex System to Adaptive Complex System

1985, 1st International Conference on Genetic Algorithms (ICGA)

1989, David Goldberg, 「Genetic Algorithms in Search, Optimization and Machine Learning」

1990's Explosion of interests, growing in quantity and quality

1997, IEEE Transactions on Evolutionary Computation

(6)

Basic terms

Evolutionary Computation

▫ EC = GA + GP + EP + ES

EC : Evolutionary Computation

GA : Genetic Algorithm

GP : Genetic Programming

EP : Evolutionary Programming

ES : Evolution Strategy

Terms

▫ chromosome

▫ population

▫ gene

▫ genotype

▫ phenotype

(7)

Structure of Genetic Algorithms

▫ crossover – create a new chromosome by partially combining two chromosomes

▫ mutation – change a very small portion of a chromosome

k/n : generation gap

k ≈ n : generational GA

k ≈ 1 : steady-state GA

▫ Stopping condition

e.g. − fixed number of iterations

− probability of population convergence Create n initial chromosomes;

repeat {

for i ← 1 to k {

pick two chromosomes p1, p2; offspringi ← crossover (p1, p2);

offspringi ← mutation (offspringi);

}

replace k chromosomes in population with offspring1 , …, offspringk } until (stopping condition is met);

return the best chromosomes from the population;

[Algorithm 1-1] Structure of GA

(8)

Representation

In the past, chromosome is represented in binary

Binary: 00110010 … 00011111 → Hexadecimal: 32…1F

Chromosome and solution

Graph Bipartition

chromosome solution

1 1 Common

k 1 Rare

1 k Very rare

Graph Bipartition In chromosome representation 2

6

9

3 4

8 7

1

5

10 Chromosome

0011001101

(9)

Schema

Patterns inside chromosomes

Example

▫ In one binary chromosome whose length is n, there are 2n schemas

▫ Pattern 11*1 is included in chromosomes 1101 and 1111

▫ In chromosome 1101, there are 16 sub-patterns (1***, *1**, **0*, ***1, 11**, 1*0*, 1**1, *10*, *1*1, **01, 110*, 1*01, 11*1, *101, 1101, ****)

Schema related terminologies

▫ * means don’t care

▫ 0 and 1 are specific symbols.

▫ Defining length is a number of symbols from the leftmost specific symbol to the rightmost specific symbol in a schema

▫ order is a number of specific symbols in a schema

▫ The example in the right has the order 4

order

**1**101***

(10)

Crossover

• An operation that combines two solutions and generate one new solution.

• Example

▫ One-point

▫ Three-point

a b c d e f g h i j

k l m n o p q r s t

a b c d e f q r s t

a b c d e f g h i j

k l m n o p q r s t

a b m n o p g h i t

(11)

Mutation

An operation that introduce a new attribute that is not in the parents to a child solution.

Example

Usually the probability is 0.015, or 0.01

Crossover vs. Mutation

▫ Crossover- more exploitation of the existing solutions

▫ Mutation- more exploration of a new problem space

a b c d e f g h i j

a b c d e f g h x j

(12)

Replacement

Generational GA has no difficulties in replacement

▫ When all generations are replaced, there is no choice

In steady-state GA, replacement is important for the performance

▫ Replace the solution of the worst quality

▫ Replace one of the parents

To preserve the diversity, remove the one that is most similar to the new one

Use Hamming distance to calculate the similarity

Replacement should be determined with the consideration of crossover and mutation

(13)

Problems that GA is useful on

Problems that GA can help

▫ The problems that traditional derterministic methods cannot solve easily

Problems that GA cannot help

▫ The problems that traditional derterministic algorithms can solve easily

▫ The nature of the problems is what traditional

derterministic algorithms cannot solve easily, but the particular problem under consideration is too small (so it is easy and fast to cover all of the problem space)

e.g. 5-city TSP

참조

관련 문서

We can compute all the thermodynamic properties relative to the ideal-gas state at 1 bat and at the same temperature and composition, provided that we have

The eigenvalue problem can be used to identify the limit state of the process, in which the state vector x is reproduced under the multiplication by the.. stochastic matrix

present everything to the students, but they should instead let students find a problem and solve it through various methods on their own to suit the STEAM class structure..

The reason why the Ni-HM secondary battery is not widely used is not necessarily the development technology of the negative electrode material but problem

This study takes about 2-3 days to analyze, which is much shorter than the existing fuming nitric acid method, so it is easy to analyze a large amount of samples and will be

The purpose of this study is to investigate the effect of the “problem solving and programming” area of ​​information subject on perception and

Which of the following statements regarding the 4 response categories by irRC is false?... Which of the following statements regarding the irRC

jQuery Mobile solves this problem, as it only uses HTML, CSS and JavaScript, which is standard for all mobile web browsers..