RISS 학술연구정보서비스

검색
다국어 입력

http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.

변환된 중국어를 복사하여 사용하시면 됩니다.

예시)
  • 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
  • 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
닫기
    인기검색어 순위 펼치기

    RISS 인기검색어

      KCI등재

      적합성 함수를 이용한 2차원 저장소 적재 문제의 휴리스틱 알고리즘 = A Heuristic Algorithm for the Two-Dimensional Bin Packing Problem Using a Fitness Function

      한글로보기

      https://www.riss.kr/link?id=A109537587

      • 0

        상세조회
      • 0

        다운로드
      서지정보 열기
      • 내보내기
      • 내책장담기
      • 공유하기
      • 오류접수

      부가정보

      국문 초록 (Abstract)

      2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다. 또한, 이들을 이용한 새로운 휴리스틱 알고리즘을 제안하였다. 끝으로 기존의 휴리스틱 또는 메타휴리스틱 기법과의 비교실험을 통해 기존의 휴리스틱 알고리즘인 와 에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘에 비해 86%의 결과가 같거나 우수한 것으로 나타났다.
      번역하기

      2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated an...

      2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다. 또한, 이들을 이용한 새로운 휴리스틱 알고리즘을 제안하였다. 끝으로 기존의 휴리스틱 또는 메타휴리스틱 기법과의 비교실험을 통해 기존의 휴리스틱 알고리즘인 와 에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘에 비해 86%의 결과가 같거나 우수한 것으로 나타났다.

      더보기

      다국어 초록 (Multilingual Abstract)

      The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing approximation algorithms, such as branch-and-bound and tabu search, have shown the low efficiency and the long execution time due to a large of iterations. To solve these problems, we first define the fitness function to simplify and increase the utility of algorithm. The function decides whether an item is packed into a given area, and as an important information for a packing strategy, the number of subarea that can accommodate a given item is obtained from the variant of the fitness function. Then we present a heuristic algorithm for 2D bin packing, constructed by the fitness function and subarea. Finally, the effectiveness of the proposed algorithm will be expressed by the comparison experiments with the heuristic and the metaheuristic of the literatures. As comparing with existing heuristic algorithms and metaheuristic algorithms, it has been found that the packing rate of algorithm BP is the same as 97% as existing heuristic algorithms, FFF and FBS, or better than them. Also, it has been shown the same as 86% as tabu search algorithm or better.
      번역하기

      The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to ...

      The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing approximation algorithms, such as branch-and-bound and tabu search, have shown the low efficiency and the long execution time due to a large of iterations. To solve these problems, we first define the fitness function to simplify and increase the utility of algorithm. The function decides whether an item is packed into a given area, and as an important information for a packing strategy, the number of subarea that can accommodate a given item is obtained from the variant of the fitness function. Then we present a heuristic algorithm for 2D bin packing, constructed by the fitness function and subarea. Finally, the effectiveness of the proposed algorithm will be expressed by the comparison experiments with the heuristic and the metaheuristic of the literatures. As comparing with existing heuristic algorithms and metaheuristic algorithms, it has been found that the packing rate of algorithm BP is the same as 97% as existing heuristic algorithms, FFF and FBS, or better than them. Also, it has been shown the same as 86% as tabu search algorithm or better.

      더보기

      분석정보

      View

      상세정보조회

      0

      Usage

      원문다운로드

      0

      대출신청

      0

      복사신청

      0

      EDDS신청

      0

      동일 주제 내 활용도 TOP

      더보기

      주제

      연도별 연구동향

      연도별 활용동향

      연관논문

      연구자 네트워크맵

      공동연구자 (7)

      유사연구자 (20) 활용도상위20명

      이 자료와 함께 이용한 RISS 자료

      나만을 위한 추천자료

      해외이동버튼