진화 알고리즘에 대한 이야기 (A story about evolutionary algorithms)

안녕하세요 lee5입니다.

오늘은 오랜만에 시간이 남아서
고퀄리티의 스팀 글들을 하나하나 둘러보고
감탄하는 하루를 보냈습니다.
I had a lot of time today. So I had a day to look around and admire the high-quality steem posts.

이런저런 생각을 하면서
우리 커뮤니티를 괴롭히는 자를 물리치려면(부끄러지 않으려면)
결국 컨텐츠가 좋아야 하는데
내가 기여할 수 있는것은 무엇일까에 대해 생각하며
자신을 돌아보는 시간을 가져봤습니다.
In order not to be ashamed, I had time to look back at myself, thinking about what I could contribute to in order to have good content.

그러다가 "나의 전공분야에 대해 쉽게 전달해보는 것도 좋겠다"는
생각에 이르러 진화알고리즘에 대한 글을 작성하게 되었습니다.
Then I came to the idea that "I would like to easily convey my major field" and wrote an article about the evolution algorithm.

인공지능에 대해서 워낙 많은 이슈가 되고 있어서 여기에 계신분들이라면 딥러닝 정도는 모두 들어보셨을 거라고 생각됩니다.
오늘 다루고자 하는 주제는 약간 다른 방향으로 진화알고리즘에 대한 이야기입니다.
There are so many issues about artificial intelligence, so if you are here, I think you've all heard deep learning.
The topic I am going to cover today is a story about evolution algorithms in a slightly different direction.

현재 인류가 많은 발전을 이루었지만 아직까지 자연으로부터 해답을 얻는 방법들에 대해서 많은 사람들이 고민하고 정말 좋은 방법들을 찾아내서 곳곳에 적용하고 있습니다.
딥러닝의 인공신경망도 뇌세포의 구조에서부터 시작이 되었고, Particle Swarm Optimization, Ant Colony Optimization 과 같이 특정 집단의 행태를 모방하여 실제 산업에서 최적화 문제에 많이 활용되고 있기도 합니다.
At present, mankind has made great progress, but many people still think about ways to get answers from nature and find really good ways to apply them in various places.
Deep Learning's artificial neural network also starts from the structure of brain cells and mimics the behaviors of specific groups such as Particle Swarm Optimization and Ant Colony Optimization.

진화 알고리즘은 여러 문제 풀이 방법들 중 하나로 Heuristic(경험적인) 접근이며 Nature-Inspired(자연모사적) 방법입니다.
인공신경망의 Gradient Decent와 같이 어떤 최적값을 찾기 위한 방법들 중 하나라고 보시면 됩니다.
다만 자연 현상에서 영감을 받은 방법론에 속하고 그 중 진화론을 모티브로한 알고리즘이라고 할 수 있습니다.
An evolutionary algorithm is a Heuristic approach to one of several problem-solving methods and is a Nature-Inspired method.
This is one of the ways to find an optimal value such as the Gradient Decent of an artificial neural network.
However, it belongs to a methodology that is inspired by natural phenomena, and it can be said that it is the algorithm which is the motive of evolution.

즉, 자연의 생물학적인 진화로부터 문제 해결의 실마리를 얻어보자 라는 점이 초기 접근 컨셉입니다.
그렇다면 과연 어떤 원리를 적용했는지가 궁금한데요.
생물학적인 진화가 가지고 있는 핵심 포인트인 Natural Selection(자연선택)과 Genetic Inheritance(상속)을 최적화와 계산에 사용하고자 했습니다.
In other words, it is an early approach concept that we should get a clue to solving problems from the biological evolution of nature.
If so, I wonder what principle was applied.
We wanted to use Natural Selection and Genetic Inheritance, which are key points of biological evolution, for optimization and calculation.

슬슬 지루해지기 시작하실텐데요 ㅜㅜ
한 단계만 더 들어가면
생물학적 진화에서 4가지의 요소를 뽑아냈습니다.
바로 Multiple(다중성), Surviving(생존), Mixing(혼합), Generation(세대)의 개념입니다.
You'll start to get bored.
When we go one step further, we have extracted 4 elements from biological evolution.
It is the concept of Multiple, Surviving, Mixing, and Generation.

이 개념들을 남녀노소 누구나 알고 있는 애니메이션 라이온킹에 적용하면
멧돼지, 원숭이, 개코원숭이, 사자 등 초기에 다양한 개성의 캐릭터들이 등장합니다. (Population)
여기서 동물들은 누구나 짝짓기를 할 수 있습니다. (Mating Pool)
하지만 서로 선택한 짝이 있어야 하죠. (Mates Selected)
이런 짝 선택은 환경에 따라 다르게 일어납니다.
라이온킹은 건전하고 교훈적이어야하는 어린이 애니메이션이다보니 착하고 용감하고 힘이쎈 사자 커플이 선택을 받았습니다.
그렇게 여차저차해서 짝짓기가 일어나고(Mating)
자식이 태어납니다.(Offspring)
그 자식들은 부모의 유전자를 물려받습니다.
이때 온전한 유전자가 아닌 두 개체의 유전자가 혼합되어 나타나고 때론 돌연변이도 발생합니다.
이러한 점때문에 부모를 능가할수도 있고 그렇지 않는 경우도 있지만
그래도 성장하게되면 착하고 용감하고 힘이쎌 확률이 높습니다.
Applying these concepts to an animated Lion King that everyone knows
Characters such as wild boar, monkey, baboon, and lion appear in various early characters. (Population)
Any animal here can mate. (Mating Pool)
But you have to have a partner of your choice. (Mates Selected)
This choice of pairing occurs differently depending on the environment.
Lion King is a healthy and instructive children's animation, and a good, courageous and powerful lion couple has been chosen.
Mating is happening so much,
Child is born. (Offspring)
They inherit the genes of their parents.
At this time, genes that are not whole genes are mixed, and mutations sometimes occur.
This may or may not be the case for parents.
If you grow, you are more likely to be good, brave, and strong.

그렇게 시간이 흘러 부모가 나이들어서 죽거나 힘이 빠지면 자식들이 주인공이 됩니다.(New population)
이런 과정들로부터 앞의 네가지 개념들을 뽑아내고 최적화 탐색 문제에 적용을 합니다.
When the parents die or die, their children become the main characters. (New population)
From these processes, we extract the previous four concepts and apply them to the optimization search problem.

진화 알고리즘은 이 그림과 같이 에러 함수를 최적화 하는 점을 찾아내는 문제에서 잘 동작할 수 있습니다.
초기에 분산 분포되어 있는 여러 점들 중 더 좋은 것들끼리 혼합되어 새로운 세대의 점들을 만들어 냅니다.
그 과정들을 반복하다보면
인구를 구성하고 있는 개체들 중 Optimum에 도달하지 못하는 개체도 발생하지만 전체 시스템적으로 보게되면 보다 빠르고 효과적으로 최적의 해에 도달할 수 있게됩니다.
An evolutionary algorithm can work well in the problem of finding points that optimize error functions as shown in this figure.
It mixes the better of the many scattered initial points to create a new generation of points.
Repeating the process will result in an individual that does not reach the optimum, but if you look at the whole system, you will be able to reach the optimal solution faster and more effectively.

최대한 쉽게 설명하고자 했는데 많이 부족하고 쉽지 않네요. ㅠㅠ
그럼 다음편에 계속하도록 하겠습니다.
I tried to explain it as easily as possible, but it is not easy enough.
Then I will continue.

추가) 이미지는 유전알고리즘 강의 자료에서 발췌되었고 내용은 직접 작성되었습니다.

@lee5