Meta-heuristic(2)

선택연산

-교차에 쓰이는 두 개의 부모해를 고르기 위한 연산
-선택압을 이용하여 해의 선택 확률을 조절 할 수 있음
*선택압:우수한 해들과 열등한 해들 사이의 적합도 차이(높을 수록 exploit/낮을 수록 explore)
*적합도: 풀고자 하는 문제에 주어진 해가 적합한 정도->평가

품질 비례 룰렛휠 선택
-각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절함
-해집단 내의 i번째 해의 적합도 fi는 다음과 같이 계산됨
fi=(Cw-Ci)+(Cw-Cb)/(k-1),k>1
Cw:해집단 내에서 가장 나쁜 해의 비용
Cb:해집단 내에서 가장 좋은 해의 비용
Ci:해의 i의 비용
k를 높이면 선택압이 높아짐->우수한 해가 선택될 확률과 열등한 해가 선택될 확률의 차이가 커짐

-각 염색체는 룰렛휠 상에 자신의 적합도 만큼의 공간을 배정 받음
-대부분의 경우 해집단에서 가장 좋은 해와 나쁜 해의 품질의 차이가 굉장히 크기 때문에, k를 사용하지 않고 해의 품질을 그대로 적합도로 사용하면 나쁜 해들의 선택 기회가 박탈됨->엄청나게 큰 선택압을 주어 해의 다양성을 급속히 떨어트리는 결과를 초래함


토너먼트 선택
-편해서 가장 많이 사용
-두개의 염색체를 임의로 선택하여 0과 1 사이의 난수를 발생시켜서, 이 값이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고 그렇지 않으면 품질이 나쁜 것을 선택
-t는 파라미터화 할 수 있는 값으로, t 값이 높을 수록 선택압이 높아짐
-t가 0.5 근처이거나 이보다 작은 것은 비합리적임
-일반적으로는 2의k승개의 염색체를 선택한 다음 이들을 토너먼트 형식으로 걸러내어 마지막으로 남은 것을 선택하는 방법도 존재(k가 크면 선택압이 높아짐)

순위 기반 선택
-간격은 같게 해주겠다
-품질 비례 선택에서는 k값을 조정함으로써 좋은 품질과 나쁜 품질의 해들의 적합도 차이의 지나친 증가를 막을 수 있음/다만 해들의 적합도 분포는 조절할 수 없음
-순위 기반 선택은 해집단 내의 해들을 품질 순으로 '순위'를 매긴 다음 가장 좋은 해부터 일차 함수적으로 적합도를 배정함
-n개의 염색체 중 i번째 순위를 가진 염색체의 적합도는 다음과 같이 계산됨/
fi-max+(i-1)*(min-max)/(n-1)/이 식에서 max와 min의 값 차이를 바꿈으로써 선택압을 조절할 수 있음
-해들의 적합도는 max와 min 사이에서 균일한 간격으로 분포하게 됨

교차연산

-유전 알고리즘의 대표적인 연산이며, 연산 중 가장 다양한 대안이 존재함
-선택연산을 통해 선택된 두개의 해를 부분 결합하여 새로운 해를 만들어냄
-해의 표현은 교차 연산과 관계되어 있을 때만 의미가 있음
  -A라는 방법으로 해를 표현했는데 교차 연산에서 이름 바꾸어 사용한다면 염색체가 A라는 방법으로 표현되었다고 할 수 없음
-가장 대표적인 일점교차 가 있음(자르는 방법은 n-1개)

산술적 교차 연산
-거의 사용하지 않는다
-실수 염색체를 사용하는 경우에 사용할 수 있는 교차 연산
-염색체의 각 위치에 대해 두 부모 염색체의 두 유전자 값의 평균을 구해 자식해의 해당 위치로 배정함
-산술적 교차는 수의 '크기'라는 개념을 교차 연산에 사용한다는 점에서 매력있는 연산임
-하지만, 산술 평균을 지향하므로 매우 빠른 수렴을 보이는 경향이 있음->변이 등을 적절히 조절하여 설익은 수렴에 이르지 않도록 유의해야 함

TSP와 GA
chromosome 표현(1)
-위치 기반 표현: 유전자의 위치가 해당 유전자의 속성을 결정함
-순서 기반 표현: 인접한 유전자의 값들이 무엇인지 중요함

chromosome 표현(2)
-순서 기반 표현:이해하기 쉽고 밀접한 관계를 갖는 도시들이 염색체에 가까운 위치에 자리하여 교차 연산시 중요한 스키마의 생존 확률 증가
-위치 기반표현: 하나의 해는 단 하나의 염색체에 대응됨/위치i는 다음도시j의 다음 방문도시를 나타냄


싸이클 교차-TSP와 같이 염색체가 순열로 표현되는 경우 적용 가능한 교차 연산
-중복x/빠뜨리기x
-그림보기

순서교차
-싸이클 교차와 마찬가지로 염색체 순열로 표시되는 경우 사용될 수 있는 교차연산
-그림

PMX
-그림

변이연산

-부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산
-교차 연산이 만들어 놓은 자식해를 미소하게 변형하여 새로운 해를 만들어 내는 연산
-전형적인 변이 연산은 각각의 유전자에 대해[0,1) 범위의 난수를 생성하여 미리 정한 임의의 임계값 미만의 수가 나오면 해당 유전자를 임의로 변형시키고 그 이상의 수가 나오면 변형하지 않음
-전형적인 임계값으로 0.015, .0.01등이 있는데, 문제의 성격과 유전 알고리즘의 다른 연산들의 종류에 따라 변할 수 있음
-변이 연산은 임의로 일어나므로 변이는 절대적인 비율로 해의 품질을 저하시킴
-변이로 잘못만들어진 유전자는 시간이 흐르면서 사라지고 가끔 발생하는 성공적인 변이는 해집단의 품질을 향상시키는데 기여함
-변이의 확률을 높이면 다양한 해를 생성할 수 있으므로 유전 알고리즘의 역동성은 늘어나지만 해집단의 수렴성이 떨어져 알고리즘의 수행시간이 길어지고 개선 속도가 느려짐


전통적인 변이
-염색체를 2진수 형태로 바꾸어 변이를 수행
-변이 연산을 수행할 때는 염색체의 구조가 문제의 정의 혹은 제약을 위반하지 않는지 고려해야 함

cut mutataion
-염색체가 순열로 표시되는 경우 사용될 수 있는 변이 연산


inverse mutation
exchange mutation
scramble mutation(임의)

대치연산

-교차와 변이 연산으로 새로운 해를 반든 후에 이를 해집단 내의 어떤 해와 대치할지 결정하는 연산
-한 세대에서 만들어지는 해의 개수 k는 해집단에서 대치되는 해의 개수이기도 함-세대차:k/n

세대형 유전 알고리즘
-대다수 물갈이라 대치 연산에 큰 고민을 할 필요가 없음

안정 상태 유전 알고리즘
-세대차가 1/n에 가까운 유전 알고리즘, 새로운 해가 생기자마자 해집단에 넣어주는방식
-해집단을 빨리 수렴시키는 경향이 있는 대신 설익은 수렴의 가능성도 큼
-한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해와 대치되므로 대치될 대상을 고르는 것이 매우 중요함
방법(1)엘리티즘
방법(2)두 부모 해 중 품질이 나쁜 해와 대치하는 방법
방법(3)해집단 전체를 비교하여 자신과 가장 가까운 해를 대치하는 방법

뻐꾸기 번식

-Levy flight
해당 지점 주위에서 맴돌다가 일정 시간 이후에 멀리 떨어진 지점을 이동하는패턴이 반복됨
exploitation:짧은 이동
exploration:긴 이동

pso

-물고기나 새들이 군집을 지어 이동하는 패턴에서 착안된 메타유리스틱 알고리즘
-최초로 연구되었을 때는 사회적인 행동을 시뮬레이션 하기 위해 개발되었음
-유전알고리즘과 다르게 해의 표현이 연속적인 형태일때 적합함
-식-그림

-pso는 자신 교차가 없으니 대체가 없다

w:입자의 속도에 대한 가중치
c1:자신의 최고 위치에 대한 가중치
c2:집단의 최고 위치에 대한 가중치
r1,r2:0과1 사이의 난수
위치 업데이트 식:그림



w이 증가하면->움직임 활발함
c1이 감소하면 exploration이 감소->입자들이 수렴함
c2가 증가하면 exploitaion->개인 행동에 치중