Abstract ▼ AI-Helper

In this study, a hybrid method is used to search the pseudo-optimal solution for the I-dimentional nesting problem. This method is composed of the genetic algorithm for the global search and a simple heuristic one for the local search near the pseudo optimal solution. Several simulation results show...

In this study, a hybrid method is used to search the pseudo-optimal solution for the I-dimentional nesting problem. This method is composed of the genetic algorithm for the global search and a simple heuristic one for the local search near the pseudo optimal solution. Several simulation results show that the hybrid method gives very satisfactory results.

In this study, a hybrid method is used to search the pseudo-optimal solution for the I-dimentional nesting problem. This method is composed of the genetic algorithm for the global search and a simple heuristic one for the local search near the pseudo optimal solution. Several simulation results show that the hybrid method gives very satisfactory results.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 연구에서는 1차원 최적 배치 문제를 다루기 위한 방법론으로 유전자 알고리즘 (GA, genetic algorithm)'"》을 변형하여 사용하였고, 몇 가지의 효율적인 경험 법칙 (heuristics)들을 고안하여 GA가 갖고 있는 한계성을 극복하고자 하였다.
• * 목적함수 : 본 연구에서는 다음과 같이 정의된 적응도(fitness)를 극대화하는 절단계획을 GA를 이용하여 탐색하고자 한다.
• 본 연구에서는 GA는 전역 탐색 능력이 우수하기 때문에 초기 해로부터 어느 정도 최적해에 도달할 때까지 해를 개선시키는데 GA를 사용하고, 경험법칙에 근거한 탐색법은 국지해 탐색에 효과적이기 때문에 탐색의 후반부에서 의사 최적해(seudo-optimal solution)로의 수렴을 위해서 사용하였다.

제안 방법

• GA 부의 총 세대교체 횟수는 200회로 제한하였고, 매 20회의 세대교체 마다 그때까지의 우수 개체들을 이용하여 새로운 개체집단을 재구성토록 하는 micro GA 개념을 추가하였다. Table 3에서 보는 바와 같이 GA는 200세대의 세대교체 결과 평균적으로 약 94.
• 본 연구에서는 1차 원 칙적배치 문제를 GA를 이용하는 방법과 경험법칙을 이용하는 방법(Heu)으로 접근하여 각각의 방법을 비교하였다. GA, Heu 각각을 단독으로 사용할 경우 대략 94%, 91% 정도의 배치 효율을 얻었다.
• 본 연구에서는 GA, Heu 각각의 장점을 이용하고 단점을 상호 보완할 수 있도록 다음과 같은 GA+Heu 형의 hybrid 법을 고안하여 사용하였다. 즉, GA의 수율이 90% 이상에 이르거나, 세대교체수가 지정횟수에 이르면 그때까지의 가장 좋은 해를 저장하고 GA는 종료한다.
• 본 연구에서는 일정 순서로 위의 3개 rule들을주어진 횟수(예, 20회) 이상 반복하도록 하였다. 이때, 이 rule들의 적용에 따른 수율 개선 양이 일정수준 이하(여】, +0.
• 본 연구에서는 절단계획 X를 조금이라도 좋은 방향으로 개선시킬 수 있는 배치의수정 방법을을 다음과 같은 경험적 방법만으로 한정하였다.
• 세대교체 횟수에 따라서 GA의 효율이 어떻게변하는가를 파악하기 위하여, 해 집단의 크기는 50 으로 하고 세대교체 수를 50, 100, 200회로 변화시켜 개체집단의 평균 수율과 최고 수율의 변화를 시뮬레이션하였다. Table 1은 시뮬레이션 결과의 요약으로서, 세대교체수를 증가시킴에 따라서 세대집단의 평균수율과 최고 수율이 향상됨을 보인다.
• 즉, 원자재 유형별 사용개수의 변화는 허용되지만, 절단 부재의 id는 고유한 것으로서 교배 후 생성된 자손에서 도 절단하고자 하는 모든 부재의 id가 반드시 한 개씩만 존재하여야 한다. 이와 같이 구속이 있는 중복순열의 유전자 상호 간의 교배를 위하여 PXC (partially matching crossover)'2, 61 교배법을 변형하여 사용하였다. 이 방법을 이용하면 치사유전자 배열을 갖는 개처】(유전자배열이 부적절한 개체: 여】, 교배에 의해서 생성된 새로운 개체가 특정 부재의 총 배치 개수를지정된 값보다 크게 하거나 작게 할 경우 등의생성을 제한할 수 있게 된다.

대상 데이터

• 3은 GA+Heu 혼합법을 적용하여 얻은 실제의 절단계획 일부와 요약이다. Table 4에서 보는 바와 같이 배치 부재는 총 35종 784개 (1010.896m)이고, 이들의 절단을 위해서 사용된 원자재는 3종 총 172개(1018.100m)이다. 짜투리 총길이는 5.

성능/효과

• 접근하여 각각의 방법을 비교하였다. GA, Heu 각각을 단독으로 사용할 경우 대략 94%, 91% 정도의 배치 효율을 얻었다. 반면에, 각각의 장점을 살리고 단점을 보완할 수 있도록 탐색의 전반부를 GA로 실시하고 후반부를 Heu로 수행토록 구성된 혼합법으로는 배치 효율 99% 이상의 훨씬 개선된 결과를 얻을 수 있따.
• 1% 보다는 대체적으로 좋은 결과이다. 그러나, GA 결과를 바탕으로 Heu를 더 적용시켜 배치를개선시키면 최고수욜이 평균적으로 99.4%에 도달하여 보다 더 개선된 배치 결과를 얻을 수 있었다.
• 반면에, Heu는 해 영역의 탐색에 있어서특정 방향으로의 국지 탐색에 효율적이다. 따라서, 초기해로부터 해영역이 어떻게 생겼는지를 모르는상황에서는 GA를 통한 전역 탐색이 효과적이고, 탐색의 후반부에서는 국자 탐색 능력이 우수한 Heu를 사용하는 것이 바람직한 것으로 나타났다.
• 위의 table 1, 2의 실행 결과에서 볼 수 있듯이, GA 자체로는 94% 정도에 다다르면 해의 개선속도가 현저히 감소하는 것으로 나타났고, Heu 만으로는 효율이 91% 정도로 비교적 낮았다.
• 수 있는가를 시뮬레이션한 결과이다. 이 결과에서 보면 Heu는 비교적 빠른 시간에 수렴하고도입된 간단한 rule들에 비하면 평균적으로는 90% 이상의 높은 수율을 보인다. 그러나, 초기해에 따라서 수렴결과가 비교적 큰 차이를 보이는 것으로 나타났다.

후속연구

• 본 연구에서 다루어진 1차원 부재의 최적 배치 문제는 고전적인 배낭문제(knapsack problem)와 유사하지만 크기가 다양한 여러 배낭을 사용하는 문제로서, 이러한 부류의 고전적인 최적해 탐색 방 법, 예컨대, 정수계획법(integer programming, IP), simplex method, graph theory 등(3)의 방법으로도 접근할 수 있는 문제이다. 그러나, 이러한 방법과의 비교는 금번의 연구에서는 다루지 않았고, 향후 좀 더 심도 있게 연구되어야 할 문제로 남겨두었다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기