X

유전 알고리즘 (Genetic Algorithm)

I. 기계학습과 진화 연산, 유전 알고리즘

가. 유전 알고리즘 개념

유전 알고리즘 절차 유전 알고리즘 개념
– 적자생존, 돌연변이 등 유전 원리에 따라 최적화형태로 진화 과정에서 해를 찾는 알고리즘
유전 알고리즘 특징
– 문제 해결 접근법
– 문제 상황과 관계 없음
– 적자생존 기반 알고리즘

나. 유전 알고리즘 구성요소

구성요소 핵심 기능 설명
자손 – 염색체 – 특정시간에 존재 염색체
염색체 – 집합, 해 – 유전 물질 집합, 해 표현
돌연변이 – 유전 정보 변경 – 교차연산 후 확률적 변경
유전자 – 유전 정보 – 염색체 하나의 유전 정보
적합도 – 표현 적합도 – 염색체가 보유한 고유값

 

II. 유전 알고리즘 흐름

가. 유전 알고리즘의 단계 별 작업

  • 유전 알고리즘은 t 에 존재하는 염색체 집합에서 최적 염색체 선택, 검색 반복 최적 해 탐색 구조

나. 유전 알고리즘 세부 절차

절차 연산 설명
① 초기 염색체 집합 생성 – 초기 염색체 생성 연산 – 초기 임의 값으로 생성
② 초기 염색체 적합도 계산 – 적합도 계산 연산 – TSP 최단 경로 연산
③ 현재 염색체 자손 생성 – 적합도 기준   염색체 선택 – 룰렛 휠 선택방법 이용 염색체 선택
– 선택 염색체   자손 생성 – 염색체 생성/분할 지점
④ 생성된 자손   적합도 계산 – 돌연변이   연산 – 확률적 돌연변이 생성
– 낮은 확률로 발생
– 생성 자손   적합도 계산 – 생성된 염색체 반복 적합도 재계산
⑤ 종료 조건   판별 – 거짓 또는   참 결과확인 – 거짓의 경우 ③번으로   이동하여 반복
  • 적합도 기준 염색체 선택 시 룰렛 휠 선택 방법 이용

 

III. 유전 알고리즘의 룰렛 휠 선택의 역할

가. 룰렛 휠 선택 (Roulette Wheel Selection)

  • 적합도가 높을수록 부모 해로 선택 확률 높아지도록 하는 방식

– 적합도가 100인 C는 선택 확률 높음
– 적합도가 40인 D는 선택 확률 낮음

– 우월한 유전자를 가질수록 부모 해로 선택될 확률 상승하는 기법을 “룰렛 휠 선택”

나. 룰렛 휠 선택 역할

– 개체 적응도에 비례하여 선택 비율 변경하도록 K값 조절하여 선택압 조절 가능
– 최소치 구하는 문제에 사용하기 어렵고, 개체 간 적응도 격차가 심한 경우 초기 수속 원인
– 실제 적응도를 스케일한 값으로 이용

– 룰렛 휠 선택 외 지정한 수만큼 랜덤한 개체 선택, 적응도 높은 개체 선택하는 토너먼트선택 기법 존재

 

IV. 유전 알고리즘 활용 사례

구분 활용 사례 설명
학습
활용
최적화 – 수치최적화, 조합최적화
– 다양한 최적화 문제 사용
기계 학습 – 분류와 예측과제 등 사용
– 신경망 가중치, 지도/비지도
진화와 학습 – 개체 학습과 종의 진화
– 어떤 영향 주는지 연구
산업
활용
자동 프로그래밍 – 특정 문제 대한 컴퓨터 프로그램 진화
경제학 – 기술혁신, 입찰전략 발전
– 경제 시장 발현 과정 모델
면역체계 – 면역 및 진화 동안 다유전인자들의 발견 면역체계 모델

– 이 외 인공지능 인력 육성과 소셜 로봇 학습 위한 빅데이터 접근성 개선 기반 시장 선도 가능

Categories: 알고리즘/AI
도리: