유전 알고리즘(쉽게 배우는)(한빛 교재 시리즈 81)

유전 알고리즘의 기본 구성에 대한 체계적인 정리,

문제 공간에 대한 새로운 관점,

경쟁력 있는 실제 구현 예



진화의 원리를 문제 해결에 이용하는 유전 알고리즘은 컴퓨터, 물리, 화학, 생물, 전자, 기계, 조선, 원자핵, 경영, 재무회계, 음악, 미술 거의 모든 분야에서 어려운 문제를 해결하는 매력적인 대안의 하나로 자리잡았다. 이 책은 이런 유전 알고리즘을 이용해 문제를 해결하는 방법을 보고 싶은 사람들을 위한 책이다. 전형적인 알고리즘으로 잘 풀리지 않는 문제를 해결하는 방법을 알고자 하는 사람들에게도 도움이 된다.



부/장별 내용 요약



도입(1장~3장)

유전 알고리즘의 기본 구조와 구성요소, 문제의 해를 표현하는 방법을 알아보고, 교차?변이?선택?대치 등과 같은 유전 알고리즘의 대표 연산을 소개한다. 1장에서 3장까지를 이해하면 간단한 유전 알고리즘을 구현할 수 있다.



스키마와 문제 공간(4장)

유전 알고리즘의 작동 원리의 핵심인 스키마 이론과 유전 알고리즘이 탐색을 하는 대상인 문제 공간에 대해 알아본다.



확장된 주제들(5장)

보다 수준 있는 유전 알고리즘을 구현하기 위해 필요한 주제를 다룬다. 유전 알고리즘의 기본 틀로 만족스런 결과를 얻지 못했을 때 도움이 된다.



유전 알고리즘의 응용 예들(6장)

유전 알고리즘을 디자인하는 방법을 다양한 응용 예를 통해 알아본다. 문제를 표현하는 방법을 중심으로 설명한다.



유전 알고리즘의 구체적 예_그래프 이등분, TSP(7장~8장)

더 상세한 유전 알고리즘의 구현 예를 보고 싶어하는 독자들을 위하여 그래프 이등분 문제와 순회 세일즈맨 문제를 위한 경쟁력 있는 유전 알고리즘을 단계별로 자세히 다룬다.



다른 스토캐스틱 탐색 기법들(9장)

유전 프로그래밍, 진화 전략, 진화 프로그래밍과 같은 다른 진화 연산 기법을 설명한다. 그리고 다른 스토캐스틱 탐색 기법도 몇 가지 소개한다.

1장. 유전 알고리즘의 개괄

01_진화

02_유전 알고리즘의 약사

03_유전 알고리즘의 기본 용어들

04_유전 알고리즘의 전형적인 구조

05_표현

06_스키마

07_교차

08_변이

09 대치

10 어떤 문제를 유전 알고리즘으로 푸는가?

[알고리즘 1-1] 유전알고리즘의 전형적 구조

[Drift] 머레이 겔만



2장. 문제의 표현

01_해란 무엇인가?

02_이진수 표현 : k-진수 표현

03_그레이 코딩

04_실수 표현

05_가변 표현

06_위치 기반 표현 : 순서 기반 표현

07_일차원 표현 : 다차원 표현

08_유전자 재배치

09 트리 표현

[Drift] 존 홀랜드 54



3장. 유전 알고리즘의 연산들

01_선택 연산

02_교차 연산

03_변이 연산

04_대치 연산

[알고리즘 3-1] 룰렛휠 선택 알고리즘

[알고리즘 3-2] 토너먼튼 선택 알고리즘

[알고리즘 3-3] 토너먼튼 선택 알고리즘(일반형)

[Drift] 크리스토퍼 랭턴



4장. 스키마와 문제 공간

01_스키마 정리와 빌딩 블록 가설

02_스키마의 생존 확률

03_상위(Epistasis)

04_문제 공간의 모양

05_연산자와 문제 공간

06_왕도 함수(Royal-Road Function)

[Drift] 존 폰 노이만



5장. 확장된 주제들

01_염색체 표현의 위상학적 재분류

02_고급 정규화(Normalization)

03_복수 개의 목적 함수를 갖는 유전 알고리즘

04_미미틱 유전 알고리즘(혼합형 유전 알고리즘)

05_개체군집최적화(Particle Swarm Optimization)

06_병렬 유전 알고리즘

07_공진화

08_해집단의 다양성 유지

09 교차 연산들의 혼용과 시너지 효과

10 분류자 시스템(Classifier System)

11 에코 (Echo) 모델

[알고리즘 5-1] PSO 알고리즘

[Drift] 복잡성 과학



6장. 유전 알고리즘의 응용 예들

01_함수 최적화

02_시스템 최적화

03_조합적 최적화

[알고리즘 6-1] LBG 알고리즘



7장. 유전 알고리즘의 구체적 예(1): 그래프 분할

01_기본 사항

02_그래프 이등분을 위한 유전 알고리즘

03_전처리(Preprocessing)

04_실험 결과

05_결론

[알고리즘 7-1] Kernighan-Lin 알고리즘

[알고리즘 7-2] 전처리된 미미틱 유전 알고리즘



8장. 유전 알고리즘의 구체적 예(2): TSP

01_기본 사항

02_지역 최적화 알고리즘

03_TSP를 위한 미미틱 유전 알고리즘

04_부언

[알고리즘 8-1] TSP를 위한 LK 알고리즘

[알고리즘 8-2] 미미틱 유전 알고리즘



9장. 다른 스토캐스틱 탐색 기법들

01_진화 연산의 다른 방법들

02_시뮬레이티드 어닐링(Simulated Annealing, SA)

03_큰 스텝 마르코브 체인

04_타부 서치(Tabu Search)

[알고리즘 9-1] 시뮬레이티드 어닐링

[알고리즘 9-2] LSMC의 전형적 구조

[알고리즘 9-3] 타부 서치의 전형적 구조



Epilogue 맺음말

참고문헌

찾아보기

문병로 저자 문병로는 서울대학교 컴퓨터공학부 교수로 재직중이다. 서울대학교 계산통계학과, KAIST 전산학과, 펜실바니아 주립대에서 각각 학사, 석사, 박사 학위를 취득했다. 석사 취득 후 LG전자 중앙연구소 연구원, 박사 취득 후 UCLA VLSI CAD Lab 박사후 연구원, LG반도체 책임연구원을 거쳤다. 문제 해결 분야와 유전알고리즘의 이론 및 응용을 연구하는 "최적화연구실"을 운영하고 있다.



주 관심사는 어려운 문제들의 속성과 공간의 특성, 알고리즘의 설계/분석, 알고리즘의 기업적 응용, 유전 알고리즘과 생태계, 경제, 사회, 개인의 사고 체계 등에서 공통적으로 관찰되는 진화적, 창발적 특성에 관한 연구 등이다. 케임브리지 IBC의 『21세기의 탁월한 과학자』, 『Marquis Who's Who』 인명사전에 등재되었다.



저서로는 『IT CookBook, 쉽게 배우는 알고리즘』(한빛미디어, 2007), 공저로는 『전산학개론』(다성, 1999), 역서로 『Introduction to Algorithms』(한빛미디어, 2005)가 있다. 국제 저널과 학술대회에 120여 편의 논문을 발표했다.