How Can We Erase States Inside a Black Hole?

Hwang, Junha,Park, Hyosub,Yeom, Dong-han,Zoe, Heeseung 한국물리학회 2018 THE JOURNAL OF THE KOREAN PHYSICAL SOCIETY Vol.73 No.10

An Integer Programming-based Local Search for the Set Partitioning Problem

Junha Hwang 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.9

The set partitioning problem is a well-known NP-hard combinatorial optimization problem, and it is formulated as an integer programming model. This paper proposes an Integer Programming-based Local Search for solving the set partitioning problem. The key point is to solve the set partitioning problem as the set covering problem. First, an initial solution is generated by a simple heuristic for the set covering problem, and then the solution is set as the current solution. Next, the following process is repeated. The original set covering problem is reduced based on the current solution, and the reduced problem is solved by Integer Programming which includes a specific element in the objective function to derive the solution for the set partitioning problem. Experimental results on a set of OR-Library instances show that the proposed algorithm outperforms pure integer programming as well as the existing heuristic algorithms both in solution quality and time.

Neighbor Generation Strategies of Local Search for Permutation-based Combinatorial Optimization

Junha Hwang(황준하) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.10

지역 탐색은 다양한 조합 최적화 문제들을 해결하기 위해 활용되어 왔다. 지역 탐색에 있어서 가장 중요한 요소 중 하나가 이웃해를 생성하는 방법이다. 본 논문에서는 순열 기반 조합 최적화를 위한 지역 탐색의 이웃해 생성 전략들을 제안하고, 순회 외판원 문제를 대상으로 각 전략들의 성능을 비교한다. 본 논문에서는 총 10가지 이웃해 생성 전략을 제안한다. 기본적으로 기존에 많이 사용했던 Swap 등 4가지 전략 이외에 Rotation 등 4가지 기법을 새롭게 제안한다. 이외에 기본 이웃해 생성 전략들을 결합하여 만든 Combined1과 Combined2가 있다. 실험은 기본적인 지역 탐색을 적용하되 이웃해 생성 전략만 변경하여 수행하였다. 실험 결과, 이웃해 생성 전략에 따라 성능차이가 큰 것을 확인하였으며 아울러 Combined2의 성능이 가장 좋음을 확인하였다. 뿐만 아니라 Combined2는 기존의 지역 탐색 기법들보다 더 좋은 성능을 발휘함을 확인하였다. Local search has been used to solve various combinatorial optimization problems. One of the most important factors in local search is the method of generating a neighbor solution. In this paper, we propose neighbor generation strategies of local search for permutation-based combinatorial optimization, and compare the performance of each strategies targeting the traveling salesman problem. In this paper, we propose a total of 10 neighbor generation strategies. Basically, we propose 4 new strategies such as Rotation in addition to the 4 strategies such as Swap which have been widely used in the past. In addition, there are Combined1 and Combined2, which are made by combining basic neighbor generation strategies. The experiment was performed by applying the basic local search, but changing only the neighbor generation strategy. As a result of the experiment, it was confirmed that the performance difference is large according to the neighbor generation strategy, and also confirmed that the performance of Combined2 is the best. In addition, it was confirmed that Combined2 shows better performance than the existing local search methods.

Greedy-based Neighbor Generation Methods of Local Search for the Traveling Salesman Problem

Hwang, Junha,Kim, Yongho 한국컴퓨터정보학회 2022 韓國컴퓨터情報學會論文誌 Vol.27 No.9

The traveling salesman problem(TSP) is one of the most famous combinatorial optimization problem. So far, many metaheuristic search algorithms have been proposed to solve the problem, and one of them is local search. One of the very important factors in local search is neighbor generation method, and random-based neighbor generation methods such as inversion have been mainly used. This paper proposes 4 new greedy-based neighbor generation methods. Three of them are based on greedy insertion heuristic which insert selected cities one by one into the current best position. The other one is based on greedy rotation. The proposed methods are applied to first-choice hill-climbing search and simulated annealing which are representative local search algorithms. Through the experiment, we confirmed that the proposed greedy-based methods outperform the existing random-based methods. In addition, we confirmed that some greedy-based methods are superior to the existing local search methods.

4륜 인휠 독립 구동 차량의 TCS 제어 개발

황준하(Junha Hwang) 한국자동차공학회 2022 한국자동차공학회 학술대회 및 전시회 Vol.2022 No.11

C 코딩 스타일 검증기의 설계 및 구현

황준하(Junha Hwang) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.2

지금까지 C 언어에 대한 다양한 코딩 스타일이 제시되어 왔으나 코딩 스타일에 대한 종합적인 검토가 부족하였다. 본 논문에서는 대표적인 C 코딩 스타일에 포함된 코딩 규칙들을 분석하고 그 외에 새로운 코딩 규칙들을 추가함으로써 새로운 C 코딩 스타일을 제안하고 있다. 아울러 CStyler라고 명명한 자동화된 C 코딩 스타일 검증기를 설계하였으며 Lex와 Yacc를 활용하여 이를 구현하였다. CStyler는 전처리가 수행된 후의 코드뿐만 아니라 전처리가 수행되기 전의 소스 코드에 대해서도 검증이 가능하도록 설계되었으며, 사용자가 새로운 코딩 규칙을 추가할 수 있도록 함으로써 유연성을 개선하였다. 본 논문에서 제시한 코딩 스타일과 코딩 스타일 검증기는 C 언어 교육과 향후 정적 분석 도구를 개발하고 확장하기 위한 연구에 활용될 수 있을 것으로 사료된다. Various coding styles for C language have been proposed so far but there has been a lack of synthetic review about them. In this paper. I propose a new C coding style by analyzing coding rules that are included in the representative C coding styles and by adding new coding rules besides them. In addition. I designed an automated C coding style checker named CStyler which was implemented using Lex and Yacc. It is designed to be able to verify unpreprocessed source code as well as preprocessed source code. And I improved its flexibility by being able to add a new coding rule by end user. I think that the new C coding style and coding style checker. CStyler. can be utilized for education and for future research to develop and extend a static analysis tool.

정수계획법과 휴리스틱 탐색기법의 결합에 의한 승무일정계획의 최적화

황준하(Junha Hwang),박춘희(Choonhee Park),이용환(Yong Hwan Lee),류광렬(Kwang Ryel Ryu) 한국정보과학회 2002 정보과학회 컴퓨팅의 실제 논문지 Vol.8 No.2

승무일정계획이란 특정 기간동안 운행할 차량들을 대상으로 각 차량마다 필요로 하는 승무원을 배정하는 계획을 말한다. 최적 승무일정계획의 수립은 일반적으로 가능한 모든 종류의 개별 근무표들을 생성한 다음 이들을 대상으로 투입 승무원의 수가 최소화 될 수 있는 최적조합을 선정하는 방식으로 이루어지고 있다. 근무표 최적조합의 선정을 위한 종래의 기법들은 주로 선형계획법에 기반을 두고 있으나, 목적함수에 선형식으로 표현하기 어려운 요소가 포함되어 있을 경우 적용이 어렵다는 문제가 있다. 본 논문은 선형식으로 표현하기 어려운 목적함수를 포함할 뿐만 아니라 동원 가능한 승무원의 수가 제한되어 있는 경우에도 계획 수립이 가능하도록, 기존의 정수계획법에 휴리스틱 탐색기법을 결합하는 방안을 제시한다. 휴리스틱 탐색은 정수계획법에 의해 일차로 도출된 계획의 불완전한 부분을 교정하기 위해 반복적 개선 탐색을 수행하는 방식으로 이루어진다. 기존의 방법으로 해결이 어려운 실제 현장의 승무일정계획 문제를 대상으로 한 실험 결과, 본 논문의 방법은 전문가의 수작업 결과보다 더 좋은 수준의 계획을 빠른 시간 내에 수립할 수 있음을 확인하였다. Crew scheduling is the problem of pairing crews with each of the vehicles in operation during a certain period of time. A typical procedure of crew schedule optimization consists of enumerating all possible pairings and then selecting the subset which can cover all the operating vehicles, with the goal of minimizing the number of pairings in the subset. The linear programming approach popularly adopted for optimal selection of pairings, however, is not applicable when the objective function cannot be expressed in a linear form. This paper proposes a method of integrating integer programming and heuristic search to solve difficult crew scheduling problems in which the objective function cannot be expressed in linear form and at the same time the number of crews available is limited. The role of heuristic search is to improve the incomplete solution generated by integer programming through iterative repair. Experimental results show that our method outperforms human experts in terms of both solution quality and execution time when applied to real world crew scheduling problems which can hardly be solved by traditional methods.

이웃해 탐색 기법을 이용한 Maximal Covering 문제의 해결

황준하(Junha Hwang) 한국컴퓨터정보학회 2006 韓國컴퓨터情報學會論文誌 Vol.11 No.1

지금까지 maximal covering 문제를 해결하기 위해 다양한 기법들이 적용되어 왔다. 타부 탐색 역시 그 중의 하나이다. 그러나 기존 연구에서는 타부 탐색을 비롯한 언덕오르기 탐색이나 시뮬레이티드 어닐링과 같은 이웃해 탐색 기법들에 대한 종합적인 분석과 성능 향상을 위한 노력이 부족하였다. 본 논문에서는 다양한 실험과 분석을 통해 이웃해 탐색 기법들의 성능을 향상시키기 위한 방안을 소개한다. 기본적으로 모든 이웃해 탐색 기법들은 k-exchange 이웃해 생성 방법을 사용하고 있으며 다양한 파라미터 설정에 따라 각 기법의 성능이 어떻게 달라지는가를 분석하였다. 실험 결과 단순 언덕오르기 탐색과 시뮬레이티드어닐링이 다른 기법들에 비해 훨씬 우수한 탐색 성능을 보였으며, 일반적인 경우와는 달리 단순 언덕오르기 탐색이 시뮬레이티드 어닐링과 비슷한 성능을 보임을 확인하였다. Various techniques have been applied to solve the maximal covering problem. Tabu search is also one of them. But, existing researches were lacking of the synthetic analysis and the effort for performance improvement about neighborhood search techniques such as hill-climbing search and simulated annealing including tabu search. In this paper, I introduce the way to improve performance of neighborhood search techniques through various experiments and analyses. Basically, all neighborhood search algorithms use the k-exchange neighborhood generation method. And I analyzed how the performance of each algorithm changes according to various parameter settings. Experimental results have shown that simple hill-climbing search and simulated annealing can produce better results than any other techniques. And I confirmed that simple hill-climbing search can produce similar results as simulated annealing unlike general case.

적분 슬라이딩 모드 제어기를 이용한 매니퓰레이터의 영상기반 비주얼 서보잉

황준하(Junha Hwang),좌동경(Dongkyoung Chwa) 대한전기학회 2021 대한전기학회 학술대회 논문집 Vol.2021 No.10

본 논문에서는 영상기반의 정보를 로봇에 적용하는 매니퓰레이터 시스템을 설계하고, 외란에 강인한 적분 슬라이딩 모드 제어기로 성능을 향상시킨다. 영상기반으로 실제 목표물의 위치를 계속해서 추종하며 목표물과 입력값의 차이인 특징점 오차를 통해 모의실험으로 제어성능을 검증한다.

심층 Q-학습을 활용한 8-퍼즐 문제의 해결

황준하(Junha Hwang) 한국지능시스템학회 2021 한국지능시스템학회논문지 Vol.31 No.1

일반적으로 최적화 문제는 다양한 탐색 알고리즘을 통해 해결되어 왔다. 본 연구는 “학습을 통해 최적해를 찾을 수 있을까?”라는 질문으로부터 출발하였으며, 기계 학습을 활용한 최적화 문제의 해결 방향을 제시한다. 이를 위해 본 논문에서는 심층 강화 학습을 활용하여 대표적인 최적화 문제인 8-퍼즐 문제를 해결하는 세 가지 방안을 제시한다. 첫 번째는 모든 상태에 대해 최적의 행동을 학습하는 것이고, 두 번째는 A* 탐색을 위한 휴리스틱 함수를 학습하는 것이다. 마지막으로 세 번째는 특정 상태에서 목표 상태까지의 최적 경로를 학습한다. 세 가지 학습 모두 대표적인 심층 강화 학습 알고리즘인 심층 Q-학습을 기반으로 학습을 수행한다. 실험 결과에 의하면 모든 상태에 대한 최적의 행동을 학습하는 것은 쉽지 않은 것으로 보인다. 그러나 A* 탐색을 위한 휴리스틱 함수의 학습뿐만 아니라 특정 상태에서 목표 상태까지의 최적 경로를 학습하는 것 또한 8-퍼즐 문제 해결을 위해 매우 효과적임을 확인하였다. In general, optimization problems have been solved by various search algorithms. This research started from the question “Can we find optimal solutions through learning?,” and suggests the direction to solve optimization problems using machine learning. To this end, this paper proposes three ways to solve the 8-puzzle problem, which is a representative optimization problem, by using deep reinforcement learning. The first is learning optimal actions for all states, and the second is learning a heuristic function for A* search. Finally, the third one learns an optimal path from a specific state to the goal state. All three types of learning are preformed based on deep Q-learning, a representative deep reinforcement learning algorithm. Experimental results show that learning optimal actions for all states seems not easy. However, it was confirmed that not only learning a heuristic function for A* search but also learning an optimal path from a specific state to the goal state is very effective for solving the 8-puzzle problem.