โจ 1 - Introduction ์๋ก
As we know, evolution is one of the most perfect adaptation mechanisms.
์ฐ๋ฆฌ๊ฐ ์๊ณ ์๋ฏ์ด, ์งํ๋ ๊ฐ์ฅ ์๋ฒฝํ ์ ์ ๋ฉ์ปค๋์ฆ ์ค ํ๋์
๋๋ค.
It is a way to achieve extraordinary and complex solutions.
์ด๋ ๋๋๊ณ ๋ณต์กํ ํด๊ฒฐ์ฑ
์ ์ป๋ ํ๋์ ๋ฐฉ๋ฒ์
๋๋ค.
Understanding the principles of evolution gave us a new approach called genetic algorithms.
์งํ์ ์๋ฆฌ๋ฅผ ์ดํดํ๋ ๊ฒ์ ์ฐ๋ฆฌ์๊ฒ ์ ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๋ ์๋ก์ด ์ ๊ทผ ๋ฐฉ์์ ๊ฐ์ ธ๋ค์ฃผ์์ต๋๋ค.
We will now explore this rather beautiful, simple, and effective approach to problem-solving.
์ด์ ์ฐ๋ฆฌ๋ ์ด ๊ฝค๋ ์๋ฆ๋ต๊ณ , ๋จ์ํ๋ฉฐ, ํจ๊ณผ์ ์ธ ๋ฌธ์ ํด๊ฒฐ ์ ๊ทผ๋ฒ์ ํ๊ตฌํ ๊ฒ์
๋๋ค.
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| evolution | ์งํ |
| adaptation | ์ ์ |
| mechanism | ๋ฉ์ปค๋์ฆ, ๊ตฌ์กฐ |
| extraordinary | ๋๋ผ์ด, ๋น๋ฒํ |
| complex | ๋ณต์กํ |
| solution | ํด๊ฒฐ์ฑ |
| principle | ์๋ฆฌ, ์์น |
| approach | ์ ๊ทผ ๋ฐฉ์ |
| genetic algorithm | ์ ์ ์๊ณ ๋ฆฌ์ฆ |
| problem-solving | ๋ฌธ์ ํด๊ฒฐ |
| simple | ๋จ์ํ |
| effective | ํจ๊ณผ์ ์ธ |
โจ 1 - Structure ๊ตฌ์กฐ
In this chapter, we will discuss the following topics :
์ด ์ฅ์์๋ ๋ค์๊ณผ ๊ฐ์ ์ฃผ์ ๋ค์ ๋
ผ์ํ ๊ฒ์
๋๋ค.
-
Nature of genetic algorithm
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ณธ์ง -
Applicability of genetic algorithms
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉ ๊ฐ๋ฅ์ฑ -
Pros and cons of genetic algorithms
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฅ๋จ์ -
Your first genetic algorithm
๋น์ ์ ์ฒซ ๋ฒ์งธ ์ ์ ์๊ณ ๋ฆฌ์ฆ
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| structure | ๊ตฌ์กฐ |
| discuss | ๋ ผ์ํ๋ค |
| topic | ์ฃผ์ |
| nature | ๋ณธ์ง, ํน์ฑ |
| applicability | ์ ์ฉ ๊ฐ๋ฅ์ฑ |
| pros and cons | ์ฅ๋จ์ |
| first | ์ฒซ ๋ฒ์งธ |
โจ 1.1 - Nature of Genetic Algorithm ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ณธ์ง
The rapid development in AI is made possible for humans to obtain solutions to abstract problems.
AI์ ๊ธ์ํ ๋ฐ์ ์ผ๋ก ์ธํด ์ธ๊ฐ์ ์ถ์์ ์ธ ๋ฌธ์ ์ ๋ํ ํด๊ฒฐ์ฑ
์ ์ป์ ์ ์๊ฒ ๋์์ต๋๋ค.
Complex computational problems that are very difficult to solve by classical methods can now be solved by AI.
์ ํต์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ํด๊ฒฐํ๊ธฐ ๋งค์ฐ ์ด๋ ค์ด ๋ณต์กํ ์ฐ์ฐ ๋ฌธ์ ๋ค๋ ์ด์ AI๋ฅผ ํตํด ํด๊ฒฐํ ์ ์์ต๋๋ค.
One of the most powerful techniques to solve such complex problems is genetic algorithms (GA), which is based on the principle of an evolutionary approach.
์ด๋ฌํ ๋ณต์กํ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๊ฐ์ฅ ๊ฐ๋ ฅํ ๊ธฐ๋ฒ ์ค ํ๋๋ ์ ์ ์๊ณ ๋ฆฌ์ฆ(GA)์ผ๋ก, ์ด๋ ์งํ์ ์ ๊ทผ ๋ฐฉ์์ ์๋ฆฌ์ ๊ธฐ๋ฐ์ ๋ก๋๋ค.
In the late 60s, American researcher J. Holland proposed to find solutions to optimization problems using methods and evolution models of animal populations in nature.
1960๋
๋ ํ๋ฐ, ๋ฏธ๊ตญ์ ์ฐ๊ตฌ์ J. Holland๋ ์์ฐ์์ ๋๋ฌผ ์ง๋จ์ ์งํ ๋ชจ๋ธ๊ณผ ๋ฐฉ๋ฒ์ ํ์ฉํ์ฌ ์ต์ ํ ๋ฌธ์ ์ ํด๊ฒฐ์ฑ
์ ์ฐพ๋ ๋ฐฉ๋ฒ์ ์ ์ํ์ต๋๋ค.
Since the evolutionโs basic laws were investigated and described by genetics, the proposed approach was called genetic algorithms.
์งํ์ ๊ธฐ๋ณธ ๋ฒ์น์ด ์ ์ ํ์ ์ํด ์ฐ๊ตฌ๋๊ณ ์ค๋ช
๋์๊ธฐ ๋๋ฌธ์, ์ด ์ ๊ทผ๋ฒ์ ์ ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ๋ช
๋ช
ํ์์ต๋๋ค.
GA is a randomly directed search algorithm based on mechanisms of natural selection and natural genetics.
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์์ฐ ์ ํ๊ณผ ์์ฐ ์ ์ ํ์ ๋ฉ์ปค๋์ฆ์ ๊ธฐ๋ฐ์ผ๋ก ํ ๋ฌด์์ ํ์ ์๊ณ ๋ฆฌ์ฆ์
๋๋ค.
It implements the principle of survival of the fittest, forming and changing the search algorithm based on evolutionary modeling.
์ด๋ ์ ์์์กด์ ์์น์ ๊ตฌํํ๋ฉฐ, ์งํ์ ๋ชจ๋ธ๋ง์ ํตํด ํ์ ์๊ณ ๋ฆฌ์ฆ์ ํ์ฑํ๊ณ ๋ณํ์ํต๋๋ค.
The basic steps in natural evolution are as follows :
์์ฐ ์งํ์ ๊ธฐ๋ณธ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
-
Selection : According to Charles Darwin, natural selection laws were formulated in the book On the Origin of Species.
์ ํ : ์ฐฐ์ค ๋ค์(Charles Darwin)์ ๋ฐ๋ฅด๋ฉด, ์์ฐ ์ ํ์ ๋ฒ์น์ _์ข ์ ๊ธฐ์_์ด๋ผ๋ ์ฑ ์์ ์ ๋ฆฌ๋์์ต๋๋ค. -
The central postulate is that individuals who can better solve problems survive and reproduce more.
ํต์ฌ ์์น์ ๋ฌธ์ ๋ฅผ ๋ ์ ํด๊ฒฐํ ์ ์๋ ๊ฐ์ฒด๊ฐ ์์กดํ๊ณ ๋ ๋ง์ด ๋ฒ์ํ๋ค๋ ๊ฒ์ ๋๋ค. -
In GAs, each individual is a solution to some problem.
์ ์ ์๊ณ ๋ฆฌ์ฆ์์๋ ๊ฐ ๊ฐ์ฒด๊ฐ ์ด๋ค ๋ฌธ์ ์ ํด๊ฒฐ์ฑ ์ ๋ํ๋ ๋๋ค -
According to this principle, individuals who solve the problem better have a greater chance of surviving and leaving offspring.
์ด ์์น์ ๋ฐ๋ผ, ๋ฌธ์ ๋ฅผ ๋ ์ ํด๊ฒฐํ๋ ๊ฐ์ฒด๊ฐ ์์กดํ๊ณ ํ์์ ๋จ๊ธธ ํ๋ฅ ์ด ๋ ๋์์ง๋๋ค.
-
Crossover : This means that the offspring chromosome is made up of parts that are derived from the parentsโ chromosomes.
๊ต์ฐจ : ์ด๋ ์์์ ์ผ์์ฒด๊ฐ ๋ถ๋ชจ์ ์ผ์์ฒด์์ ์ผ๋ถ๋ฅผ ๊ฐ์ ธ์ ํ์ฑ๋จ์ ์๋ฏธํฉ๋๋ค. -
This principle was discovered in 1865 by G. Mendel.
์ด ์๋ฆฌ๋ 1865๋ G. ๋ฉ๋ธ(G. Mendel)์ ์ํด ๋ฐ๊ฒฌ๋์์ต๋๋ค.
-
Mutation : In 1900, H. de Vries discovered the principle of random change.
๋์ฐ๋ณ์ด : 1900๋ , H. ๋ ๋ธ๋ฆฌ์ค(H. de Vries)๊ฐ ๋ฌด์์ ๋ณํ์ ์๋ฆฌ๋ฅผ ๋ฐ๊ฒฌํ์์ต๋๋ค. -
Initially, this term was used to describe significant changes in descendantsโ properties that were not present in their parents.
์ฒ์์๋ ์ด ์ฉ์ด๊ฐ ๋ถ๋ชจ์๊ฒ ์์๋ ํน์ฑ์ด ์์์๊ฒ ๋ํ๋๋ ํฐ ๋ณํ๋ฅผ ์ค๋ช ํ๋ ๋ฐ ์ฌ์ฉ๋์์ต๋๋ค. -
By analogy, genetic algorithms use a similar mechanism to change offspringโs properties, thereby increasing individualsโ diversity in a population.
์ด๋ฅผ ์ ์ถํ์ฌ, ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฒด๊ตฐ ๋ด์์ ๊ฐ์ฒด๋ค์ ๋ค์์ฑ์ ์ฆ๊ฐ์ํค๊ธฐ ์ํด ์ ์ฌํ ๋ฉ์ปค๋์ฆ์ ์ฌ์ฉํฉ๋๋ค.
Genetic algorithms have the following characteristics :
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ ํน์ง์ ๊ฐ์ง๋๋ค.
-
Easy to implement
๊ตฌํ์ด ์ฉ์ดํจ -
Used for a wide range of tasks
๋ค์ํ ๋ฌธ์ ์ ์ ์ฉ ๊ฐ๋ฅํจ -
They do not require any additional information about the nature of the problem
๋ฌธ์ ์ ๋ณธ์ง์ ๋ํ ์ถ๊ฐ์ ์ธ ์ ๋ณด๊ฐ ํ์ ์์ -
Easy and convenient to parallelize
๋ณ๋ ฌ ์ฒ๋ฆฌ๊ฐ ์ฝ๊ณ ํธ๋ฆฌํจ
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| obtain | ์ป๋ค, ํ๋ํ๋ค |
| abstract | ์ถ์์ ์ธ |
| classical | ์ ํต์ ์ธ, ๊ณ ์ ์ ์ธ |
| optimization | ์ต์ ํ |
| evolution | ์งํ |
| mechanism | ๋ฉ์ปค๋์ฆ, ๊ตฌ์กฐ |
| natural selection | ์์ฐ ์ ํ |
| postulate | ๊ฐ์ , ์์น |
| offspring | ์์, ํ์ |
| chromosome | ์ผ์์ฒด |
| descendant | ํ์, ์์ |
| analogy | ์ ์ฌ, ๋น์ |
| diversity | ๋ค์์ฑ |
| parallelize | ๋ณ๋ ฌ ์ฒ๋ฆฌํ๋ค |
| survival of the fittest | ์ ์์์กด |
| formulation | ๊ณต์ํ, ์ ๋ฆฌ |
| mutation | ๋์ฐ๋ณ์ด |
| crossover | ๊ต์ฐจ |
| principle | ์๋ฆฌ, ์์น |
| implementation | ๊ตฌํ, ์คํ |
| convenient | ํธ๋ฆฌํ |
| significant | ์ค์ํ, ์๋ฏธ ์๋ |
| complexity | ๋ณต์ก์ฑ |
โจ 1.2 - Applicability of genetic algorithms ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉ ๊ฐ๋ฅ์ฑ
As a solution, the GA tries to find the extremum of some function that characterizes the quality of the solution to the problem.
์ ์ ์๊ณ ๋ฆฌ์ฆ(GA)์ ๋ฌธ์ ์ ํด์ ํ์ง์ ๋ํ๋ด๋ ์ด๋ค ํจ์์ ๊ทน๊ฐ์ ์ฐพ์ผ๋ ค๊ณ ์๋ํฉ๋๋ค.
Generally, the GA does not guarantee that the solution found is the best of all thatโs possible.
์ผ๋ฐ์ ์ผ๋ก, GA๋ ์ฐพ์ ํด๊ฐ ๊ฐ๋ฅํ ๋ชจ๋ ํด ์ค์์ ์ต์ ์์ ๋ณด์ฅํ์ง ์์ต๋๋ค.
Usually, this is not required, but it is only important that the found solution satisfies the meaning of the problem being solved.
๋๋ถ๋ถ์ ๊ฒฝ์ฐ, ์ด๋ ํ์์ ์ด์ง ์์ผ๋ฉฐ, ์ค์ํ ๊ฒ์ ์ฐพ์ ํด๊ฒฐ์ฑ
์ด ํด๊ฒฐํ๋ ค๋ ๋ฌธ์ ์ ์๋ฏธ๋ฅผ ์ถฉ์กฑํ๋ ๊ฒ์
๋๋ค.
The areas of application of GAs include the following:
GA์ ์ ์ฉ ๋ถ์ผ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
-
Search for extremum of various functions
๋ค์ํ ํจ์์ ๊ทน๊ฐ ํ์ -
Finding the shortest paths (traveling salesman problem)
์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ (์ธํ์ ๋ฌธ์ ) -
Combinatorial optimization
์กฐํฉ ์ต์ ํ -
Tasks of placement and scheduling
๋ฐฐ์น ๋ฐ ์ผ์ ๊ณํ ๋ฌธ์ -
Automatic programming tasks
์๋ ํ๋ก๊ทธ๋๋ฐ ๊ณผ์ -
AI tasks (choosing the structure and parameters of artificial neural networks)
AI ๊ณผ์ (์ธ๊ณต ์ ๊ฒฝ๋ง์ ๊ตฌ์กฐ ๋ฐ ๋งค๊ฐ๋ณ์ ์ ํ)
In real-time scenarios, GAs are used to develop AI systems, like designing tasks for aircraft routes at airports, finding the optimal behavior of robots, problems of constructing investment portfolios, and so on.
์ค์ ์ํฉ์์ GA๋ AI ์์คํ
๊ฐ๋ฐ์ ์ฌ์ฉ๋๋ฉฐ, ๊ณตํญ์์ ํญ๊ณต๊ธฐ์ ์ต์ ๊ฒฝ๋ก ์ค๊ณ, ๋ก๋ด์ ์ต์ ํ๋ ํ์, ํฌ์ ํฌํธํด๋ฆฌ์ค ๊ตฌ์ฑ ๋ฌธ์ ๋ฑ์ ํ์ฉ๋ฉ๋๋ค.
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| solution | ํด๊ฒฐ์ฑ , ํด |
| extremum | ๊ทน๊ฐ |
| characterize | ํน์ง์ง๋ค, ์ ์ํ๋ค |
| guarantee | ๋ณด์ฅํ๋ค |
| satisfy | ๋ง์กฑ์ํค๋ค |
| application | ์ ์ฉ, ์์ฉ |
| placement | ๋ฐฐ์น |
| develop | ๊ฐ๋ฐํ๋ค |
| optimal | ์ต์ ์ |
| behavior | ํ๋ |
| construct | ๊ตฌ์ฑํ๋ค, ๋ง๋ค๋ค |
โจ 1.3 - Pros and cons of genetic algorithms ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฅ๋จ์
Like any other approach to problem-solving, GAs have their pros and cons as well.
๋ค๋ฅธ ๋ฌธ์ ํด๊ฒฐ ๋ฐฉ๋ฒ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก, ์ ์ ์๊ณ ๋ฆฌ์ฆ(GA)์๋ ์ฅ์ ๊ณผ ๋จ์ ์ด ์กด์ฌํฉ๋๋ค.
Understanding these features will allow you to solve practical problems in a better way.
์ด๋ฌํ ํน์ฑ์ ์ดํดํ๋ฉด ์ค์ง์ ์ธ ๋ฌธ์ ๋ฅผ ๋ ํจ๊ณผ์ ์ผ๋ก ํด๊ฒฐํ ์ ์์ต๋๋ค.
The pros of genetic algorithms are as follows :
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ฅ์ ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
-
A wide range of tasks to be solved : GA is successfully applied in the following areas โ combinatorial optimization, finance (portfolio optimization), machine learning (feature extraction, neural network hyper-parameter optimization), code-breaking, game theory, natural sciences, and so on.
ํด๊ฒฐ ๊ฐ๋ฅํ ๋ฌธ์ ์ ํญ์ด ๋์ : GA๋ ์กฐํฉ ์ต์ ํ, ๊ธ์ต(ํฌํธํด๋ฆฌ์ค ์ต์ ํ), ๋จธ์ ๋ฌ๋(ํน์ง ์ถ์ถ, ์ ๊ฒฝ๋ง ํ์ดํผํ๋ผ๋ฏธํฐ ์ต์ ํ), ์ฝ๋ ํด๋ , ๊ฒ์ ์ด๋ก , ์์ฐ ๊ณผํ ๋ฑ ๋ค์ํ ๋ถ์ผ์ ์ฑ๊ณต์ ์ผ๋ก ์ ์ฉ๋ฉ๋๋ค.
-
Ease of implementation : The algorithm implies the presence of steps โ natural selection, crossing, and mutation. This conceptual simplicity makes this method available to a wide range of developers.
๊ตฌํ์ด ์ฉ์ดํจ : ์ด ์๊ณ ๋ฆฌ์ฆ์ ์์ฐ ์ ํ, ๊ต์ฐจ, ๋์ฐ๋ณ์ด ๋ฑ์ ๋จ๊ณ๋ฅผ ํฌํจํฉ๋๋ค. ์ด๋ฌํ ๊ฐ๋ ์ ๋จ์์ฑ ๋๋ถ์ ๋ง์ ๊ฐ๋ฐ์๋ค์ด ์ฝ๊ฒ ์ฌ์ฉํ ์ ์์ต๋๋ค.
-
Resistance to dynamic changes in problem conditions : The GA is able to retrain if the conditions of the problem change when searching for a solution.
๋ฌธ์ ์กฐ๊ฑด์ ๋์ ๋ณํ์ ๋ํ ์ ํญ์ฑ : ๋ฌธ์ ํด๊ฒฐ ๊ณผ์ ์์ ์กฐ๊ฑด์ด ๋ณํํ๋๋ผ๋ GA๋ ์ฌํ์ตํ ์ ์์ต๋๋ค.
-
The ability for self-adaptation : GAs are able, after a certain period of evolution, to adapt to the conditions of the problem being solved.
์์ฒด ์ ์ ๋ฅ๋ ฅ : GA๋ ์ผ์ ํ ์งํ ๊ณผ์ ์ ๊ฑฐ์น ํ, ํด๊ฒฐํ๋ ค๋ ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ์ํ ์ ์์ต๋๋ค.
-
Ease of scaling : Can easily be used on big data where the data is spread over distributed systems. GAs, as a highly parallel process, can be easily parallelized, which makes it possible to proportionally accelerate the finding of a solution with an increase in computing power.
ํ์ฅ ์ฉ์ด์ฑ : GA๋ ๋ฐ์ดํฐ๊ฐ ๋ถ์ฐ ์์คํ ์ ๋ถํฌ๋ ๋น ๋ฐ์ดํฐ ํ๊ฒฝ์์๋ ์ฝ๊ฒ ์ฌ์ฉํ ์ ์์ต๋๋ค. GA๋ ๋ณ๋ ฌ ์ฒ๋ฆฌ์ ์ ํฉํ์ฌ ์ปดํจํ ์ฑ๋ฅ์ด ์ฆ๊ฐํ ์๋ก ๋ฌธ์ ํด๊ฒฐ ์๋๋ฅผ ๋น๋ก์ ์ผ๋ก ํฅ์์ํฌ ์ ์์ต๋๋ค.
-
Solving problems for which there is no solution experience : One of the biggest advantages of GAs is their ability to investigate problems for which there is no relevant solution experience. It should be noted that expert assessments are often used to solve difficult-to-formalize problems, but they sometimes give less acceptable solutions than automated methods
ํด๊ฒฐ ๊ฒฝํ์ด ์๋ ๋ฌธ์ ํด๊ฒฐ ๊ฐ๋ฅ : GA์ ๊ฐ์ฅ ํฐ ์ฅ์ ์ค ํ๋๋ ๊ธฐ์กด์ ํด๊ฒฐ ๊ฒฝํ์ด ์๋ ๋ฌธ์ ๋ฅผ ํ์ํ ์ ์๋ค๋ ์ ์ ๋๋ค. ์ผ๋ฐ์ ์ผ๋ก ์ ๋ฌธ๊ฐ์ ํ๊ฐ๋ฅผ ํตํด ํ์ํํ๊ธฐ ์ด๋ ค์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ค ํ์ง๋ง, ๊ทธ๋ค์ ๊ฐ๋ ์๋ํ๋ ๋ฐฉ๋ฒ๋ณด๋ค ๋ง์กฑ์ค๋ฝ์ง ๋ชปํ ํด๊ฒฐ์ฑ ์ ์ ๊ณตํ๊ธฐ๋ ํฉ๋๋ค.
The cons of genetic algorithms are as follows :
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๋จ์ ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
-
The complexity of representing an individual in a population and determining the fitness function.
๊ฐ์ฒด๋ฅผ ์ด๋ป๊ฒ ํํํ ๊ฒ์ธ์ง, ๊ทธ๋ฆฌ๊ณ ์ ํฉ๋๋ฅผ ์ด๋ป๊ฒ ํ๊ฐํ ๊ฒ์ธ์ง ๊ฒฐ์ ํ๋ ๊ณผ์ ์ด ๋ณต์กํ ์ ์์ต๋๋ค.
-
For real problems, it is initially not-at-all obvious in what form it is necessary to present a set of individual genes for a successful solution to the problem, and also determine the assessment of the quality of a particular individual.
์ค์ ๋ฌธ์ ์์๋ ๊ฐ๋ณ ์ ์ ์ ์ธํธ๋ฅผ ์ด๋ค ํํ๋ก ํํํด์ผ ์ฑ๊ณต์ ์ธ ํด๊ฒฐ์ด ๊ฐ๋ฅํ์ง, ๊ทธ๋ฆฌ๊ณ ํน์ ๊ฐ์ฒด์ ํ์ง์ ์ด๋ป๊ฒ ํ๊ฐํด์ผ ํ ์ง ์ฒ์์๋ ๋ช ํํ์ง ์์ ์ ์์ต๋๋ค.
(๊ฐ์ฒด ํํ๊ณผ ์ ํฉ๋ ํจ์ ์ค์ ์ ๋ณต์ก์ฑ)
-
The choice of parameters of the architecture of the GA.
GA๋ฅผ ๊ตฌ์ฑํ๋ ๋ค์ํ ๋งค๊ฐ๋ณ์๋ฅผ ์ด๋ป๊ฒ ์ ํํด์ผ ํ๋์ง์ ๋ํ ๋ช ํํ ๊ธฐ์ค์ด ์์ต๋๋ค.
(GA์ ๊ตฌ์กฐ์ ๋งค๊ฐ๋ณ์ ์ ํ ๋ฌธ์ )
-
There are no effective criteria for the termination of the algorithm.
GA๋ฅผ ์ธ์ ๋ฉ์ถฐ์ผ ํ๋์ง์ ๋ํ ๋ช ํํ ๊ธฐ์ค์ด ์๋ ๊ฒฝ์ฐ๊ฐ ๋ง์ต๋๋ค.
(์๊ณ ๋ฆฌ์ฆ ์ข ๋ฃ์ ๋ํ ํจ๊ณผ์ ์ธ ๊ธฐ์ค์ด ์์ )
-
Not effective for finding an extremum for smooth functions with one extremum.
GA๋ ๋ค์ค ๊ทน๊ฐ์ด ์๋ ๋ฌธ์ ์์ ๋ ํจ๊ณผ์ ์ด๋ฉฐ, ๊ทน๊ฐ์ด ํ๋๋ง ์๋ ๋งค๋๋ฌ์ด ํจ์์์๋ ํจ์จ์ด ๋จ์ด์ง ์ ์์ต๋๋ค.
(๋ค์ค ๊ทน๊ฐ์ ๊ฐํ๋, ๋จ์ผ ๊ทน๊ฐ์ ๋นํจ์จ์ )
-
They require large enough computing resources.
GA๋ ๋๊ท๋ชจ ๊ณ์ฐ์ ์ํํด์ผ ํ๋ฏ๋ก ์๋นํ ์ปดํจํ ์์์ ์๊ตฌํ ์ ์์ต๋๋ค.
(๋ง์ ์ปดํจํ ์์์ด ํ์)
-
When solving problems, there are cases of premature convergence, and therefore, generally, they do not guarantee in finding the global extremum.
GA๋ ํ์ ๊ณผ์ ์์ ์กฐ๊ธฐ์ ์ต์ ํด๋ฅผ ์ฐพ์๋ค๊ณ ํ๋จํ์ฌ ๋ ๋์ ํด๋ฅผ ์ฐพ๋ ํ์์ ๋ฉ์ถ ์ ์์ผ๋ฉฐ, ์ด๋ก ์ธํด ์ ์ญ ๊ทน๊ฐ์ ๋ฐ๋์ ์ฐพ๋๋ค๊ณ ๋ณด์ฅํ ์ ์์ต๋๋ค.
(์กฐ๊ธฐ ์๋ ด ๋ฌธ์ ๋ฐ์ ๊ฐ๋ฅ์ฑ)
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| extremum | ๊ทน๊ฐ |
| conceptual | ๊ฐ๋ ์ ์ธ |
| retrain | ์ฌํ์ตํ๋ค |
| self-adaptation | ์์ฒด ์ ์ |
| distributed systems | ๋ถ์ฐ ์์คํ |
| scalability | ํ์ฅ์ฑ |
| proportionally | ๋น๋ก์ ์ผ๋ก |
| computing power | ๊ณ์ฐ ์ฑ๋ฅ, ์ปดํจํ ํ์ |
| formalize | ํ์ํํ๋ค |
| assessment | ํ๊ฐ |
| fitness function | ์ ํฉ๋ ํจ์ |
| architecture (of GA) | ๊ตฌ์กฐ, ์ค๊ณ (GA์ ๊ตฌ์กฐ) |
| termination | ์ข ๋ฃ, ๋๋ |
| premature convergence | ์กฐ๊ธฐ ์๋ ด |
| global extremum | ์ ์ญ ๊ทน๊ฐ |
โจ 1.4 - Your first genetic algorithm ๋น์ ์ ์ฒซ ๋ฒ์งธ ์ ์ ์๊ณ ๋ฆฌ์ฆ
Well, letโs try to build our first GA solution.
์, ์ฐ๋ฆฌ์ ์ฒซ ๋ฒ์งธ GA ์๋ฃจ์
์ ๋ง๋ค์ด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
We will start from a trivial example which shows us the basics.
๊ธฐ๋ณธ์ ๋ณด์ฌ์ฃผ๋ ๊ฐ๋จํ ์์ ๋ถํฐ ์์ํ๊ฒ ์ต๋๋ค.
Letโs say we have the following function, sin(x) - 0.2 * abs(x).
๋ค์๊ณผ ๊ฐ์ ํจ์๊ฐ ์๋ค๊ณ ๊ฐ์ ํด ๋ด
์๋ค: sin(x) - 0.2 * abs(x).
Refer to the following figure
๋ค์ ๊ทธ๋ฆผ์ ์ฐธ๊ณ ํ์ธ์.
We will find the maxima of the preceding function.
์ฐ๋ฆฌ๋ ์์ ์ฃผ์ด์ง ํจ์์ ์ต๋๊ฐ์ ์ฐพ์ ๊ฒ์
๋๋ค.
This function has several local maximums.
์ด ํจ์๋ ์ฌ๋ฌ ๊ฐ์ ๊ตญ์ ์ต๋๊ฐ์ ๊ฐ์ง๊ณ ์์ต๋๋ค.
All individuals in the population in our GA will try to climb as high as possible.
GA์ ๊ฐ์ฒด๋ค์ ๊ฐ๋ฅํ ํ ๋์ ๊ฐ์ ์ฐพ์ผ๋ ค๊ณ ํ ๊ฒ์
๋๋ค.
Letโs see the GA in action.
GA๊ฐ ์๋ํ๋ ๊ฒ์ ์ดํด๋ณด๊ฒ ์ต๋๋ค.
Execute the following code (we will cover the details in future chapters).
๋ค์ ์ฝ๋๋ฅผ ์คํํ์ธ์ (์ธ๋ถ ์ฌํญ์ ์ดํ ์ฅ์์ ๋ค๋ฃฐ ๊ฒ์
๋๋ค).
๐ก ์ฝ๋์ ๋ํ ์์ธํ ๋ถ์์ ์ฝ๋ ํด๋๋ฅผ ์ฐธ๊ณ ํ์ธ์
import random
from typing import List
import numpy as np
import matplotlib.pyplot as plt
def constraints(g, min_=-10, max_=10):
if max_ and g > max_:
g = max_
if min_ and g < min_:
g = min_
return g
def crossover_blend(g1, g2, alpha):
shift = (1 + 2 * alpha) * random.random() - alpha
new_g1 = (1 - shift) * g1 + shift * g2
new_g2 = shift * g1 + (1 - shift) * g2
return constraints(new_g1), constraints(new_g2)
def mutate_gaussian(g, mu, sigma):
mutated_gene = g + random.gauss(mu, sigma)
return constraints(mutated_gene)
def select_tournament(population, size):
new_offspring = []
for _ in range(len(population)):
candidates = [random.choice(population) for _ in range(size)]
new_offspring.append(max(candidates, key=lambda ind: ind.fitness))
return new_offspring
def func(x):
return np.sin(x) - .2 * abs(x)
def get_best(population):
best = population[0]
for ind in population:
if ind.fitness > best.fitness:
best = ind
return best
def plot_population(population, number_of_population):
best = get_best(population)
x = np.linspace(-10, 10)
plt.plot(x, func(x), '--', color='blue')
plt.plot(
[ind.get_gene() for ind in population],
[ind.fitness for ind in population],
'o', color='orange'
)
plt.plot([best.get_gene()], [best.fitness], 's', color='green')
plt.title(f"Generation number {number_of_population}")
plt.show()
plt.close()
class Individual:
def __init__(self, gene_list: List[float]) -> None:
self.gene_list = gene_list
self.fitness = func(self.gene_list[0])
def get_gene(self):
return self.gene_list[0]
def crossover(parent1, parent2):
child1_gene, child2_gene = crossover_blend(parent1.get_gene(), parent2.get_gene(), 1)
return Individual([child1_gene]), Individual([child2_gene])
def mutate(ind):
mutated_gene = mutate_gaussian(ind.get_gene(), 0, 1)
return Individual([mutated_gene])
def select(population):
return select_tournament(population, size=3)
def create_random():
return Individual([random.uniform(-10, 10)])
random.seed(52)
# random.seed(16) # local maximum
POPULATION_SIZE = 10
CROSSOVER_PROBABILITY = .8
MUTATION_PROBABILITY = .1
MAX_GENERATIONS = 10
first_population = [create_random() for _ in range(POPULATION_SIZE)]
plot_population(first_population, 0)
generation_number = 0
population = first_population.copy()
while generation_number < MAX_GENERATIONS:
generation_number += 1
# SELECTION
offspring = select(population)
# CROSSOVER
crossed_offspring = []
for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CROSSOVER_PROBABILITY:
kid1, kid2 = crossover(ind1, ind2)
crossed_offspring.append(kid1)
crossed_offspring.append(kid2)
else:
crossed_offspring.append(ind1)
crossed_offspring.append(ind2)
# MUTATION
mutated_offspring = []
for mutant in crossed_offspring:
if random.random() < MUTATION_PROBABILITY:
new_mutant = mutate(mutant)
mutated_offspring.append(new_mutant)
else:
mutated_offspring.append(mutant)
population = mutated_offspring.copy()
plot_population(population, generation_number)Now, letโs examine how individuals of each population behave during each generation.
์ด์ ๊ฐ ์ธ๋ ๋์ ๋ชจ์ง๋จ์ ๊ฐ์ฒด๋ค์ด ์ด๋ป๊ฒ ํ๋ํ๋์ง ์ดํด๋ณด๊ฒ ์ต๋๋ค.
Refer to the following graphs:
๋ค์ ๊ทธ๋ํ๋ฅผ ์ฐธ๊ณ ํ์ธ์.
In the preceding figure, the first generation is just the random distribution of points on the curve.
์ ๊ทธ๋ฆผ์์ ์ฒซ ๋ฒ์งธ ์ธ๋๋ ๋จ์ํ ๊ณก์ ์์ ๋ฌด์์๋ก ๋ถํฌ๋ ์ ๋ค์
๋๋ค.
We denote the green point as the highest.
์ฐ๋ฆฌ๋ ๋
น์ ์ ์ ๊ฐ์ฅ ๋์ ๊ฐ์ผ๋ก ํ์ํฉ๋๋ค.
The second generation, as shown in the preceding figure, produces an individual on the top of the highest hill.
์ด์ ๊ทธ๋ฆผ์์ ๋ณผ ์ ์๋ฏ์ด, ๋ ๋ฒ์งธ ์ธ๋๋ ๊ฐ์ฅ ๋์ ์ธ๋์ ๊ผญ๋๊ธฐ์ ์๋ ๊ฐ์ฒด๋ฅผ ์์ฑํฉ๋๋ค.
But letโs see how other individuals will behave.
๊ทธ๋ฌ๋ ๋ค๋ฅธ ๊ฐ์ฒด๋ค์ด ์ด๋ป๊ฒ ํ๋ํ ์ง ์ดํด๋ด
์๋ค.
The third generation, as shown in the preceding figure, shows an interesting situation.
์ด์ ๊ทธ๋ฆผ์์ ๋ณผ ์ ์๋ฏ์ด, ์ธ ๋ฒ์งธ ์ธ๋๋ ํฅ๋ฏธ๋ก์ด ์ํฉ์ ๋ณด์ฌ์ค๋๋ค.
The highest point moved a little bit right from the top.
๊ฐ์ฅ ๋์ ์ง์ ์ด ๊ผญ๋๊ธฐ์์ ์ฝ๊ฐ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ์ต๋๋ค.
This behavior is typical for genetic algorithms.
์ด๋ฌํ ํ๋์ ์ ์ ์๊ณ ๋ฆฌ์ฆ์์ ์ผ๋ฐ์ ์ผ๋ก ๋ํ๋๋ ํ์์
๋๋ค.
Evolution is the constant search for the best solution;
์งํ๋ ์ต์์ ํด๊ฒฐ์ฑ
์ ์ง์์ ์ผ๋ก ํ์ํ๋ ๊ณผ์ ์
๋๋ค.
it always explores the nearest area trying to offer another slightly different mechanism that suits better.
ํญ์ ์ฃผ๋ณ ์์ญ์ ํ์ํ๋ฉฐ ๋ ์ ํฉํ ์๋ก์ด ๋ฉ์ปค๋์ฆ์ ์ ์ํ๋ ค๊ณ ํฉ๋๋ค.
In the fourth generation, as shown in the preceding figure, we see how the entire population begins to strive for the individual that is at the top.
์ด์ ๊ทธ๋ฆผ์์ ๋ณผ ์ ์๋ฏ์ด, ๋ค ๋ฒ์งธ ์ธ๋์์๋ ์ ์ฒด ๊ฐ์ฒด๊ตฐ์ด ๊ผญ๋๊ธฐ์ ์๋ ๊ฐ์ฒด๋ฅผ ํฅํด ๋์๊ฐ๊ธฐ ์์ํ๋ ๋ชจ์ต์ ๋ณผ ์ ์์ต๋๋ค.
The most successful individual in several generations managed to share their genes with other members of the population,
์ฌ๋ฌ ์ธ๋ ๋์ ๊ฐ์ฅ ์ฑ๊ณต์ ์ธ ๊ฐ์ฒด๋ ์์ ์ ์ ์ ์๋ฅผ ๊ฐ์ฒด๊ตฐ์ ๋ค๋ฅธ ๊ตฌ์ฑ์๋ค๊ณผ ๊ณต์ ํ ์ ์์์ต๋๋ค.
which made them look like themselves.
๊ทธ ๊ฒฐ๊ณผ, ๋ค๋ฅธ ๊ฐ์ฒด๋ค๋ ๊ทธ ๊ฐ์ฒด์ ๋น์ทํ ๋ชจ์ต์ ๊ฐ์ง๊ฒ ๋์์ต๋๋ค.
Closer! Almost all population individuals have reached the top, as shown in the preceding figure.
๊ฑฐ์ ๋ค ์์ต๋๋ค! ์ด์ ๊ทธ๋ฆผ์์ ๋ณผ ์ ์๋ฏ์ด, ๊ฑฐ์ ๋ชจ๋ ๊ฐ์ฒด๊ฐ ๊ผญ๋๊ธฐ์ ๋๋ฌํ์ต๋๋ค.
After 10 generations, all individuals of the population are in the most optimal position for themselves, as shown in the preceding figure.
10์ธ๋ ํ, ๊ฐ์ฒด๊ตฐ์ ๋ชจ๋ ๊ฐ์ฒด๊ฐ ์ด์ ๊ทธ๋ฆผ์์ ๋ณด์ด๋ ๊ฒ์ฒ๋ผ ์์ ์๊ฒ ๊ฐ์ฅ ์ต์ ์ธ ์์น์ ๋๋ฌํฉ๋๋ค.
NOTE : GA is random by its nature, and by itself, it cannot guarantee the best solution (that is, global maxima)!
์ฐธ๊ณ : GA(์ ์ ์๊ณ ๋ฆฌ์ฆ)๋ ๋ณธ์ง์ ์ผ๋ก ๋ฌด์์์ ์ด๋ฉฐ, ์์ฒด์ ์ผ๋ก๋ ์ต์ ์ ํด(์ฆ, ์ ์ญ ์ต๋๊ฐ)๋ฅผ ๋ณด์ฅํ์ง ์์ต๋๋ค!
We will cover different techniques trying to maximize this probability, but it is important to understand that GA finds local, but not global maxima.
์ด ํ๋ฅ ์ ๊ทน๋ํํ๋ ๋ค์ํ ๊ธฐ๋ฒ์ ๋ค๋ฃฐ ์์ ์ด์ง๋ง, GA๋ ์ ์ญ ์ต๋๊ฐ์ด ์๋๋ผ ์ง์ญ ์ต๋๊ฐ์ ์ฐพ๋๋ค๋ ์ ์ ์ดํดํ๋ ๊ฒ์ด ์ค์ํฉ๋๋ค.
Letโs see the random behavior of our solution, uncomment the following line in the preceding script :
์ฐ๋ฆฌ์ ํด๊ฒฐ์ฑ
์ด ์ด๋ป๊ฒ ๋ฌด์์์ ์ผ๋ก ๋์ํ๋์ง ์ดํด๋ณด๊ฒ ์ต๋๋ค. ์ด์ ์คํฌ๋ฆฝํธ์์ ๋ค์ ์ค์ ์ฃผ์์ ํด์ ํ์ญ์์ค.
# random.seed(16) # local maximum
We have the following final distribution of population :
๋ค์์ ๊ฐ์ฒด๊ตฐ์ ์ต์ข
๋ถํฌ์
๋๋ค.
In the case of our problem, this is very unlikely, but it can happen.
์ง์ญ : ์ฐ๋ฆฌ ๋ฌธ์ ์ ๊ฒฝ์ฐ, ์ด๋ ๋งค์ฐ ๋๋ฌธ ์ผ์ด์ง๋ง ๋ฐ์ํ ์ ์์ต๋๋ค.
์์ญ : ์ฐ๋ฆฌ์ ๊ฒฝ์ฐ์๋ ๋๋ฌธ ์ผ์ด์ง๋ง, ๋๋ค ์๋์ ๋ฐ๋ผ ์ง์ญ ์ต์ ํด์ ๊ฐํ ๊ฐ๋ฅ์ฑ์ด ์์ต๋๋ค.
In future chapters, we will cover the details of the algorithm we used here.
์์ผ๋ก์ ์ฅ์์ ์ฐ๋ฆฌ๊ฐ ์ฌ๊ธฐ์ ์ฌ์ฉํ ์๊ณ ๋ฆฌ์ฆ์ ์ธ๋ถ ์ฌํญ์ ๋ค๋ฃฐ ๊ฒ์
๋๋ค.
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| trivial | ์ฌ์ํ, ๋จ์ํ |
| denote | ๋ํ๋ด๋ค, ํ์ํ๋ค |
| preceding | ์ด์ ์, ์์ |
| distribution | ๋ถํฌ |
| strive | ๋ ธ๋ ฅํ๋ค, ์ ์ฐ๋ค |
| mechanism | ๊ธฐ์ , ๋ฉ์ปค๋์ฆ |
| constantly | ๋์์์ด, ์ง์์ ์ผ๋ก |
| suit | ์ ํฉํ๋ค, ๋ง๋ค |
| optimal | ์ต์ ์ |
| random | ๋ฌด์์์ |
| maximize | ๊ทน๋ํํ๋ค |
| global maxima | ์ ์ญ ์ต๋๊ฐ |
| uncomment | ์ฃผ์์ ํด์ ํ๋ค |
| final distribution | ์ต์ข ๋ถํฌ |
| unlikely | ์์ ๋ฒํ์ง ์์, ๊ฐ๋ฅ์ฑ์ด ๋ฎ์ |
โจ 1 - Conclusion ๊ฒฐ๋ก
In this chapter, we began our acquaintance with genetic algorithms, how this approach relates to the principles of evolution and natural selection.
์ด๋ฒ ์ฅ์์๋ ์ ์ ์๊ณ ๋ฆฌ์ฆ๊ณผ์ ์ฒซ ๋ง๋จ์ ๊ฐ์ง๋ฉฐ, ์ด ์ ๊ทผ๋ฒ์ด ์งํ์ ์์ฐ ์ ํ์ ์๋ฆฌ์ ์ด๋ป๊ฒ ๊ด๋ จ๋๋์ง์ ๋ํด ์์๋ณด์์ต๋๋ค.
We examined the operation of this algorithm in action with a specific example.
๋ํ, ํน์ ์์ ๋ฅผ ํตํด ์ด ์๊ณ ๋ฆฌ์ฆ์ด ์ด๋ป๊ฒ ์๋ํ๋์ง๋ฅผ ์ดํด๋ณด์์ต๋๋ค.
In the next chapter, we will continue our study and consider the basic logical blocks and the structure of genetic algorithms.
๋ค์ ์ฅ์์๋ ์ฐ๊ตฌ๋ฅผ ๊ณ์ ์งํํ๋ฉฐ, ์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ณธ ๋
ผ๋ฆฌ ๋ธ๋ก๊ณผ ๊ตฌ์กฐ๋ฅผ ์ดํด๋ณผ ๊ฒ์
๋๋ค.
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| acquaintance | ์น์ํจ, ์ฒซ ๋ง๋จ |
| relate to | ~์ ๊ด๋ จ๋๋ค |
| examine | ์กฐ์ฌํ๋ค, ์ดํด๋ณด๋ค |
| in action | ์ค์ ๋ก ์๋ํ๋ ๋ชจ์ต |
| specific example | ํน์ ์์ |
| logical block | ๋ ผ๋ฆฌ ๋ธ๋ก |
| structure | ๊ตฌ์กฐ |
| consider | ๊ณ ๋ คํ๋ค, ๊ฒํ ํ๋ค |
โจ 1 - Questions ์ง๋ฌธ
Genetic algorithms always guarantee to find the best solution. Is it true?
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ํญ์ ์ต์ ์ ํด๋ฅผ ์ฐพ๋ ๊ฒ์ ๋ณด์ฅํ ๊น์?
One of the most important features of genetic algorithms is to find a solution to a problem without any accumulated experience. Is that true?
์ ์ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ์ฅ ์ค์ํ ํน์ง ์ค ํ๋๋ ์ถ์ ๋ ๊ฒฝํ ์์ด ๋ฌธ์ ์ ํด๊ฒฐ์ฑ
์ ์ฐพ๋ ๊ฒ์
๋๋ค. ์ด๊ฒ์ด ์ฌ์ค์ผ๊น์?
How would you formulate the basic principles of natural selection?
์์ฐ ์ ํ์ ๊ธฐ๋ณธ ์๋ฆฌ๋ฅผ ์ด๋ป๊ฒ ์ ๋ฆฌํ ์ ์์๊น์?
๐ก ์ฃผ์ ๋จ์ด
| ์์ด ๋จ์ด | ํ๊ธ ๋ป |
|---|---|
| guarantee | ๋ณด์ฅํ๋ค |
| accumulate | ์ถ์ ํ๋ค |
| formulate | ์ ๋ฆฌํ๋ค, ๊ณต์ํํ๋ค |
| principle | ์๋ฆฌ, ์์น |