최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기한국지능시스템학회 논문지 = Journal of Korean institute of intelligent systems, v.22 no.4, 2012년, pp.414 - 424
전소영 (한국과학기술원 전산학과) , 김용혁 (광운대학교 컴퓨터소프트웨어학과)
Finding or automatically generating problem instance is useful for algorithm analysis/test. The topic has been of interest in the field of hardware/software engineering and theory of computation. We apply objective value-distance correlation analysis to problem spaces, as previous researchers applie...
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
문제 인스턴스란? | 문제 인스턴스(problem instance)는 문제를 푸는 알고리즘에 구체적으로 주어진 입력 데이터이다. 가령(1,4,3,2) 이라는 순열을 (1,2,3,4)라는 순열로 정렬해야 한다면 (1,4,3,2)가 문제 인스턴스가 된다. | |
문제 인스턴스의 목적값의 정의는? | 본 연구에서는 해(解) 공간에 사용된 목적값-거리 상관관계 분석을 문제 인스턴스 공간에 적용하였다. 문제 인스턴스의 목적값은 문제에 따라 알고리즘의 수행 시간과 최적해를 잘 구하는 정도로 정의하였다. 이러한 정의는 문제 인스턴스의 난이도로 해석할 수 있다. | |
문제 인스턴스 탐색은 문제 인스턴스에 관해 정의된 목적 함수로 얻은 목적값을 최대화 혹은 최소화하는 문제 인스턴스를 찾는 문제로 정식화될 수 있는데, 이때 예를 설명하시오. | 문제 인스턴스 탐색은 문제 인스턴스에 관해 정의된 목적 함수로 얻은 목적값(objective value)을 최대화 혹은 최소화하는 문제 인스턴스를 찾는 문제로 정식화(formulate) 될 수 있다. 예를 들어 알고리즘의 최악의 성능을 알기 위해서 문제 인스턴스의 목적 함수를 문제 인스턴스를 푸는데 걸리는 시간으로 정의해보자. 그러면 목적값을 최대화하는 인스턴스를 탐색함으로써 최악의 성능을 실험적으로 확인할 수 있다. |
D. Saab, Y. Saab, and J. Abraham. CRIS: A test cultivation program for sequential VLSI circuits. In Proceedings of 1992 IEEE/ACM International Conference on Computer Aided Design, pp. 216-219, 1992.
M. Srinvas and L. Patnaik. A simulation-based test generation scheme using genetic algorithms. In Proceedings International Conference VLSI Design, pp. 132-135, 1993.
E. Rudnick, J. Patel, G. Greenstein, and T. Niermann. Sequential circuit test generation in a genetic algorithm framework. In Proceedings of the 31st Annual Conference on Design Automation (DAC '94) , pp. 698-704, 1994.
F. Corno, E. Sanchez, M. Sonza Reorda, and G. Squillero. Automatic test program generation - a case study. IEEE Design & Test, 21(2):102-109, 2004.
P. McMinn, Search-based software test data generation: a survey, Software Testing Verification and Reliability, 14(2):105-156, 2004.
C. Cotta and P. Moscato. A mixed-evolutionary statistical analysis of an algorithm's complexity. Applied Mathematics Letters, 16(1):41-47, 2003.
J. Hemert. Evolving combinatorial problem instances that are difficult to solve. Evolutionary Computation, 14(4):433-462, 2006.
M. Johnson and A. Kosoresow. Finding worst-case instances of, and lower bounds for, online algorithms using genetic algorithms. Lecture Notes in Computer Science, 2557:344-355, 2002.
S.-Y. Jeon and Y.-H. Kim. A genetic approach to analyze algorithm performance based on the worst-case instances. Journal of Software Engineering and Applications, 3(8):767-775, 2010.
S.-Y. Jeon and Y.-H. Kim. Finding the best-case instances for analyzing algorithms: comparing with the results of finding the worst-case instance. In Proceedings of the Korea Computer Congress 2010, vol. 37, no. 2(C), pp. 145-150, 2010. (in Korean)
문병로, 쉽게 배우는 유전 알고리즘-진화적 접근법, 한빛미디어, 2008.
K. D. Boese, A. B. Kahng, and S. Muddu. A new adaptive multi-start technique for combinatorial global optimization. Operations Research Letters, 16(2):101-113, 1994.
Y.-H. Kim and B.-R. Moon. Investigation of the fitness landscapes in graph bipartitioning: an empirical study. Journal of Heuristics, 10(2): 111-133, 2004.
T. Jones and S. Forrest. Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms. In Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 184-192, 1995.
C. Reeves and T. Yamada. Genetic algorithms, path relinking, and the flowshop sequencing problem. Evolutionary Computation, 6(1):45-60, 1998.
T. Stutzle and H. Hoos. MAX-MIN Ant System. Future Generation Computer Systems, 16(8):889-914, 2000.
S.-Y. Jeon and Y.-H. Kim. New trials on test data generation: analysis of test data space and design of improved algorithm, In Proceedings of the International Conference on Software Engineering Research and Practice, pp. 352-356, 2011.
M. Main and W. Savitch. Data Structures and Other Objects Using C++, 3rd ed., Pearson/Addison-Wesley, 2004.
R. Sedgewick. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd ed., Addison-Wesley, 1998.
D. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
R. Neapolitan, and K. Naimipour. Foundations of Algorithms Using C++ Pseudocode, 3rd ed., Jones and Bartlett Publishers, Inc., 2008.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.