Journal of the Korean Institute of Intelligent Systems (한국지능시스템학회논문지)

Korean Institute of Intelligent Systems (한국지능시스템학회)
권호 표지
DOI QR코드

DOI QR Code

A Hybrid Genetic Algorithm Using Epistasis Information for Sequential Ordering Problems

서열순서화문제를 위한 상위정보를 이용하는 혼합형 유전 알고리즘

  • 서동일 (서울대학교 컴퓨터공학부) ;
  • 문병로 (서울대학교 컴퓨터공학부)
  • Published : 2005.12.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we propose a new hybrid genetic algorithm for sequential ordering problem (SOP). In the proposed genetic algorithm, the Voronoi quantized crossover (VQX) is used as a crossover operator and the path-preserving 3-Opt is used as a local search heuristic. VQX is a crossotver operator that uses the epistasis information of given problem instance. Since it is a crossover proposed originally for the traveling salesman problem (TSP), its application to SOP requires considerable modification. In this study, we appropriately modify VQX for SOP, and develop three algorithms, required in the modified VQX, named Feasible solution Generation Algorithm, Precedence Cycle Decomposition Algorithm, and Genic Distance Assignment Method. The results of the tests on SOP instances obtained from TSPLIB and ZIB-MP-Testdata show that the proposed genetic algorithm outperforms other genetic algorithms in stability and solution quality.

본 논문에서는 서열순서화문제를 위한 새로운 혼합형 유전알고리즘을 제안한다. 제안된 유전알고리즘에서는 보로노이양자 화교차를 교차연산자로 사용하고 경로보전 3-최적화를 지역탐색 휴리스틱으로 사용한다. 보로노이양자화교차는 주어진 문제 인스턴스의 상위 정보를 이용하는 교차연산자이다. 이것은 원래 순회판매원문제를 위해서 제안된 교차연산자이기 때문에 서열순서화문제에 적용하기 위해서는 상당한 변형을 필요로 한다. 본 연구에서는 서열순서화문제에 맞도록 보로노이양자화교차를 적절히 변형하고, 변형된 보로노이양자화교차에서 필요로 하는 가능해생성알고리즘, 선행관계사이클분해알고리즘, 유전자거리지정방법 등을 개발하였다. TSPLIB와 ZIB-MP-Testdata로부터 얻어진 서열순서화문제 인스턴스들에 대한 실험결과, 제안된 유전알고리즘이 비교된 다른 유전알고리즘들에 비해서 더 안정적이고 성능이 우수한 것으로 나타났다.

Keywords

References

  1. L. F. Escudero, 'An exact algorithm for the sequential ordering problem,' European Journal of Operational Research, Vol. 37, pp. 232-253, 1988
  2. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Comple teness, W. H. Freeman and Company, 1979
  3. L. M. Gambardella and M. Dorigo, 'An ant colony system hybridized with a new local search for the sequential ordering problem,' INFORMS Journal on Computing, Vol. 12, No. 3, pp. 237-255, 2000 https://doi.org/10.1287/ijoc.12.3.237.12636
  4. S. Chen and S. Smith, Commonality and genetic algo rithms, Technical Report CMU-RI-TR-96-27, The Robotic Institute, Carnegie Mellon University, 1996
  5. 이건명, 이혜리, '서열 순서화 문제와 job shop 문제 에 대한 선행관계유지 유전연산자의 비교,' 퍼지 및 지능시스템 학회 논문지, 제14권, 5호, pp. 563-570, 2004
  6. 이혜리, 이건명, 'Sequential ordering problem과 job shop scheduling problem에 적용 가능한 선행관계유지 유전 연산자의 비교,' Journal of the Research Institute for Computer and Information Communication, Vol. 7, No. 2, 1999
  7. D. I. Seo and B. R. Moon, 'Voronoi quantized cros sover for traveling salesman problem,'In Genetic and Evolutionary Computation Conference, pp. 544 -552, 2002
  8. J. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, 1975
  9. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989
  10. 문병로, 유전알고리즘, 두양사, 2003
  11. D. I. Seo and B. R. Moon, 'A survey on chromos omal structures and operators for exploiting topol ogical linkages of genes,' In Genetic and Evolutio nary Computation Conference, pp. 1357-1368, 2003
  12. T. N. Bui and B. R. Moon, 'A new genetic approach for the traveling salesman problem,' In IEEE Conference on Evolutionary Computation, pp. 7-1 2, 1994
  13. A. Gersho and R. M. Gray, Vector Quantization a nd Signal Compression, Kluwer Academic Publish ers, 1992
  14. B. Freisleben and P. Merz, 'New genetic local search operators for the traveling salesman proble m,' In Parallel Problem Solving from Nature, pp. 890-900, 1996
  15. D. Whitley, T. Starkweather, and D. Fuquay, 'Scheduling problem and traveling salesman: the genetic edge recombination operator,' In International Conference on Genetic Algorithms, pp.133-139, 1989