선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 연구에서는 MLP를 위한 해법으로 인공면역시스템의 복제선택해법과 모집단관리 유전해법을 개발하려고 한다. 해법의 유효성을 실험하기 위해 일반 유전해법과 비교하려고 한다.
- 우리가 조사한 범위에서 유전해법과 같은 메타 휴리스틱이 MLP에 사용된 예는 찾아보지 못했다. 우리는 MLP를 위한 해법으로 유전 해법의 새로운 전략인 복제선택해법과 모집단 관리 유전해법을 도입하려고 한다.
가설 설정
- 차량은 계획 시점에 차고지에서 대기하고 있으며 고객의 서비스 요청은 계획 시점이전에 발생하여 미리 알려져 있다. 고객과 차고지는 2차원 상의 좌표로 주어져 있으며 점간의 거리는 직선거리를 가정하였다. MLP는 고객 대기시간의 합을 최소화하는 경로 π 를 구하는 문제이다.
- TSPLIB에서 16개 문제를 사용하였다. 차고지는 각 문제 공간의 중심에 있고 거리는 직선거리를 가정하였다. 먼저 해법별 목적함수값을 비교한 것이 <표1>에 제시 되었다.
제안 방법
- 교차 : 모집단에서 두 개의 개체를 임의로 선택하여 유전 해법에서 설명한 2점 교차를 수행하였다. 2점 교차의 결과 얻어진 두 개의 자식 개체 중 임의로 하나를 선택하여 모집단 관리를 수행하였다.
- 메타휴리스틱으로는 유전해법과 복제 선택해법 그리고 모집단 관리 유전해법을 이용하여 MLP해법을 개발하였다. TSPLIB에서 찾아낸 16개의 문제에 대하여 해법간의 비교 실험을 실시하였다. 실험 결과 목적함수값에서는 복제선택해법이 가장 우수하고 모집단관리 유전해법이 가장 열등하였다.
- 개발된 세 가지 해법인 GAMLP, CSAMLP와 PMGAMLP를 비쥬얼 스튜디오 시스템으로 구축하였다. 실험은 인텔의 Core2 Quad 2.
- 복제 전략에서는 모집단의 각 개체를 평가하고, 모집단에서 가장 우수한 개체의 목적함수값(최우수적합도)와 가장 열등한 개체의 목적함수값(최열등적합도)를 구한다. 개체의 상대적합도에 의해서 개체의 복제율(cloning rate)을 결정하였다[12][13].
- 먼저 개체의 일부를 마스터 경로의 동일 부분과 교환하였다. 개체의 원래 부분 중에서 마스터 경로에서 복사된 노드를 제외한 나머지들을 원래의 개체에 복사하였다. P를 부모 개체, M을 마스터 경로, 지역 탐색중의 부모 개체의 수정된 결과를 P'과 P"라 하고, O를 자식 개체라 하면 지역 탐색의 절차는 다음과 같다.
- 돌연 변이는 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 실시하였다. 다음으로 1%의 비율로 선택된 일부 개체에 대하여 지역 탐색을 실시하였다. 매 단계마다 가장 우수한 해를 찾아서 최우수해로 보관하였다.
- 항체의 상대적합도에 의해서 하이퍼 돌연변이율이 결정되고 이에 따라 각 선택된 항체들에 대하여 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 실시하였다. 다음으로 하이퍼 돌연변이율에 의해서 선택된 일부 항체에 대하여 지역 탐색을 실시하였다. 매 단계마다 가장 우수한 항체를 찾아서 최우수해로 보관하였다.
- 또한 1%의 돌연변이율로 선택된 일부 개체에 대하여는 돌연변이 작업을 수행하였다. 돌연 변이는 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 실시하였다. 다음으로 1%의 비율로 선택된 일부 개체에 대하여 지역 탐색을 실시하였다.
- 우리는 MLP를 위한 메타 휴리스틱을 개발하였다. 메타휴리스틱으로는 유전해법과 복제 선택해법 그리고 모집단 관리 유전해법을 이용하여 MLP해법을 개발하였다. TSPLIB에서 찾아낸 16개의 문제에 대하여 해법간의 비교 실험을 실시하였다.
- 해법의 매 단계마다 상대적합도를 이용하여 복제를 실시하였다. 복제된 모집단에 대하여 하이퍼 돌연변이를 수행하였다. 항체의 상대적합도에 의해서 하이퍼 돌연변이율이 결정되고 이에 따라 각 선택된 항체들에 대하여 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 실시하였다.
- 유전해법의 매 단계마다 토너먼트 선택을 사용하여 다음 세대의 모집단을 작성하였다. 새로운 모집단의 개체 중 1%의 교차 비율로 선택된 개체에 대하여 이미 설명한 교차작업을 수행하였다. 또한 1%의 돌연변이율로 선택된 일부 개체에 대하여는 돌연변이 작업을 수행하였다.
- 문제의 복잡성이 NP-hard로 증명되었고 실용적으로도 TSP보다 어려운 문제로 알려져 있다. 우리는 MLP를 위한 메타 휴리스틱을 개발하였다. 메타휴리스틱으로는 유전해법과 복제 선택해법 그리고 모집단 관리 유전해법을 이용하여 MLP해법을 개발하였다.
- 유전 해법 : 유전 해법은 최기해로 랜덤함수에 의해서 초기 개체들을 생성하였다. 유전해법의 매 단계마다 토너먼트 선택을 사용하여 다음 세대의 모집단을 작성하였다. 새로운 모집단의 개체 중 1%의 교차 비율로 선택된 개체에 대하여 이미 설명한 교차작업을 수행하였다.
- 지역탐색 : 모집단에서 임의의 한 개체를 선택하여 지역 탐색을 수행하였다. 지역 탐색은 최단거리이웃삽입전략을 사용하였으며 지역탐색으로 얻어진 개체는 모집단관리를 수행하였다.
- 지역탐색 : 모집단에서 임의의 한 개체를 선택하여 지역 탐색을 수행하였다. 지역 탐색은 최단거리이웃삽입전략을 사용하였으며 지역탐색으로 얻어진 개체는 모집단관리를 수행하였다.
- 먼저 하이퍼 돌연변이율은 상대적합도가 우수한 경우 낮은 돌연변이율을 적용하고 상대적합도가 열등한 경우 높은 돌연변이율을 적용하는 방법이다[12][13]. 하이퍼 돌연변이율에 의해서 선택된 항체에 대하여는 유전해법에서 설명한 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 선택하여 실시하였다.
- 복제된 모집단에 대하여 하이퍼 돌연변이를 수행하였다. 항체의 상대적합도에 의해서 하이퍼 돌연변이율이 결정되고 이에 따라 각 선택된 항체들에 대하여 점 교환 돌연변이, 가지 이동 돌연변이, 가지 교환 돌연변이중 하나를 랜덤하게 실시하였다. 다음으로 하이퍼 돌연변이율에 의해서 선택된 일부 항체에 대하여 지역 탐색을 실시하였다.
- 매 단계마다 가장 우수한 해를 찾아서 최우수해로 보관하였다. 해법은 1000번의 반복회수로 설정하였으며 우수해의 변화가 없는 반복회수가 100회이면 종료하도록 하였다. 이상을 정리하면 MLP를 위한 유전해법은 다음과 같다.
- 복제선택해법 : 복제선택해법은 최기해로 랜덤함수에 의해서 초기 개체들을 생성하였다. 해법의 매 단계마다 상대적합도를 이용하여 복제를 실시하였다. 복제된 모집단에 대하여 하이퍼 돌연변이를 수행하였다.
- 본 연구에서는 MLP를 위한 해법으로 인공면역시스템의 복제선택해법과 모집단관리 유전해법을 개발하려고 한다. 해법의 유효성을 실험하기 위해 일반 유전해법과 비교하려고 한다. 사용하려는 복제선택해법과 모집단관리 유전해법의 이론적인 배경을 각 해법의 개발자들의 논문을 중심으로 설명하면 다음과 같다.
대상 데이터
- 66Ghz CPU 가 장착된 컴퓨터에서 실시하였다. TSPLIB에서 16개 문제를 사용하였다. 차고지는 각 문제 공간의 중심에 있고 거리는 직선거리를 가정하였다.
- 개체 : 개체로는 유전 해법에서 사용한 개체와 동일한 개체를 사용하였다.
- 항체 : 복제선택해법에서는 유전해법에서 사용하는 개체라는 용어 대신 항체라는 용어를 사용한다. 사용하는 항체는 유전 해법에서 설명한 것과 같은 형태의 개체를 사용하였다.
이론/모형
- 돌연변이 : 모집단중 하나의 개체를 임의로 선택하여 돌연변이를 수행한다. 돌연변이 방법은 유전해법에서 설명한 점교환 돌연변이, 가지이동 돌연변이, 가지교환돌연변이를 사용하였다. 돌연변이의 결과 생성된 개체는 모집단관리를 수행하였다.
- 지역탐색 : 유전 해법에서 설명한 최단거리이웃삽입 전략을 사용하였다.
- 지역탐색 : 지역탐색으로는 최단거리이웃삽입전략을 사용하였다. 이 전략은 차고지로부터 가장 가까운 고객을 찾아서 다음 방문지로 결정하고 그 고객으로부터 가장 가까운 고객을 찾아서 경로에 연결하는 방법이다.
- 토너먼트 선택 : 유전해법에서는 토너먼트 선택을 사용하였다. 토너먼트 선택이란 모집단에서 k개의 개체를 선택하여 그 중 가장 우수한 개체를 선택하여 다음 세대의 모집단에 복제한다.
성능/효과
- 평균적인 연산의 복잡도가 O(n2) 정도인 것으로 나타났다. CSAMLP와 PMGAMLP의 경우에는 문제의 크기에 따른 연산 시간의 증가율이 크지 않은 것으로 나타났다.
- 연산시간은 PMGAMLP가 가장 작게 나왔으며 다음으로 우수한 해법은 CSAMLP이었다. CSAMLP의 경우 GAMLP과 비교하면 12%대의 연산시간이었으며 PMGAMLP는 GAMLP과 비교 했을 때 3.45%의 연산 시간이 소요되었다. PMGAMLP의 연산시간이 극적으로 단축되는 것은 일반 유전 해법이 모든 개체에 대하여 돌연변이와 교차 및 지역 탐색을 수행한 후 전체 모집단을 선별하지만 모집단관리 유전 해법은 매 회소수의 개체에 대하여 돌연변이와 지역탐색을 적용하고 대신 모집단의 분산성을 유지하는 전략을 사용하여 연산 시간이 단축된 것으로 판단된다.
- 전체 16개 문제 중에서 6개의 문제는 세 가지 해법이 동일한 결과를 제시하였다. GAMLP가 가장 우수한 결과를 준 경우는 5가지 문제였으며, CSAMLP는 4가지 문제에서 우수했다.
- 먼저 해법별 목적함수값을 비교한 것이 <표1>에 제시 되었다. 목적함수값은 CSAMLP가 평균값에서 우수했고 다음이 GAMLP였으며 PMGAMLP가 가장 열등했다. 전체 16개 문제 중에서 6개의 문제는 세 가지 해법이 동일한 결과를 제시하였다.
- TSPLIB에서 찾아낸 16개의 문제에 대하여 해법간의 비교 실험을 실시하였다. 실험 결과 목적함수값에서는 복제선택해법이 가장 우수하고 모집단관리 유전해법이 가장 열등하였다. 계산시간에서는 모집단관리 유전해법이 다른 해법들에 비하여 월등히 우수하였다.
- 해법별 연산시간을 비교한 것이 <표2>에 제시되었다. 연산시간은 PMGAMLP가 가장 작게 나왔으며 다음으로 우수한 해법은 CSAMLP이었다. CSAMLP의 경우 GAMLP과 비교하면 12%대의 연산시간이었으며 PMGAMLP는 GAMLP과 비교 했을 때 3.
- 이상을 정리하면 목적함수값에서는 복제선택해법이 가장 우수했다. 그러나 다른 해법과의 비교에서 그 차이는 1%내였다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.