유전알고리즘 시험 내용 요약

Chapter 1.

1. 유전 알고리즘의 기본 용어

• 유전 알고리즘의 기본 구조 : 개체들은 교차에 의해 염색체를 부분 결합하고 돌연변이에 의해 조금씩 변화된 새로운 염색체를 가진 새로운 개체를 만들어 내는데, 이 때 개체는 환경에 적응하기 유리한 정도에 따라 선택적으로 번성하게 됨. 유전 알고리즘은 이러한 생물의 진화 과정을 문제 해결 과정으로 옮긴 것.
• 염색체(chromosome) : 임의의 해를 유전 알고리즘이 이해하는 형태로 표현한 것
• 해집단(population) : 정해진 수의 염색체 집단.
• 유전자(gene) : 해를 구성하는 인자
• 유전자형(genotype) : 보이는 그대로의 유전자 조합. 염색체 그 자체.
• 표현형(phenotype) : 유전자형과 관계되어 관찰되는 형질. 해의 성질이나 품질

 

2. 유전 알고리즘의 전형적인 구조

n개의 초기 염색체 생성

repeat{

    for i = 1 to k{

        두 염색체 p1, p2 선택;

        offspring_i = crossover(p_1, p_2);

        offspring_i = mutation(offspring_i);

    }

    offspring_1, ..., offspring_k를 population내의 k개의 염색체와 대치;

}until(정지 조건 만족);

남은 염색체 중 최상의 염색체를 return;

먼저 n개의 초기 염색체(해)를 임의로 생성. 생성한 해집단으로부터 k개의 새로운 해를 만들어낼 때, 선택(selection), 교차(crossover), 변이(mutation)의 단계를 거침. 이렇게 만든 k개의 해는 해집단 내의 k개의 해와 대치됨. 

이 과정을 정해진 조건을 만족할 때까지 반복 후 가장 좋은 염색체를 반환함.

• 세대 차(generation gap) : k / n, 상수 k는 해집단이 한번에 얼마나 많이 대치될 지를 결정함.
• 세대형 유전 알고리즘(generational GA) : 세대 차가 1에 가까워, 절대 다수의 해가 대치되는 경우
• 안정 상태 유전 알고리즘(steady-state GA) : 새로운 해가 생기자마자 해집단에 넣어주는 방식.
• 안전 상태 유전 알고리즘이 해집단을 빨리 수렴, 하지만 설익은 수렴(premature convergence)의 가능성 큼.
• 선택(selection) : 교차를 위해 임의의 해를 선택하는 연산. -> 선택된 임의의 해 : 부모 해(parent)
• 교차(crossover) : 두 개의 부모 해로부터 자식 해(offspring)을 만드는 연산.
• 변이(mutation) : 해를 임의로 변형시키는 연산
• 정지하기 위한 조건
• repeat-until 루프를 일정 횟수만큼 수행 후 정지.
• 해집단에 있는 해들의 다양성이 어느 정도 이하로 떨어질 때 정지.

 

3. 표현

• 가장 전형적으로 사용되는 표현 방법은 “이진 스트링”모양의 염색체로 표현하기
• 16진수로 표현하기

 

4. 스키마

• 스키마(schema) : 염색체에 깃들어 있는 부분 패턴. ex) 00**00****
• 무관 기호(don’t care symbol) : 스키마에서 * 로 표시된 기호.
• 특정 기호(specific symbol) : 스키마에서 * 가 아닌 기호
• 작은 스키마로 시작 -> 큰 스키마를 이루는 과정
• 작은 스키마에서는 존재하지 않던 특징이 큰 스키마에서 창발(emergent)하는게 유전 알고리즘의 핵심.
• 유전 알고리즘이 종료된 후 리턴되는 염색체는 하나의 거대한 스키마.

 

5. 교차

• 두 해의 특징을 부분 결함해 하나의 새로운 해를 만들어 내는 연산.
• 먼저 문제의 표현 방법이 결정되어야 함.

        

6. 변이

• 부모 해에 없는 속성을 자식해에 도입하는 역할을 함.
• 알고리즘
• 가장 왼쪽 유전자부터 각가에 대해 [0, 1) 범위의 난수 생성.
• 미리 정한 임계값, 예를 들어 0.015 미만의 수가 나오면 유전자를 변형시킴.
• 임계값 보다 큰 값이면 유전자를 변형하지 않음.

                

• 변이의 확률을 높임 : 다양한 해를 생성할 수 있어 역동성은 늘지만, 해집단의 수렴성이 떨어져 수행시간이 길어지고 개선의 속도가 느려짐.
• 유전 알고리즘에서는 대부분의 변이가 해의 품질에 영향을 미침.

 

7. 대치

• 해집단에서 가장 우수한 해는 남겨두고, 나머지만 대치함.
• 가장 품질이 낮은 해만 대치하기도 함 -> 수렴을 빠르게 하지만, 해집단이 충분한 탐색 과정을 거치지 못하고 설익은 수렴을 할 가능성이 큼.
• 대치 연산을 선택할 때 중요한 점은 해집단의 다양성을 합리적으로 유지시닐 수 있는 연산을 선택해야 함.
• 교차, 변이 연산화 연관되어서 결정되어야 함.
• 교차/변이 연산 쌍이 부모해를 많이 변형시키면(perturbation이 강하면) 수렴성이 강한 대치 연산을 사용해보자.
• 변형이 작으면 해집단의 다양성을 지속시킬 수 있게 대치 연산을 사용.

 

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

• 세일즈맨 문제
• NP-hard 문제

 

 

Chapter2. 문제의 표현

1. 해란 무엇인가?

• 유전 알고리즘 : 품질이 가장 좋은 해를 찾기 위한 방법.

 

2. 이진수 표현 : k-진수 표현

• 이진수 표현 : 교차시에 자름선을 둘 수 있는 위치가 보다 많아져 추가적인 변이의 효과가 발생.
• k-진수 표현 : 한 번 정의된 k-진수 수는 나눌 수 없고, 단위로 움직이게 됨. (분리될 수 없음)
• k-진수 표현에서도 이진수처럼 나눌 수 있게 코딩하면 됨. 누가 우위에 있느냐는 큰 의미 없음.

 

3. 그레이 코딩

• 인접한 수는 단 한 비트만 차이가 나도록 만든 이진수 코딩 체계.

            

• 의미상으로 유사한 두 해가 문제 공간에서 가까이 위치하도록 함. -> 비트를 변화시킬 때 급격한 변화를 막음.
• 항상 한 비트의 차이가 모두 인접한 건 아님. ex) 1001에서 맨 앞의 1의 변화 하면 그레이코딩에서 변화가 크다.

 

4. 실수 표현

• 실수 하나를 한 유전자로 정의.
• C언어에서 float타입이나 double 타입 변수 하나를 한 유전자에 할당.
• 장점 : 인자와 유전자가 일대일 대응, 수의 “크기” 개념을 연산에 담을 수 있음.

 

5. 가변 표현

• 표현 방법을 미리 고정하지 않고 유전 알고리즘 수행 중에 표현 방식이 변함.
• 역치 연산

        

 

• fghi 구간의 유전자 위치가 역순으로 바뀜.
• 유전자 e와 i가 밀접한 관계를 가짐 -> 교차를 통해 생존하기 쉬움.
• 반면에 유전자 e와 f가 밀접한 관계였다면 -> 나쁜 패턴으로 변함.
• 메시 유전 알고리즘
• 염색체의 길이가 변하면서 발현하지 않는 잠재적 유전자를 가짐.
• (위치, 속성) 쌍으로 나열.
• 한 위치에 대해 두 개 이상의 유전자가 나타날 수도 있고, 어떤 위치에 대해서는 유전자가 없을 수도 있음.
• ex) 1 0 * 0 -> ( 1, 1), (2, 0),(2, 1),  (4, 0) , (1, 0)
• 과잉 표현(overspecification) : 위치 1과 위치 2처럼 하나의 위치에 두 개의 유전자가 있음.
• 결손 표현(underspecification) : 위치 3처럼 특정 위치에 유전자가 없는 경우.
• 과잉 표현은 맨 앞에 나타난 것만 의미를 가지고 나머지를 무시함.
• 결손 표현이 있으면 임의의 값을 채워서 품질을 평가하는데 사용함. -> 대표성을 갖기 어려움 -> 지역 최적해로 채워넣자.( 임의의 값으로 채운 뒤, 한 비트씩 변화시켜서 개선시킬 수 있는 한계까지 개선)

 

6. 위치 기반 표현 : 순서 기반 표현

• 위치 기반 표현
• 함수 최적화 문제의 한 염색체에서 15번째 유전자는 15번째 변수의 값을 나타냄
• 그래프 문제의 염색체에서 28번째 유잔자는 28번 노드의 속성을 나타냄.
• 순서 기반 표현
• 유전자 위치는 별 의미 없고 유전자 값들의 상대적 순서가 의미를 가짐.
• 이해하기 쉽고 밀접한 관계를 갖는 도시들이 염색체 상에서 비교적 가까운 위치에 자리해 이로 인해 교차 연산시 중요한 스키마의 생존 확률을 높일 가능성이 많음.

 

7. 일차원 표현 : 다차원 표현

• 이차원에서 일차원으로 배열했을 때, 원래 그래프에 존재하는 노드의 인접 관계가 손상됨.

 

8. 유전자 재배치

 

 

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

1. 선택 연산

• 교차에 쓰일 두 개의 부모해를 고르기 위한 연산.
• 원칙 : 우수한 해가 선택될 확률이 높아야 함.
• 선택압(selection pressure) : 우수한 해들과 열등한 해들 사이의 적합도 차이, 하이퍼 파라미터
• 선택압이 높음 -> 수렴은 빠르나 설익은 수렴(premature convergence)의 가능성이 높음
• 선택압이 낮음 -> 해집단의 평균 품질이 좋아지지 않을 가능성이 많음.
• 품질 비례 룰렛휠 선택
• 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절

        

• C_w : 해집단 내에서 가장 나쁜 해의 비용
• C_b : 해집단 내에서 가장 좋은 해의 비용
• C_i : 해 i의 비용
• k값을 높이면 선택앞이 높아짐. 우수한 해가 선택될 확률과 열등한 해가 선택될 확률이 더 차이가 남. 보통 k는 3~4를 사용.

                        

 

point = random(0, SumOfFitness);

sum = 0;

for i = 0 to n-1 {

    sum = sum + f_i;

    if (point < sum ) return i

}

• k를 사용해서 적합도를 조정하지 않고, 주어진 문제에서의 해의 품질을 그대로 적합도로 사용하면 안됨.
• 이렇게 하면 대부분 해집단에서 가장 좋은해와 가장 나쁜 해의 품질이 너무 차이가 나서, 나쁜 해들은 거의 선택될 기회를 잃음. -> 해의 다양성이 급격하게 떨어짐.

 

• 토너먼트 선택
• 두 개의 염색체를 임의로 선택해 [0, 1) 범위의 난수를 발생시킨 다음, 이것이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고 그렇지 않으면 품질이 나쁜 것을 선택.

두 염색체 x1, x2를 선택.( x1의 품질이 더 좋다고 가정 )

r = [0, 1)

if (t > r ) then select x1;

            else select x2;

• t는 하이퍼 파라미터로, t가 높을수록 선택압이 높아짐.
• t가 0.5이거나 그보다 작을 경우 비합리적.

 

• 순위 기반 선택
• 해집단 내의 해들을 품질 순으로 “순위”를 매긴 다음 가장 좋은 해부터 일차 함수적으로 적합도를 배정함.

                        

• max와 min 값의 차이를 바꿈으로써 선택압을 조절할 수 있음. 해들의 적합도는 max와 min 사이에서 균일한 간격으로 분포.

                        

 

• 공유
• 해집단의 다양성을 보다 오래 유지하고자 하는 목적에서 고안.
• 품질 비례 선택이나 순위 기반 선택에서 쓰는 적합도 값을 구함.
• 해당 염색체가 해집단 내의 나머지 염색체들과 유사한(특징을 “공유”) 정도가 높을수록 큰 값으로 나누어 적합도를 조정함.

                        

• F_i : 공유를 고려한 염색체 i의 적합도
• f_i : 일반 적합도
• s( ) : 공유 함수
• d_i, j : 염색체 i와 염색체 j의 차이
• 공유 함수 s( )는 두 염색체의 차이가 적을수록 큰 값을 가져야 함. 공유 함수는 전형적으로 일차 함수로 나타남. 이차함수로 (

  

  ) 정의하면 염색체 간 유사성에 불이익을 많이 줌.

                      

    

• 해집단 내의 해들을 문제 공간 상에서 지리적으로 분산되게 도와주는 효과가 있음.
• 유전자형 공유 : 염색체의 모양 그 자체가 다른 정도를 사용.(해밍 거리)
• 표현형 공유 : 표현형의 차이를 계산.

 

2. 교차 연산

• 일차원 교차 연산
• n인 일차원 문자열로 된 염색체 상에서 일점 교차로 자르는 방법의 수는 n-1가지임.

                        

        

• 다점 교차
• 염색체의 길이가 n일 때, k점 교차로 자르는 방법의 총 수 :

  

• 맨 오른쪽에도 자름선이 올 수 있도록 하면 자르는 방법의 총 수는

  

• 넓은 탐색 공간을 가지지만, 교란이 강하면 수렴성이 떨어져 주어진 시간 내에 수렴하지 않을 가능성이 큼.
• 교란이 강함 -> 스키마가 파괴됨. 하지만 새로운 스키마의 생성을 다양하게 할 수 있음.
• 미미틱 알고리즘 : 지역 최적화 알고리즘 + 유전 알고리즘
• 스키마의 파손 확률은 잚선의 개수에 영향을 많이 받음.
• 일점 교차는 스키마의 길이가 결정적인 영향을 미치고, 다점 교차는 이의 영향을 덜 받음.
• 균등 교차
• 자름선을 이용하지 않음.
• 임계 확률 P_0을 정함.

• 일점 교차나 다점 교차에 비해 스키마의 결합 형태가 다양하고 스키마 내의 특정 기호의 위치가 영향을 미치지 않음.
• 교란의 정도가 커서 수렴 시간이 오래 걸림.

 

• 싸이클 교차

            

            

            

 

• 순서 교차
• 염색체가 순열로 표시되는 경우를 위해 고안됨.

              

 

• PMX
• 염색체가 순열로 표시되는 경우를 위하여 고안됨.

                

• 산술적 교차
• 실수 염색체를 사용하는 경우에 사용할 수 있음.
• 두 부모 염색체의 두 유전자 값에 대한 평균을 자식해로 배정.

                

• 평균을 지향하므로 빠른 수렴. 설익은 수렴이 되지 않도록 조심.
• 간선 재조합
• TSP를 위해 개발됨.
• 두 부모해를 분석, 각도시에 연결된 인접 도시 목록을 만듬.
• 한 도시는 최대 4개까지의 인접 도시를 가질 수 있고, 최소 2개는 가짐.

                

 

3. 변이 연산

• 전형적 변이
• 부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산
• 각각 유전자에 대해 [0, 1) 범위의 난수를 생성해 미리 정한 임의의 임계값 미만의 수가 나오면 해당 유전자를 임의로 변형시키고 그 이상의 수가 나오면 그냥 둠.
• 비균등 변이
• 변이의 강도를 점점 줄여나가는 연산.

 

4. 대치 연산

• 해집단 내에서 품질이 낮은 해를 대치. 강한 수렴성을 가지고 설익은 수렴하지 않도록 조심.
• 엘리티즘(elitism) : 해집단 내에서 가장 우수한 해는 대치되어 없어지지 않도록 함.
•  

 

Chapter4. 스키마와 문제 공간

1. 스키마 정리와 빌딩 블록 가설

• 스키마 : 염색체들에 포함되어 있는 패턴
• 초기의 작은 스키마 -> 큰 스키마로 확장
• 스키마 차수 : 스키마에 포함된 특정 기호들의 총 수
• 스키마 정리(Schema theory) : 일점 교차를 사용하는 유전 알고리즘에서 스키마의 생존에 스키마의 길이와 품질이 큰 영향을 미침
• 유전 알고리즘의 세대 t+1에서의 임의의 스키마 H를 포함하는 염색체의 개수의 기대치

                    

• 

  는 염색체에서 자름선이 놓일 수 있는 모든 경우에 대한 스키마 길이의 비율, 스키마가 파손될 확률
• 자름선이 스키마 내부에 놓여도, 상대 부모해가 똑같은 특정 기호를 갖고 있다면, 스키마는 파손되지 않음
• 스키마 정리는 스키마의 생존 가능성에 대한 하한을 제시.
• 내재적 동시성(implicit parallelism) : 해집단의 해들의 품질을 평가함으로써 그 속에 깃든 훨씬 많은 수의 스키마의 품질을 동시에 평가하게 되는 유전 알고리즘의 성질.
• 빌딩 블록 가설
• 유전 알고리즘의 동작 원리는 작은(저차원의) 스키마들의 병렬 배치(juxtaposition)에 의해 점점 더 큰(고차수의) 스키마로 발전하는 과정
• 일점 교차 : 길이가 짧은 고품질의 스키마들이 빌딩 블록 역할을 함.
• 왕도 함수(royal-road function) : 스키마의 결합과 발달 과정을 관찰하기 위해, 개별 스키마들의 품질을 미리 정의하고 이와 함께 발달 과정을 미리 알 수 있는 함수
• 스키마가 만드는 공간
• 스키마를 초평면(hyperplane)이라 함.
• 스키마가 다차원 문제 공간에서 항상 특정 영역과 대응되기 때문.
• 유전자의 위치가 바뀌면 문제 공간에서의 적합도 지형(fitness landscape)이 달라짐.
• 해의 품질 평가는 평균으로 우위를 매김.

 

2. 스키마의 생존 확률

• 모든 특정 기호들 사이에 짝수 개의 자름선이 존재하면(0인 경우 포함), 스키마는 생존.
• 자름선일 짝수 개일 경우, 스키마의 길이가 길더라도 홀수개에 비해 생존 확률이 높음.
• 홀수 개의 자름선을 사용할 경우, 모든 특정 기호 사이에 짝수 개씩의 자름선을 놓고 나면 특정 기호대의 바깥에 반드시 하나 이상의 자름선이 놓여야 하기 때문.
• 균등 교차와 관계된 생존 확률은 오직 스키마의 차수만이 상관 있고, 스키마의 모양과는 무관함.
• 스키마의 생존이 다는 아니다
• 고품질의 스키마를 미리 파악하는게 쉽지 않음.
• 교차 연산 : 채굴(exploitation)이 강하면, 탐험(ㄷxploration)의 경향의 트레이드오프.

 

3. 상위 ( x )

• 상위 : 유전자 또는 인자들의 상호 관계를 총칭하는 말
• 상위가 작음 : 유전자들이 “비교적” 독립적 -> 문제 공간의 적합도 지형은 단순해지고 문제는 쉬워짐
• 상위가 높은 문제를 낮은 문제로 변환해 풀고자 함.
•  

 

4. 문제 공간의 모양

• 적합도-거리 상관관계
• 적합도-거리 상관관계 : 문제 공간 상에서 해의 품질과 전역 최적해(global optimum)와의 거리간의 상관 관계를 나타냄
• 적합도-거리 상관관계로 문제의 난이도를 예측하고자 함.
• 임의의 해집합

  

  에 대해

  

  을 각 해의 적합도

• 

  을 가장 가까운 전역 최적해와의 거리라 가정.( 여러 개의 전역해가 있을 수 있음)
• 상관계수(correlation coefficient)

                        

,

• 상관 계수가 0.15 이상이면 공간 탐색을 호도하는 문제(misleading problem), -0.15보다 작으면 쉬운 문제(straight forward problems),
• -0.15부터 0.15 사이의 문제는 어려운 문제로 가정함.
• 상관 거리
• 임의의 연산을 통해 만들어지는 해들의 시계열적인 성격을 분석해 문제 공간이 해당 연산에 대해 얼마나 오랫동안 상관성을 유지하는지 알아봄.
• 큰 계곡
• 상당한 수의 서로 다른 지역 최적해들을 모은 다음, 각각의 해에 대해서 1) 나머지 해들과의 거리의 평균 2) 이 지역 최적해들 중 가장 좋은 해와의 거리를 계산해봄.
• 각 해의 품질과의 관계를 그려봄
• 비용이 낮을 수록(품질이 좋을수록) 다른 해들과의 평균 거리가 짧고, 가장 좋은 해와의 거리도 짧음.
• 결론 : 문제 공간은 최상의 해를 중심으로 “큰 계곡(big valley)”을 이루고 있음을 시사.
• 문제 공간 종앙 부근의 매력
• 많은 수의 서로 다른 지역 최적해들을 수집한 다음 이들의 유클리드 공간 상의 중점을 단순 계산으로 구해 품질일 알아봄
• 중점해 : 지역 최적해들의 유클리드 공간 중심점의 품질
• 지역 최적해의 군집도
• 끌개의 수, 분포, 밀도
• 끌개(attractor) : 지역 최적해
• 임의의 해로부터 이동하는 행위를 반복하면 궁극적으로 더 올라갈 수 없는 해를 의미함.
• 끌개의 크기 : 궁극적으로 해당 끌개에 이르게 되는 해들의 총 수

 

5. 연산자와 문제 공간

• 연산자가 문제 공간에 미치는 영향
• 문제 공간은 연산자에 따라 결정됨
• 2-change
• Or-change
• swap-change
• 2-change연산이 끌개 수를 가장 적게 생성, swap-change는 끌개 수를 가장 많이 생성
• 끌개 수가 많음 -> 공간이 구불구불해 탐색이 힘듬.
• 끌개의 개수 추정하기
•  

 

 

 

Chapter 5. 확장된 주제들

1. 염색체 표현의 위상학적 재분류

• 일차원 배열
• 이차원 배열
• 삼차원 배열
• 순환형 배열
• 일차원 실수 공간
• 이차원 실수 공간
• 완전 그래프

2. 고급 정규화

• 한 개의 해를 표현하기 위한 염색체가 여러 개인 경우, 하나의 표현형에 여러 개의 유전자형이 대응되는 경우 교차 연산에 초래하는 혼란을 줄일 수 있는 기법
• 문제 공간의 크기를 줄여주는 함수 효과가 있음
• 그래프 분할, 정렬 네트워크 최적화, 신경망 최적화, 지수귀문도 최적화 등이 정규화의 필요성이 확인된 주제들
• 그래프 분할
• 그래프 이등분 문제 : 임의의 그래프를 같은 수의 노드를 갖는 두 부분 집합으로 분리하되 두 부분 집합을 연결하는 간선의 개수, 교차 간선의 수를 최소화하는 분리 방법을 찾는 문제
• 0100111001과 1111000100은 전체 10비트 중 8비트가 다름. 하나를 0과 1로 바꿔(정규화) 수행하면 부모해의 특징을 훨씬 잘 반영함.
• 정렬 네트워크
• 신경망
• 신경망의 히든 레이어는 모두 동일한 위상학적 성질을 가지고 있음.
• 히든 레이어에서 제일 왼쪽에 있는 노드나, 제일 오른쪽에 있는 노드나 같음.
• 그런데 어떻게 번호를 매기느냐에 따라 유전자형이 다름.
• 두 부모해의 교차 전에 신경망 표현의 다양성을 고려하여 한 부모해를 같은 의미를 유지하면서 다른 부모해와 최대한 유사한 모양으로 변환, 정규화를 통해 연산의 혼란을 덜어줌.

 

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

• 모든 목적 함수에 대해 최적인 해는 근본적으로 존재하지 않는 경우가 많음.
• 열성해(dominated solution)과 비열성해(non-dominated solution)
• 목적함수 k개가 있고, 임의의 해 x가 있을 때,

  

  에 대해

  

  이고, 적어도 하나의 목적함수

  

  에 대해

  

  인 해 y가 존재하면
• x를 열성해라 부름
• 이러한 해 y가 존재하지 않으면, x를 비열성해 또는 파레토 최적해(Pareto-optimal solution)이라 함.

 

4. 미미틱 유전 알고리즘(혼합형 유전 알고리즘)

• 미미틱 유전 알고리즘, 혼합형 유전 알고리즘 : 교차와 변이로 만들어진 해에 지역 최적화 알고리즘을 사용.
• 교차와 변이는 해를 지역 최적점 근처에 갖다 놓는 역할을 하고, 지역 최적화 알고리즘은 해를 지역 최적점으로 안내함.
• 지역 최적화 알고리즘이 유전 알고리즘의 지역 최적점 근처에서의 미세 조정을 도와줌.
• 유전 알고리즘이 지역 최적화 알고리즘을 위한 다양한 초기해를 제공.
• 라마르크형(Lamarckian) : 염색체에 지역 최적화 알고리즘을 적용한 다음 연색체를 덮어씀.(지역 최적화의 결과로 염색체가 바뀜)
• 볼드윈형(Baldwinian) : 지역 최적화 알고리즘을 적용은 하되 염색체는 그대로 둠. 지역 최적화로 나온 해는 염색체의 적합도 평가를 위해서 참조만 함.
• 고전 순수 유전 알고리즘과 다른점
• 더 강한 교란을 허용
• 순수 유전 알고리즘은 부모해의 특징을 최대한 유지하려함. 미미틱 알고리즘은 너무 미약한 교란은 자식해를 부모해 중의 하나로 복원시켜버리므로 후반부에 공간 탐색 능력을 현저히 떨어뜨릴 수 있음.
• 후반부에 변이를 높여주는게 좋을 것 같음.
• 대부분 지역 최적화 알고리즘에서 시간을 많이 씀. 해집단의 수렴성은 순수 유전 알고리즘보다 훨씬 강함.
• 순수 유전 알고리즘과 비교해 시행착오가 감소하므로 해집단의 크기를 작게해서 사용하는게 일반적.

 

5. 개체군집최적화

• 개체들을 군집으로 관리하면서 이들이 상호간의 관계 네트워크를 통해 진화를 하도록 하는 방식
• 복수의 군집(swarm)을 가지고 운영. 현재 운영 중인 모든 개체 중 가장 좋은 개체와 “이웃”의 범주에 드는 개체와만 교류함.

1. 병렬 유전 알고리즘