MINE 알고리즘은 범용성을 보이기 위하여 2009년 제안된 메타 휴리스틱 알고리즘 (Meta Heuristic Algorithm)이다. S-MINE (Search-MINE)알고리즘은 MINE 알고리즘에 기반을 두고 있으며, 본 논문에서는 MINE 알고리즘을 TSP 에 적용하기 위하여 알고리즘을 ...
MINE 알고리즘은 범용성을 보이기 위하여 2009년 제안된 메타 휴리스틱 알고리즘 (Meta Heuristic Algorithm)이다. S-MINE (Search-MINE)알고리즘은 MINE 알고리즘에 기반을 두고 있으며, 본 논문에서는 MINE 알고리즘을 TSP 에 적용하기 위하여 알고리즘을 정형화 하고, 형식화 하여 개선된 S-MINE 알고리즘을 제안하였다.
S-MINE 알고리즘은 탐색영역의 이동과 집중탐색을 강화시켰다. 탐색영역과 집중탐색을 효율적으로 활용하여 범용성이 강화된 메타 휴리스틱 알고리즘을 증명하였다.
S-MINE 알고리즘은 여러 개의 탐색지점으로 탐색을 실시하며, 탐색지점들이 이동함에 따라 각 탐색지점의 탐색밀도와 탐색영역의 크기를 변화시켜 기존 알고리즘의 문제점을 개선하고, 문제 유형의 다양성을 갖도록 하였다.
S-MINE 알고리즘의 성능을 평가하고, 개선 정도를 알아보기 위하여 TSP(Traveling Salesman Problem) 문제에 적용하여 그 결과를 고찰하였고, 기존의 메타 휴리스틱 알고리즘과의 비교실험을 통하여 객관적인 향상된 성능을 보였고, 알고리즘 안정성 실험을 통하여 S-MINE 알고리즘의 완성도를 도출하였다.
TSP 문제는 대표적인 NP_Hard 문제로 탐색 알고리즘이나 최적화 알고리즘을 실험하는데 많이 사용되고 있으며, 복잡한 사회의 많은 문제들의 표준 모델로 제시되고 있다.
본 논문에서 사용한 TSP 데이터 셋은 국제적으로 공인된 TSP예제로 알려진 TSPLIB에서 추출하였다. TSPLIB에서는 각 TSP 샘플데이터 셋마다 지금까지 알려진 최적해 값이 함께 제공되고 있어 실험 결과에 대한 평가 기준으로 사용하도록 한다.
실험을 통하여 S-MINE 알고리즘이 TSP 데이터 셋에서 최적해 탐색을 잘 하고 있음을 알았다. TSP 문제에 적용한 결과 6개의 실험 데이터 셋에서 TSPLIB에서 제공하는 알려진 최적 경로 값에 90% 이상 접근하는 탐색률을 보였다.
S-MINE 알고리즘의 객관적 성능을 평가하기 위하여 기존의 대표적인 메타 메타 휴리스틱 알고리즘인 유전 알고리즘(GA), 개체군집 최적화 알고리즘(PSO), 개미집단 최적화 알고리즘(ACO)과의 비교실험을 하였다. 그 결과 S-MINE 알고리즘이 유전 알고리즘보다 탐색시간 효율이 높게 나타났으며, 개체군집 최적화 알고리즘보다 우수한 탐색성능을 보였다. TSP 문제에 정형화된 ACO와 거의 비슷한 성능을 보였지만 1차수렴에서 거의 멈추는 특징을 가진 ACO의 단점을 보완하여 알고리즘이 지속적으로 탐색을 진행하는 특징도 잘 나타났다.
본 연구에서는 S-MINE 알고리즘의 TSP 적용실험 결과 및 분석을 통하여 S- MINE 알고리즘이 새로운 메타 휴리스틱 알고리즘으로서 가능성을 보였고, 연속형 문제 뿐만 아니라 비연속형 문제에서도 좋은 성능을 보이고 있음을 보임으로써 그 범용성을 보였다. 또한 대표적은 TSP 문제에 적용하여 봄으로써 응용문제에 적용할 수 있는 기틀을 마련하였다. 비교실험 결과 S-MINE 알고리즘이 객관적으로 좋은 성능을 보였다.
MINE 알고리즘은 범용성을 보이기 위하여 2009년 제안된 메타 휴리스틱 알고리즘 (Meta Heuristic Algorithm)이다. S-MINE (Search-MINE)알고리즘은 MINE 알고리즘에 기반을 두고 있으며, 본 논문에서는 MINE 알고리즘을 TSP 에 적용하기 위하여 알고리즘을 정형화 하고, 형식화 하여 개선된 S-MINE 알고리즘을 제안하였다.
S-MINE 알고리즘은 탐색영역의 이동과 집중탐색을 강화시켰다. 탐색영역과 집중탐색을 효율적으로 활용하여 범용성이 강화된 메타 휴리스틱 알고리즘을 증명하였다.
S-MINE 알고리즘은 여러 개의 탐색지점으로 탐색을 실시하며, 탐색지점들이 이동함에 따라 각 탐색지점의 탐색밀도와 탐색영역의 크기를 변화시켜 기존 알고리즘의 문제점을 개선하고, 문제 유형의 다양성을 갖도록 하였다.
S-MINE 알고리즘의 성능을 평가하고, 개선 정도를 알아보기 위하여 TSP(Traveling Salesman Problem) 문제에 적용하여 그 결과를 고찰하였고, 기존의 메타 휴리스틱 알고리즘과의 비교실험을 통하여 객관적인 향상된 성능을 보였고, 알고리즘 안정성 실험을 통하여 S-MINE 알고리즘의 완성도를 도출하였다.
TSP 문제는 대표적인 NP_Hard 문제로 탐색 알고리즘이나 최적화 알고리즘을 실험하는데 많이 사용되고 있으며, 복잡한 사회의 많은 문제들의 표준 모델로 제시되고 있다.
본 논문에서 사용한 TSP 데이터 셋은 국제적으로 공인된 TSP예제로 알려진 TSPLIB에서 추출하였다. TSPLIB에서는 각 TSP 샘플데이터 셋마다 지금까지 알려진 최적해 값이 함께 제공되고 있어 실험 결과에 대한 평가 기준으로 사용하도록 한다.
실험을 통하여 S-MINE 알고리즘이 TSP 데이터 셋에서 최적해 탐색을 잘 하고 있음을 알았다. TSP 문제에 적용한 결과 6개의 실험 데이터 셋에서 TSPLIB에서 제공하는 알려진 최적 경로 값에 90% 이상 접근하는 탐색률을 보였다.
S-MINE 알고리즘의 객관적 성능을 평가하기 위하여 기존의 대표적인 메타 메타 휴리스틱 알고리즘인 유전 알고리즘(GA), 개체군집 최적화 알고리즘(PSO), 개미집단 최적화 알고리즘(ACO)과의 비교실험을 하였다. 그 결과 S-MINE 알고리즘이 유전 알고리즘보다 탐색시간 효율이 높게 나타났으며, 개체군집 최적화 알고리즘보다 우수한 탐색성능을 보였다. TSP 문제에 정형화된 ACO와 거의 비슷한 성능을 보였지만 1차수렴에서 거의 멈추는 특징을 가진 ACO의 단점을 보완하여 알고리즘이 지속적으로 탐색을 진행하는 특징도 잘 나타났다.
본 연구에서는 S-MINE 알고리즘의 TSP 적용실험 결과 및 분석을 통하여 S- MINE 알고리즘이 새로운 메타 휴리스틱 알고리즘으로서 가능성을 보였고, 연속형 문제 뿐만 아니라 비연속형 문제에서도 좋은 성능을 보이고 있음을 보임으로써 그 범용성을 보였다. 또한 대표적은 TSP 문제에 적용하여 봄으로써 응용문제에 적용할 수 있는 기틀을 마련하였다. 비교실험 결과 S-MINE 알고리즘이 객관적으로 좋은 성능을 보였다.
Most of the Meta Heuristic Algorithms are made by modeling the action of the animals but S-MINE Algorithm is a Meta Heuristic that is modeled by the Human Social Activities.
The main idea is that there is a pattern in the Human Social Activities like the action of animals. But there are different...
Most of the Meta Heuristic Algorithms are made by modeling the action of the animals but S-MINE Algorithm is a Meta Heuristic that is modeled by the Human Social Activities.
The main idea is that there is a pattern in the Human Social Activities like the action of animals. But there are different characteristics between animals and humans as followed. First, humans are guided by self-interest and have a personality so humans behave independently in social. Second, humans can predict what might happen in a certain situation; therefore, we can control the necessary conditions for the future. Third, humans don’t always choose the best way. S-MINE Algorithm is designed to cut a module of high ability at a point of time. Fourth, humans can change their positions according to the necessity of the situation. It is a type of flexibility. Lastly, humans can organize a group for a purpose. We define and divide the work for the efficiency.
Self-organization is the most important idea in S-MINE algorithm. The methods which adapt systems to new environments are learning and self-organization. They can be classified into two methods because of their differences in using knowledge.
The learning method is about receiving knowledge first and then adapting the system to the new environment using its knowledge. Therefore, a change of environment has a big effect on its knowledge since it has to receive new information according to different environments. So there is close correlation between knowledge and environment in this method.
Traveling Salesman Problem (TSP) is a typical NP-hard problem of optimization. Recently TSP has been well studied by many Meta Heuristic approaches. In this paper we propose the S-MINE algorithm which applies for path searching in TSP. S-MINE is a ‘search’ algorithm and ‘simplifies’ the parameter of MINE Algorithm. To verify the optimal solution searching ability, the proposed approach has been tested using TSPLIB dataset and compared with best known solution for symmetric TSPs. And we tested it 100 times for stability of S-MINE algorithm; it is shown the potential of search Algorithm [6][13][46].
S-MINE Algorithm showed a satisfying result in searching in TSP dataset. The search rate was compared to the best solution from the TSPLIB and the results were over 90% similar. To test the complexity of the S-MINE Algorithm, we did a time stability test and a search rating stability test. According to a comparison test of S-MINE Algorithms to GA and ACO, we were able to find out about the objective ability of the S-MINE Algorithm.
Most of the Meta Heuristic Algorithms are made by modeling the action of the animals but S-MINE Algorithm is a Meta Heuristic that is modeled by the Human Social Activities.
The main idea is that there is a pattern in the Human Social Activities like the action of animals. But there are different characteristics between animals and humans as followed. First, humans are guided by self-interest and have a personality so humans behave independently in social. Second, humans can predict what might happen in a certain situation; therefore, we can control the necessary conditions for the future. Third, humans don’t always choose the best way. S-MINE Algorithm is designed to cut a module of high ability at a point of time. Fourth, humans can change their positions according to the necessity of the situation. It is a type of flexibility. Lastly, humans can organize a group for a purpose. We define and divide the work for the efficiency.
Self-organization is the most important idea in S-MINE algorithm. The methods which adapt systems to new environments are learning and self-organization. They can be classified into two methods because of their differences in using knowledge.
The learning method is about receiving knowledge first and then adapting the system to the new environment using its knowledge. Therefore, a change of environment has a big effect on its knowledge since it has to receive new information according to different environments. So there is close correlation between knowledge and environment in this method.
Traveling Salesman Problem (TSP) is a typical NP-hard problem of optimization. Recently TSP has been well studied by many Meta Heuristic approaches. In this paper we propose the S-MINE algorithm which applies for path searching in TSP. S-MINE is a ‘search’ algorithm and ‘simplifies’ the parameter of MINE Algorithm. To verify the optimal solution searching ability, the proposed approach has been tested using TSPLIB dataset and compared with best known solution for symmetric TSPs. And we tested it 100 times for stability of S-MINE algorithm; it is shown the potential of search Algorithm [6][13][46].
S-MINE Algorithm showed a satisfying result in searching in TSP dataset. The search rate was compared to the best solution from the TSPLIB and the results were over 90% similar. To test the complexity of the S-MINE Algorithm, we did a time stability test and a search rating stability test. According to a comparison test of S-MINE Algorithms to GA and ACO, we were able to find out about the objective ability of the S-MINE Algorithm.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.