당신은 주제를 찾고 있습니까 “유전 알고리즘 예제 – 유전 알고리즘으로 비밀번호를 뚫어보자 – Python“? 다음 카테고리의 웹사이트 th.taphoamini.com 에서 귀하의 모든 질문에 답변해 드립니다: th.taphoamini.com/wiki. 바로 아래에서 답을 찾을 수 있습니다. 작성자 빵형의 개발도상국 이(가) 작성한 기사에는 조회수 23,515회 및 좋아요 314개 개의 좋아요가 있습니다.
Table of Contents
유전 알고리즘 예제 주제에 대한 동영상 보기
여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!
d여기에서 유전 알고리즘으로 비밀번호를 뚫어보자 – Python – 유전 알고리즘 예제 주제에 대한 세부정보를 참조하세요
유전 알고리즘으로 엄마가 걸어놓은 비밀번호를 손쉽게 뚫어봅시다!
유전자 생성 – 유전자 평가 – 교배 – 진화
Source code(Github): https://github.com/kairess/password_cracker
Dependencies:
– Python
사업 및 개발문의: [email protected]
빵형의 개발도상국 후원: https://toon.at/donate/helloworld
유전 알고리즘 예제 주제에 대한 자세한 내용은 여기를 참조하세요.
basic genetic algorithm / 유전 알고리즘 입문 (예제) – Medium
basic genetic algorithm / 유전 알고리즘 입문 (예제). Charles Darwin. 유전 알고리즘은 찰스 다윈의 ‘자연 선택’ 개념을 구현한 알고리즘 입니다.
Source: medium.com
Date Published: 8/29/2022
View: 8833
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자!
그렇다면 파이썬으로 유전 알고리즘을 구현해보자. 함수가 많아서 함수 하나하나씩 잘라서 설명을 해보려고 한다. 우선 비밀번호는 문자열을 사용하고 …
Source: tasddc.tistory.com
Date Published: 3/15/2022
View: 5007
유전 알고리즘 – GIL’s LAB
유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 … 최적화 문제를 소개하는 과정에서 나왔던 예제를 유전 알고리즘을 통해 …
Source: gils-lab.tistory.com
Date Published: 3/22/2021
View: 1535
유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기
1. 정의. 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 …
Source: koreapy.tistory.com
Date Published: 8/5/2021
View: 9595
유전 알고리즘 가지고 놀기 – Blog4Study
예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm 유전 알고리즘이란, “유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 …
Source: blog.devkcr.org
Date Published: 9/5/2021
View: 8519
Top 6 유전 알고리즘 예제 Top 20 Best Answers
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! — 수구리의 데브로그. Article author: tasddc.tistory.com; Reviews from users: …Source: toplist.avitour.vn
Date Published: 10/23/2022
View: 5378
유전 알고리즘 (Genetic Algorithm) – 블로그 – 네이버
유전 알고리즘 (Genetic Algorithm) … 0. 유전 알고리즘이란? 생물학적 진화에 바탕을 둔 통계적 탐색 알고리즘 집합이다. 쉽게 말하면 그냥 유전을 …
Source: blog.naver.com
Date Published: 7/17/2021
View: 5875
유전 알고리즘 예제 | 01-3 Dimensionality Reduction
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! 그렇다면 파이썬으로 유전 알고리즘을 구현해보자. 함수가 많아서 함수 하나하나씩 …Source: you.xosotanphat.com
Date Published: 7/28/2021
View: 3909
[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm) – Untitled
[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm) · 1. 소개. 유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 …Source: untitledtblog.tistory.com
Date Published: 4/22/2021
View: 9479
유전 알고리즘(Genetic Algorithm) · Data Science – by Yngie
유전 알고리즘(Genetic algorithm)은 메타 휴리스틱 방법론 중 하나의 방법입니다. 유전 알고리즘에 대해 알아보기 전에 먼저 메타 휴리스틱 방법론이 …
Source: yngie-c.github.io
Date Published: 8/16/2022
View: 6604
주제와 관련된 이미지 유전 알고리즘 예제
주제와 관련된 더 많은 사진을 참조하십시오 유전 알고리즘으로 비밀번호를 뚫어보자 – Python. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.
주제에 대한 기사 평가 유전 알고리즘 예제
- Author: 빵형의 개발도상국
- Views: 조회수 23,515회
- Likes: 좋아요 314개
- Date Published: 2018. 11. 4.
- Video Url link: https://www.youtube.com/watch?v=PjEQVWefmqc
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자!
이번 포스팅에서는 유전 알고리즘을 통해 비밀번호를 찾는 알고리즘이다.
그전에 유전 알고리즘에 대해서 간략하게 설명을 하자면 다음과 같다.
말 그대로 유전 즉, 세대가 존재한다는 뜻이다. 이게 무슨 뜻이냐…
우선 랜덤으로 최초의 아이들을 생성한다.
그리고 그 생성된 아이들을 가지고 fitness (성능)을 측정한다.
성능을 측정할 때 적절한 점수를 부여하여 만약 점수가 높다면 해당 아이들을 선발해 낸다.
그리고 선발된 아이들을 교배하여 다음 세대를 만들어낸다.
그 과정에서 돌연변이도 추가하여 다음 세대를 만들어 내고 또 태어난 자식들을 가지고 성능을 측정하여
위의 과정을 계속 반복하여 수 세대를 걸쳐서 답을 도출해 내는 것이 유전 알고리즘이다.
그렇다면 파이썬으로 유전 알고리즘을 구현해보자.
함수가 많아서 함수 하나하나씩 잘라서 설명을 해보려고 한다.
우선 비밀번호는 문자열을 사용하고 길이가 최소 2 ~ 최대 10 정도로 적당하게 설정한다.
그리고 랜덤으로 아스키코드의 문자와 숫자를 생성해야 하기 때문에 random과 string을 import 한다.
유전 알고리즘
728×90
개요
유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 복잡한 최적화 문제를 푸는데 사용된다.
스케줄링 등 복잡한 최적화 문제를 해결하는데 활용되고 있고, 딥러닝의 초기 웨이트 설정, 특징 선택 등 머신러닝 문제를 해결하는데도 많이 사용된다.
필자의 주력 연구 방법론중 하나이며, 지금도 유전 알고리즘을 이용한 쉐이플릿 탐색이라는 주제로 연구를 진행하고 있다.
그러면 이제 유전 알고리즘이 어떻게 작동하는지, 또 파이썬으로 어떻게 구현할 수 있는지를 소개하자.
가능하면 비전공자의 입장에서 친절히 설명하고자 한다.
최적화 문제란?
최적화 문제는 제약 하에서 목적식을 최소화 혹은 최대화하는 결정 변수의 값을 찾는 문제이다.
제약이란 것은 해가 만족해야 하는 조건이고, 목적식은 최소화 혹은 최대화해야 하는 대상이며, 결정 변수는 값을 찾아야 하는 변수이다.
위키피디아에서 소개하고 있는 간단한 예제를 보자 (참고로 선형 계획법은 최적화 문제의 대표적인 유형이다).
홍길동 씨가 두 가지 종류의 빵을 판매하는데, 초코빵을 만들기 위해서는 밀가루 100g과 초콜릿 10g이 필요하고 밀빵을 만들기 위해서는 밀가루 50g이 필요하다. 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다. 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다. 만든 빵을 전부 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 홍길동 씨는 이익을 극대화 하기 위해서 어떤 종류의 빵을 얼마나 만들어야 하는지 다음과 같이 선형 계획법을 이용하여 계산할 수 있다.
여기서 x1과 x2가 결정변수이다.
저 문제는 100×1 + 50×2 <= 3000, 10x1 <= 100, x1, x2 >=0을 만족하는 x1과 x2가운데, 100×1 + 40×2를 최대화하는 x1과 x2를 찾아라 라고 해석할 수 있다.
이 정도의 문제는 매우 간단하기 때문에 사실 유전 알고리즘을 사용할 필요가 없다.
여기서 간단하다는 것은 저 문제의 최적해(=정답)를 구하는 과정이 공식처럼 정의되어 있다는 것이다.
그런데 현실 문제는 저 정도로 간단하지 않은 것이 보통이다.
휴리스틱과 메타휴리스틱
이제 휴리스틱이라는 단어가 무엇인지 이해해보자.
위키피디아에서는 휴리스틱을 아래와 같이 정의하고 있다.
휴리스틱(heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.
어렵게 정의하고 있지만, 휴리스틱은 결국 그럴싸하게 대충 푸는 방법이라고 볼 수 있다.
외판원 문제 (traveling sales problem)을 예로 들어보자.
이 문제는 택배 기사가 현 위치에서 어느 순서대로 택배를 배달해야 최소한의 거리로 움직일 수 있는지를 찾는 문제로, 대표적인 NP 문제 (일단은 풀기 어려운 문제라고 이해하고 넘어가자)이다.
이 문제의 가장 직관적인 해법은 지금 있는 곳에서 가장 가까운 곳부터 배달을 가는 것이다 (즉 그리디하게 탐색하는 것)
시작점이 택배회사였다면, 택배회사에서 가장 가까운 A를 가고, 또 A에서는 A에서 가장 가까운 B를 가는 것이다.
그럴싸하지 않은가? 우리도 여러 군데를 들려야 하는 상황이라면, 가장 가까운 곳 먼저 들리는 경우가 많기 때문에, 그럴싸하고 합리적인 것처럼 보인다. 물론, 이 접근으로 찾은 답은 정답이 아닐 가능성이 훨씬 높다.
이처럼 문제를 알려진 공식으로 풀 수 없는 경우에 그럴싸하게 대충 푸는 접근을 휴리스틱이라고 할 수 있다.
그런데 휴리스틱은 문제마다 문제 상황에 맞는 경험이나 직관을 이용해야 하는 어려움이 있다.
그러니까 위에서 예를 들었던 그리디 서치는 외판원 문제에는 적용할 수 있을지 몰라도, 다른 문제에는 적용할 수 없다.
그래서 등장한 것이 메타 휴리스틱이고, 유전 알고리즘도 메타 휴리스틱에 속한다.
메타 휴리스틱은 휴리스틱이긴한데, 그 풀이 과정 등이 구조적으로 잘 정의되어 있어 대부분의 문제에 어려움없이 적용할 수 있는 휴리스틱을 말한다.
유전 알고리즘의 개념 이해하기
유전 알고리즘은 기본적으로 여러 개의 해로 구성된 해 집단을 만들고 평가한 뒤, 좋은 해를 선별해서 새로운 해 집단을 만드는 메타휴리스틱 알고리즘이다.
유전 알고리즘의 구성 등을 살펴보기 전에 작동 과정에 대해 개략적으로 이해하고 시작하자.
아래와 같이 함수 f(x)가 있고, x에 따른 f(x)의 최소값을 찾는 문제가 있다고 하자.
설명을 위해, 이 함수를 산이라고 하고, 해를 토끼, 그리고 산의 낮은 곳일수록 더 좋은 곳이라고 하자.
유전 알고리즘은 여러 토끼를 만들고, 좋은 환경에 우연히 있던 토끼들만 살아남아서 비슷한 위치에 자식을 만드는 과정을 통해, 가장 낮은 곳, 즉 최적값을 찾게 된다.
육안으로 어느 x가 가장 좋은지 알 수 있지만, 실제 문제에서는 저 그래프를 그리는 것 자체가 불가능한 경우가 대부분이다.
배우신 분들(?)은 미분을 하면 되지 않느냐라고 주장할 수도 있겠지만, 미분 자체가 불가능한 경우도 역시 매우 흔하다.
정답이 모두 정수여야 하는 정수 계획법 문제의 경우에는 어느 경우에서도 미분이 불가능할 것이다.
다시 설명으로 돌아와서 아래와 같이 5마리의 주황색 토끼를 만들어 임의로 배치한다.
우연히 4번과 5번 있던 토끼는 좋은 환경에 있었고, 1, 2, 3번은 그렇지 못하다.
즉, 4번과 5번이 적자이고, 나머지는 적자가 아니다.
이제 적자라서 살아남은 4번과 5번이 자식 a, b, c를 만든다.
자식들은 파란색으로 표시했다.
이제 다시 살펴보니, 부모보다 좋은 위치에 있는 자식 b와 c도 있고, 부모랑 비슷하거나 더 나쁜 위치에 있는 a도 생겼다.
그럼 이제 가장 적합한 b와 c가 살아남아 또 대를 이어 나갈 것이다.
그러다보면 언젠가는 최저점에 있는 토끼를 만나게 될테고, 다시말해 최적해를 구할 것이다.
주요 용어를 거의 사용하지 않고 설명한 내용이지만, 여기서 유전 알고리즘에 관한 몇 가지 인사이트를 얻을 수 있다.
(1) 해를 많이 만들면, 더 좋은 해를 찾을 가능성이 높다. 물론 시간은 더 소요될 것이다.
(2) 너무 잘난 해라면, 세대가 지나도 계속 세대를 구성하는 일원으로 남아있다.
(3) 다음 세대에서 자식을 만드는 부모의 수가 많을수록, 더 많은 해를 탐색할 수는 없다. 그렇지만 더 안정적일 것이다.
(4) 처음에 해들이 한 곳에 몰려있었다면 (특히, 1, 2번 위치), 세대를 거듭해도 좋은 해를 못 찾을 수도 있다.
유전 알고리즘 순서도
이제 본격적으로 유전 알고리즘에 대해 알아보자.
유전 알고리즘은 아래 그림과 같이 초기 해 생성, 적합도 평가, 교차 연산, 돌연변이 연산을 반복한다.
파라미터 정의
단계에는 포함하지 않았지만, 유전 알고리즘을 사용하려면 아래 내용을 미리 결정해야 한다.
해 표현 방법
최대 세대 수
종료 조건
세대 별 포함되는 해의 개수
교차 연산자
돌연변이 연산자
교차 비율
적합도 함수
돌연변이 비율 등
초기 해 생성
첫 번째 단계에서는 초기 해, 즉 첫 번째 세대의 해들을 생성한다.
이 과정에서는 보통 임의로 해를 생성하는데, 문제에 따라서 특정 조건에 맞는 해를 만들도록 설계하는 것이 유리하기도 하다. 그리고 여기서 가장 중요한 것은 해를 어떻게 표현할 것인가이다. 이를 줄여서 해 표현이라 하는데, 해 표현을 어떻게 하느냐에 따라서 문제 풀이가 쉬울 수도 있고 그렇지 않을 수도 있다. 유전 알고리즘을 많이 사용해본 사람과 그렇지 않은 사람의 차이가 사실 여기서 판가름난다.
가장 흔히 사용되는 해 구조는 다음과 같은 이진 벡터이다.
이진 벡터가 많이 사용되는 이유는 뒤에서 설명할 교차 연산이나 돌연변이 연산이 편리하기 때문이다.
외판원 문제처럼 순서를 결정하는 경우라면 이진 벡터보다는 각 위치가 도달한 장소의 인덱스를 나타내는 벡터로 표현하는 것이 적합할 수도 있다.
적합도 평가 및 해 선택
이 단계에서는 현재 세대에 있는 모든 해들을 적합도 함수라는 것을 이용하여 평가한다.
적합도는 보통 최적화 문제의 목적식을 그대로 사용하는 것이 일반적이다.
가령, 외판원 문제에서는 해의 적합도가 전체 이동 거리에 반비례할테고, 최대화 문제라면 해의 적합도가 목적식에 비례할 것이다.
적합도 평가 결과를 토대로 그 다음 세대를 만들 해들을 결정한다.
즉, 교차연산과 돌연변이 연산을 적합도가 우수한 해들에 적용하여 다음 세대에 속할 해를 만든다.
여기서 적합도가 높은 상위 N1개의 해를 선택하여 N2개의 해를 만드는 방식으로 다음 세대를 구성할 수도 있고 (세대별 해의 개수 (N) = N1 + N2), 혹은 적합도에 비례하게 해를 확률적으로 선택하여 해를 생성할 수도 있다.
전자의 경우에는 이전 세대의 해가 다음 세대로 그대로 넘어가고, 좋은 해들만 선별되므로 안정적이라는 장점이 있으나, 지역 최적에 빠질 위험이 있다.
후자의 경우에는 반대로 세대가 거듭될수록 이전에 고려하지 않았던 새로운 종류의 해를 탐색할 수 있으므로, 더 좋은 해를 찾을 수도 있지만, 수렴하지 못할 가능성이 크다.
교차 연산
교차 연산은 두 개의 부모 해를 바탕으로 자식 해를 만드는 연산을 말한다.
즉, 부모가 결합하여 자식을 낳는 과정을 모방한 것이 바로 교차 연산이다.
당연히 교차 연산을 해서 나온 해는 부모를 닮게 된다.
대표적인 교차 연산자로는 한 점 교차 연산자, 두 점 교차 연산자 등이 있다.
이들 교차 연산자는 교차 지점을 임의로 설정한 뒤, 교차 지점 앞쪽에서는 부모 1의 유전자를, 뒤쪽에서는 부모 2의 유전자를 가져와 새로운 자식을 만든다.
아래 그림에서 빨간색 해와 파란색 해가 교차되면서, 앞쪽이 빨갛고 뒤쪽이 파란 해와 앞쪽이 파랗고 뒤쪽이 빨간 해가 생성되었다.
한 점 교차 연산자 두 점 교차 연산자
돌연변이 연산
돌연변이 연산은 만들어진 자식 해를 일부 수정하는 것이다.
즉, 두 부모가 교차를 하더라도, 두 부모와는 완전히 일치하지 않는 그런 특성을 만들기 위한 연산이다.
세대를 거듭할수록 다양한 해를 찾지 않고 특정한 해로 빠르게 수렴하는 것을 막기 위한 연산이다.
아래와 같은 함수가 있고, 해가 주황색으로 표시된 상황을 보자.
여기서 저 네 개의 해를 바탕으로 교차 연산을 계속해서 진행하면 왼쪽 지역 최적에 빠져버리게 될 위험이 있다.
그런데 돌연변이 연산을 해주게 되면, 아예 엉뚱한 위치에 해를 만들기도 하므로, 우연히 좋은 해를 찾을 가능성이 높아지는 것이다.
다시 한 번 강조하지만, 돌연변이 연산을 한다고 해서 무조건 좋은 해를 찾을 수 있는 것은 아니다.
오히려 전역 최적에 가까워지다가 돌연변이 연산 때문에 전역 최적과 멀어지기도 한다.
대표적인 돌연변이 연산 방법으로는 flip-bit 변이 연산이 있다.
임의로 돌연변이를 할 자식을 선택하고, 자식의 유전 개체 (참고: 해를 유전자라하며, 해의 구성 요소 (즉 벡터의 구성 요소)를 유전 개체라 함)를 임의로 선택하여, 0이면 1로, 1이면 0으로 바꾸는 간단한 연산이다.
파이썬을 이용한 예제 풀이
최적화 문제를 소개하는 과정에서 나왔던 예제를 유전 알고리즘을 통해 풀어보자.
이 문제에서는 x1과 x2를 찾아야 한다.
해 구조는 다음과 같은 2 x 5 크기의 이진 행렬을 사용한다.
첫 번째 행은 x1과 관련이 있고, 두 번째 행은 x2와 관련이 있다.
즉, 위 구조의 해는 x1과 x2를 다음과 같이 표현한다.
사실 이렇게 모두 양수만 표현하도록 설계한 이유는 세 번째 제약을 만족시키는 해를 만들기 위함이다 (이런게 유전 알고리즘을 사용할 때 매우 중요한 센스이다!).
해 표현을 제외한 유전 알고리즘의 주요 파라미터는 다음과 같이 설정한다.
최대 세대 수: 10
종료 조건: 최대 세대 수 도달
세대 별 포함되는 해의 개수: 20
교차 연산자: 1점 교차 연산
부모 수: 10
돌연변이 연산자: flip bit 돌연변이 연산
적합도 함수: 목적식 (제약을 만족못하면 0점)
돌연변이 비율: 10%
돌연변이 유전 개체 비율: 20%
이제 파이썬을 사용해서 유전 알고리즘의 각 단계를 함수 단위로 구현해보도록 하자.
유전 알고리즘을 사용할 수 있는 패키지가 있긴 하지만, 문제에 따라서 직접 정의해야 하는 부분이 많다보니 개인적으로는 numpy를 활용하는 것이 편리하다.
먼저, numpy를 임포트해주자.
import numpy as np
그리고 N개의 초기 해를 생성하는 함수를 정의하자.
이 함수는 random.randint를 사용하여 0과 2사이 중 하나를 선택하여 (N, 2, 5) shape의 배열을 생성한다.
즉, 0과 1로만 구성되는 (N, 2, 5) shape의 배열을 만드는 것이며, N은 결국 해의 개수, (2, 5)는 해의 구조 (행렬 구조)라고 볼 수 있다.
def generate_initial_population(N): initial_population = np.random.randint(0, 2, (N, 2, 5)) return initial_population
이제 각각의 해를 평가하는 적합도 함수를 만들자.
제약이 문제에 포함되어 있으므로 제약을 어기는 경우에는 적합도를 0으로 주도록 하자.
먼저 2 * 5 크기의 행렬이 입력되면, 여기서 x1과 x2를 계산한다.
그리고 문제의 제약을 만족하는지 여부를 확인해서, 모두 만족하면 목적식으로 적합도를 평가하고, 하나라도 만족하지 못하면 적합도를 0으로 설정한다.
def evaluate_fitness(solution): x1 = sum([2**(4-i) * solution[0][i] for i in range(5)]) x2 = sum([2**(4-i) * solution[1][i] for i in range(5)]) constraint_1 = (100 * x1 + 50 * x2) <= 3000 constraint_2 = (10 * x1) <= 100 if constraint_1 and constraint_2: fitness_value = 100 * x1 + 40 * x2 else: fitness_value = 0 # 제약을 하나라도 위반하면 적합도 0점 return fitness_value 이제 한 세대에서 두 개의 해를 선택하여 1점 교차 연산을 수행하는 함수를 정의하자. 이 함수는 두 개의 해 (solution1, solution2)를 입력받아 교차 지점을 1과 5사이에서 임의로 선택하여 자식을 만든다. 해 자체가 행렬이기 때문에 교차 지점을 각 행마다 설정했다. 자세히 살펴보면, 각 행마다 교차 지점은 1, 2, 3 중 하나를 선택하는데, 0이나 4가 교차지점이 되면 사실상 하나의 부모의 유전자가 그대로 내려오는 것이기 때문에 0과 4는 제외하였다. 그리고 자식 해를 빈 배열로 생성한 뒤, 0번째 행과 1번째 행을 각각 부모들의 유전자로 채운다. 리스트로 만들어서 더하는 방식도 괜찮지만, 그렇게 되면 ndarray와 리스트를 왔다갔다하면서 문제가 생길 위험이 있기 때문에, empty 함수를 사용했다. def crossover(solution1, solution2): crossover_point_1 = np.random.randint(1, 4) # x1에 대한 교차 지점 crossover_point_2 = np.random.randint(1, 4) # x2에 대한 교차 지점 child = np.empty((2, 5)) # 자식을 빈 배열로 생성 # 부모 유전자 가져오기 child[0][:crossover_point_1] = solution1[0][:crossover_point_1] child[0][crossover_point_1:] = solution2[0][crossover_point_1:] child[1][:crossover_point_2] = solution1[1][:crossover_point_2] child[1][crossover_point_2:] = solution2[1][crossover_point_2:] return child 이제 돌연변이 연산을 정의하자. p는 각 개체에서 돌연변이가 일어날 확률이다. 해의 모든 인덱스를 row와 col로 순회하면서, 각 위치마다 난수를 생성한 뒤, 그 난수가 p보다 작다면 (즉, p의 확률로), 그 위치에 있는 값을 바꿔준다. 여기서 유용한 두 가지 테크닉을 짚고 넘어가자. x = 1 - x는 x가 0이면 1로, 1이면 0으로 바꾸는데 사용 if 난수 < p는 결국 p의 확률로 선택하는데 사용 def mutation(child, p): for row in range(2): for col in range(5): if np.random.random() < p: child[row, col] = 1 - child[row, col] return child 이제 함수 정의는 끝났으니, 함수들을 이용하여 유전 알고리즘을 구현하자. 먼저, 파라미터를 이렇게 정의하자. num_iter = 10 # 세대 수 N = 20 # 한 세대에 포함되는 해의 개수 N_P = 10 # 부모 개수 mutation_sol_prob = 0.1 # 유전자(해)가 돌연변이일 확률 mutation_gene_prob = 0.2 # 유전 개체가 돌연변이일 확률 그리고나서 메인 코드를 작성한다. 가장 먼저 초기 해를 생성하고, 지금까지 찾은 최대 적합도를 초기화한다. 그리고 각 이터레이션마다 현재 세대를 평가하고, 현재 세대에 지금까지 찾은 최대 적합도보다 큰 적합도를 갖는 해가 있다면, 그 해를 best_solution에, 그 해의 적합도를 best_score에 저장한다. 그리고 fitness_value_list를 기준으로 상위 N_P개의 해를 선택하여 parents에 저장한다. 그리고 한 세대에 포함되야 하는 해의 개수에서 부모의 개수를 뺀 만큼 자식을 생성한 뒤, 20%의 확률로 돌연변이 연산을 적용한 자식을 new_population에 추가한다. # 초기 해 생성 current_population = generate_initial_population(N) best_score = -1 # 지금까지 찾은 최대 적합도 초기화 for _ in range(num_iter - 1): # 해 평가 수행 fitness_value_list = np.array([evaluate_fitness(solution) for solution in current_population]) # 지금까지 찾은 최대 적합도보다 현세대에 있는 최대 적합도가 크다면 업데이트 if fitness_value_list.max() > best_score: best_score = fitness_value_list.max() best_solution = current_population[fitness_value_list.argmax()] # 적합도 기준 상위 N_P개 해 선정 (값이 큰 순으로 정렬하기 위해 -를 붙임) parents = current_population[np.argsort(-fitness_value_list)] # 새로운 해 집단 정의 new_population = parents # 두 개의 부모를 선택하면서 자식 생성 for _ in range(N – N_P): # N – N_P = 생성해야 하는 자식 개수 # 부모 선택 parent_1_idx, parent_2_idx = np.random.choice(N_P, 2, replace = False) parent_1 = parents[parent_1_idx] parent_2 = parents[parent_2_idx] # 자식 생성 child = crossover(parent_1, parent_2) # mutation_sol_prob의 확률로 돌연변이 연산 수행 if np.random.random() < mutation_sol_prob: child = mutation(child, mutation_gene_prob) # new_population에 child 추가 (child 구조가 (2, 5)라서 vstack이 안되므로, 구조를 변경) new_population = np.vstack([new_population, child.reshape(1, 2, 5)]) 이렇게 찾은 해는 다음과 같다. best_solution을 뜯어보면, x1 = 10, x2 = 31인데, 주어진 해 구조에서는 최적임을 쉽게 알 수 있다. 다 풀고 나서 실수를 알아차렸는데, 2*5크기가 아니라 2*6크기의 해 구조를 정의했으면 최적해를 찾았을 것이다... 728x90
유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기
https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
1. 정의
유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화기법으로, 최적화 문제를 해결하는 기법의 하나이다.
생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용(채용)하였으며, 변이(돌연변이), 교배 연산 등이 존재한다.
또한 세대, 인구등의 용어도 문제풀이 과정에서 사용된다.
2. 개요
유전 알고리즘은 자연계의 생물 유전학에 기본이론을 두며, 병렬적이고 전역적인 탐색알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 한다.
유전 알고리즘은
1) 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음,
2) 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다.
3) 여기에서 해들을 나타내는 자료구조는 유전자,
4) 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다.
달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다.
유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다.
일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다.
이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수준의 해를 보여줄 수 있다.
이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있다.
유전 알고리즘은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로, 자연과학/공학 및 인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다.
3. 요구 조건
유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 유전자의 형식으로 표현할 수 있어야 하며, 이 해가 얼마나 적합한지를 적합도 함수를 통해 계산할 수 있어야 한다.
일반 생명체의 특성이 유전체의 집합인 유전자로 나타나는 것과 같이, 유전 알고리즘에서는 해의 특성을 숫자의 배열이나 문자열과 같은 자료 구조를 통해서 표시 하게 된다.
적합도 함수는 이렇게 나타내어진 해가 얼마나 문제의 답으로 적합한지를 평가하기 위한 함수이다.
이는 실세계의 생명체가 유전적 특성에 따라 환경에 얼마나 잘 적응할 수 있는지가 결정되는 것과 비교할 수 있다.
4. 흐름
어떤 문제에 대해 유전자 형식이 정의되었다면, 어떤 해들의 유전자들을 서로 조합함으로써 기존의 해로부터 새로운 해를 만들어낼 수 있다.
이런 조합 연산은 교배(Crossover)에 비유할 수 있다.
우수한 해들을 선택하여 이들을 교배하면, 만들어진 해는 우수한 해들이 가지는 특성을 물려받을 가능성이 높게 된다.
우수한 해의 선택에는 앞에서 정의한 적합도 함수를 이용할 수 있으며, 적합도가 높은 해가 선택될 확률을 높게 만들면, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 되고, 따라서 다음 세대의 해들은 최적해에 점차 가까워지게 된다.
또 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨주도록 할 수 있으며, 이는 지역 최적점에 빠지지 않도록 하는 주요한 기법이다.
해들을 교배하기 위해서는 아담과 하와처럼 초기 해의 집단이 필요하다.
초기해 집단은 단지 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것이므로, 우수한 해들로 이루어질 필요는 없다. 일반적으로는 유전자를 랜덤하게 생성하여 초기화해 ‘초기해’ 집단을 구성한다.
초기해 집단이 구성되면, 이들 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 되며, 이를 세대를 거듭하면서 반복해 가면, 해들은 점점 정답에 가까워지게 된다.
유전 알고리즘이 전역 최적해를 구하려면, 많은 인구를 유지하면서 많은 세대를 내려갈 필요가 있다.
따라서, 대부분의 경우는 세대가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다.
5. 연산
유전 알고리즘은
1) 선택,
2) 교차,
3) 변이,
4) 대치 등 몇가지 주요 연산으로 구성된다.
6. 선택
한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다.
선택 방법에는
1) 균등 비례 룰렛 휠 선택,
2) 토너먼트 선택,
3) 순위 기반 선택 등이 있다.
해의 선택은 유전 알고리즘의 성능에 큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역 최적해에 빠지는 경우가 생길 수도 있기 때문이다.
또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다.
따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할 수 있다.
일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 많이 사용된다.
이는 반대로 말하면, 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 준다고 볼 수 있다. 현 세대에서 가장 좋은 해라 할지라도 실제로는 지역 최적해에 가까운 해일 수도 있고, 반대로 좋지 않은 해라 할지라도 전역 최적해에는 더 가까울 수도 있기 때문이다.
실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로, 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적해에 빠지는 것을 가능한 한가지 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다.
7. 교차
생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다.
이와 마찬가지로 유전 알고리즘에서 자연 선택된 해들은 교배를 통하여 다음 세대의 해들을 생성하게 된다. 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 되며, 이를 통해 생성된 해는 각각의 부모 해의 교차 연산을 통해서 서로 겹치지 않는 위치의 유전인자를 받아 새로운 유전자를 구성하게 된다.
실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다.
유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다.
교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다.
또한 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있다. 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다.
8. 변이
일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다.
변이 연산은 주어진 해의 유전자 내의 유전 인자의 순서 혹은 값이 임의로 변경되어 다른 해로 변형되는 연산이다.
해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다.
따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해집단의 다양성을 높여준다.
9. 대치
교차·변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고, 기존 해 중 열등한 해를 가려내서 제외시키는 연산이다.
가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법(해집단의 다양성을 유지하기 위함) 등이 있다.
예)
{1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 각 해의 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다.
먼저 첫 세대를 아무렇게나 생성한다. 첫 세대가 만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 형성되었다고 하자. 각각의 적합도를 구하면, { 11, 3, 6, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다.
다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적으로 선택한다. (룰렛 알고리즘이 자주 쓰인다) 위의 예에서 적합도가 3인 (8,0,9)는 적합도가 6인 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 첫번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8), (9,0,9)가 되며, 각각의 적합도는 5, 2가 된다.
10. 관련 기법
11. 참고 문헌
12. 관련 논문
Differential Gene Set Enrichment Analysis: A statistical approach to quantify the relative en- richment of two gene sets
https://github.com/Kcrong/Simple-Genetic-Algorithm
원문
https://blog.devkcr.org/entry/%EC%9C%A0%EC%A0%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%80%EC%A7%80%EA%B3%A0-%EB%86%80%EA%B8%B0
예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm
유전 알고리즘이란,
“유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다.” – 위키피디아
유전 알고리즘은 부모의 유전 정보들이 자식들에게 골고루 분포 됨으로써, 문제에 대한 해를 찾아가는 알고리즘이다.
자식 해는 부모 해와 비슷한 형질을 가지며, 우월한 유전자들은 다시 자식해를 만들며 우수 유전자를 널리 퍼트리는 특징이 있다.
소스 설명 전, 사용할 용어에 대한 설명은 아래와 같다.
1. 유전자
예시 소스에서는 integer list 로 정의했다. 하지만 그 형태와 값의 크기는 무엇이든지 될 수 있으며, 제한이 없다. (구현이 어려울 뿐..)
2. 세대
유전자들의 생성과 소멸을 아우르는 하나의 주기를 말한다.
보통 생성 > 번식 > 소멸 의 주기를 가진다.
3. 적합도 (Fitness)
유전자가 얼마나 우월한지 보여주는 지수.
이 지수가 높을 수록 우월한 유전자임을 뜻한다.
전체적인 알고리즘은 3가지로 이루어져있다.
1. 부모 유전자 선택
2. 번식
3. 돌연변이
부모 유전자 선택
부모 유전자를 선택하는 부분에서는, 룰렛 휠 선택 방식을 이용했다.
1
2
3 # 부모를 select_list를 이용해 정함.
# 부모로 선출될 확률은 fitness 과 비례한다.
parents = tuple(self.select_list[rand( 0 , len (self.select_list))] for i in range ( 2 )) cs
룰렛 휠 방식
이미지 출처: http://blog.secmem.org/category/IT%20%EB%86%80%EC%9D%B4%ED%84%B0/Elite%20Member%20Tech%20%26%20Talk?page=37
룰렛 휠 방식이란, 적합도가 높을수록 부모 해로 선택될 확률이 높아지도록 하는 방식이다.
위 그림처럼, 적합도가 100인 C는 룰렛에서 보듯이 선택될 확률이 높다.
하지만 적합도가 40인 D는 C와 달리 선택될 확률이 적다.
이처럼 우월한 유전자를 가질 수록 부모 해로 선택될 확률을 높이는 것을 룰렛 휠 방식이라고 한다.
번식 (교차)
자식 유전자를 만들 때는, 2점 교차 라는 방식을 이용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 # 각 교차 포인트를 정한다.
# rand 함수의 반환이 float 형이므로, 소수점을 버리기 위해 int() 형변한을 해준다.
switch_point = (rand( 1 , gene_len / / 2 ), rand(gene_len / / 2 , gene_len))
# 처음 자식이 받는 유전자는 parent1
# 다만 교차 포인트에 다다르면, 다른 parent 유전자 정보를 받아오기 시작한다. (parent = parent2)
parent = parents[ 0 ]
for i in range (gene_len):
# 자식 유전자 정보는 부모 유전자에서 받아온다
gene_data.append(parent.gene_data[i])
if i in switch_point:
# 유전자를 받아오는 부모 변경
try :
parent = parents[parents.index(parent) + 1 ]
except IndexError:
parent = parents[ 0 ]
“” ”
a = parents.index(parent) –> 현재 부모의 index 값
parents[a+1] –> 부모 리스트에서, 현재 부모 인덱스값보다 +1 된 값 가져옴
IndexError –> 만약 1이 넘어가면
parent = parents[0] 다시 0으로 돌아옴
” “”
Colored by Color Scripter cs
2점 교차는 두 점을 임의로 선택하여, 그 점을 기준으로 각 부모 유전자에서 번갈아 유전자를 받아오는 방법이다.
물론 점의 위치에 따라 부모1과 부모2의 유전 정보 비율은 달라질 수 있지만 교차의 경우 섞이는 복잡도를 정하는 단계이므로 신경쓰지 않는다.
–> Mutation (돌연변이)
1
2
3
4 # 돌연변이 확률은 fitness 와 반비례 한다.
# fitness 가 높을 수록, 돌연변이 확률이 적어진다.
if rand( 0 , self.fitness * 100 ) = = 0 :
return DNA([rand(min(WE_WANT), max(WE_WANT)) for i in range ( len (WE_WANT))]) cs
돌연변이 확률은 적합도와 반비례 하도록 구현했으며, 돌연변이는 기존 부모와 상관없는 전혀 새로운 유전자를 갖는다.
돌연변이는 그 확률 설정에 따라 다른 결과가 나온다. 자세한 내용은 아래 결과 분석에서 살펴보자.
결과분석
우선 목표값을
0 과 1로 이루어진 8자리 list 로 잡았다.
결과는 다음 이미지와 같다. X축이 세대, Y축이 적합도 수치를 나타낸다.
[그림1] 목표 값 [0,1,0,1,0,1,0,1]목표값이 단순한 관계로 얼마 지나지 않아, 40번째 세대 쯤에서 최대 적합도에 수렴하는 것을 볼 수 있다.
목표값을 조금 복잡하게 해보자.
0~9의 값을 가지도록 조정해봤다.
[그림2] 목표 값 [3,1,2,9,7,4,3,6]조금 더 흥미로운 결과가 나왔다.
목표 값의 범위를 늘리자 최대 적합도에 도달하는 세대가 늘어난 것이다.
위 1차 결과와는 달리 80 ~ 100 번째 세대에서 최대 적합도에 가까이 수렴하는 결과가 나왔다.
조금 더 복잡하게 해보자. 이번엔 목표 값의 길이를 바꿔볼 것이다.
[그림3-1] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9]100 세대로는 최대 적합도에 도달하기에 한참 부족한 듯 싶다. 진화 횟수를 조금 늘려보았다.
[그림3-2] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가비록 최대 적합도에는 도달하지 못했지만, 근사한 값을 얻었다.
그럼 보다 더 최대 적합도에 가까운 값을 얻기 위해서는 어떻게 해보는 것이 좋을까?
돌연변이의 확률을 늘리고, 세대에서 가장 좋은 유전자 (Fitness 수치가 가장 높은) 1개를 다음 세대에도 보존 시켜보았다.
[그림3-3] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존최대 적합도에 도달하는데 성공했다!!!
하지만 필요 세대가 너무 많다는 문제점이 있다…
또한 돌연변이 확률을 늘렸더니 중간중간 생기는 뾰족한 부분 (내려오는 부분)이 늘어났다.
위 문제 를 조금 개선시켜보자.
우월한 유전자를 자식 세대에 포함시키는 과정에서, 1개가 아닌 5개를 포함시켜보았다.
[그림3-4] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가약 1100 – 850 = 250 세대가 감소했다!!~!
우월 유전자의 보존 비율 조금 더 늘려보자.
이번엔 5개 대신 10개를 포함시켜 보았다.
더욱 개선된 결과가 나오리라 생각했다.
[그림3-5] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가 _ 10개 보존예상과는 달리, 이전 결과 보다 더욱 못한 결과가 나왔다.
이유를 살펴보았더니, 우월 유전자의 보존 비율이 증가하면 우월 유전자에 가까운 자식 유전자들이 많이 생기지만,
우월 유전자의 잘못된 부분도 같이 유지되는 문제가 있었다.
우월 유전자의 보존 비율이 높다고 진화의 방향이 좋은 것은 아니라는 것이다.
이번 실험 결과 중, 우리의 실생활과 매우 흡사한 부분이 아닐까 싶다. 🙂
P.s
질문이나 기타 문제점은 GitHub 이슈로 달아주세요
풀리퀘 받는 것도 좋아합니다.
출처: https://blog.devkcr.org/entry/유전-알고리즘-가지고-놀기 [Blog4Study]
유전 알고리즘 가지고 놀기
예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm
유전 알고리즘이란,
“유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다.” – 위키피디아
유전 알고리즘은 부모의 유전 정보들이 자식들에게 골고루 분포 됨으로써, 문제에 대한 해를 찾아가는 알고리즘이다.
자식 해는 부모 해와 비슷한 형질을 가지며, 우월한 유전자들은 다시 자식해를 만들며 우수 유전자를 널리 퍼트리는 특징이 있다.
소스 설명 전, 사용할 용어에 대한 설명은 아래와 같다.
1. 유전자
예시 소스에서는 integer list 로 정의했다. 하지만 그 형태와 값의 크기는 무엇이든지 될 수 있으며, 제한이 없다. (구현이 어려울 뿐..)
2. 세대
유전자들의 생성과 소멸을 아우르는 하나의 주기를 말한다.
보통 생성 -> 번식 -> 소멸 의 주기를 가진다.
3. 적합도 (Fitness)
유전자가 얼마나 우월한지 보여주는 지수.
이 지수가 높을 수록 우월한 유전자임을 뜻한다.
전체적인 알고리즘은 3가지로 이루어져있다.
1. 부모 유전자 선택
2. 번식
3. 돌연변이
부모 유전자 선택
부모 유전자를 선택하는 부분에서는, 룰렛 휠 선택 방식을 이용했다.
1 2 3 # 부모를 select_list를 이용해 정함. # 부모로 선출될 확률은 fitness 과 비례한다. parents = tuple(self.select_list[rand( 0 , len (self.select_list))] for i in range ( 2 )) cs
룰렛 휠 방식
이미지 출처: http://blog.secmem.org/category/IT%20%EB%86%80%EC%9D%B4%ED%84%B0/Elite%20Member%20Tech%20%26%20Talk?page=37
룰렛 휠 방식이란, 적합도가 높을 수록 부모 해로 선택될 확률이 높아지도록 하는 방식이다.
위 그림처럼, 적합도가 100인 C는 룰렛에서 보듯이 선택될 확률이 높다. 하지만 적합도가 40인 D는 C와 달리 선택될 확률이 적다.
이처럼 우월한 유전자를 가질 수록 부모 해로 선택될 확률을 높이는 것을 룰렛 휠 방식이라고 한다.
번식 (교차)
자식 유전자를 만들 때는, 2점 교차 라는 방식을 이용했다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 # 각 교차 포인트를 정한다. # rand 함수의 반환이 float 형이므로, 소수점을 버리기 위해 int() 형변한을 해준다. switch_point = (rand( 1 , gene_len / / 2 ), rand(gene_len / / 2 , gene_len)) # 처음 자식이 받는 유전자는 parent1 # 다만 교차 포인트에 다다르면, 다른 parent 유전자 정보를 받아오기 시작한다. (parent = parent2) parent = parents[ 0 ] for i in range (gene_len): # 자식 유전자 정보는 부모 유전자에서 받아온다 gene_data.append(parent.gene_data[i]) if i in switch_point: # 유전자를 받아오는 부모 변경 try : parent = parents[parents.index(parent) + 1 ] except IndexError: parent = parents[ 0 ] “” ” a = parents.index(parent) –> 현재 부모의 index 값 parents[a+1] –> 부모 리스트에서, 현재 부모 인덱스값보다 +1 된 값 가져옴 IndexError –> 만약 1이 넘어가면 parent = parents[0] 다시 0으로 돌아옴 ” “” Colored by Color Scripter cs
2점 교차는 두 점을 임의로 선택하여, 그 점을 기준으로 각 부모 유전자에서 번갈아 유전자를 받아오는 방법이다.
물론 점의 위치에 따라 부모1과 부모2의 유전 정보 비율은 달라질 수 있지만 교차의 경우 섞이는 복잡도를 정하는 단계이므로 신경쓰지 않는다.
–> Mutation (돌연변이)
1 2 3 4 # 돌연변이 확률은 fitness 와 반비례 한다. # fitness 가 높을 수록, 돌연변이 확률이 적어진다. if rand( 0 , self.fitness * 100 ) = = 0 : return DNA([rand(min(WE_WANT), max(WE_WANT)) for i in range ( len (WE_WANT))]) cs
돌연변이 확률은 적합도와 반비례 하도록 구현했으며, 돌연변이는 기존 부모와 상관없는 전혀 새로운 유전자를 갖는다.
돌연변이는 그 확률 설정에 따라 다른 결과가 나온다. 자세한 내용은 아래 결과 분석에서 살펴보자.
결과분석
우선 목표값을
0 과 1로 이루어진 8자리 list 로 잡았다.
결과는 다음 이미지와 같다. X축이 세대, Y축이 적합도 수치를 나타낸다.
[그림1] 목표 값 [0,1,0,1,0,1,0,1]목표 값이 단순한 관계로 얼마 지나지 않아 40번째 세대 쯤에서 최대 적합도에 수렴하는 것을 볼 수 있다.
목표 값을 조금 복잡하게 해보자.
0~9의 값을 가지도록 조정해봤다.
[그림2] 목표 값 [3,1,2,9,7,4,3,6]조금 더 흥미로운 결과가 나왔다.
목표 값의 범위를 늘리자 최대 적합도에 도달하는 세대가 늘어난 것이다.
위 1차 결과와는 달리 80 ~ 100 번째 세대에서 최대 적합도에 가까이 수렴하는 결과가 나왔다.
조금 더 복잡하게 해보자. 이번엔 목표 값의 길이를 바꿔볼 것이다.
[그림3-1] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9]100 세대로는 최대 적합도에 도달하기에 한참 부족한 듯 싶다. 진화 횟수를 조금 늘려보았다.
[그림3-2] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가비록 최대 적합도에는 도달하지 못했지만, 근사한 값을 얻었다.
그럼 보다 더 최대 적합도에 가까운 값을 얻기 위해서는 어떻게 해보는 것이 좋을까?
돌연변이의 확률을 늘리고, 세대에서 가장 좋은 유전자 (Fitness 수치가 가장 높은) 1개를 다음 세대에도 보존 시켜보았다.
[그림3-3] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존최대 적합도에 도달하는데 성공했다!!!
하지만 필요 세대가 너무 많다는 문제점이 있다…
또한 돌연변이 확률을 늘렸더니 중간중간 생기는 뾰족한 부분 (내려오는 부분)이 늘어났다.
위 문제 를 조금 개선시켜보자.
우월한 유전자를 자식 세대에 포함시키는 과정에서, 1개가 아닌 5개를 포함시켜보았다.
[그림3-4] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가약 1100 – 850 = 250 세대가 감소했다!!~!
우월 유전자의 보존 비율 조금 더 늘려보자.
이번엔 5개 대신 10개를 포함시켜 보았다.
더욱 개선된 결과가 나오리라 생각했다.
[그림3-5] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가 _ 10개 보존예상과는 달리, 이전 결과 보다 더욱 못한 결과가 나왔다.
이유를 살펴보았더니, 우월 유전자의 보존 비율이 증가하면 우월 유전자에 가까운 자식 유전자들이 많이 생기지만,
우월 유전자의 잘못된 부분도 같이 유지되는 문제가 있었다.
우월 유전자의 보존 비율이 높다고 진화의 방향이 좋은 것은 아니라는 것이다.
이번 실험 결과 중, 우리의 실생활과 매우 흡사한 부분이 아닐까 싶다. 🙂
P.s
질문이나 기타 문제점은 GitHub 이슈로 달아주세요
풀리퀘 받는 것도 좋아합니다.
Top 6 유전 알고리즘 예제 Top 20 Best Answers
Password Cracker with Genetic Algorithm – Python
Password Cracker with Genetic Algorithm – Python
유전 알고리즘 예제
Article author: medium.com
Reviews from users: 44431 Ratings
Ratings Top rated: 4.5
Lowest rated: 1
Summary of article content: Articles about 유전 알고리즘 예제 유전 알고리즘은 개체들이 모인 집단에서 시작합니다. 각 개체(노드)는 1과 0에 의한 바이너리 형태(무조건은 아니지만 바이너리로 표현되는 것이 … …
Most searched keywords: Whether you are looking for 유전 알고리즘 예제 유전 알고리즘은 개체들이 모인 집단에서 시작합니다. 각 개체(노드)는 1과 0에 의한 바이너리 형태(무조건은 아니지만 바이너리로 표현되는 것이 …
Table of Contents:
유전 알고리즘 예제
Read More
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! — 수구리의 데브로그Article author: tasddc.tistory.com
Reviews from users: 33510 Ratings
Ratings Top rated: 4.3
Lowest rated: 1
Summary of article content: Articles about [ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! — 수구리의 데브로그 그렇다면 파이썬으로 유전 알고리즘을 구현해보자. 함수가 많아서 함수 하나하나씩 잘라서 설명을 해보려고 한다. 우선 비밀번호는 문자열을 사용하고 … …
Most searched keywords: Whether you are looking for [ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! — 수구리의 데브로그 그렇다면 파이썬으로 유전 알고리즘을 구현해보자. 함수가 많아서 함수 하나하나씩 잘라서 설명을 해보려고 한다. 우선 비밀번호는 문자열을 사용하고 … 이번 포스팅에서는 유전 알고리즘을 통해 비밀번호를 찾는 알고리즘이다. 그전에 유전 알고리즘에 대해서 간략하게 설명을 하자면 다음과 같다. 말 그대로 유전 즉, 세대가 존재한다는 뜻이다. 이게 무슨 뜻이냐….
Table of Contents:
블로그 메뉴
공지사항
인기 글
태그
최근 댓글
최근 글
티스토리
티스토리툴바
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자! — 수구리의 데브로그Read More
유전 알고리즘
Article author: gils-lab.tistory.com
Reviews from users: 14212 Ratings
Ratings Top rated: 3.9
Lowest rated: 1
Summary of article content: Articles about 유전 알고리즘 유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 … 최적화 문제를 소개하는 과정에서 나왔던 예제를 유전 알고리즘을 통해 … …
Most searched keywords: Whether you are looking for 유전 알고리즘 유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 … 최적화 문제를 소개하는 과정에서 나왔던 예제를 유전 알고리즘을 통해 … 개요 유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 복잡한 최적화 문제를 푸는데 사용된다. 스케줄링 등 복잡한 최적화 문제를 해결하는데 활용되고 있고, 딥러닝의 초기 웨이트 설정,..
Table of Contents:
GIL’s LAB
유전 알고리즘 본문
유전 알고리즘
Read More
유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기
Article author: koreapy.tistory.com
Reviews from users: 20965 Ratings
Ratings Top rated: 3.2
Lowest rated: 1
Summary of article content: Articles about 유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기 1. 정의. 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 … …
Most searched keywords: Whether you are looking for 유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기 1. 정의. 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 … https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 1. 정의 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 의..
Table of Contents:
py
유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기 본문
1 정의
2 개요
5 연산
예)
10 관련 기법
11 참고 문헌
원문
유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기
Read More
[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm)Article author: untitledtblog.tistory.com
Reviews from users: 10858 Ratings
Ratings Top rated: 3.9
Lowest rated: 1
Summary of article content: Articles about [최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm) 유전 알고리즘에서 가장 많이 이용되는 방법은 어떠한 규칙도 없이 단순히 임의의 값으로 염색체를 생성하는 것이다. 예를 들어, 자바로 작성된 [코드 1] … …
Most searched keywords: Whether you are looking for [최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm) 유전 알고리즘에서 가장 많이 이용되는 방법은 어떠한 규칙도 없이 단순히 임의의 값으로 염색체를 생성하는 것이다. 예를 들어, 자바로 작성된 [코드 1] … 1. 소개 유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 검색 방법이다. 유전 알고리즘은 이론적으로 전역 최적점을 찾을 수 있으며, 수학적으로 명확하게 정의되지..
Table of Contents:
Untitled
[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm) [최적화전역 최적화] 유전 알고리즘 (Genetic Algorithm) 본문Read More
유전 알고리즘 가지고 놀기
Article author: blog.devkcr.org
Reviews from users: 43670 Ratings
Ratings Top rated: 4.0
Lowest rated: 1
Summary of article content: Articles about 유전 알고리즘 가지고 놀기 예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm. 유전 알고리즘이란,. “유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 … …
Most searched keywords: Whether you are looking for 유전 알고리즘 가지고 놀기 예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm. 유전 알고리즘이란,. “유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 … 예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm 유전 알고리즘이란, “유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975..
Table of Contents:
‘기계학습’ Related Articles
티스토리툴바
유전 알고리즘 가지고 놀기
Read More
유전 알고리즘 (Genetic Algorithm) : 네이버 블로그
Article author: m.blog.naver.com
Reviews from users: 24671 Ratings
Ratings Top rated: 4.9
Lowest rated: 1
Summary of article content: Articles about 유전 알고리즘 (Genetic Algorithm) : 네이버 블로그 유전 알고리즘 (Genetic Algorithm) … 0. 유전 알고리즘이란? 생물학적 진화에 바탕을 둔 통계적 탐색 알고리즘 집합이다. 쉽게 말하면 그냥 유전을 … …
Most searched keywords: Whether you are looking for 유전 알고리즘 (Genetic Algorithm) : 네이버 블로그 유전 알고리즘 (Genetic Algorithm) … 0. 유전 알고리즘이란? 생물학적 진화에 바탕을 둔 통계적 탐색 알고리즘 집합이다. 쉽게 말하면 그냥 유전을 …
Table of Contents:
카테고리 이동
게임학과
이 블로그
알고리즘 인공지능
카테고리 글
카테고리
이 블로그
알고리즘 인공지능
카테고리 글
유전 알고리즘 (Genetic Algorithm) : 네이버 블로그
Read More
유전자 알고리즘 실습 – 날도의 잡다한 기술 블로그 | NaLDo’s IT Blog
Article author: naldo627.github.io
Reviews from users: 36182 Ratings
Ratings Top rated: 3.2
Lowest rated: 1
Summary of article content: Articles about 유전자 알고리즘 실습 – 날도의 잡다한 기술 블로그 | NaLDo’s IT Blog 유전 알고리즘은 생물체가 환경에 적응하며 진화하는 모습을 모방하여, … 이번엔 비교적 간단한 예제를 파이썬으로 실습을 진행할 계획이다. …
Most searched keywords: Whether you are looking for 유전자 알고리즘 실습 – 날도의 잡다한 기술 블로그 | NaLDo’s IT Blog 유전 알고리즘은 생물체가 환경에 적응하며 진화하는 모습을 모방하여, … 이번엔 비교적 간단한 예제를 파이썬으로 실습을 진행할 계획이다. 대한민국 경기도 성남시 거주, 가천대학교 재학 중, 공부 많이 하려고 맘만먹는 공돌이Spring, Python, Java, C, C++, MFC, Github
Table of Contents:
인공지능
유전자 알고리즘(GA)이란
실습 개요
실습 과정
실습 후기
소스코드
유전자 알고리즘 실습 – 날도의 잡다한 기술 블로그 | NaLDo’s IT Blog
Read More
[Data Mining] Genetic Algorithm 유전 알고리즘 / 퀴즈Article author: hororolol.tistory.com
Reviews from users: 40748 Ratings
Ratings Top rated: 4.1
Lowest rated: 1
Summary of article content: Articles about [Data Mining] Genetic Algorithm 유전 알고리즘 / 퀴즈 유전 알고리즘이란? Genetic Algorithm: GA; 생물학적 진화 원리에 기반한 Directed Search Algorithm. 유전 알고리즘의 응용 예. …
Most searched keywords: Whether you are looking for [Data Mining] Genetic Algorithm 유전 알고리즘 / 퀴즈 유전 알고리즘이란? Genetic Algorithm: GA; 생물학적 진화 원리에 기반한 Directed Search Algorithm. 유전 알고리즘의 응용 예. 유전 알고리즘이란? Genetic Algorithm: GA 생물학적 진화 원리에 기반한 Directed Search Algorithm 유전 알고리즘의 응용 예 함수 최적화 시스템 최적화 조합적 최적화 분류기 유전 알고리즘의 기본 구조 생물학..
Table of Contents:
너와 나의 스토리
[Data Mining] Genetic Algorithm 유전 알고리즘 퀴즈 본문티스토리툴바
[Data Mining] Genetic Algorithm 유전 알고리즘 / 퀴즈Read More
See more articles in the same category here: https://toplist.avitour.vn/blog/.
[ Genetic Algorithm ] 유전 알고리즘을 통해 비밀번호를 뚫어보자!이번 포스팅에서는 유전 알고리즘을 통해 비밀번호를 찾는 알고리즘이다. 그전에 유전 알고리즘에 대해서 간략하게 설명을 하자면 다음과 같다. 말 그대로 유전 즉, 세대가 존재한다는 뜻이다. 이게 무슨 뜻이냐… 우선 랜덤으로 최초의 아이들을 생성한다. 그리고 그 생성된 아이들을 가지고 fitness (성능)을 측정한다. 성능을 측정할 때 적절한 점수를 부여하여 만약 점수가 높다면 해당 아이들을 선발해 낸다. 그리고 선발된 아이들을 교배하여 다음 세대를 만들어낸다. 그 과정에서 돌연변이도 추가하여 다음 세대를 만들어 내고 또 태어난 자식들을 가지고 성능을 측정하여 위의 과정을 계속 반복하여 수 세대를 걸쳐서 답을 도출해 내는 것이 유전 알고리즘이다. 그렇다면 파이썬으로 유전 알고리즘을 구현해보자. 함수가 많아서 함수 하나하나씩 잘라서 설명을 해보려고 한다. 우선 비밀번호는 문자열을 사용하고 길이가 최소 2 ~ 최대 10 정도로 적당하게 설정한다. 그리고 랜덤으로 아스키코드의 문자와 숫자를 생성해야 하기 때문에 random과 string을 import 한다.
유전 알고리즘
728×90 개요 유전 알고리즘은 자연계의 진화 체계를 모방한 메타휴리스틱 알고리즘으로 복잡한 최적화 문제를 푸는데 사용된다. 스케줄링 등 복잡한 최적화 문제를 해결하는데 활용되고 있고, 딥러닝의 초기 웨이트 설정, 특징 선택 등 머신러닝 문제를 해결하는데도 많이 사용된다. 필자의 주력 연구 방법론중 하나이며, 지금도 유전 알고리즘을 이용한 쉐이플릿 탐색이라는 주제로 연구를 진행하고 있다. 그러면 이제 유전 알고리즘이 어떻게 작동하는지, 또 파이썬으로 어떻게 구현할 수 있는지를 소개하자. 가능하면 비전공자의 입장에서 친절히 설명하고자 한다. 최적화 문제란? 최적화 문제는 제약 하에서 목적식을 최소화 혹은 최대화하는 결정 변수의 값을 찾는 문제이다. 제약이란 것은 해가 만족해야 하는 조건이고, 목적식은 최소화 혹은 최대화해야 하는 대상이며, 결정 변수는 값을 찾아야 하는 변수이다. 위키피디아에서 소개하고 있는 간단한 예제를 보자 (참고로 선형 계획법은 최적화 문제의 대표적인 유형이다). 홍길동 씨가 두 가지 종류의 빵을 판매하는데, 초코빵을 만들기 위해서는 밀가루 100g과 초콜릿 10g이 필요하고 밀빵을 만들기 위해서는 밀가루 50g이 필요하다. 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다. 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다. 만든 빵을 전부 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 홍길동 씨는 이익을 극대화 하기 위해서 어떤 종류의 빵을 얼마나 만들어야 하는지 다음과 같이 선형 계획법을 이용하여 계산할 수 있다. 여기서 x1과 x2가 결정변수이다. 저 문제는 100×1 + 50×2 <= 3000, 10x1 <= 100, x1, x2 >=0을 만족하는 x1과 x2가운데, 100×1 + 40×2를 최대화하는 x1과 x2를 찾아라 라고 해석할 수 있다. 이 정도의 문제는 매우 간단하기 때문에 사실 유전 알고리즘을 사용할 필요가 없다. 여기서 간단하다는 것은 저 문제의 최적해(=정답)를 구하는 과정이 공식처럼 정의되어 있다는 것이다. 그런데 현실 문제는 저 정도로 간단하지 않은 것이 보통이다. 휴리스틱과 메타휴리스틱 이제 휴리스틱이라는 단어가 무엇인지 이해해보자. 위키피디아에서는 휴리스틱을 아래와 같이 정의하고 있다. 휴리스틱(heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다. 어렵게 정의하고 있지만, 휴리스틱은 결국 그럴싸하게 대충 푸는 방법이라고 볼 수 있다. 외판원 문제 (traveling sales problem)을 예로 들어보자. 이 문제는 택배 기사가 현 위치에서 어느 순서대로 택배를 배달해야 최소한의 거리로 움직일 수 있는지를 찾는 문제로, 대표적인 NP 문제 (일단은 풀기 어려운 문제라고 이해하고 넘어가자)이다. 이 문제의 가장 직관적인 해법은 지금 있는 곳에서 가장 가까운 곳부터 배달을 가는 것이다 (즉 그리디하게 탐색하는 것) 시작점이 택배회사였다면, 택배회사에서 가장 가까운 A를 가고, 또 A에서는 A에서 가장 가까운 B를 가는 것이다. 그럴싸하지 않은가? 우리도 여러 군데를 들려야 하는 상황이라면, 가장 가까운 곳 먼저 들리는 경우가 많기 때문에, 그럴싸하고 합리적인 것처럼 보인다. 물론, 이 접근으로 찾은 답은 정답이 아닐 가능성이 훨씬 높다. 이처럼 문제를 알려진 공식으로 풀 수 없는 경우에 그럴싸하게 대충 푸는 접근을 휴리스틱이라고 할 수 있다. 그런데 휴리스틱은 문제마다 문제 상황에 맞는 경험이나 직관을 이용해야 하는 어려움이 있다. 그러니까 위에서 예를 들었던 그리디 서치는 외판원 문제에는 적용할 수 있을지 몰라도, 다른 문제에는 적용할 수 없다. 그래서 등장한 것이 메타 휴리스틱이고, 유전 알고리즘도 메타 휴리스틱에 속한다. 메타 휴리스틱은 휴리스틱이긴한데, 그 풀이 과정 등이 구조적으로 잘 정의되어 있어 대부분의 문제에 어려움없이 적용할 수 있는 휴리스틱을 말한다. 유전 알고리즘의 개념 이해하기 유전 알고리즘은 기본적으로 여러 개의 해로 구성된 해 집단을 만들고 평가한 뒤, 좋은 해를 선별해서 새로운 해 집단을 만드는 메타휴리스틱 알고리즘이다. 유전 알고리즘의 구성 등을 살펴보기 전에 작동 과정에 대해 개략적으로 이해하고 시작하자. 아래와 같이 함수 f(x)가 있고, x에 따른 f(x)의 최소값을 찾는 문제가 있다고 하자. 설명을 위해, 이 함수를 산이라고 하고, 해를 토끼, 그리고 산의 낮은 곳일수록 더 좋은 곳이라고 하자. 유전 알고리즘은 여러 토끼를 만들고, 좋은 환경에 우연히 있던 토끼들만 살아남아서 비슷한 위치에 자식을 만드는 과정을 통해, 가장 낮은 곳, 즉 최적값을 찾게 된다. 육안으로 어느 x가 가장 좋은지 알 수 있지만, 실제 문제에서는 저 그래프를 그리는 것 자체가 불가능한 경우가 대부분이다. 배우신 분들(?)은 미분을 하면 되지 않느냐라고 주장할 수도 있겠지만, 미분 자체가 불가능한 경우도 역시 매우 흔하다. 정답이 모두 정수여야 하는 정수 계획법 문제의 경우에는 어느 경우에서도 미분이 불가능할 것이다. 다시 설명으로 돌아와서 아래와 같이 5마리의 주황색 토끼를 만들어 임의로 배치한다. 우연히 4번과 5번 있던 토끼는 좋은 환경에 있었고, 1, 2, 3번은 그렇지 못하다. 즉, 4번과 5번이 적자이고, 나머지는 적자가 아니다. 이제 적자라서 살아남은 4번과 5번이 자식 a, b, c를 만든다. 자식들은 파란색으로 표시했다. 이제 다시 살펴보니, 부모보다 좋은 위치에 있는 자식 b와 c도 있고, 부모랑 비슷하거나 더 나쁜 위치에 있는 a도 생겼다. 그럼 이제 가장 적합한 b와 c가 살아남아 또 대를 이어 나갈 것이다. 그러다보면 언젠가는 최저점에 있는 토끼를 만나게 될테고, 다시말해 최적해를 구할 것이다. 주요 용어를 거의 사용하지 않고 설명한 내용이지만, 여기서 유전 알고리즘에 관한 몇 가지 인사이트를 얻을 수 있다. (1) 해를 많이 만들면, 더 좋은 해를 찾을 가능성이 높다. 물론 시간은 더 소요될 것이다. (2) 너무 잘난 해라면, 세대가 지나도 계속 세대를 구성하는 일원으로 남아있다. (3) 다음 세대에서 자식을 만드는 부모의 수가 많을수록, 더 많은 해를 탐색할 수는 없다. 그렇지만 더 안정적일 것이다. (4) 처음에 해들이 한 곳에 몰려있었다면 (특히, 1, 2번 위치), 세대를 거듭해도 좋은 해를 못 찾을 수도 있다. 유전 알고리즘 순서도 이제 본격적으로 유전 알고리즘에 대해 알아보자. 유전 알고리즘은 아래 그림과 같이 초기 해 생성, 적합도 평가, 교차 연산, 돌연변이 연산을 반복한다. 파라미터 정의 단계에는 포함하지 않았지만, 유전 알고리즘을 사용하려면 아래 내용을 미리 결정해야 한다. 해 표현 방법 최대 세대 수 종료 조건 세대 별 포함되는 해의 개수 교차 연산자 돌연변이 연산자 교차 비율 적합도 함수 돌연변이 비율 등 초기 해 생성 첫 번째 단계에서는 초기 해, 즉 첫 번째 세대의 해들을 생성한다. 이 과정에서는 보통 임의로 해를 생성하는데, 문제에 따라서 특정 조건에 맞는 해를 만들도록 설계하는 것이 유리하기도 하다. 그리고 여기서 가장 중요한 것은 해를 어떻게 표현할 것인가이다. 이를 줄여서 해 표현이라 하는데, 해 표현을 어떻게 하느냐에 따라서 문제 풀이가 쉬울 수도 있고 그렇지 않을 수도 있다. 유전 알고리즘을 많이 사용해본 사람과 그렇지 않은 사람의 차이가 사실 여기서 판가름난다. 가장 흔히 사용되는 해 구조는 다음과 같은 이진 벡터이다. 이진 벡터가 많이 사용되는 이유는 뒤에서 설명할 교차 연산이나 돌연변이 연산이 편리하기 때문이다. 외판원 문제처럼 순서를 결정하는 경우라면 이진 벡터보다는 각 위치가 도달한 장소의 인덱스를 나타내는 벡터로 표현하는 것이 적합할 수도 있다. 적합도 평가 및 해 선택 이 단계에서는 현재 세대에 있는 모든 해들을 적합도 함수라는 것을 이용하여 평가한다. 적합도는 보통 최적화 문제의 목적식을 그대로 사용하는 것이 일반적이다. 가령, 외판원 문제에서는 해의 적합도가 전체 이동 거리에 반비례할테고, 최대화 문제라면 해의 적합도가 목적식에 비례할 것이다. 적합도 평가 결과를 토대로 그 다음 세대를 만들 해들을 결정한다. 즉, 교차연산과 돌연변이 연산을 적합도가 우수한 해들에 적용하여 다음 세대에 속할 해를 만든다. 여기서 적합도가 높은 상위 N1개의 해를 선택하여 N2개의 해를 만드는 방식으로 다음 세대를 구성할 수도 있고 (세대별 해의 개수 (N) = N1 + N2), 혹은 적합도에 비례하게 해를 확률적으로 선택하여 해를 생성할 수도 있다. 전자의 경우에는 이전 세대의 해가 다음 세대로 그대로 넘어가고, 좋은 해들만 선별되므로 안정적이라는 장점이 있으나, 지역 최적에 빠질 위험이 있다. 후자의 경우에는 반대로 세대가 거듭될수록 이전에 고려하지 않았던 새로운 종류의 해를 탐색할 수 있으므로, 더 좋은 해를 찾을 수도 있지만, 수렴하지 못할 가능성이 크다. 교차 연산 교차 연산은 두 개의 부모 해를 바탕으로 자식 해를 만드는 연산을 말한다. 즉, 부모가 결합하여 자식을 낳는 과정을 모방한 것이 바로 교차 연산이다. 당연히 교차 연산을 해서 나온 해는 부모를 닮게 된다. 대표적인 교차 연산자로는 한 점 교차 연산자, 두 점 교차 연산자 등이 있다. 이들 교차 연산자는 교차 지점을 임의로 설정한 뒤, 교차 지점 앞쪽에서는 부모 1의 유전자를, 뒤쪽에서는 부모 2의 유전자를 가져와 새로운 자식을 만든다. 아래 그림에서 빨간색 해와 파란색 해가 교차되면서, 앞쪽이 빨갛고 뒤쪽이 파란 해와 앞쪽이 파랗고 뒤쪽이 빨간 해가 생성되었다. 한 점 교차 연산자 두 점 교차 연산자 돌연변이 연산 돌연변이 연산은 만들어진 자식 해를 일부 수정하는 것이다. 즉, 두 부모가 교차를 하더라도, 두 부모와는 완전히 일치하지 않는 그런 특성을 만들기 위한 연산이다. 세대를 거듭할수록 다양한 해를 찾지 않고 특정한 해로 빠르게 수렴하는 것을 막기 위한 연산이다. 아래와 같은 함수가 있고, 해가 주황색으로 표시된 상황을 보자. 여기서 저 네 개의 해를 바탕으로 교차 연산을 계속해서 진행하면 왼쪽 지역 최적에 빠져버리게 될 위험이 있다. 그런데 돌연변이 연산을 해주게 되면, 아예 엉뚱한 위치에 해를 만들기도 하므로, 우연히 좋은 해를 찾을 가능성이 높아지는 것이다. 다시 한 번 강조하지만, 돌연변이 연산을 한다고 해서 무조건 좋은 해를 찾을 수 있는 것은 아니다. 오히려 전역 최적에 가까워지다가 돌연변이 연산 때문에 전역 최적과 멀어지기도 한다. 대표적인 돌연변이 연산 방법으로는 flip-bit 변이 연산이 있다. 임의로 돌연변이를 할 자식을 선택하고, 자식의 유전 개체 (참고: 해를 유전자라하며, 해의 구성 요소 (즉 벡터의 구성 요소)를 유전 개체라 함)를 임의로 선택하여, 0이면 1로, 1이면 0으로 바꾸는 간단한 연산이다. 파이썬을 이용한 예제 풀이 최적화 문제를 소개하는 과정에서 나왔던 예제를 유전 알고리즘을 통해 풀어보자. 이 문제에서는 x1과 x2를 찾아야 한다. 해 구조는 다음과 같은 2 x 5 크기의 이진 행렬을 사용한다. 첫 번째 행은 x1과 관련이 있고, 두 번째 행은 x2와 관련이 있다. 즉, 위 구조의 해는 x1과 x2를 다음과 같이 표현한다. 사실 이렇게 모두 양수만 표현하도록 설계한 이유는 세 번째 제약을 만족시키는 해를 만들기 위함이다 (이런게 유전 알고리즘을 사용할 때 매우 중요한 센스이다!). 해 표현을 제외한 유전 알고리즘의 주요 파라미터는 다음과 같이 설정한다. 최대 세대 수: 10 종료 조건: 최대 세대 수 도달 세대 별 포함되는 해의 개수: 20 교차 연산자: 1점 교차 연산 부모 수: 10 돌연변이 연산자: flip bit 돌연변이 연산 적합도 함수: 목적식 (제약을 만족못하면 0점) 돌연변이 비율: 10% 돌연변이 유전 개체 비율: 20% 이제 파이썬을 사용해서 유전 알고리즘의 각 단계를 함수 단위로 구현해보도록 하자. 유전 알고리즘을 사용할 수 있는 패키지가 있긴 하지만, 문제에 따라서 직접 정의해야 하는 부분이 많다보니 개인적으로는 numpy를 활용하는 것이 편리하다. 먼저, numpy를 임포트해주자. import numpy as np 그리고 N개의 초기 해를 생성하는 함수를 정의하자. 이 함수는 random.randint를 사용하여 0과 2사이 중 하나를 선택하여 (N, 2, 5) shape의 배열을 생성한다. 즉, 0과 1로만 구성되는 (N, 2, 5) shape의 배열을 만드는 것이며, N은 결국 해의 개수, (2, 5)는 해의 구조 (행렬 구조)라고 볼 수 있다. def generate_initial_population(N): initial_population = np.random.randint(0, 2, (N, 2, 5)) return initial_population 이제 각각의 해를 평가하는 적합도 함수를 만들자. 제약이 문제에 포함되어 있으므로 제약을 어기는 경우에는 적합도를 0으로 주도록 하자. 먼저 2 * 5 크기의 행렬이 입력되면, 여기서 x1과 x2를 계산한다. 그리고 문제의 제약을 만족하는지 여부를 확인해서, 모두 만족하면 목적식으로 적합도를 평가하고, 하나라도 만족하지 못하면 적합도를 0으로 설정한다. def evaluate_fitness(solution): x1 = sum([2**(4-i) * solution[0][i] for i in range(5)]) x2 = sum([2**(4-i) * solution[1][i] for i in range(5)]) constraint_1 = (100 * x1 + 50 * x2) <= 3000 constraint_2 = (10 * x1) <= 100 if constraint_1 and constraint_2: fitness_value = 100 * x1 + 40 * x2 else: fitness_value = 0 # 제약을 하나라도 위반하면 적합도 0점 return fitness_value 이제 한 세대에서 두 개의 해를 선택하여 1점 교차 연산을 수행하는 함수를 정의하자. 이 함수는 두 개의 해 (solution1, solution2)를 입력받아 교차 지점을 1과 5사이에서 임의로 선택하여 자식을 만든다. 해 자체가 행렬이기 때문에 교차 지점을 각 행마다 설정했다. 자세히 살펴보면, 각 행마다 교차 지점은 1, 2, 3 중 하나를 선택하는데, 0이나 4가 교차지점이 되면 사실상 하나의 부모의 유전자가 그대로 내려오는 것이기 때문에 0과 4는 제외하였다. 그리고 자식 해를 빈 배열로 생성한 뒤, 0번째 행과 1번째 행을 각각 부모들의 유전자로 채운다. 리스트로 만들어서 더하는 방식도 괜찮지만, 그렇게 되면 ndarray와 리스트를 왔다갔다하면서 문제가 생길 위험이 있기 때문에, empty 함수를 사용했다. def crossover(solution1, solution2): crossover_point_1 = np.random.randint(1, 4) # x1에 대한 교차 지점 crossover_point_2 = np.random.randint(1, 4) # x2에 대한 교차 지점 child = np.empty((2, 5)) # 자식을 빈 배열로 생성 # 부모 유전자 가져오기 child[0][:crossover_point_1] = solution1[0][:crossover_point_1] child[0][crossover_point_1:] = solution2[0][crossover_point_1:] child[1][:crossover_point_2] = solution1[1][:crossover_point_2] child[1][crossover_point_2:] = solution2[1][crossover_point_2:] return child 이제 돌연변이 연산을 정의하자. p는 각 개체에서 돌연변이가 일어날 확률이다. 해의 모든 인덱스를 row와 col로 순회하면서, 각 위치마다 난수를 생성한 뒤, 그 난수가 p보다 작다면 (즉, p의 확률로), 그 위치에 있는 값을 바꿔준다. 여기서 유용한 두 가지 테크닉을 짚고 넘어가자. x = 1 - x는 x가 0이면 1로, 1이면 0으로 바꾸는데 사용 if 난수 < p는 결국 p의 확률로 선택하는데 사용 def mutation(child, p): for row in range(2): for col in range(5): if np.random.random() < p: child[row, col] = 1 - child[row, col] return child 이제 함수 정의는 끝났으니, 함수들을 이용하여 유전 알고리즘을 구현하자. 먼저, 파라미터를 이렇게 정의하자. num_iter = 10 # 세대 수 N = 20 # 한 세대에 포함되는 해의 개수 N_P = 10 # 부모 개수 mutation_sol_prob = 0.1 # 유전자(해)가 돌연변이일 확률 mutation_gene_prob = 0.2 # 유전 개체가 돌연변이일 확률 그리고나서 메인 코드를 작성한다. 가장 먼저 초기 해를 생성하고, 지금까지 찾은 최대 적합도를 초기화한다. 그리고 각 이터레이션마다 현재 세대를 평가하고, 현재 세대에 지금까지 찾은 최대 적합도보다 큰 적합도를 갖는 해가 있다면, 그 해를 best_solution에, 그 해의 적합도를 best_score에 저장한다. 그리고 fitness_value_list를 기준으로 상위 N_P개의 해를 선택하여 parents에 저장한다. 그리고 한 세대에 포함되야 하는 해의 개수에서 부모의 개수를 뺀 만큼 자식을 생성한 뒤, 20%의 확률로 돌연변이 연산을 적용한 자식을 new_population에 추가한다. # 초기 해 생성 current_population = generate_initial_population(N) best_score = -1 # 지금까지 찾은 최대 적합도 초기화 for _ in range(num_iter - 1): # 해 평가 수행 fitness_value_list = np.array([evaluate_fitness(solution) for solution in current_population]) # 지금까지 찾은 최대 적합도보다 현세대에 있는 최대 적합도가 크다면 업데이트 if fitness_value_list.max() > best_score: best_score = fitness_value_list.max() best_solution = current_population[fitness_value_list.argmax()] # 적합도 기준 상위 N_P개 해 선정 (값이 큰 순으로 정렬하기 위해 -를 붙임) parents = current_population[np.argsort(-fitness_value_list)] # 새로운 해 집단 정의 new_population = parents # 두 개의 부모를 선택하면서 자식 생성 for _ in range(N – N_P): # N – N_P = 생성해야 하는 자식 개수 # 부모 선택 parent_1_idx, parent_2_idx = np.random.choice(N_P, 2, replace = False) parent_1 = parents[parent_1_idx] parent_2 = parents[parent_2_idx] # 자식 생성 child = crossover(parent_1, parent_2) # mutation_sol_prob의 확률로 돌연변이 연산 수행 if np.random.random() < mutation_sol_prob: child = mutation(child, mutation_gene_prob) # new_population에 child 추가 (child 구조가 (2, 5)라서 vstack이 안되므로, 구조를 변경) new_population = np.vstack([new_population, child.reshape(1, 2, 5)]) 이렇게 찾은 해는 다음과 같다. best_solution을 뜯어보면, x1 = 10, x2 = 31인데, 주어진 해 구조에서는 최적임을 쉽게 알 수 있다. 다 풀고 나서 실수를 알아차렸는데, 2*5크기가 아니라 2*6크기의 해 구조를 정의했으면 최적해를 찾았을 것이다... 728x90 유전 알고리즘(Generic Algorithm in Python) 파이썬으로 풀기 https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 1. 정의 유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산모델로, 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용(채용)하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구등의 용어도 문제풀이 과정에서 사용된다. 2. 개요 유전 알고리즘은 자연계의 생물 유전학에 기본이론을 두며, 병렬적이고 전역적인 탐색알고리즘으로서, 다윈의 적자생존 이론을 기본 개념으로 한다. 유전 알고리즘은 1) 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 2) 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 낸다. 3) 여기에서 해들을 나타내는 자료구조는 유전자, 4) 이들을 변형함으로써 점점 더 좋은 해를 만들어 내는 과정은 진화로 표현할 수 있다. 달리 표현하면, 유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다. 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 문제를 풀기 위한 접근방법에 가까우며, 유전 알고리즘에서 사용할 수 있는 형식으로 바꾸어 표현할 수 있는 모든 문제에 대해서 적용할 수 있다. 일반적으로 문제가 계산 불가능할 정도로 지나치게 복잡할 경우 유전 알고리즘을 통하여, 실제 최적해를 구하지는 못하더라도 최적해에 가까운 답을 얻기 위한 방안으로써 접근할 수 있다. 이 경우 해당 문제를 푸는 데 최적화되어 있는 알고리즘보다 좋은 성능을 보여주지는 못하지만, 대부분 받아들일 수 있는 수준의 해를 보여줄 수 있다. 이러한 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘들로 진화 전략(Evolutionary strategies), 유전 프로그래밍(Genetic programming) 등 여러 형태의 이론과 기법들이 최근에 활발히 연구되고 있다. 유전 알고리즘은 이 중에서 가장 기본이 되고 대표적인 알고리즘으로, 자연과학/공학 및 인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다. 3. 요구 조건 유전 알고리즘을 어떤 문제에 적용하기 위해서는 해를 유전자의 형식으로 표현할 수 있어야 하며, 이 해가 얼마나 적합한지를 적합도 함수를 통해 계산할 수 있어야 한다. 일반 생명체의 특성이 유전체의 집합인 유전자로 나타나는 것과 같이, 유전 알고리즘에서는 해의 특성을 숫자의 배열이나 문자열과 같은 자료 구조를 통해서 표시 하게 된다. 적합도 함수는 이렇게 나타내어진 해가 얼마나 문제의 답으로 적합한지를 평가하기 위한 함수이다. 이는 실세계의 생명체가 유전적 특성에 따라 환경에 얼마나 잘 적응할 수 있는지가 결정되는 것과 비교할 수 있다. 4. 흐름 어떤 문제에 대해 유전자 형식이 정의되었다면, 어떤 해들의 유전자들을 서로 조합함으로써 기존의 해로부터 새로운 해를 만들어낼 수 있다. 이런 조합 연산은 교배(Crossover)에 비유할 수 있다. 우수한 해들을 선택하여 이들을 교배하면, 만들어진 해는 우수한 해들이 가지는 특성을 물려받을 가능성이 높게 된다. 우수한 해의 선택에는 앞에서 정의한 적합도 함수를 이용할 수 있으며, 적합도가 높은 해가 선택될 확률을 높게 만들면, 보다 나은 유전자를 가진 해가 다음 세대에 자신의 유전자를 넘겨줄 확률이 높게 되고, 따라서 다음 세대의 해들은 최적해에 점차 가까워지게 된다. 또 비록 교배를 통해 후손을 남기지 못하더라도, 변이를 통해 새로운 유전자를 형성하여 다음 세대로 넘겨주도록 할 수 있으며, 이는 지역 최적점에 빠지지 않도록 하는 주요한 기법이다. 해들을 교배하기 위해서는 아담과 하와처럼 초기 해의 집단이 필요하다. 초기해 집단은 단지 이후의 해를 구하는 데 있어 필요한 초기 개체로서의 역할만을 위한 것이므로, 우수한 해들로 이루어질 필요는 없다. 일반적으로는 유전자를 랜덤하게 생성하여 초기화해 ‘초기해’ 집단을 구성한다. 초기해 집단이 구성되면, 이들 내부의 해의 교배를 통해 다음 세대의 해의 집합을 생성하게 되며, 이를 세대를 거듭하면서 반복해 가면, 해들은 점점 정답에 가까워지게 된다. 유전 알고리즘이 전역 최적해를 구하려면, 많은 인구를 유지하면서 많은 세대를 내려갈 필요가 있다. 따라서, 대부분의 경우는 세대가 일정 수준 진행되었거나, 해가 특정 범위에 들게되면 알고리즘을 종료하게 된다. 5. 연산 유전 알고리즘은 1) 선택, 2) 교차, 3) 변이, 4) 대치 등 몇가지 주요 연산으로 구성된다. 6. 선택 한 세대에서 다음 세대로 전해지는 해의 후보가 되는 해들을 선택한다. 선택 방법에는 1) 균등 비례 룰렛 휠 선택, 2) 토너먼트 선택, 3) 순위 기반 선택 등이 있다. 해의 선택은 유전 알고리즘의 성능에 큰 영향을 미친다. 어떤 방법을 쓰느냐에 따라 최적해로 다가가는 속도가 더디게 되거나, 아니면 지역 최적해에 빠지는 경우가 생길 수도 있기 때문이다. 또는 우수한 해가 보유한 나쁜 인자가 전체 인구에 퍼지거나, 반대로 나쁜 해가 보유한 우수한 인자가 영구히 사장될 수도 있다. 따라서 어떤 해를 선택하는지는 유전 알고리즘의 성능을 위해서 중요한 요소라고 할 수 있다. 일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 많이 사용된다. 이는 반대로 말하면, 나쁜 해라 할지라도 그 해에 포함된 좋은 인자를 퍼뜨릴 기회를 준다고 볼 수 있다. 현 세대에서 가장 좋은 해라 할지라도 실제로는 지역 최적해에 가까운 해일 수도 있고, 반대로 좋지 않은 해라 할지라도 전역 최적해에는 더 가까울 수도 있기 때문이다. 실제로 전역 최적해가 어디에 있는지는 알 수 없는 일이므로, 가능한 해들의 평균적인 적합도를 높여 가면서도 유전자의 다양성을 유지하는 것이 지역 최적해에 빠지는 것을 가능한 한가지 방지하는 방법이며, 이는 실세계의 생명체들 역시 유전적 다양성을 유지하는 종이 장기적인 생존 가능성이 높은 것과 비견할 수 있다. 7. 교차 생명체는 세대 내에서의 교배를 통해 다음 세대를 생성한다. 이와 마찬가지로 유전 알고리즘에서 자연 선택된 해들은 교배를 통하여 다음 세대의 해들을 생성하게 된다. 일반적으로 두 개의 해를 선택한 후 둘 간에 교배 연산을 수행하게 되며, 이를 통해 생성된 해는 각각의 부모 해의 교차 연산을 통해서 서로 겹치지 않는 위치의 유전인자를 받아 새로운 유전자를 구성하게 된다. 실제 생명체의 염색체가 재조합되는 과정에서 부모 염색체의 일부분이 특정 위치를 기준으로 서로 바뀌어 결합되는 경우가 있는데, 이 현상을 교차라고 한다. 유전 알고리즘의 교차 연산은 이 현상을 본따, 부모 해의 유전자들을 서로 교차시켜서 자식해를 만들어낸다. 교차 연산의 실제 수행 방법은 비트 단위 교차에서부터 블록 단위 교차까지 다양한 방법으로 구현할 수 있으며, 교차를 한 번만 수행할지 전 영역에 대해서 교차시킬지 역시 결정할 수 있다. 또한 모든 해에 대해 교차연산을 수행할 경우 우수한 해가 다른 해와의 교배를 통해서 우수성을 잃어버림에 따라 세대의 최고 우수해가 보존되지 않는 상황이 발생할 수 있다. 이런 경우를 방지하기 위하여 교차를 확률적으로 수행하여 우수한 해가 변형되지 않고 그대로 다음 세대에 전해질 확률을 부여하는 방법도 사용된다. 8. 변이 일반 생명체에서, 유전자의 교배 뿐 아니라, 하나의 유전자가 직접적으로 변이를 일으켜서 주어진 환경에서 살아남을 확률 역시 존재한다. 변이 연산은 주어진 해의 유전자 내의 유전 인자의 순서 혹은 값이 임의로 변경되어 다른 해로 변형되는 연산이다. 해의 유전자들을 가상의 공간에 맵핑할 경우 교배 연산은 부모해들 사이의 어떤 지점에 자식해를 생성하는 것이라고 볼 수 있다면, 변이 연산은 임의의 위치로 점프하는 것에 비견할 수 있다. 따라서 약간의 확률로 변이 연산을 수행시켜 주는 것은 전체 세대가 함께 지역 최적해에 빠져드는 경우를 방지하기 위한 주요한 기법이 될 수 있으며, 해집단의 다양성을 높여준다. 9. 대치 교차·변이 등을 거쳐서 만들어진 새로운 해를 해집단에 추가하고, 기존 해 중 열등한 해를 가려내서 제외시키는 연산이다. 가장 품질이 나쁜 해를 대치하는 방법, 새로운 해의 부모해 중에서 새로운 해와 가장 비슷한 해를 대치시키는 방법(해집단의 다양성을 유지하기 위함) 등이 있다. 예) {1, 5, 6, 8, 3, 7, 3, 5, 9, 0} 중 3개를 골라서 20으로 만드는 문제가 있다고 하자. 여기서 유전체는 각 숫자이며, 각 해의 유전자는 (1,5,3)와 같이 유전체 3개의 집합으로 이루어진다. 적합도 함수를 20과 얼마나 가까운지를 나타내는 값으로 둔다면, (1,5,3)에 대한 적합도는 f( (1,5,3) ) = 11이 된다. 먼저 첫 세대를 아무렇게나 생성한다. 첫 세대가 만약 { (1,5,3) (8,0,9) (9,9,8) (3,7,5) } 으로 형성되었다고 하자. 각각의 적합도를 구하면, { 11, 3, 6, 5 }이 되며, 이 값이 높을수록 20에서 멀기 때문에 해로서 부적당하다는 것을 의미하며, 따라서 세대를 거침에 따라 살아남을 확률이 낮게 된다. 다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적으로 선택한다. (룰렛 알고리즘이 자주 쓰인다) 위의 예에서 적합도가 3인 (8,0,9)는 적합도가 6인 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 첫번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8), (9,0,9)가 되며, 각각의 적합도는 5, 2가 된다. 10. 관련 기법 11. 참고 문헌 12. 관련 논문 Differential Gene Set Enrichment Analysis: A statistical approach to quantify the relative en- richment of two gene sets https://github.com/Kcrong/Simple-Genetic-Algorithm 원문 https://blog.devkcr.org/entry/%EC%9C%A0%EC%A0%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%80%EC%A7%80%EA%B3%A0-%EB%86%80%EA%B8%B0 예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm 유전 알고리즘이란, “유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다.” – 위키피디아 유전 알고리즘은 부모의 유전 정보들이 자식들에게 골고루 분포 됨으로써, 문제에 대한 해를 찾아가는 알고리즘이다. 자식 해는 부모 해와 비슷한 형질을 가지며, 우월한 유전자들은 다시 자식해를 만들며 우수 유전자를 널리 퍼트리는 특징이 있다. 소스 설명 전, 사용할 용어에 대한 설명은 아래와 같다. 1. 유전자 예시 소스에서는 integer list 로 정의했다. 하지만 그 형태와 값의 크기는 무엇이든지 될 수 있으며, 제한이 없다. (구현이 어려울 뿐..) 2. 세대 유전자들의 생성과 소멸을 아우르는 하나의 주기를 말한다. 보통 생성 > 번식 > 소멸 의 주기를 가진다. 3. 적합도 (Fitness) 유전자가 얼마나 우월한지 보여주는 지수. 이 지수가 높을 수록 우월한 유전자임을 뜻한다. 전체적인 알고리즘은 3가지로 이루어져있다. 1. 부모 유전자 선택 2. 번식 3. 돌연변이 부모 유전자 선택 부모 유전자를 선택하는 부분에서는, 룰렛 휠 선택 방식을 이용했다. 1 2 3 # 부모를 select_list를 이용해 정함. # 부모로 선출될 확률은 fitness 과 비례한다. parents = tuple(self.select_list[rand( 0 , len (self.select_list))] for i in range ( 2 )) cs 룰렛 휠 방식 이미지 출처: http://blog.secmem.org/category/IT%20%EB%86%80%EC%9D%B4%ED%84%B0/Elite%20Member%20Tech%20%26%20Talk?page=37 룰렛 휠 방식이란, 적합도가 높을수록 부모 해로 선택될 확률이 높아지도록 하는 방식이다. 위 그림처럼, 적합도가 100인 C는 룰렛에서 보듯이 선택될 확률이 높다. 하지만 적합도가 40인 D는 C와 달리 선택될 확률이 적다. 이처럼 우월한 유전자를 가질 수록 부모 해로 선택될 확률을 높이는 것을 룰렛 휠 방식이라고 한다. 번식 (교차) 자식 유전자를 만들 때는, 2점 교차 라는 방식을 이용했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 # 각 교차 포인트를 정한다. # rand 함수의 반환이 float 형이므로, 소수점을 버리기 위해 int() 형변한을 해준다. switch_point = (rand( 1 , gene_len / / 2 ), rand(gene_len / / 2 , gene_len)) # 처음 자식이 받는 유전자는 parent1 # 다만 교차 포인트에 다다르면, 다른 parent 유전자 정보를 받아오기 시작한다. (parent = parent2) parent = parents[ 0 ] for i in range (gene_len): # 자식 유전자 정보는 부모 유전자에서 받아온다 gene_data.append(parent.gene_data[i]) if i in switch_point: # 유전자를 받아오는 부모 변경 try : parent = parents[parents.index(parent) + 1 ] except IndexError: parent = parents[ 0 ] “” ” a = parents.index(parent) –> 현재 부모의 index 값 parents[a+1] –> 부모 리스트에서, 현재 부모 인덱스값보다 +1 된 값 가져옴 IndexError –> 만약 1이 넘어가면 parent = parents[0] 다시 0으로 돌아옴 ” “” Colored by Color Scripter cs 2점 교차는 두 점을 임의로 선택하여, 그 점을 기준으로 각 부모 유전자에서 번갈아 유전자를 받아오는 방법이다. 물론 점의 위치에 따라 부모1과 부모2의 유전 정보 비율은 달라질 수 있지만 교차의 경우 섞이는 복잡도를 정하는 단계이므로 신경쓰지 않는다. –> Mutation (돌연변이) 1 2 3 4 # 돌연변이 확률은 fitness 와 반비례 한다. # fitness 가 높을 수록, 돌연변이 확률이 적어진다. if rand( 0 , self.fitness * 100 ) = = 0 : return DNA([rand(min(WE_WANT), max(WE_WANT)) for i in range ( len (WE_WANT))]) cs 돌연변이 확률은 적합도와 반비례 하도록 구현했으며, 돌연변이는 기존 부모와 상관없는 전혀 새로운 유전자를 갖는다. 돌연변이는 그 확률 설정에 따라 다른 결과가 나온다. 자세한 내용은 아래 결과 분석에서 살펴보자. 결과분석 우선 목표값을 0 과 1로 이루어진 8자리 list 로 잡았다. 결과는 다음 이미지와 같다. X축이 세대, Y축이 적합도 수치를 나타낸다. [그림1] 목표 값 [0,1,0,1,0,1,0,1] 목표값이 단순한 관계로 얼마 지나지 않아, 40번째 세대 쯤에서 최대 적합도에 수렴하는 것을 볼 수 있다. 목표값을 조금 복잡하게 해보자. 0~9의 값을 가지도록 조정해봤다. [그림2] 목표 값 [3,1,2,9,7,4,3,6] 조금 더 흥미로운 결과가 나왔다. 목표 값의 범위를 늘리자 최대 적합도에 도달하는 세대가 늘어난 것이다. 위 1차 결과와는 달리 80 ~ 100 번째 세대에서 최대 적합도에 가까이 수렴하는 결과가 나왔다. 조금 더 복잡하게 해보자. 이번엔 목표 값의 길이를 바꿔볼 것이다. [그림3-1] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] 100 세대로는 최대 적합도에 도달하기에 한참 부족한 듯 싶다. 진화 횟수를 조금 늘려보았다. [그림3-2] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 비록 최대 적합도에는 도달하지 못했지만, 근사한 값을 얻었다. 그럼 보다 더 최대 적합도에 가까운 값을 얻기 위해서는 어떻게 해보는 것이 좋을까? 돌연변이의 확률을 늘리고, 세대에서 가장 좋은 유전자 (Fitness 수치가 가장 높은) 1개를 다음 세대에도 보존 시켜보았다. [그림3-3] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 최대 적합도에 도달하는데 성공했다!!! 하지만 필요 세대가 너무 많다는 문제점이 있다… 또한 돌연변이 확률을 늘렸더니 중간중간 생기는 뾰족한 부분 (내려오는 부분)이 늘어났다. 위 문제 를 조금 개선시켜보자. 우월한 유전자를 자식 세대에 포함시키는 과정에서, 1개가 아닌 5개를 포함시켜보았다. [그림3-4] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가 약 1100 – 850 = 250 세대가 감소했다!!~! 우월 유전자의 보존 비율 조금 더 늘려보자. 이번엔 5개 대신 10개를 포함시켜 보았다. 더욱 개선된 결과가 나오리라 생각했다. [그림3-5] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가 _ 10개 보존 예상과는 달리, 이전 결과 보다 더욱 못한 결과가 나왔다. 이유를 살펴보았더니, 우월 유전자의 보존 비율이 증가하면 우월 유전자에 가까운 자식 유전자들이 많이 생기지만, 우월 유전자의 잘못된 부분도 같이 유지되는 문제가 있었다. 우월 유전자의 보존 비율이 높다고 진화의 방향이 좋은 것은 아니라는 것이다. 이번 실험 결과 중, 우리의 실생활과 매우 흡사한 부분이 아닐까 싶다. 🙂 P.s 질문이나 기타 문제점은 GitHub 이슈로 달아주세요 풀리퀘 받는 것도 좋아합니다. 출처: https://blog.devkcr.org/entry/유전-알고리즘-가지고-놀기 [Blog4Study]
So you have finished reading the 유전 알고리즘 예제 topic article, if you find this article useful, please share it. Thank you very much. See more: 파이썬 유전 알고리즘 예제, 유전 알고리즘 활용 사례, 유전 알고리즘 파이썬, 파이썬 유전 알고리즘 라이브러리, 유전 알고리즘 딥러닝, 유전 알고리즘 게임, 유전 알고리즘 pdf, 마이크로 유전알고리즘
유전 알고리즘 예제 | 01-3 Dimensionality Reduction – Genetic Algorithm 모든 답변
We are using cookies to give you the best experience on our website.
You can find out more about which cookies we are using or switch them off in settings.
전역 최적화] 유전 알고리즘 (Genetic Algorithm)
1. 소개
유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 검색 방법이다. 유전 알고리즘은 이론적으로 전역 최적점을 찾을 수 있으며, 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있기 때문에 매우 유용하게 이용된다. 일반적으로 유전 알고리즘에 대해 알고리즘이라는 표현을 이용하지만, 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 최적화 문제를 풀기 위한 방법론에 가깝다. 즉, 모든 문제에 적용 가능한 하나의 알고리즘이나 소스 코드가 있는 것이 아니기 때문에 유전 알고리즘의 원리를 이해하고, 이를 자신이 원하는 문제에 적용할 수 있도록 하는 것이 중요하다. 유전 알고리즘을 정의하기 위해 아래와 같은 개념들을 정의한다.
염색체 (chromosome) : 생물학적으로는 유전 물질을 담고 있는 하나의 집합을 의미하며, 유전 알고리즘에는 하나의 해 (solution)를 표현한다. 어떠한 문제의 해를 염색체로 인코딩 (encoding)하는 것에 대한 예시는 [5. 예제] 항목에서 자세하게 서술한다.
유전자 (gene) : 염색체를 구성하는 요소로써, 하나의 유전 정보를 나타낸다. 어떠한 염색체가 [A B C]라면, 이 염색체에는 각각 A, B 그리고 C의 값을 갖는 3개의 gene이 존재한다.
자손 (offspring) : 특정 시간 $t$에 존재했던 염색체들로부터 생성된 염색체를 $t$에 존재했던 염색체들의 자손이라고 한다. 자손은 이전 세대와 비슷한 유전 정보를 갖는다.
적합도 (fitness) : 어떠한 염색체가 갖고 있는 고유값으로써, 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지를 나타낸다. 적합도에 대한 예시는 [5. 예제] 항목에서 자세하게 서술한다.
2. 알고리즘 구조
유전 알고리즘은 $t$에 존재하는 염색체들의 집합으로부터 적합도가 가장 좋은 염색체를 선택하고, 선택된 해의 방향으로 검색을 반복하면서 최적해를 찾아가는 구조로 동작한다. 유전 알고리즘의 동작을 단계별로 표현하면 아래와 같다.
1) 초기 염색체의 집합 생성
2) 초기 염색체들에 대한 적합도 계산
3) 현재 염색체들로부터 자손들을 생성
4) 생성된 자손들의 적합도 계산
5) 종료 조건 판별
6-1) 종료 조건이 거짓인 경우, (3)으로 이동하여 반복
6-2) 종료 조건이 참인 경우, 알고리즘을 종료
유전 알고리즘의 구조는 매우 간단하다. 그러나 (3)의 자손들을 생성하는 단계에서 알고리즘의 성능을 향상시키기 위한 몇가지 기법들이 적용되기 때문에 다음 항목에서 이러한 기법들에 설명한다.
3. 연산 정의
유전 알고리즘을 어떠한 문제에 적용하기 위해서는 총 5개의 아래와 같은 연산을 정의해야 한다.
초기 염색체를 생성하는 연산
적합도를 계산하는 연산
적합도를 기준으로 염색체를 선택하는 연산
선택된 염색체들로부터 자손을 생성하는 연산
돌연변이 (mutation) 연산
각각의 연산에 대해서는 아래에 자세히 설명한다. 그러나 아래의 설명은 유전 알고리즘에서 일반적으로 이용되는 하나의 예시일뿐이며, 필요에 따라서는 해결하고자 하는 문제에 맞는 연산으로 대체할 수 있다.
3.1. 초기 염색체 생성 연산
초기에는 이전 염색체가 존재하지 않기 때문에 선택된 염색체들로부터 자손을 생성할 수가 없다. 따라서, 초기 염색체를 생성하는 연산을 별도로 정의해야 한다. 유전 알고리즘에서 가장 많이 이용되는 방법은 어떠한 규칙도 없이 단순히 임의의 값으로 염색체를 생성하는 것이다. 예를 들어, 자바로 작성된 [코드 1]과 같은 소스 코드는 유전 알고리즘의 초기 염색체 생성 연산으로 이용될 수 있다.
1 2 3 4 5 6 Random rand = new Random (); int [] chromosome = new int [SIZE_CHROMOSOME]; for ( int i = 0 ; i < SIZE_CHROMOSOME; i + + ) { chromosome[i] = rand.nextInt(MAX_VAL_GENE); } Colored by Color Scripter cs [코드 1] 초기 염색체 생성 연산의 예시. [코드 1]에서는 어떠한 염색체에 단순히 [0, MAX_VAL_GENE) 사이의 값을 임의로 할당하고 있다. 3.2. 적합도를 계산하는 연산 염색체에 표현된 정보를 기반으로 적합도를 계산하는 연산이다. 이 연산은 해결하고자 하는 문제에 매우 종속적이므로, 다음의 [5. 예제]에서 자세하게 설명한다. 3.3. 적합도를 기준으로 염색체를 선택하는 연산 자손을 생성하기 위한 두 개의 부모 염색체를 선택할 때는 단순히 적합도가 가장 높은 두 개의 염색체를 선택할 수도 있다. 그러나 이러한 방법은 염색체의 다양성을 크게 훼손시키기 때문에 전역 최적해를 찾기에는 부적합하다. 이러한 문제점을 해결하기 위해 유전 알고리즘에서는 일반적으로 룰렛 휠 선택 (roulette wheel selection) 방법을 이용한다. 룰렛 휠 선택의 개념은 매우 간단하다. 어떠한 염색체를 아래의 [식 1]과 같이 정의된 \(P({Ch}_{i})\)를 바탕으로 확률적으로 선택하는 것이 룰렛 휠 선택이다. [식 1]에서 $N$은 염색체의 수이고, $f$는 염색체의 적합도를 구하는 함수이다. [식 1]로 표현되는 룰렛 휠 선택을 그림으로 표현하면 아래의 [그림 1]과 같다. [그림 1] 룰렛 휠 선택 (Roulette wheel selection)의 개념. 즉, 룰렛 휠 선택은 [식 1]을 이용하여 [그림 1]과 같은 룰렛을 만들고, 만들어진 룰렛을 이용하여 확률적으로 염색체를 선택하는 것이다. 룰렛 휠 선택을 이용하면, 적합도가 높은 염색체가 더 높은 확률로 선택되도록 설정하는 동시에 염색체들의 다양성도 유지할 수 있다. 3.4. 선택된 염색체들로부터 자손을 생성하는 연산 앞에서 설명한 룰렛 휠 선택 방법을 통해 선택된 두개의 부모 염색체들로부터 하나의 자손 염색체를 생성한다. 유전 알고리즘에서는 자손을 생성하는 연산으로 주로 crossover라는 연산을 이용한다. Crossover 연산을 그림으로 표현하면, 아래의 [그림 2]와 같다. [그림 2] Crossover 연산의 동작. Crossover 연산에서 염색체를 분할하는 지점인 division point는 임의로 선택된다. 3.5. 돌연변이 (mutation) 연산 만약, 앞에서 설명한 4-3, 4-4와 같은 연산을 이용해서 검색을 진행하면, 유전 알고리즘은 지역 최적점에 도달하게 될 것이다. 유전 알고리즘에서는 지역 최적점에 빠지는 문제를 해결하기 위해 새롭게 생성된 염색체에 확률적으로 돌연변이가 발생하도록 한다. 일반적으로 0.1%, 0.05% 등의 아주 낮은 확률로 돌연변이가 발생하도록 설정하며, 염색체에서 돌연변이를 발생시키는 연산은 매우 다양하다. 예를 들어, [그림 2]에서 생성된 자손에 대해 아래의 [그림 3]과 같은 두 개의 돌연변이 연산을 정의할 수 있다. [그림 3] 돌연변이 연산에 대한 두 가지 예시. [그림 3-a]는 임의로 하나의 유전자를 선택하여 0이면 1로, 1이면 0으로 값을 바꾸는 돌연변이 연산이다. [그림 3-b]는 두 개의 유전자를 임의로 선택하여 두 유전자의 값을 교환하는 돌연변이 연산이다. 돌연변이 연산에는 이외에도 많은 종류가 있으며, 해결하고자 하는 문제에 맞게 돌연변이 연산을 정의하면 된다. 4. 예제 - 유전 알고리즘과 TSP 이 항목에서는 유전 알고리즘을 이용하여 NP-hard에 속하는 대표적인 문제인 TSP (Travelling Salesman Problem)의 최적해를 구해 본다. TSP를 간단히 정의하면 아래와 같다. 출발점에서 시작하여 모든 노드를 단 한번만 지나 출발점으로 돌아오는 최단 경로를 구하는 문제 노드가 15개만 있다고 해도 TSP의 완벽한 답을 찾기 위해서는 $15!$에 해당하는 약 1조 3000천억개의 경우를 계산해야 한다. 따라서, 현실적으로 TSP의 정확한 답을 찾는 것은 불가능하다. 그러나 유전 알고리즘을 이용한다면, 정확한 답은 아니더라 도 거리가 일정 수준 이하인 최적의 답은 찾을 수 있다. 이 예제에서는 유전 알고리즘을 이용하여 도시의 수가 5개인 TSP의 최적해를 구할 것이다. 각 도시의 이름과 좌표는 아래와 같으며, 출발 도시는 A이다. A (10, 10) B (10, 5) C (14, 5) D (40, 50) E (1, 3) 도시의 좌표 정보를 바탕으로 아래의 [그림 4]와 같은 거리 정보 테이블을 구성할 수 있다. 거리 정보 테이블은 염색체의 적합도를 계산할 때 이용되므로, 메모리상에 보관하는 것이 좋다. [그림 4] 거리 정보 테이블. 그리고 예제의 TSP에 대한 염색체를 아래의 [그림 5]의 좌측과 같이 크기가 4인 배열의 형태로 인코딩할 수 있다 (염색체의 크기가 4라는 것은 유전자가 4개라는 것과 같다). [그림 5]의 우측은 어떠한 염색체 [E C D B]가 의미하는 TSP의 해를 나타낸다. 염색체 [E C D B]는 출발점 A에서 시작하여 E→C→D→B를 거쳐 다시 A로 돌아오는 경로를 의미한다. [그림 5] 예제 문제에 대한 염색체 인코딩 (encoding). 또한, 유전 알고리즘의 인자 (parameter)인 한 세대 당 염색체의 수 (population size)는 4로, 돌연변이 확률은 0.1%, 최대 반복 횟수는 1000, 허용 거리는 125으로 설정했다고 가정한다. 그리고 염색체의 적합도 함수는 아래의 [식 2]와 같이 정의한다. [식 2]에서 $N$은 염색체의 크기이고, $d(A, B)$는 두 도시 $A$와 $B$의 거리를 구하는 함수이다. [식 2]는 A에서 염색체에 나타난 첫 번째 도시로 이동할 때의 거리와 염색체에 나타난 순서대로 도시를 이동할 때의 거리, 그리고 염색체의 마지막에 나타난 도시에서 A로 이동할 때의 거리를 합하여 역수를 취하고 있다. 예를 들어, [그림 5]의 염색체에 대해서는 A→E, E→C, C→D, D→B, B→A, 총 5개의 이동에 대해 거리를 계산하여 합산한다. [식 2]에서 역수의 분자에 1000을 설정하고, 제곱을 하는 것은 어떠한 규칙이 아니라, 단순히 경험론적으로 설정한 것이다. 따라서, 실제 구현에서 [식 2]와 똑같이 적합도 함수를 정의할 필요는 없다. 위에서 설정한 알고리즘의 인자 및 적합도 함수와 염색체에 대해 [항목 3]에서 서술한 대로 유전 알고리즘을 동작하면 다음과 같다. 1) 초기 염색체의 집합 생성 초기 염색체 생성 연산에 의해 생성된 염색체들은 아래의 [그림 6]과 같다. [그림 6] 초기 염색체의 집합. 2) 초기 염색체들에 대한 적합도 계산 [그림 6]의 염색체들에 대한 적합도를 계산하면 아래의 [그림 7]과 같다. [그림 7] 초기 염색체들에 대한 적합도 계산. 3) 현재 염색체들로부터 자손들을 생성 룰렛 휠 선택 방법을 통해 염색체 [B C E D]와 [D E C B]가 선택되었다고 가정하면, crossover 연산을 통해 [그림 8]과 같은 자손이 생성된다. [그림 8] 두 염색체로부터 자손 생성. TSP에서는 도시를 한 번만 경유해야 하기 때문에 첫 번째 부모로부터 B C를 받은 경우, 두 번째 부모 염색체에서 C B를 그대로 가져오는 것이 아니라, 중복되지 않은 도시들을 순서대로 가져온다. 따라서, 자손은 [B C C B]가 아니라, [B C D E]가 된다. Crossover 연산을 통해 성공적으로 자손을 생성하였다면, 확률적으로 새롭게 생성된 자손에 돌연변이를 일으킨다. 유전 알고리즘의 인자를 설정하는 단계에서 돌연변이 확률을 0.1%로 설정하였기 때문에 0.1%의 확률로 새롭게 생성된 자손에 돌연변이가 발생한다. 만약, [그림 8]에서 생성된 자손에 0.1%의 확률로 돌연변이가 발생하였다고 가정하면, [그림 9]와 같은 과정을 통해 새롭게 생성된 자손이 변형된다. 돌연변이 연산은 두 유전자를 임의로 선택하여 교환하는 exchange로 하였다. 따라서, 최종적으로 생성된 자손은 [B E D C]가 된다. [그림 9] 돌연변이 연산. 한 세대 당 염색체의 수를 4로 설정하였기 때문에 [그림 8~9]와 같은 룰렛 휠 선택→crossover→돌연변이의 과정을 3번 더 반복한다. 4) 생성된 자손들의 적합도 계산 앞의 과정을 통해 생성된 4개의 자손에 대해 적합도를 계산하면, 아래의 [그림 10]과 같다. [그림 10] 새롭게 생성된 자손들에 대한 적합도 계산. 5) 종료 조건 판별 최대 반복 횟수가 1000이고, 적합도가 가장 큰 [C B E D] 염색체의 이동 거리는 약 130으로 목표값인 125보다 크기 때문에 종료 조건 판별 연산에서는 거짓이 반환된다. 6-1) 종료 조건이 거짓인 경우, (3)으로 이동하여 반복 종료 조건 판별 연산에서 거짓이 반환되었으므로, "(3) 현재 염색체들로부터 자손들을 생성"으로 돌아가 알고리즘을 반복한다. 참고문헌 [1] E. H. L. Aarts, A. H. Eiben, and K. M. Van Hee. 1989. A general theory of genetic algorithms, In Computing Science Notes,. Eindhoven University of Technology. [2] Sangit Chatterjee, Cecilia Carrera, Lucy A. Lynch. 1996. Genetic algorithms and traveling salesman problems. European Journal of Operational Research, Vol. 93, Issue 3, pp. 490-510. [3] Sadiq M. Sait and Habib Youssef. 2000. Iterative Computer Algorithms with Applications in Engineering. Published by the IEEE Computer Society, pp. 109-173.
유전 알고리즘(Genetic Algorithm) · Data Science
Follow me : |
Increscunt animi virescit volnere virtus by Friedrich Nietzsche
© 2021 Yngie. This work is liscensed under CC BY-NC 4.0.
This blog is forked from ratsgo’s blog
키워드에 대한 정보 유전 알고리즘 예제
다음은 Bing에서 유전 알고리즘 예제 주제에 대한 검색 결과입니다. 필요한 경우 더 읽을 수 있습니다.
이 기사는 인터넷의 다양한 출처에서 편집되었습니다. 이 기사가 유용했기를 바랍니다. 이 기사가 유용하다고 생각되면 공유하십시오. 매우 감사합니다!
사람들이 주제에 대해 자주 검색하는 키워드 유전 알고리즘으로 비밀번호를 뚫어보자 – Python
- 개발
- 인공지능
- 파이썬
- python
- ai
- 유전알고리즘
- geneticalgorithm
유전 #알고리즘으로 #비밀번호를 #뚫어보자 #- #Python
YouTube에서 유전 알고리즘 예제 주제의 다른 동영상 보기
주제에 대한 기사를 시청해 주셔서 감사합니다 유전 알고리즘으로 비밀번호를 뚫어보자 – Python | 유전 알고리즘 예제, 이 기사가 유용하다고 생각되면 공유하십시오, 매우 감사합니다.