Bi-Level Optimization with Intercept-Type Arcs for Low-Thrust Gravity-Assist Trajectory Design

Kim, Pureum 연세대학교 일반대학원 2026 국내박사

This dissertation addresses the problem of designing fuel-efficient low-thrust gravity-assist (LTGA) trajectories for interplanetary missions, increasingly favored for their ability to support long-duration, complex missions while minimizing propellant mass. Optimizing LTGA trajectories, which combine continuous low-level propulsion with multiple gravity assists, poses a complex optimal control problem. This research builds upon a bi-level nested optimization framework. At the inner level, low-thrust trajectory segments (arcs) are designed using a shape-based method with finite Fourier series representations, optimized via nonlinear programming solvers to generate dynamically feasible and fuel-efficient arcs. The outer level employs metaheuristics to globally optimize key parameters such as event timing (launch, arrival, and swing-bys), swing-by configurations, and constituent arc boundary conditions. This nested structure enables a comprehensive search of the solution space, yielding fuel-efficient LTGA trajectories that adhere to realistic thrust constraints. A major contribution of this dissertation is the development of novel outer-level problem formulations within the bi-level design framework that reduce the dimensionality of the search space. By selectively omitting the spacecraft’s inbound velocity boundary conditions at swing-bys, some decision variables are eliminated. Complementing this, inner-level intercept-type arc design algorithms are introduced to support the newly suggested outer-level problem models. This dimensionality reduction enables more efficient exploration of the LTGA trajectory solution space, enhancing the likelihood of outer-level optimizers reaching global or strong local minima without sacrificing access to high-quality solutions. Comprehensive benchmark studies demonstrate that the new problem models consistently enhance trajectory design performance, facilitating the discovery of superior trajectories in fewer optimization runs. Another contribution is a comparison of population-based metaheuristic algorithms—genetic algorithm, particle swarm optimization, and differential evolution—used as the outer-level solver, where differential evolution and particle swarm optimization outperformed the genetic algorithm. This study also presents a refined version of differential evolution with modified bound handling strategies for improved navigation of the solution space, delivering modest performance enhancements. These findings provide practical guidance for selecting and tuning metaheuristics in LTGA trajectory design. Verification against two-step design solutions in the literature demonstrates that the proposed bi-level framework can reliably generate preliminary LTGA trajectories that closely approximate refined solutions obtained by two-step design frameworks, while incorporating complex and realistic constraints directly in a single-step optimization process. Furthermore, in one case, the suggested bi-level optimization strategy succeeds in yielding more fuel-efficient LTGA trajectory solutions than previously reported. This highlights the robustness and reliability of the bi-level design framework for producing accurate mission parameter estimates, capabilities that are especially valuable for early-phase mission design. Altogether, the work advances LTGA trajectory optimization by enhancing the likelihood of identifying global or strong local minima in the bi-level architecture via an appropriate choice of trajectory modeling and metaheuristics to meet the increasing requirements of contemporary interplanetary mission design. 본 논문은 저추력 추진계를 탑재한 태양계 탐사선의 궤적설계를 위해 스윙바이를 활용하는 저추력 스윙바이(LTGA) 궤적의 연료최적 설계를 다룬다. LTGA 궤적설계는 저추력 궤적설계의 본질적인 난점에, 스윙바이의 활용으로 인해 발생하는 많은 수의 지역 최적 해라는 난점까지 더해진 어려운 문제로 여겨진다. 본 논문에서는 이중 레벨 중첩 최적화 프레임워크를 이용하여 LTGA 궤적설계 문제에 접근한다. 이중 레벨 최적화의 내부 레벨은 하나의 LTGA 궤적을 구성하는 다수의 부분궤적(아크)의 준최적 설계를 담당하며, 이 과정에서 각 아크의 삼차원 좌표를 유한 푸리에 급수 형태로 표현한 뒤 비선형 계획법으로 푸는 방식의 형태 기반 접근법을 사용한다. 한편, 외부 레벨에서는 LTGA 궤적의 주요한 파라미터(발사, 스윙바이, 도착 시각 및 스윙바이 파라미터)와 내부 레벨 최적화에 필요한 각 아크의 경계조건 설정용 파라미터를 메타휴리스틱 알고리즘을 통해 탐색한다. 이중 레벨 최적화 프레임워크를 이용해 연료최적 LTGA 궤적설계 문제에 접근함으로써, 저추력 추진계의 추력 제한조건을 좀 더 현실적으로 반영하면서도, 동시에 넓은 탐색 영역 내에서 전역 최적 해를 탐색할 수 있다. 본 논문에서는 이중 레벨 중첩 최적화 프레임워크의 단점 중 하나인 높은 계산 요구량을 개선하기 위해, 외부 레벨 최적화 문제와 해당 문제를 풀 때 사용하는 메타휴리스틱 알고리즘에 초점을 두었다. 본 연구에서 새로이 제안하는 방식으로 외부 레벨 최적화 문제를 정의하기 위해, 내부 레벨 최적화 문제(아크 설계 문제)에서 기존 연구에서 채택한 랑데부형 아크 대신, 아크 도착 지점에서의 속도 경계조건이 아예 정의되지 않거나 느슨하게 정의되는 인터셉트형 아크를 채택하였다. 이러한 인터셉트형 아크를 활용하여 외부 레벨 최적화 문제의 차원을 감소시킬 수 있으며, 이로 인한 탐색 공간의 축소는 LTGA 궤적 해 탐색 효율을 높여, 결과적으로 좋은 LTGA 궤적을 더 효율적으로 찾을 수 있을 것으로 기대하였다. 외부 레벨 최적화를 수행하는 메타휴리스틱 알고리즘의 선택에 따라서도 최적화 성능이 큰 영향을 받으므로, 다수의 메타휴리스틱(유전 알고리즘, 입자 군집 최적화, 차등 진화) 중 어떤 알고리즘이 LTGA 궤적설계에 적합한지 분석하였다. 추가적으로, 외부 레벨 문제에 포함된 다수의 각도 변수의 탐색 범위를 메타휴리스틱 알고리즘 내에서 필요에 따라 적절히 변형하는 전략을 도입함으로써, 메타휴리스틱의 추가적인 효율 향상을 도모하였다. 본 연구에서 새로이 제안한 인터셉트형 아크 기반 LTGA 궤적 문제 모델의 활용 및 메타휴리스틱 알고리즘의 적절한 선택을 통해 이중 레벨 최적화 프레임워크의 궤적설계 성능이 얼마나 개선되는지 분석하기 위해, 1회 또는 2회의 스윙바이가 포함되는 6종의 벤치마크 궤적설계 문제를 정의하였다. 외부 레벨 문제 모델을 변경하며 정의된 벤치마크 문제를 풀어본 결과, 새로 제안한 인터셉트형 아크 기반 LTGA 궤적 문제 모델을 활용하여 전반적으로 더 좋은 품질의 LTGA 궤적 해를 더 효율적으로 찾을 수 있다는 점을 확인하였다. 한편, 비교한 메타휴리스틱 알고리즘 중 입자 군집 최적화 알고리즘과 차등 진화 알고리즘이 좋은 성능을 보였으며, 특히 본 논문에서 제안한 각도 변수 탐색 범위 번형 전략을 반영한 차등 진화 알고리즘을 활용해 빠른 계산 시간과 높은 궤적 품질 양쪽을 조화롭게 달성할 수 있음을 확인하였다. 추가적인 검증을 위해, 더 전통적인 LTGA 궤적설계 기법인 2단계 설계 프레임워크(매우 단순화된 방식의 궤적설계 수행 후, 이를 초기 추정 해로 삼아 좀 더 정밀하게 궤적설계를 수행하는 전략)와의 비교·검증을 수행하였다. 제안한 이중 레벨 최적화 프레임워크로 획득한 해는 기존 문헌에 알려진 2단계 설계 프레임워크의 해와 매우 유사하였으며, 일부 사례에서는 2단계 설계 프레임워크의 해보다 더 낮은 연료량을 요구하는 해를 발견할 수 있었다. 또한, 2단계 설계 방식에서 필수적으로 요구되는 정밀 궤적설계 단계 없이도, 삼차원 동역학과 탐사선 추력계 제원을 잘 반영한 궤적설계를 수행할 수 있다는 장점을 확인하였다. 결론적으로, 본 연구에서 새로 고안한 문제 모델을 활용하고 적절한 메타휴리스틱 알고리즘을 선택함으로써, 이중 레벨 중첩 최적화 프레임워크 기반 LTGA 궤적설계 효율성을 향상시킬 수 있으며, 제시한 궤적설계 전략이 저추력 추진계를 탑재한 태양계 탐사선의 초기 궤적설계에 충분히 활용될 수 있음을 확인하였다.

Rural postman problem 해법을 위한 메타휴리스틱 알고리즘 비교 분석

강명주 慶熙大學校 1998 국내박사

유전자 알고리즘 기반 ETL 배치작업 스케줄링 최적화 연구

최기선 서울과학기술대학교 2017 국내석사

With the development of the Social Network and the Internet of Things (IOT), the big data era has come, in which large amounts of data that could not otherwise be imagined are generated. Data analysis is essential to discover and use value from large amounts of data. In order to do this, an ETL (Extract Transformation Loading) task to load the data to be analyzed into DW or Big Data System should be preceded. ETL schedules hundreds or thousands of jobs on the limited system resource into a sequential relationship and keeps the pre and post-relationships of the tasks at a right time. In addition, it is difficult to optimize the overall performance of the ETL, because the scheduled ETL is performed by a complex number of operations. Therefore, it is necessary to increase or decrease the data capacity due to the business change. The performance may be delayed due to the complex load. For these reasons, professional engineer is needed to optimize and operate it, but it is a realistic difficulty. Because it requires not only a lack of experienced engineers but also a high cost. In order to optimize the performance of the ETL task and maintain the optimized performance on the various changing situation, this study has developed the optimization method by the genetic algorithm which is a kind of meta - heuristic technique and artificial intelligence. Optimizing ETL performance means you can deliver data at the right time in your business, without delay. To do this, optimizing the performance of the ETL unit job is also important, but it is important to optimize the performance of batch jobs that contain the whole unit job. It is also important to minimize the number of failures due to abnormal performance loads. To do this, we used minimization of ETL batch execution time and load minimization of server CPU resources as a fitness function of genetic algorithm. ETL batch end time and number of concurrent execution tasks were used as constraints. The data of this study were used to simplify the 3 - month average CPU usage and execution time of the 260 ETL units that are being performed in the business. Also, a mathematical model is defined for genetic algorithm implementation and implemented using Java program and Maria DB. Experiments were repeated to change the parameters of the implemented program in order to obtain optimal results. This study is expected to be an important foundation for constructing and maintaining a stable big data system by loading the explosive data of the Big Data era. It is a meaningful attempt to automatically optimize the loading of ETL data of the information system. 소셜 네트워크(Social Network) 및 사물인터넷(IoT, Internet of Things)의 발전에 따라 기존에는 상상하지 못했던 대용량의 데이터가 생성되는 빅데이터 시대가 도래 하였다. 대용량의 데이터로부터 가치를 발견하고 활용하기 위해서는 데이터 분석 작업이 필수적이다. 이를 위해서는 DW나 빅데이터 시스템에 분석의 대상이 되는 데이터를 적재하는 ETL(Extract Transformation Loading) 작업이 선행되어야 한다. ETL은 한정된 시스템 자원에서 수 백, 수 천 개의 작업을 선후 관계로 묶어 정해진 시간에 작업의 선, 후 관계를 지켜가며 수행이 되도록 스케줄링 한다. 이렇게 스케줄링된 ETL은 다 수의 작업이 복잡하게 엮여서 수행이 되기 때문에 전체적인 성능을 최적화하는 것이 어려울 뿐만 아니라, 비즈니스 변화에 의한 데이터 용량의 증감이나 작업들 간의 자원 경합, 동일한 DBMS에서 수행이 되는 분석 작업과의 동시 수행이 될 경우 복합 부하로 인해 성능 지연이 발생할 수 있다. 이 때문에 실제 현업에서는 경험 많은 기술자가 이를 최적화하고 운영해야 하는 상황이지만 경험 많은 기술자가 부족할 뿐 아니라 많은 비용이 소요되기 때문에 현실적인 어려움이 있다. 본 연구에서는 ETL 작업의 성능을 최적화하고 변화하는 상황에서도 최적화된 성능을 유지하기 위하여 메타 휴리스틱 기법의 일종이며 인공지능의 한 분야인 유전자 알고리즘을 적용하여 최적화 방안을 도출하였다. ETL 성능을 최적화한다는 의미는 비즈니스 업무에서 요구하는 적시적인 시간에 지연이 없이 데이터를 제공할 수 있다는 의미이다. 이를 위해서는 ETL 작업을 구성하고 있는 단위 작업의 성능 최적화도 중요하지만 전체를 묶어둔 배치작업의 성능 최적화가 중요하다. 또한 비정상적으로 발생하는 성능부하로 인한 장애의 경우를 최소화하는 것이 중요하다. 이를 위해 유전자 알고리즘의 적합도함수로 ETL 배치작업 수행 시간 최소화와 서버 CPU 자원의 부하 최소화를 사용하였고 제약조건으로 ETL 배치작업 종료 시간, 동시 실행 작업수를 두었다. 연구 대상 데이터는 현업에서 수행되고 있는 260개 ETL 단위 작업의 3개월 평균 CPU 사용량과 실행시간 정보를 단순화하여 활용하였다. 또한 유전자 알고리즘 구현을 위하여 수학적 모델을 정의하고 이를 자바 프로그램과 Maria DB를 이용하여 구현하였다. 최적의 결과를 도출하기 위하여 구현한 프로그램의 파라미터를 변경하며 실험을 반복 수행하였다. 본 연구는 정보계 시스템의 ETL 데이터 적재작업을 자동으로 최적화하기 위한 의미 있는 시도로서 빅데이터 시대의 폭증하는 데이터를 적재하여 안정적인 빅데이터 시스템을 구축하고 유지 관리할 수 있는 중요한 기반이 될 것으로 기대한다.

유전자 알고리즘을 활용한 철도 선로배분 모델링 연구

김현승 서울市立大學校 2017 국내박사

The Korean Ministry of Land, Infrastructure, and Transport (MOLIT) recently established the Railway Capacity Allocation Guideline (RCAG) to provide answers to questions about railway capacity allocation such as who should operate the railway service, who should maintain the railway tracks, when the railway plan should be initiated, and how the railway timetable should be constructed. Korea Railroad (KORAIL) has a monopoly for providing rail transportation, which meant that railway capacity allocation until the first half of 2016 involved having to resolve conflicting interests between KORAIL and KR. This hampered research into Korean railway capacity allocation. Recently, a new railway company, Suseo High-speed Railway Corporation (SHSRC), was established and has started to provide a high-speed railway service. The Korean high-speed rail market is very competitive and hence the profits of the railway service providers depend heavily on the railway capacity allocation. Therefore, there is a pressing need to develop a fair and objective railway capacity allocation procedure. Train operation planning involves each railway company constructing its own train timetable in order to maximize its revenue. Therefore, it is highly likely that conflicts will arise between the train schedules of the different companies. The railway distributor collates the train timetables submitted by the railway companies and adjusts them so that conflicts are kept to the minimum. The aim of this study is to develop a model that can be applied to the railway capacity allocation process in Korea. The model developed here represents the railway network as a location–time network. Since an administered mechanism is used for railway capacity allocation in Korea, various requirements should be considered. In addition, we propose a genetic algorithm (GA) to solve the train timetable problem. The railway capacity distributor establishes a railway track operation plan by adjusting the train timetable requested by each railway company. If there is a conflict among the requested train schedules, the distributor attempts to resolve it using the following process. Firstly, the distributor adjusts the departure time at the station of origin for each train in order to minimize the conflict; the allowable adjustment time is typically ±5 min for passenger trains and ±30 min for freight trains. Minimizing the conflict means retaining as many feasible scheduled trains as possible in the train operation plan after adjustment by the capacity distributor. In general, the requested train schedule can only be shifted from left to right (i.e., only parallel movement of the schedule in the train graph is allowed). This rule preserves the total journey time for trains to complete their respective itineraries (known as the transit travel time). However, if an adjustment of a train’s transit travel time is needed in order to increase the feasibility of the train timetable, train overtaking is possible at stations that have sidings. When one train overtakes another, it is the train with the higher priority that does the overtaking. To prevent unrealistically excessive waiting events, we restrict the maximum waiting time during overtaking to 5 min. From the viewpoint of the capacity distributor, it makes sense to pursue the maximization of the railway access charge. In this research, we assume that the access charge for each railway section is the same. Thus, maximizing the railway access charge is equivalent to maximizing the scheduled trains after adjustment for any train conflicts. I propose a mathematical model for the train timetable problem. The optimization problem for railway capacity allocation in this paper is stated formally as follows. Firstly, set the railway network with as a set of nodes that can be stations or junctions, a detailed layout of the track at each node, and the number of tracks and the number of platforms in station . From the train timetables requested by each railway operators, given 1) the total number of trains, 2) a set of trains, 3) a set of journey sequences for train with respect to its starting location , its final destination , and the ithlocation that it passes, 4) a set of journey times for train with respect to its journey time between and , and 5) a set of commercial stops for train with respect to a commercial time at location for train . The commercial time at the starting location (or the station of origin) of train is zero. The proposed model aims to maximize the number of feasible scheduled trains by adjusting the departure time at location for train . The result of the model is the integrated timetable for railway capacity allocation. The railway capacity allocation model that was developed during this study has three hierarchical objectives. The first is to maximize the number of feasible scheduled trains, where feasibility means that there are no conflicts among the trains. Because the first objective function counts the number of feasible scheduled trains, the model searches for the most feasible optimum solution. The second objective is to minimize the total adjustment that is required for the allocation. The model looks for the solution that requires the least amount of departure-time adjustment at the station of origin. This second objective function comes into play when two or more solutions have the same number of feasible scheduled trains. The third objective is to minimize the total delayed transit time in excessive of the requested itineraries. Clearly, this third objective function is required when two or more solutions cannot be distinguished using the first and second objectives. The model determines a suitable departure time for each train from its first station. However, there are some constraints on this choice that must be considered, such as safety time, headway, and overtaking restrictions. The model searches for the earliest departure time that satisfies each constraint at each passing station for each train. Meta-heuristic methods such as GA, simulated annealing, and tabu search try to find a better solution by searching randomly; these methods are simple and easy to implement. A model with a nonlinear representation of the objective function and its constraints can also be solved using meta-heuristic. Meta-heuristic can find good solutions in many cases given sufficient computational time. Simulated annealing considers only neighborhood solutions, which may prohibit the diversification of solutions. Tabu search also uses the method of neighborhood searching, which does not guarantee finding good solutions. GA have been applied successfully to the train timetable problem. Therefore, GA was applied to the various objective functions and constraints of Korean railways. GA performance depends on how a solution is represented. In this work, a gene consist of a train and the number of genes in a chromosome equates to the number of trains requested by a railway company. Trains are assigned arrival and departure times at all stations in the order in which they pass through. These assignments are conducted in the order of the gene list. GA function consists of an initial population generation, selection, crossover, mutation, and evaluation. In initial population generaton, the algorithm randomly generates the predetermined number of chromosomes. The GA attempt to form the train timetable by considering genes sequentially in a chromosome. If a train cannot be scheduled in the current timetable, it is eliminated. The total number of genes inserted after all genes have been considered defines the fitness value of the corresponding chromosome. The selection process determines which chromosomes survive into the next generation. I select two chromosomes at random and the select the fitter one; this is known as the tournament selection method. I set the selection probability of a chromosome to 80%, which is the crossover probability in this paper. The crossover process makes it possible for offspring to inherit superior genetic characteristics from their parents by combining one part of a chromosome from each parent, which is known as one-point crossover. During the mutation process, I alter the location of a randomly selected gene in a selected chromosome to increase the diversity of the population. The selected gene is then inserted at a random position in the chromosome. I set the selection probability of a gene in the mutation process to 5%, which is the mutation probability. In the evaluation process, the algorithm calculates the fitness value of the chromosomes in the newly generated population. These GA functions are executed repeatedly until the algorithm reaches the predetermined maximum number of generations. A fictitious timetable of 388 trains was made in order to implement and solve the proposed model. I assumed that two railway companies, KORAIL and SHSRC, want to operate 258 and 130 express trains, respectively, on the Korean express railway network (KERN) during the second half of 2016. Of the 388 trains, 201 are downward and 187 are upward. Only 98 trains are feasible; each of the remaining 290 trains has a conflict (i.e., it violates one or more of constraints mentioned previously) in the test data. Author’s view is that the test data under consideration reflect the real-world scenario in which the most profitable time slots are almost the same to all railway operators, who are not motivated to negotiate unless they are forced to do so. It would appear that the most important factor affecting the uptake of railway capacity is safety time, so we chose two test scenarios: a safety time of 2 min (scenario 1) or 3 min (scenario 2). From the 388 requested trains, the GA constructed a feasible integrated train timetable for 341 trains in scenario 1 and for 303 trains in scenario 2. The results suggest that more trains could be inserted into the timetable for a shorter safety gap, which is to be expected. Of the initial 290 conflicts, the GA resolved 243 in scenario 1 and 205 in scenario 2. The two test scenarios converged to a solution within 20 iterations, which took 148 min in scenario 1 and 129 min in scenario 2. The GA converged relatively quickly with this test data. I validated the test results in two ways: a compulsory scheduling attempt, and a headway analysis. Firstly, I tried to schedule infeasible (or non-scheduled) trains compulsively, which proved impossible to do without relaxing one or more constraints in each test scenario. For the headway analysis, I calculated an average headway for feasible scheduled trains by dividing the total service (or operating) time by the number of scheduled trains. The service time was 17 h (1,020 min) per day, which resulted in average headways of 5.8 min for downward trains and 6.2 min for upward ones in scenario 1, and 6.6 min for downward trains and 6.8 min for upward ones in scenario 2. The average headway for real trains operating on the GEL is 7.2 min, which is acceptably close to what I found in analysis. Future research will include other meta-heuristic approaches to the proposed model, such as simulated annealing and tabu searching. By comparing diverse meta-heuristic methods, I expect to find a more efficient approach to the problem of railway capacity allocation. And considering diverse train type or train class might be our future study, too. 우리나라는 2016년 상반기까지는 단독 철도운영사인 Korail만이 철도서비스를 제공하여 왔기 때문에 사실상 선로배분권자의 선로배분업무는 단독 철도운영자와 선로작업시행자간의 상충 해소에 그쳤다. 이러한 이유로 선로배분업무의 복잡성이 비교적 낮았고, 선로배분과 관련한 연구나 합리적이고 공정한 선로배분을 위한 모형 개발 등이 미흡한 실정이었다. 최근 수서 고속철도라는 새로운 철도운영사가 고속철도 서비스를 제공하기 시작함에 따라 국내에도 복수 철도운영사 시대가 도래하였고, 이에 따라 이전에 비하여 공정하고 객관적인 철도 선로배분이 요구되기 시작하였다. 각 철도운영사는 자사의 수익 극대화를 위해 열차운행계획(열차시각표)을 수립한다. 따라서 복수의 철도운영사들이 수립한 열차운행계획에는 상충이 발생할 가능성이 매우 크다. 철도 선로배분자는 철도운영사들이 수립하여 제출한 열차운행계획에서 발생한 열차 간 상충을 해소하여 조정된 열차운행계획을 수립한다. 본 연구는 우리나라의 철도 선로배분절차에 적용할 수 있는 선로배분모형을 개발하는 것을 목적으로 한다. 선로배분절차는 규칙기반 선로배분, 비용기반 선로배분, 입찰에 의한 선로배분방식 3가지가 있다고 알려져있다. 우리나라는 규칙기반 선로배분방식을 사용하고 있는데, 선로배분지침에 의해서 철도운영사간 열차운행계획을 조정하고 있다. 본 연구에서는 선로배분지침에 따라 선로배분권자가 조정 가능한 범위, 철도운영사의 서비스 유지를 위한 요구조건, 안전을 위한 필수 요구조건을 검토하여 이를 모형에 반영하였다. 철도 선로배분을 모형화한 연구들은 크게 철도 네트워크를 표현하는 방식에 따라 Space-Time Network 모형, Space Network 모형, Location-Time Network 모형으로 분류할 수 있다. 본 연구에서는 다양한 목적식과 제약식의 수용 가능성, 모델의 확장성 및 구현 용이성, 결과 해석 등의 의사소통 용이성 등의 측면에서 장점이 많은 Location-Time Network 모형을 사용하였다. 한편, 이들 철도 네트워크 모형은 의사결정변수의 개수가 많아 합리적인 시간 내에 해를 도출해내지 못하는 NP-Hard문제로 알려져있어 대부분의 철도 선로배분 모형 개발 연구들은 Heuristic방법론을 사용한다. 국내 선로배분절차와 철도운영사들의 요구조건과 안전을 위한 필수조건들을 제약식으로 표현한 뒤 최대한 이들 제약식을 많이 반영할 수 있는 방법을 검토한 결과 비선형, 조건부(if~then 형태) 제약식 등을 모두 반영하기에는 Heuristic 알고리즘이 적절하다고 판단하였다. 이에 여러 Heuristic 알고리즘들을 비교 검토하여, 모형의 확장성, 제약식의 추가 및 완화 용이성, 다양한 제약식 수용 가능성의 장점이 있는 유전자 알고리즘을 사용하였다. Location-Time Network 모형과 유전자 알고리즘을 활용한 철도 선로배분 모형을 국내 고속철도(경부선, 호남선, 전라선)에 적용하여 본 결과 유전자 알고리즘 20번의 Iteration(Computing Running Time 기준 약 300분) 이내 해를 도출할 수 있는 것으로 나타났다. 해의 성능은 최초 388개의 열차 중 290개의 상충 열차가 존재하는 상태에서 최대 243개의 열차(약 83%)가 상충이 해소되었고, 상충이 해소되지 못해 제거된 열차들은 더 이상 제약식을 완화하지 않는 이상 스케줄링이 불가능한 상태로 분석되었다. 또한 현재 운행중인 KTX의 평균 운행시격 7.2분 대비 모형에 의한 열차시각표의 평균 운행시격은 5.8~6.2분으로 나타나 최소한 현재 운행시각표 보다 더 효율적인 해를 도출해내는 것으로 볼 수 있어 간접적으로 본 모형의 적정성을 확인할 수 있었다.

건물 에너지에 대한 발견적 해법과 메타 발견적 해법 최적화

서원준 성균관대학교 일반대학원 2012 국내석사

국제적으로 에너지 자원의 고갈 위기가 심화되고 지구 온난화로 인한 환경위기가 심화되면서 건물 에너지 저감에 대한 관심이 높아지고 있으며, 이에 따라 건축물의 고효율, 저에너지화가 설계과정에서의 중요한 목표로 떠오르게 되었다. 이러한 목표를 달성하기 위한 여러 가지 노력의 일환으로 설계단계에서 건물 에너지 시뮬레이션 도구의 사용이 크게 증가하였다. 건축물의 설계변수들과 주변 기후, 재실자, 실내 기기, 기계 시스템들 간의 상호작용은 매우 복잡하기 때문에 설계자는 이러한 요소들 간의 상호작용을 분석하기 위해 시뮬레이션 도구에 의존한다. 이러한 시뮬레이션 도구의 사용을 통해 설계자는 어떠한 설계변수에 대한 의사결정을 내린 뒤 그 결정에 대한 효과를 분석하고 분석 결과를 다시 의사결정에 반영하는 피드백 과정을 가진다. 피드백 기반의 의사결정 중에서, 의사결정자의 전문적 지식과 경험, 직관에 의해 최적의 대안을 찾는 발견적 해법(發見的解法, 휴리스틱, Heuristic)이 가장 일반적이다. 발견적 해법이란 어떠한 문제에 대한 해답에 빠르게 접근하기 위하여 어림짐작이나 직감, 직관적 판단, 전문적 지식을 이용하는 방법이며, 어떠한 문제 해결을 위해 접근이 용이하고(readily accessible) 느슨하게 적용(loosely applicable)가능한 정보를 활용한다. 발견적해법을 통해 가장 이상적인 해답을 구할 수 는 없지만, 제한된 정보와 시간 내에 직관적으로 실현 가능한 해답을 찾는 장점이 있다. 그러나 발견적해법을 이용한 설계 최적화의 경우, 발견적해법에 의한 해가 최적해에 얼마나 근접한지는 알 수 없다. 또한 대안을 제시하고 그 대안에 대해서만 평가하는 과정의 반복인 ‘시나리오 중심(scenario-by-scenario)' 접근이기 때문에, 제한된 수의 설계대안에 대해서만 평가가 이루어지고, 좁은 탐색범위를 갖는 단점이 존재한다. 발견적해법에 대비, 메타휴리스틱 최적화 방법이 존재한다. 메타휴리스틱은 반복적인 과정을 통해 최적화 문제 해집합의 품질을 향상시키는 방법이다. 메타휴리스틱은 발견적해법과는 달리 넓은 해공간을 탐색할 수 있으며, 다양한 문제에 적용가능하다. 본 연구에서는 발견적해법과 메타휴리스틱 방법 중의 하나인 유전알고리즘을 우체국 건물 에너지 최적화에 적용하였다. 대상 건물은 2010년 정부에서 발주한 프로젝트의 일환으로, 건물 에너지 시뮬레이션 도구인 에너지플러스를 이용하여 에너지 최적화를 달성하는 것이다. 본 연구에서는 발견적해법에 의한 최적화 결과와 유전알고리즘에 의한 최적화 결과 비교를 통하여, 두 가지 방법의 결과 차이와 장단점을 비교분석한다. In this paper, application of heuristic and meta-heuristic to energy optimization of a post office building is presented. The target building was first optimized by a heuristic approach which is based on expertise, experience and intuition of experts with the use of a whole building simulation tool, EnergyPlus. Then, the heuristic approach is compared to one of the meta-heuristic approaches, Genetic Algorithm (GA), in terms of energy savings and pros/cons of each approach. The meta-heuristic approach was completed in MATLAB platform where EnergyPlus and GA are coupled. A M-script file was developed to automate execution of simulation runs (reading output files and writing input files) with GA. It should be noted that in this study, most of design and simulation parameters were fixed and given by the client, therefore, the simulationists were not allowed to make any significant change to the original design of the building. It is not surprising that GA is much better in finding global optimum than the heuristic approach but it takes significant simulation run times as well as programming efforts. The heuristic approach has advantages such as reflection of design context in the decision making and fast communication between stakeholders.

Generation of CNN architectures using advanced parameter-setting-free HS algorithm

정용운 중앙대학교 대학원 2022 국내석사

When used as an image processing method, convolutional neural networks (CNNs) cannot verify conditions that can achieve high performance; however, they show sufficiently high performance and are used in various fields. The architecture of a CNN and various parameters determine its performance, and it is impossible to verify the number of all cases that determine the performance of the CNN. Therefore, well-known CNN models are generally used. Recently, various methods for adjusting the parameters of CNNs or generating CNN architectures have been studied in various ways. Methods using meta-heuristic algorithms often focus on parameter tuning, or the use of simple hierarchical architectures. This paper proposes a method to create a CNN model with a complex CNN architecture that can be applied to different datasets using the harmony search (HS) algorithm from among meta-heuristic algorithms. This study aimed to generate a CNN architecture using fewer computing resources and to verify the results. The main variables used when using Harmony Search can be set with advanced parameter-setting-free. In this paper, the performance during Harmony Search is adjusted in real time using advanced parameter-setting-free. To make the CNN model in units of cells, the internal and hierarchical architecture of the cell was created based on the learning of the CIFAR image dataset through HS, and the performance was confirmed by applying it to the classification of a damaged sewer pipe image dataset. 이미지를 처리하는 방법으로 사용된 Convolution neural networks(CNNs)은 높은 성능을 낼 수 있는 조건을 검증할 수 없지만 충분히 높은 성능을 보이며 다양한 분야에서 사용되고 있습니다. CNN의 성능은 CNN의 구조 및 다양한 파라미터에 따라 결정되며 이를 결정하는 모든 경우의 수를 검증하는 것은 불가능 합니다. 따라서 일반적으로는 잘 알려진 CNN 구조들을 사용하게 됩니다. 최근에는 다양한 방법으로 CNN의 파라미터를 조정하거나 CNN 구조를 생성하는 다양한 방법이 연구되고 있습니다. 이러한 방법들 중 메타 휴리스틱 알고리즘을 사용하는 방식들은 주요 파라미터의 값을 약간씩 조정하는 튜닝을 중점적으로 수행하거나 간단한 계층구조를 사용하는 경우가 많습니다. 본 논문은 메타 휴리스틱 알고리즘 중 하모니 서치 알고리즘을 사용하여 복잡한 CNN구조를 가지며 서로 다른 데이터셋에 적용이 가능한 CNN 모델을 생성하는 방법을 제안합니다. 본 연구에서는 적은 컴퓨터 연산 자원에서 적은 시간을 소요하여 CNN 구조를 생성하고 그 결과를 확인하는 것을 목표로 하였습니다. 하모니 서치 알고리즘을 사용할 때에 사용하는 주요 변수들은 advanced parameter-setting-free로 정할 수 있습니다. 본 논문에서는 parameter-setting-free를 사용하여 하모니 서치 알고리즘 수행중의 성능을 실시간으로 조정하였습니다. CNN의 모델을 Cell 단위로 만들기 위해 Cell의 내부 및 계층구조를 하모니 서치를 통해 CIFAR 이미지 데이터셋의 학습을 기준으로 제작하고 이를 손상된 하수도관 이미지 데이터셋의 분류에 적용하여 성능을 확인하였습니다.

메타휴리스틱 알고리즘을 활용한 argyrodite-type 신규 고체전해질 소재 개발

심성근 세종대학교 대학원 2022 국내석사

상대적 긴급도 계산 기반 초기해 개선을 통한 제조 스케줄링 최적화

백지원 서울대학교 대학원 2026 국내석사

본 연구는 잡샵 스케줄링 문제(Job Shop Scheduling Problem, JSSP)의 최적해를 구하기 위한 탐색 기반 알고리즘의 초기해 생성 알고리즘으로써 RUBI(Relative Urgency Based Initialization)를 제안한다. JSSP는 여러 개의 작업이 복수의 공정을 거쳐 완료되는 제조 시스템을 모델링한 대표적인 조합 최적화 문제이며, 전체 작업의 완료 시간인 makespan을 최소화하는 것을 목적으로 한다. 조선소와 같은 대규모 생산 시스템의 경우 다수의 작업 대상이 존재하고 공정 간의 복잡한 선후행 제약 조건이 존재한다는 점에서 JSSP로 모델링할 수 있다. 본 논문에서 제안하는 RUBI는 메타휴리스틱을 비롯한 탐색 알고리즘에서 JSSP 문제의 최적해에 근접한 이웃해를 다수 생성하여 초기해로 활용하는 방법으로, 그래프 기반 해 표현의 위상적 구조를 활용하여 작업 시간 특성과 무관하게 해를 생성한다는 점에서 기존 방법론과 대비된다. 이때 작업 간의 상대적 긴급도(Relative Urgency)가 높은 순으로 먼저 처리할 작업을 선택함으로써 JSSP의 해를 생성하며, 본 논문에서는 이를 RU principle로 정식화하여 제안하였다. 본 연구에서는 제안 방법의 효과성을 증명하기 위해 다수의 JSSP 인스턴스에 대해 RUBI를 적용한 유전 알고리즘 기반의 최적화를 수행하였으며, 그 결과 RUBI가 전통적인 초기해 생성 기법인 Giffler and Thompson 알고리즘과 비교하여 비슷하거나 더 우수한 수준의 초기해를 더 빠른 시간 내에 생성한다는 것을 확인하였다. 본 연구에서는 또한 JSSP 문제의 특성에 따라 RUBI의 성능 편차가 발생하는지 검증하기 위한 실험을 진행하였다. JSSP 문제의 크기를 결정하는 작업 및 설비의 개수, 설비의 분포 특성에 해당하는 Bottleneck Index 및 Flowshop Index, 작업 시간의 표준편차 등 5개 요인을 선정하여 RUBI의 makespan 개선 비율인 PIR(Performance Improvement Ratio)에 대한 영향을 평가한 결과, 작업 및 설비의 개수가 PIR에 영향을 주지 않으며, 작업 시간의 표준편차와 RUBI의 PIR 간에 음의 상관관계가 존재한다는 것을 확인하였다. 또한 RUBI의 PIR과 Bottleneck Index 사이에 2차함수적 관계가 존재하며, Flowshop Index 와는 관계가 없다는 것을 확인하였다. 마지막으로, 실제 조선소 공정 데이터를 바탕으로 생성한 JSSP 인스턴스를 활용하여 RUBI의 대규모 제조 시스템에 대한 적용 가능성을 검증하였다. 형강 공정 및 안벽 의장 공정 데이터를 바탕으로 생성한 대규모 JSSP 인스턴스에 대해 RUBI를 적용한 결과, 비교 알고리즘에 비해 빠른 시간 내에 최적해에 근접한 이웃해를 생성할 수 있음을 확인하였다. 이를 통해 RUBI가 대규모 제조 시스템 최적화 문제에 대해 효과적인 초기화 알고리즘으로 작동할 수 있음을 확인하였다. This thesis proposes Relative Urgency-Based Initialization (RUBI) as an initialization framework for search-based algorithms solving the Job Shop Scheduling Problem (JSSP). The JSSP is a representative combinatorial optimization problem that models manufacturing systems in which multiple jobs are completed through multiple operations on shared machines, typically with the objective of minimizing the makespan. RUBI generates a set of initial solutions by constructing feasible schedules that follow the Relative Urgency (RU) principle, which prioritizes operations with higher relative urgency, defined by the number of remaining operations within a job. By exploiting the topological structure of a graph-based representation and encoding solutions in a repetitive permutation form, RUBI produces diverse neighborhood solutions that are close to high-quality regions of the search space and can be directly used as an initial population for subsequent enumerative search techniques. To validate the RU principle, this study defines an RU score that quantifies the degree to which a solution satisfies RU-based ordering. Linear regression analysis reveals a strong relationship between RU score and makespan. The effectiveness of RUBI is further evaluated through genetic-algorithm-based optimization on a wide range of benchmark JSSP instances. The results show that RUBI produces initial solutions of comparable or superior quality to the classical Giffler and Thompson method while requiring less computational time. In addition, sensitivity analyses are conducted with respect to five instance characteristics: the number of jobs, the number of machines, Bottleneck Index, Flowshop Index, and processing-time variance. The results indicate that RUBI’s performance improvement ratio is independent of problem size, negatively correlated with processing-time variability, exhibits a quadratic relationship with the Bottleneck Index, and shows no significant relationship with the Flowshop Index. Finally, the applicability of RUBI to industrial-scale scheduling is demonstrated using large JSSP instances generated from shipyard production data, including profile processing and quay wall outfitting scenarios. The results confirm that RUBI efficiently generates high-quality initial populations and can serve as an effective initialization framework for large-scale manufacturing scheduling problems.

Evolutionary algorithms for tree-based network design problems

석상문 광주과학기술원 2005 국내박사

메타 휴리스틱을 이용한 (m, n)중 -(r, s) : F 시스템 정비정책에 관한 연구

신동열 국방대학교 2007 국내석사