[논문]복합 유전자 알고리즘에서의 국부 탐색을 위한 셀룰러 학습 전략

고명숙; 길준민

문제 정의

다수성 규칙이 적용된 셀룰러 오토마타는 단계가 진행됨에 따라 특정 패턴으로 수렴함을 볼 수 있다. 본 논문에서는 오토마타의 이러한 특징들을 국부 탐색 과정에서 적합도 함수의 변이에 반영함으로써 함수의 수렴을 유도하고자 한다.
본 논문에서는 전역 최적해로의 수렴도와 학습 속도를 향상시키기 위한 국부 탐색 방법으로서 적합도 함수값 변화를 이용하여 국부 탐색을 수행하는 새로운 학습전략을 제시하고자 한다.
이 논문에서는 새로운 학습 전략인 셀룰러 학습 기법을 제안하고 이 기법을 기존의 유전자 알고리즘과 결합시킴으로써 학습 속도의 개선과 전역 최적해로의 수렴도의 향상을 보이고자 한다. 또한, Witley의 테스트 함수와 Dejong의 테스트 함수[4] 에 대한 최적화 실험을 통하여 제안하는 기법의 탐색 효율에 대한 성능을 평가 분석한다.

가설 설정

최적화하기 위한 함수의 상태 공간이 비교적 완만하거나 또는 이웃하는 목적 함수 값의 변화가 크지 않을 경우에는 라마키안 알고리즘은 좋은 성능을 보일 수 있을 것이다. 즉 단순 유전자 알고리즘보다 목적 함수의 평가 횟수는 상대적으로 증가하지만, 수렴 속도는 상당히 빠를 것이다. 반면에 볼드윈 효과에 의한 국부 탐색은 각 개체의 유전 형질의 변화를 유발하지 않으므로 모집단의 다양성을 비교적 잘 유지할 수 있는 학습 전략이다.

제안 방법

1) 유기체가 그 세대에 획득한 지식, 경험 및 환경의 변화에 대한 내용을 유전 형질은 변화시키지 않으면서 다음 세대로 물려줄 수 있는 셀룰러 학습 전략을 제안하였다.
:본 논문에서 제안하는 셀룰러 학습에서는 하나의, 중심 셀이 alive 또는 dead 상태로 변하는 것이 아니라 현재 그 개체의 적합도 함수 값이 주위의 개체들의 적합도 함수 값에 의해 어떤 방향으로 변하는지에 대한 규칙을 정함에 있어서 셀룰러 오토마타에서의 생명 게임 규칙을 학습 전략을 기반으로 하였다. 즉, 생명 게임 규칙에서처럼 하나의 셀이 이웃 셀들에 의해 다음 단계 (step)에서의 생존 여부가 가려지는 것이 아니라 셀에 해당하는 하나의 개체의 적합도 함수 값이 그 세대에서 어떤 값을 가지게 되는지의 결정을 이웃 크기 내에 있는 개체들(여기서는 가상의 개체들어〕의해 결정하는 것을 말한다.
탐색 후의 개체는 지역적으로 최적 해에 해당하는 상태 공간에 있게 되며 결과적으로 국부 최적 해에 도달할 수 있도록 학습되는 것이다. 각 개체가 학습한 내용이 다음 세대에 전달되도록 하기 위해 기존의 국부 최적화 방법으로 학습을 시킨 후에 평가와 선택을 수행한다. 국부 탐색의 기반이 되는 언덕 오르기 알고리즘은 다음 그림 1과 같다.
전체 탐색 공간에 대한상관 계수 값의 계산을 위하여 모집단을 구성하는 초기해 개체들을 출발점으로 하여 그 개체와 가장 가까운 국부 최적 점 (local optimum) 까지 힐 크라이 밍 (hillclimbing) 국부 탐색을 적용한다. 그 다음 국부 최적점에 도달 할때까지 변화하는 각 탐색 공간 상의 개체들에 대한 적합도 함수값들의 대한 평균값을 측정함으로써 전체 탐색 공간에 대한 상관 계수값을 얻는다.
하는 것이다. 따라서 이 규칙은 이웃 크기 내에 속하게 되는 개체에 따라 다른 값들을 결과로 산출하게 되며, 항상 고정되어 있는 것이 아니라 이웃 크기의 변화에 따라 영향을 받게 되며 현재 이웃 크기내에 속해 있는 개체들에 적응적으로 값을 산출해 낸다. 단, 이러한 셀룰러 학습이 진행되기 위해서는 경계 초기화되어야 한다.
향상을 보이고자 한다. 또한, Witley의 테스트 함수와 Dejong의 테스트 함수[4] 에 대한 최적화 실험을 통하여 제안하는 기법의 탐색 효율에 대한 성능을 평가 분석한다.
본 논문에서 제안하는 유전자 알고리즘은 단일 교차 연산과 wheel of fortune 선택 메커니즘을 사용하였으며 다음과 같은 9개의 요소로 구성되어 진다. 각 요소에 대한 설명은 다음 그림 7과 같다.
본 논문에서는 상관 계수를 이용하여 학습이 적용되는 단위인 섬(island)의 개수를 결정하고 각 섬에 대한 초기화를 수행하는 경계 초기화 단계를 행한다. 세대가 진행됨에 따라 셀룰러 학습의 결과로 함수의 상태 공간의 굴곡 정도를 나타내는 값이 커지므로(상관 계수 값은 굴곡 정도와 반비례하므로), 섬의 크기는 커지게 되고 반대로 섬의 개수는 감소하게 된다.
이 장에서는 제안하는 셀룰러 학습 전략의 성능을 기존의 국부 탐색 방법인 라마키안 진화와 볼드윈 효과와 비교하여 평가하고자 한다. 최적화 실험에 많이 사용되는 드종과 쉐퍼에 의해 제안된 테스트 베드 함수들[4]을 대상으로 살험을 행하였다.
이웃 크기값을 1로 초기화시킨 후 부-모집단 1에 대한 셀룰러 학습을 행하고 각 개체의 실제 적합도 함수 값을 계산한다.
여기서 牛■이웃 내에는 실제 모집단 내에 존재하는 개체들이 포함되며 또한, 실제 이웃 크기 내에 존재 가능한 개체들도 포함되도록 한다. 이웃 크기는 절대 거리의 개념으로 정한 것이므로 셀룰러 학습을 적용시키는 과정에서 이웃 크기 내에 실제로 포함되는 개체들이 자기 자신을 제외하고 전혀 존재하지 않을 경우는 이웃 크기로부터 생성될 수 있는 가상 개체와 또한 그에 대응되는 적합도 함수값을 적용시킴으로써 셀룰러 학습을 행하도록 하였다.
의해 섬의 크기를 결정한다. 이웃 크기를 1로 초기화하고, 초기화된 각 섬 내에서 셀룰러 학습을 수행한다. 이중 가장 높은 적합도 함수 값을 갖는 개체를 그 섬의 대표로 결정한다.
방법이다. 중심 셀에 해당하는 개체는 모집단을 구성하는 개체들이 되고 이 개체의 적합도 함수 값에 영향을 주게 되는 개체들은 이웃 크기 범위에 속하는 균등 분할 4-이웃 (함수 최적화의 경우 입력 매개 변수 xl, x2에 대한 이웃 크기 범위 내에서의 균등 위치 값이 됨)이 형성되고 각각에 대한 적합도 함수 값은 현재 최적화시키고자 하는 함수에 의해 계산하는 방식으로 학습을 수행한다. 여기서 牛■이웃 내에는 실제 모집단 내에 존재하는 개체들이 포함되며 또한, 실제 이웃 크기 내에 존재 가능한 개체들도 포함되도록 한다.
초기의 전체 탐색 공간에 대한 상관 계수를 측정하고 이값에 의해 섬의 크기를 결정한다. 이웃 크기를 1로 초기화하고, 초기화된 각 섬 내에서 셀룰러 학습을 수행한다.

대상 데이터

평가하고자 한다. 최적화 실험에 많이 사용되는 드종과 쉐퍼에 의해 제안된 테스트 베드 함수들[4]을 대상으로 살험을 행하였다. 실험에 사용된 함수들은 다음 표 2와 같다.

데이터처리

탐색 공간의 전체적 특성을 반영하기 위해 적합도 함수 값의 상관 계수(correlation coefficient) 값에 대한 통계적 성질을 이용해서 탐색 공간의 굴곡 정도(rugged- □ess)를 측정한다. 굴곡 정도가 큰 탐색 공간은 이웃 점들과의 관련성이 적음을 나타내고, 굴곡 정도가 작은 탐색 공간(완만한 탐색 공간)은 이웃 점들과의 관련성이 많음을 의미한다.

성능/효과

1) 가변 환경에서 종(species)이 진화할 때, 생존 기간 동안 햑습할 수 있는 능력을 갖는 개체가 더 선호되는 진화 압력 (evolutionary pressure)이 생긴다,
2) 굴곡이 심한 상태 공간을 갖는 함수의 최적화 문제에 대해서 모집단의 다양성 유지와 함께 근사 상태 공간을 형성하는 방법을 통하여 전역 최적 '해 立의 수렴 확률을 높일 수 있다.
2) 많은 특질들을 배울 수 있는 개체는 고정된 특질과 관련된 유전 형질을 가지게 될 확률이 낮아진다.
3) 상태 공간을 상관 계수 값에 의해 섬으로 구분한 후 초기화시킴으로써 모집단의 임의 초기화에서 발생할 수 있는 표본화 오류를 줄일 수 있다.
4) 기존 학습 전략에 비해 학습 속도의 개선을 꾀하였다.
변화를 관찰한 실험 결과이다. 각 값의 분포로부터 모집단의 수렴 정도가 볼드윈 효과보다 빠름을 알 수 있고, 전역 최적 해에 도달하였음을 볼 수 있다. 또한 평균 적합도 함수 값(Favg)의 분포 곡선이 변화가 작은 완만한 증가를 보이므로 모집단내의 개체들의 다양성이 세대가 진행됨에 따라 비교적 잘 유지되고 있음을 알 수 있다.
첫째, 개체의 형질에 영향을 주지 않으므로 학습이 진행되어도 개체의 다양성 유지가 가능하며, 선택 압력에 의한 국부 최적값(local optimum) 에빠지는 현상을 막을 수 있다. 둘째, 이웃 크기 내에서의 학습은 셀룰러 학습이 수행하는 단계 반복 개념을 이웃 크기의 증가로 대체할 수 있기 때문에 기울기 강하 기법에 의한 학습보다 학습 속도의 향상을 유도한다. 셋째, 전체 탐색 공간에 대한 균등 탐색을 가능하게 하는 섬 분할에 의한 학습은 이웃 m기 내에서의 학습을 통한 지역적 탐색(exploitation)과 동시에 각 섬을 대표하는 개체들 간의 유전 연산을 통한 전역 탐색 (exploration) 의 효과를 적절히 결합시킬 수 있다.
각 값의 분포로부터 모집단의 수렴 정도가 볼드윈 효과보다 빠름을 알 수 있고, 전역 최적 해에 도달하였음을 볼 수 있다. 또한 평균 적합도 함수 값(Favg)의 분포 곡선이 변화가 작은 완만한 증가를 보이므로 모집단내의 개체들의 다양성이 세대가 진행됨에 따라 비교적 잘 유지되고 있음을 알 수 있다.
본 논문에서 제안하는 학습 전략은 복잡한 상태 공간을 나타내는 함수를 완만한 형태의 공간으로 근사 시켜나가면서 최적해로 수렴할 수 있도륵 해주는 학습 전략이다 이때, 개체의 형질을 그대로 보존시키고 적합도 함수 값만을 이웃하는 개체의 값에 의해 보정해, 나감으로써 모집단의 다양성을 유지하여 지역 최적 해에 수렴할 확률을 줄일 수 있었다. 또한 근사화시키는 학습 전략에 의해 전역 최적해를 찾는 수렴속도를 꾀할 수 있었다.
이로부터 각 세대에 대한 국부 탐색이 전체 모집단 내의 개체의 적합도 함수값을 거의 균일하게 유지되도록 함으로써 최적해로 수렴하는 속도가 매우 빠름을 알 수 있으나 반면에 전역 해에 도달할 수는 없었음을 볼 수 있다. 볼드윈 효과에 의한 방법은 수렴 속도가 다소 느리지만 모집단의 평균 적합도 함수의 값의 분포로부터 알 수 있듯이 개체들의 다양성 유지와 함께 전역 해로 수렴함을 볼 수 있었다.
상관계수 값은 전체 상태 공간의 특징을 나타내는 값으로서 二 절대값이 클수록 모집단 내의 개체들이 밀접하게 연판되어 있음을 의미하므로 따라서 다양성을 유지를 측정할 수 있는 척도로 쓰일 수, 있다. 세대 진행에 따른 모집단의 다양성 유지 '정도를 알아보기 위해 상관 계수 값을 각 섬에 대해 측정해 보았으며, 그 결과로부터 셀룰러 학습에 의한 알고리즘이 라마 키 안과 볼드윈 방법보다 월등히 다양성 유지에 효과적임을 실험으로 증명하였다.
둘째, 이웃 크기 내에서의 학습은 셀룰러 학습이 수행하는 단계 반복 개념을 이웃 크기의 증가로 대체할 수 있기 때문에 기울기 강하 기법에 의한 학습보다 학습 속도의 향상을 유도한다. 셋째, 전체 탐색 공간에 대한 균등 탐색을 가능하게 하는 섬 분할에 의한 학습은 이웃 m기 내에서의 학습을 통한 지역적 탐색(exploitation)과 동시에 각 섬을 대표하는 개체들 간의 유전 연산을 통한 전역 탐색 (exploration) 의 효과를 적절히 결합시킬 수 있다.
실험 결과에서 알 수 있듯이 라마키안 진화에 의한 방법이 볼드윈 효과에 의한 방법보다 수렴 속도가 월등히 빠름을 볼 수 있다. 라마키안 알고리즘에 의한 학습 결과를 보면 15세대 이후부터는 최대 적합도 함수 값이 모집단의 평균 적합도 함수 값과 거의 유사해 짐을 볼 수 있다.
요약할 수 있다. 첫째, 개체의 형질에 영향을 주지 않으므로 학습이 진행되어도 개체의 다양성 유지가 가능하며, 선택 압력에 의한 국부 최적값(local optimum) 에빠지는 현상을 막을 수 있다. 둘째, 이웃 크기 내에서의 학습은 셀룰러 학습이 수행하는 단계 반복 개념을 이웃 크기의 증가로 대체할 수 있기 때문에 기울기 강하 기법에 의한 학습보다 학습 속도의 향상을 유도한다.
함수 F2에 대해서는 비교적 잘 수렴되었지만 함수 F3에 대한 실험결과를 보면 단순 유전자 알고리즘은 최적 해를 찾지 못하였으며 라마키안 알 也_리즘은 최적해 수렴 확률이 볼드윈 효과와 셀룰러 학습에 의한 결과보다 낮음을 볼 수 있다. 함수 F2에 대해서는 실험 함수의 상태 공간이 국부 최적 점을 비교적 적게 포함하는 특성으로 인하여 라마키안 알고리즘도 좋은 성능을 보였는데, 이로부터 상태 공간에 대한 정보를 미리 알고 있으면서 빠른 학습 효과를 요구하는 문제에 대해서는 라마키안 학습도 비교적 좋은 결과를 제공하여 줄 수 있으리라는 것을 예측할 수 있다.

후속연구

앞으로의 연구 과제로는 셀룰러 학습 전략의 다중 최적화 문제로의 적용과 셀룰러 학습 기법의 탐색 공간상의 변이에 대한 기존 학습 전략간의 비교에 대한 연구이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

복합 유전자 알고리즘에서의 국부 탐색을 위한 셀룰러 학습 전략
A Cellular Learning Strategy for Local Search in Hybrid Genetic Algorithms 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

복합 유전자 알고리즘에서의 국부 탐색을 위한 셀룰러 학습 전략 A Cellular Learning Strategy for Local Search in Hybrid Genetic Algorithms 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

참고문헌 (16)

이 논문을 인용한 문헌

저자의 다른 논문 :

고명숙 (1)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

복합 유전자 알고리즘에서의 국부 탐색을 위한 셀룰러 학습 전략
A Cellular Learning Strategy for Local Search in Hybrid Genetic Algorithms 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper