[논문]2-단계 병렬 유전자 알고리즘

길원배; 이승구

2-단계 병렬 유전자 알고리즘
A Two-Phase Parallel Genetic Algorithm 원문보기

길원배 (포항공과대학교 전자전기공학과) , 이승구 (포항공과대학교 전자전기공학과)

본 논문에서는 유전자 알고리즘(Genetic Algorithm: GA)의 새로운 병렬화 방법을 제안 하고 있다. 기존의 병렬 유전자 알고리즘(Parallel Genetic Algorithm: PGA)은 전체 개체집단을 부개체집단 (Subpopulation)으로 나누어 해의 가능 영역을 동시에 탐색하는 것이 일반적인 방법인데 반해. 본 논문에서 제안하는 병렬화 방법은 전체 해의 영역을 나누어 각각의 영역에서 독립된 개체집단들이 서로 다른 영역을 탐색하게 하는 방법이다. 이 방법은 두 가지 단계의 병렬 유전자 알고리즘으로 구성된다. 먼저 적응교배 연산자(Adaptive Crossover Operator: ACO)를 이용한 PGA를 통해 지역해에 인접한 범위들로 해의 영역을 나누고, 이렇게 나누어진 각각의 영역들에서 다시 병렬로 GA를 적용시켜 자세하게 탐색하는 방법이다. 첫 번째 수행되는 PGA 단계에서는 탐색 시간을 줄이고 두 번째 PGA 단계에서는 보다 자세한 탐색을 하기 위해 정밀도(Precision)의 조정을 유전자 알고리즘의 병렬화에 적용하였으며. 이를 통해 빠르고 자세한 탐색이 가능한 유전자 알고리즘의 병렬화 방법을 제안하고 있다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

따라서 진화(Ev어나tion)가 거듭될个록 주어진 환경에 더 적합한 유전자들만이 남아 있게 되는 것이다[1]. 이러한 GA는 군본적으로 녕렬성 읗 가지고 있으며, 방대한 해의 영역을 가지는 문제에서 조금이라도 더 빠른 함색을 하기 위해 병렬 유전자 알고 리즘(Parallel Genetic Algorithm: PGA)에 관한 연구가 많이 행해져 왔다, [2, 3] 본 논문은 뿐산 환경에서 기존의 병렬 유전자 알고리즘에서 가지는 통신 시간에 의한 부담을 줉어고, 병렬 유전자 알고리좀모다 종 더 邮르고 정일한 탕색물 하기 위해 유전자 알고리즘의 새로운 병렬화 방법을 제안하고 있다. 이룰 위해 [4]에서 제얀된 적응 교배 연산자(Adaptive Crossover Operator)를 본 논문의 목적에 맞게 변형한 적응 교배 연산자養 유전자 알고리즘에 이용하고 있다.

가설 설정

위와 같은 다변수 함수의 해를 유전자 알고리즘에서 하나의 개체로 표현하기위해 이진수 표현기법을 사용하고 있으며, 각각의 변수는 m개의 비트로 다음과 같이 표현 가능하다고 가정한다. 다음은 하나의 변수 篠에 대한 이진수 표현이다.

제안 방법

본 논문에서 제안하는 2-단계 병렬 异전자 알고리즘은 기존의 병렬 유전자알고리즘과는 다른 관점에서 제안된 방법이다. 즉, 기존의 병렬 유전자알고리즘이 개체집단의 분할을 통해 병렬성을 개발한 알고리즘이라고 한다면, 제안된 방법은 탐색영역의 분할을 동해 병렬성을 개발한 방법이라고 할 수 있다.
첫 번째 단계의 导전자 알고리즘은 전역 최적해를 포함한 지역 최적해들에 인접한 범위들로 해의 영역을 나누기 위해 수행되는 것이며, PGA에 의해 수행 된다. 이 과정에서 소요되는 탐색시간을 줄이기 위해 계산의 복잡도가 낮고 수행속도가 麟른 적응 교배 연산자 룔 이용한 PGA를 사용하며, 보다 昭른 탐색을 위해 원하는 정밀도보다 낮은 정밀도를 사용하여 탐색하는 방법을 사용한다. 이 무분에서 정밀도를 낮춘다는 말은 하나의 개체를 이진수로 표현할 때 사용 하는 비트수를 줄 인다는 말이며, 이렇게 할 수 있는 이유는 첫 번째 유전 자 알고리즘(PGA)의 탐색 목적이 두 번째로 수행될 유전자 알고리즘(GA)을 위한 지역해들의 대략적인 범위를 먼저 찾는 것이므로 자세한 탐색을 필요로 하지 않기 때 문이다.

이론/모형

이러한 GA는 군본적으로 녕렬성 읗 가지고 있으며, 방대한 해의 영역을 가지는 문제에서 조금이라도 더 빠른 함색을 하기 위해 병렬 유전자 알고 리즘(Parallel Genetic Algorithm: PGA)에 관한 연구가 많이 행해져 왔다, [2, 3] 본 논문은 뿐산 환경에서 기존의 병렬 유전자 알고리즘에서 가지는 통신 시간에 의한 부담을 줉어고, 병렬 유전자 알고리좀모다 종 더 邮르고 정일한 탕색물 하기 위해 유전자 알고리즘의 새로운 병렬화 방법을 제안하고 있다. 이룰 위해 [4]에서 제얀된 적응 교배 연산자(Adaptive Crossover Operator)를 본 논문의 목적에 맞게 변형한 적응 교배 연산자養 유전자 알고리즘에 이용하고 있다. 또한 정밀도(Precision)의 조정을 유전자 알고리즘의 병룔화에 적용하여 빠르고 자세 한 탐색이라는 궁극적 목적에 부합되는 명렬화 방법을 제안하고 있다.

성능/효과

즉, 기존 병렬 유전자 알고리즘에서 노드들 사이의 통신량이 알고리즘 수행 시간의 큰 비중을 차지하는 것에 비해 제안된 알고리즘에서는 독립된 탐색영역들에서 각각 유전자 알고리즘이 수행되기 해문에 통신량에 의한 부담이 거의 없다는 장 점을 가지게 된다. 그리고 본 논문에서 제안된 병렬화 방법은 변형된 적응교배연산자와 정밀도 조정을 이용해 빼른 범위탐색과 정밀한 부분탐색을 의도하고 있다는 측연에서 유전자알고리즘의 전역탐색과 지역탐색의 균형을 다른 차원에서 구현하고 있다는 것에 큰 의이를 둘 수 있다.
실제 경계값의 기와 개수는 병렬 异전자 알고리즘의 수행시간을 고려해서 설정 되어야 하며, 적용되는 문제에 따라 다르게 설정 될 수 있다. 본 논문에서는 다변수 함수의 최소값을 구하는 문제이므로 평균 평가 함수값이 경계값보다 작을 패 교 배 범위를 줄여 주게 된다. 주 노드에서 평균 평가함수 값은 부개체집단에서 계산된 평균 평가함수 값들의 평균 값이며, 부개체집단에서의 평균 평가함수 값은 아래 식 (5)과 같다.
즉, 기존의 병렬 유전자알고리즘이 개체집단의 분할을 통해 병렬성을 개발한 알고리즘이라고 한다면, 제안된 방법은 탐색영역의 분할을 동해 병렬성을 개발한 방법이라고 할 수 있다. 이는 기존의 병렬 유전자알고리 즘이 부개체집단들의 중복된 영역 탐색 가능성으로 인해 병렬성을 감소시킬 수 있는 반면, 제안된 병렬화 방법은 탐색 영역의 중복 가능성이 전혀 없으므로 유전자알고리 좀의 병렬화에 새로운 가능성을 보여준 방법이라고 할 수 있다. 또한 이러한 특성은 분산 환경에서 각 노드들 간의 통신량에서 잘 나타나게 된다.
또한 이러한 특성은 분산 환경에서 각 노드들 간의 통신량에서 잘 나타나게 된다. 즉, 기존 병렬 유전자 알고리즘에서 노드들 사이의 통신량이 알고리즘 수행 시간의 큰 비중을 차지하는 것에 비해 제안된 알고리즘에서는 독립된 탐색영역들에서 각각 유전자 알고리즘이 수행되기 해문에 통신량에 의한 부담이 거의 없다는 장 점을 가지게 된다. 그리고 본 논문에서 제안된 병렬화 방법은 변형된 적응교배연산자와 정밀도 조정을 이용해 빼른 범위탐색과 정밀한 부분탐색을 의도하고 있다는 측연에서 유전자알고리즘의 전역탐색과 지역탐색의 균형을 다른 차원에서 구현하고 있다는 것에 큰 의이를 둘 수 있다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

2-단계 병렬 유전자 알고리즘
A Two-Phase Parallel Genetic Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

2-단계 병렬 유전자 알고리즘 A Two-Phase Parallel Genetic Algorithm 원문보기

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

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

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

2-단계 병렬 유전자 알고리즘
A Two-Phase Parallel Genetic Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper