선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 유전자알고리즘의 조숙수렴현상을 완화하여 유전자알고리즘의 성능을 향상시키는 선택적 돌연변이 방법을 제안하였다. 선택적 돌연변이는 기존의 돌연변이에 추가하여 실행되는 것으로 좋은 개체는 해당 개체 주변을 탐색하게하고 나쁜 개체는 먼 곳을 탐색하게 함으로서 조숙수렴현상을 쉽게 벗어나면서도 전역 최적해에 접근하게 한다.
- 본 논문에서는 조숙수렴 정도나 다양성지수를 계산할 필요나 새로운 파라미터를 경험적으로 선택할 필요가 없고 적합도나 인코딩 방법에 상대적으로 의존성이 적은 단순하면서도 강력한 새로운 방법을 제안한다. 본 논문에서 제안하는 방법은 개체의 적합도를 이용하여 등급을 매기고 등급에 따라서 염색체에 특정한 부위에 추가적으로 선택적 돌연변이를 수행하는 방법으로 개체의 다양성을 확장시킨다.
제안 방법
- 좋은 개체들은 하위비트 영역을 선택적으로 돌연변이 하게하고 나쁜 개체들은 상위비트 영역을 선택적 돌연변이 하게 하였다. 4개의 함수최적화 문제에 적용하여 알고리즘의 성능을 측정하였다. 실험결과 선택적 돌연변이를 추가한 유전자알고리즘의 성능이 기존의 방법보다 최대 3배까지 좋아짐을 관찰할 수 있었다.
- 다양성을 사용한 방법에서 다양성을 측정하는데 사용하는 미리 정의된 문턱치 D는 개체수의 1/3을 사용했다. 다양성을 사용한 방법에서는 돌연변이 확률 이외에 교배확률도 조정하였지만 세 방법의 공정한 비교를 위하여 본 논문에서는 돌연변이 확률만 조정하여 실험하였다.
- 실험결과 선택적 돌연변이를 추가한 유전자알고리즘의 성능이 기존의 방법보다 최대 3배까지 좋아짐을 관찰할 수 있었다. 다양성을 이용하여 돌연변이 확률을 조정하는 방법도 같이 실험하였다. 다양성을 이용한 방법은 때때로 기존 방법보다 성능이 약간 좋아지는 것을 볼 수 있었으나 대부분의 실험에서 우리가 제안한 방법보다는 성능이 좋지 못했다.
- DGA는 특히 함수 f4에서 좋지 않았는데, 이는 (그림 3)에서 보듯이 함수 f4가 영역이 두 지역최적화 영역으로 크게 나뉘기 때문에 강한 돌연변이 확률이 아니고서는 전역최적화 영역으로 가기 힘들기 때문으로 보인다. 다음으로 개체수가 12개이고 선택적 돌연변이 수가 1비트 일 때 염색체 길이에 따른 성능을 실험해 보았다.
- 돌연변이 확률을 조정하기 위하여 기 개발된 방법으로는 크게 첫 번째로 초기 세대에 큰 돌연변이 확률로 시작하여 세대가 진행됨에 따라서 수식에 따라서 돌연변이 확률을 줄여주는 방법, 두 번째로 적합도를 이용하여 조숙수렴 정도를 측정하고 이를 이용하여 돌연변이 확률을 조정하는 방법, 마지막으로 다양성 지수를 도입하여 이를 이용하여 돌연변이 확률을 조정하는 방법이 개발되었다.
- 2인 경우 두 번의 선택적 돌연변이를 시도하는데 만약 무작위적으로 생성된 비트 위치가 다르면 모두 각 위치에 선택적 돌연변이가 일어나며 같으면 선택적 돌연변이가 일어난 곳에 또 선택적 돌연변이가 일어나 원래의 값이 된다. 등급은 염색체 길이가 비교적 짧아서 두 그룹으로 나누어 적용하였다. 즉 개체를 상위그룹과 하위그룹으로 나누고 그룹에 따라서 염색체를 두 영역으로 나누어 선택적 돌연변이를 수행하였다.
- 마지막으로 개체수가 12개이고 염색체길이가 12개 일 때 선택적 돌연변이 수에 따른 성능을 측정하여 보았다.
- 본 논문에서는 조숙수렴 정도나 다양성지수를 계산할 필요나 새로운 파라미터를 경험적으로 선택할 필요가 없고 적합도나 인코딩 방법에 상대적으로 의존성이 적은 단순하면서도 강력한 새로운 방법을 제안한다. 본 논문에서 제안하는 방법은 개체의 적합도를 이용하여 등급을 매기고 등급에 따라서 염색체에 특정한 부위에 추가적으로 선택적 돌연변이를 수행하는 방법으로 개체의 다양성을 확장시킨다. 보다 자세히 설명하면 등급이 높은 좋은 개체는 염색체의 하위영역에 선택적으로 돌연변이를 추가하고 등급이 낮은 나쁜 개체는 염색체의 상위영역에 선택적으로 돌연변이를 추가한다.
- 본 논문에서 제안한 선택적 돌연변이가 기존의 유전자알고리즘의 성능향상에 얼마나 기여하는지 알아보기 위하여 4개의 함수최적화 문제를 이용하여 실험하였다. 다음은 4개의 함수 최적화 문제를 기술한 수식이다.
- 표준편차도 구했지만 간략하게 표현하기 위하여 생략하였다. 실험은 유전자 알고리즘이 전역 최적해를 찾은 경우 해당 세대수를 기록하는 방식으로 수행되었다. 그러므로 짧은 세대에 전역 최적해를 찾는 유전자 알고리즘이 성능이 좋은 유전자 알고리즘이다.
- 위의 예에서 설명한 것처럼 개체군을 적합도에 따라서 등급을 매기고 그룹 수 N에 따라서 개체를 N그룹으로 나누고 염색체 스트링도 동일한 N 영역으로 나눈다.
- 그러나 좋은 개체에도 높은 pm을 적용하면 좋은 빌딩블럭이 파괴되어 전역 최적해로의 접근을 방해한다. 이를 위하여 분자 항 fmax-f를 적용하여 좋은 개체일 경우에는 낮은 돌연변이 확률을 적용하게 하였다. 적합도 f가 #인 경우에는 k2값을 갖게 되며 평균적합도 보다 낮은 적합도를 갖는 개체는 좀 더 강력하게 돌연변이를 할 수 있게 하기 위하여 일정한 돌연변이 확률 k4로 설정한다.
- 선택적 돌연변이는 기존의 돌연변이에 추가하여 실행되는 것으로 좋은 개체는 해당 개체 주변을 탐색하게하고 나쁜 개체는 먼 곳을 탐색하게 함으로서 조숙수렴현상을 쉽게 벗어나면서도 전역 최적해에 접근하게 한다. 좋은 개체와 나쁜 개체를 구분하기 위하여 개체에 등급을 매기고 등급에 따라서 두 그룹으로 나누었다. 좋은 개체들은 하위비트 영역을 선택적으로 돌연변이 하게하고 나쁜 개체들은 상위비트 영역을 선택적 돌연변이 하게 하였다.
- 등급은 염색체 길이가 비교적 짧아서 두 그룹으로 나누어 적용하였다. 즉 개체를 상위그룹과 하위그룹으로 나누고 그룹에 따라서 염색체를 두 영역으로 나누어 선택적 돌연변이를 수행하였다. 일반적으로 유전자알고리즘은 초기 개체에 따라서 최적 값을 찾는 시간이 달라진다.
- 그러므로 모든 실험 결과는 100번을 실험한 결과를 평균하여 나타내었다. 표준편차도 구했지만 간략하게 표현하기 위하여 생략하였다. 실험은 유전자 알고리즘이 전역 최적해를 찾은 경우 해당 세대수를 기록하는 방식으로 수행되었다.
대상 데이터
- <표 1>에서 보듯이 대부분의 파라미터는 일반적으로 사용하는 파라미터 값을 설정하였다. 개체 수는 12, 48, 96으로 선택하였다. 염색체 길이는 x,y 각 축으로 8, 10, 12 비트로 설정하였다.
데이터처리
- 일반적으로 유전자알고리즘은 초기 개체에 따라서 최적 값을 찾는 시간이 달라진다. 그러므로 모든 실험 결과는 100번을 실험한 결과를 평균하여 나타내었다. 표준편차도 구했지만 간략하게 표현하기 위하여 생략하였다.
- 제안한 방법의 성능을 측정하기 위하여 4개의 대표적인 함수최적화 문제를 이용하여 실험하였으며 최초 제안된 유전자 알고리즘과 다양성을 사용한 유전자 알고리즘과 성능을 비교하였다. 실험결과 다양성 사용한 유전자 알고리즘이 가끔 최초 제안된 유전자 알고리즘에 비하여 성능이 좋았으나 그렇게 성능이 많이 향상되지는 않았다.
성능/효과
- 다만 돌연변이는 유전자 알고리즘의 핵심인 스키마이론에서 이미 찾은 빌딩 블럭(building block)을 파괴하므로 너무 강력하면 최적해로 접근하는 것을 방해하게 된다. 결론적으로 다양성 유지 측면에서 교배연산이나 교배확률을 조정하는 것보다 돌연변이 연산이나 돌연변이 확률을 조정하는 것이 수월하나 정교하게 조정하지 못하면 오히려 성능을 떨어뜨릴 우려가 있다.
- 그러나 본 논문에서 제안한 선택적 돌연변이가 이것을 사용하지 않은 방법에 비하여 2～3배의 성능향상을 가져옴을 보았다.
- 이러한 경향은 개체 수가 증가 하더라도 거의 유지되었다. 그러므로 본 논문에서 제안한 방법은 개체 수에 상관없이 일정하게 성능을 향상시킴을 보았다. 다양성을 이용한 유전자 알고리즘 DGA는 때때로 OGA보다 성능이 좋았지만 우리가 제안한 방법 RGA보다는 성능이 좋지 않았다.
- 그러므로 본 논문에서 제안한 방법은 개체 수에 상관없이 일정하게 성능을 향상시킴을 보았다. 다양성을 이용한 유전자 알고리즘 DGA는 때때로 OGA보다 성능이 좋았지만 우리가 제안한 방법 RGA보다는 성능이 좋지 않았다. DGA는 특히 함수 f4에서 좋지 않았는데, 이는 (그림 3)에서 보듯이 함수 f4가 영역이 두 지역최적화 영역으로 크게 나뉘기 때문에 강한 돌연변이 확률이 아니고서는 전역최적화 영역으로 가기 힘들기 때문으로 보인다.
- 이런 결과로 볼 때 본 논문에서 제안한 선택적 돌연변이가 유전자 알고리즘 성능 향상에 기여함을 확인 하였다. 본 논문에서 제안한 방법은 기존 유전자알고리즘의 틀을 유지하고 추가적으로 실행하는 것이기 때문에 쉽게 다른 유전자 알고리즘에 적용될 수 있는 장점이 있다.
- 제안한 방법의 성능을 측정하기 위하여 4개의 대표적인 함수최적화 문제를 이용하여 실험하였으며 최초 제안된 유전자 알고리즘과 다양성을 사용한 유전자 알고리즘과 성능을 비교하였다. 실험결과 다양성 사용한 유전자 알고리즘이 가끔 최초 제안된 유전자 알고리즘에 비하여 성능이 좋았으나 그렇게 성능이 많이 향상되지는 않았다. 그러나 본 논문에서 제안한 선택적 돌연변이가 이것을 사용하지 않은 방법에 비하여 2～3배의 성능향상을 가져옴을 보았다.
- 4개의 함수최적화 문제에 적용하여 알고리즘의 성능을 측정하였다. 실험결과 선택적 돌연변이를 추가한 유전자알고리즘의 성능이 기존의 방법보다 최대 3배까지 좋아짐을 관찰할 수 있었다. 다양성을 이용하여 돌연변이 확률을 조정하는 방법도 같이 실험하였다.
- 다양성을 이용한 방법은 때때로 기존 방법보다 성능이 약간 좋아지는 것을 볼 수 있었으나 대부분의 실험에서 우리가 제안한 방법보다는 성능이 좋지 못했다. 이런 결과로 볼 때 본 논문에서 제안한 선택적 돌연변이가 유전자 알고리즘 성능 향상에 기여함을 확인 하였다. 본 논문에서 제안한 방법은 기존 유전자알고리즘의 틀을 유지하고 추가적으로 실행하는 것이기 때문에 쉽게 다른 유전자 알고리즘에 적용될 수 있는 장점이 있다.
- 표 2에서 보듯이 제안한 방법이 기존의 방법보다 대략 2배에서 3배 정도의 성능향상을 보였다. 이러한 경향은 개체 수가 증가 하더라도 거의 유지되었다.
- <표 2>는 염색체길이가 12비트(x, y축으로는 24비트)이며 선택적 돌연변이 수가 1 비트일 때 개체 수별로 실험한 결과를 보여준다. 표에서 OGA, DGA, RGA는 각각 초기 유전자알고리즘 [1], 다양성을 사용한 적용한 유전자 알고리즘 [17], 그리고 본 논문에서 제안한 등급중심 유전자 알고리즘을 나타낸다. 다양성을 사용한 방법에서 다양성을 측정하는데 사용하는 미리 정의된 문턱치 D는 개체수의 1/3을 사용했다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.