개척자 기반 새로운 최적화 알고리즘: POA (Pioneer-inspired Optimization Algorithm)

정용운(Yong-Woon Jeong),박승민(Seung-Min Park),심귀보(Kwee-Bo Sim) 한국지능시스템학회 2021 한국지능시스템학회논문지 Vol.31 No.6

메타-휴리스틱 알고리즘 분야는 Evolutionary algorithm 분야로 시작하여 지금은 다양한 분야를 사용하는 새로운 메타-휴리스틱 알고리즘들이 발표되고 있다. 이렇게 발표된 메타-휴리스틱 알고리즘 중 초기에 발표된 주요 알고리즘은 수행 중에 얻은 지역 해를 중심으로 하여 새로운 해를 찾아가는 것을 기본으로 한다. 이러한 메타-휴리스틱 알고리즘의 가장 큰 문제는 하나의 지역 해를 중심으로 새로운 해를 찾으려고 할 경우 전역해를 찾지 못하는 문제가 발생할 수 있다는 것이다. 이 문제를 해결하기 위해서 본 논문에서는 해 후보들이 한점으로 수렴되는 요소를 사용하는 탐색 방식의 역으로, 하나의 해에서 점차 멀어지는 방향으로 주요 해 탐색을 수행하는 메타-휴리스틱 최적화 알고리즘을 제안한다. 우리는 이 알고리즘을 Pioneer-inspired Optimization Algorithm으로 명명하였다. 본 논문에서 제안한 알고리즘에 사용된 각 매개변수의 역할을 설명하고, 다른 유명한 메타-휴리스틱 알고리즘과의 비교를 하여 기존의 알고리즘에 비해 새로운 알고리즘이 더 좋은 결과를 냄을 보였다. The field of meta-heuristic algorithms started with evolutionary algorithms, and now new meta-heuristic algorithms using various fields are being announced. Among the meta-heuristic algorithms announced in this way, the main algorithm announced at the beginning is based on finding a new solution based on the local solution obtained during execution. For this reason, the biggest problem with meta-heuristic algorithms is that when trying to find a new solution based on one local solution, the problem of not finding a global solution may occur. To solve this problem, in this paper, we propose a meta-heuristic optimization algorithm that performs the main solution search in a direction that gradually moves away from one solution, in the reverse of the search method that uses elements where the solution candidates converge to one point. We named this algorithm the Pioneer-inspired Optimization Algorithm. The role of each parameter used in the algorithm proposed in this paper is explained and compared with other famous meta-heuristic algorithms, and it is shown that the new algorithm has better results than the existing algorithm.

An Integer Program and a Hybrid Genetic Algorithm for the University Timetabling Problem

Yuna Lee,Ilkyeong Moon 대한산업공학회 2014 대한산업공학회 추계학술대회논문집 Vol.2014 No.11

The university timetabling problem (UTP) has been studied by numerous research groups for decades. The studies were conducted through various methods including linear algorithms, mathematical models, heuristics, and metaheuristics. In this paper, an integer program, a heuristic algorithm, and a hybrid genetic algorithm are used to solve the UTP characterized by real-world constraints such as periodicity and consecutiveness. The integer program can be used to efficiently alter constraints and improve accuracy. However, it is inefficient with large problems, because the UTP is NP-hard problem, so a heuristic algorithm with left upper strategy and a hybrid genetic algorithm were developed. The first experiment showed the effects of the periodicity and consecutiveness constraints ratio and the second experiment compared the performances of the heuristic and hybrid genetic algorithms with small, medium, and large problems. The integer program was coded in FICO Xpress-IVE version 7.3, and the heuristic and the hybrid genetic algorithm were implemented in Java programming language. The results illustrate that the higher ratio of the lectures with consecutiveness constraints deducted the better objectives. For larger problems, the IP could not reach the optimum within 7200 seconds, and the hybrid genetic algorithm yielded better solutions than the heuristic algorithm.

휴리스틱 기반의 유전 알고리즘을 활용한 경로 탐색 알고리즘

고정운(Jung-Woon Ko ),이동엽(Dong-Yeop Lee) 한국게임학회 2017 한국게임학회 논문지 Vol.17 No.5

경로 탐색 알고리즘은 이동 가능한 에이전트가 게임 내의 가상 월드에서 현재 위치로부터 목적지까지 가는 경로를 탐색하는 알고리즘을 뜻한다. 기존의 경로 탐색 알고리즘은 A*, Dijkstra와 같이 비용기반으로 그래프 탐색을 수행한다. A*와 Dijkstra는 월드 맵에서 이동 가능한 노드와 에지 정보들을 필요로 해서 맵의 정보가 다양하고 많은 온라인 게임에 적용하기 힘들다. 본 논문에서는 가변환경이나 맵의 데이터가 방대한 게임에서 적용 가능한 경로 탐색 알고리즘을 개발하기 위해 맵의 정보 없이 교배, 교차, 돌연변이, 진화 연산을 통해 해를 찾는 유전 알고리즘(Genetic Algorithm, GA)을 활용한 Heuristic-based Genetic Algorithm Path–finding(HGAP)를 제안한다. 제안하는 알고리즘은 Binary-Coded Genetic Algorithm을 기반으로 하며 목적지에 더 빨리 도달하기 위해 목적지로 가는 경로를 추정하는 휴리스틱 연산을 수행하여 경로를 탐색한다. The path-finding algorithm refers to an algorithm for navigating the route order from the current position to the destination in a virtual world in a game. The conventional path-finding algorithm performs graph search based on cost such as A-Star and Dijkstra. A-Star and Dijkstra require movable node and edge data in the world map, so it is difficult to apply online games with lots of map data. In this paper, we provide a Heuristic-based Genetic Algorithm Path-finding(HGAP) using Genetic Algorithm(GA). Genetic Algorithm is a path-finding algorithm applicable to game with variable environment and lots of map data. It seek solutions through mating, crossing, mutation and evolutionary operations without the map data. The proposed algorithm is based on Binary-Coded Genetic Algorithm and searches for a path by performing a heuristic operation that estimates a path to a destination to arrive at a destination more quickly.

무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 population 초기화 방법에 관한 연구

홍성삼(Sung-Sam Hong),한명묵(Myung-Mook Han),최혁진(Hyuk-Jin Choi),문창민(Chang-Min Mun) 한국지능시스템학회 2012 한국지능시스템학회논문지 Vol.22 No.5

무기할당 문제(Weapon Target Allocation : WTA)는 전형적인 NP-Complete 문제로 공중에서 위협하는 표적에 대해 아군의 무기를 적절히 할당하는 문제이다. 이러한 NP-Complete 문제들은 주로 휴리스틱 알고리즘을 이용하여 최적해를 찾는다. 유전자 알고리즘은 대표적인 휴리스틱 알고리즘으로 다양한 도메인에서 우수한 성능을 보여주는 휴리스틱 알고리즘이다. 유전자 알고리즘의 단계 중에 population 초기화는 최초 염색체를 결정하는 문제로 유전자 알고리즘의 해의 질을 높일 수 있고, 탐색 성능을 높일 수 있으나 많은 연구가 이루어지고 있지 않는 분야이다. 따라서 본 논문에서는 WTA 문제를 해결하기 위해 유전자 알고리즘의 성능을 향상시키기 위한 population 초기화 알고리즘을 제안하고자 한다. 제안하는 알고리즘은 초기화할 때 WTA 문제 도메인의 특성을 반영하고, 우성유전자를 상속받는다. 또한, 문제 공간에서의 탐색 공간을 넓게 선정하여 질이 좋은 해를 효율적으로 찾을 수 있도록 하였다. 본 논문에서는 제안하는 알고리즘과 다른 알고리즘과의 다양한 속성의 비교분석 및 실험을 통해 성능을 분석하여 제안하는 알고리즘의 우수성을 검증하였다. 실험 결과 제안하는 알고리즘이 WTA 문제 해결에서 다른 방법들에 비해 좋은 성능을 보였다. 특히, 제안하는 알고리즘은 문제 상황에 따라 RMI 수치를 조정하여 적응성 있게 적용할 수 있기 때문에, 문제의 상황이 다양한 WTA 문제 도메인에 적용하기 적합한 알고리즘이다. The Weapon Target Allocation(WTA) problem is the NP-Complete problem. The WTA problem is that the threatful air targets are assigned by weapon of allies for killing the targets. A good solution of NP-complete problem is heuristic algorithms. Genetic algorithms are commonly used heuristic for global optimization, and it is good solution on the diverse problem domain. But there has been very little research done on the generation of their initial population. The initialization of population is one of the GA step, and it decide to initial value of individuals. In this paper, we propose to the population initialization method to improve a Genetic Algorithm. When it initializes population, the proposed algorithm reflects the characteristics of the WTA problem domain, and inherits the dominant gene. In addition, the search space widely spread in the problem space to find efficiently the good quality solution. In this paper, the proposed algorithm to verify performance examine that an analysis of various properties and the experimental results by analyzing the performance compare to other algorithms. The proposed algorithm compared to the other initialization methods and a general genetic algorithm. As a result, the proposed algorithm showed better performance in WTA problem than the other algorithms. In particular, the proposed algorithm is a good way to apply to the variety of situation WTA problem domain, because the proposed algorithm can be applied flexibly to WTA problem by the adjustment of RMI.

3축 가속도 센서를 이용한 실시간 걸음 수 검출 알고리즘

김윤경 ( Yun-kyung Kim ),김성목 ( Sung-mok Kim ),노형석 ( Hyung-suk Lho ),조위덕 ( We-duke Cho ) 한국인터넷정보학회 2011 인터넷정보학회논문지 Vol.12 No.3

본 논문에서는 3축 가속도 센서를 이용하여 사람이 보행 시 발생하는 센서 데이터를 획득하여 실시간 걸음 수 검출이 가능한 웨어러블 디바이스를 개발하였다. 피험자 59명을 대상으로 트레드밀에서 Actical 과 본 연구에서 개발된 디바이스를 착용 후 36분 동안 테스트 프로토콜에 따라 느리게 걷기, 걷기, 빠르게 걷기, 천천히 뛰기, 뛰기, 빠르게 뛰기 등의 다양한 걸음속력에서 테스트를 진행하였다. 3축 가속도 센서의 X, Y, Z축 출력 값을 하나의 대표 값으로 처리하는 신호벡터크기(Signal Vector Magnitude:SVM)를 사용하였다. 또한 정확한 걸음 수를 검출하기 위해 휴리스틱 알고리즘(Heuristic Algorithm:HA)을 제안하고 적응적인 임계값 알고리즘(Adaptive Threshold Algorithm:ATA), 적응적인 잠금 구간 알고리즘(Adaptive Locking Period Algorithm:ALPA)을 제안한다. 실험결과 제안하는 알고리즘의 걸음 수 인식률은 97.34%로 Actical의 인식률(91.74%)보다 5.6%향상 되었다. We have developed a wearable device that can convert sensor data into real-time step counts. Sensor data on gait were acquired using a triaxial accelerometer. A test was performed according to a test protocol for different walking speeds, e.g., slow walking, walking, fast walking, slow running, running, and fast running. Each test was carried out for 36 min on a treadmill with the participant wearing an Actical device, and the device developed in this study. The signal vector magnitude (SVM) was used to process the X, Y, and Z values output by the triaxial accelerometer into one representative value. In addition, for accurate step-count detection, we used three algorithms: an heuristic algorithm (HA), the adaptive threshold algorithm (ATA), and the adaptive locking period algorithm (ALPA). The recognition rate of our algorithm was 97.34% better than that of the Actical device(91.74%) by 5.6%.

시력교정 과정에서 착안된 새로운 메타휴리스틱 최적화 알고리즘의 개발

이의훈(Lee, Eui Hoon),유도근(Yoo, Do Geun),최영환(Choi, Young Hwan),김중훈(Kim, Joong-Hoon) 한국산학기술학회 2016 한국산학기술학회논문지 Vol.17 No.3

본 연구에서는 안경의 광학적 특성에서 고안된 새로운 메타휴리스틱 최적화 알고리즘인 Vision Correction Algorithm(VCA)을 개발하였다. VCA는 안경광학분야에서 수행되는 검안과 교정과정을 최적해 탐색 과정에 적용한 기법으로 근시/원시교정-밝기조정-압축시행-난시교정의 과정을 거쳐 최적화를 수행하게 된다. 제안된 VCA는 기존의 메타휴리스틱 알고리즘과 달리 현재까지 축적된 최적화 결과를 기반으로 전역탐색과 국지탐색 적용 확률, 그리고 전역탐색의 방향이 자동적으로 조정 된다. 제안된 방법을 대표적인 최적화 문제(수학 및 공학 분야)에 적용하고, 그 결과를 기존 알고리즘들과 비교하여 제시하였다. In this study, a new meta-heuristic optimization algorithm, Vision Correction Algorithm (VCA), designed according to the optical properties of glasses was developed. The VCA is a technique applying optometry and vision correction procedure to optimization algorithm through the process of myopic/hyperopic correction-brightness adjustment-compression enforcement-astigmatism adjustment. The proposed VCA unlike the conventional meta-heuristic algorithm is an automatically adjusting global/local search rate and global search direction based on accumulated optimization results. The proposed algorithm was applied to the representative optimization problem (mathematical and engineering problem) and results of the application are compared with that of the present algorithms.

Improving Heuristic Algorithms for a Batch of the Nonlinear Parameter Estimation Problems

Kihun Kim,Hyungjin Kim,Chuljin Park 한국산업경영시스템학회 2021 한국산업경영시스템학회 학술대회 Vol.2021 No.춘계

This study pursues to solve a batch of nonlinear parameter estimation (NPE) problems where a model interpreting the independent and the dependent variables is given and fixed but corresponding data sets vary. Specifically, we assume that the model does not have an explicit form and the discrepancy between a value from a data set and a corresponding value from the model is unknown. Due to the complexity of the problem, one may prefer to use heuristic algorithms rather than gradient-based algorithms, but the performance of the heuristic algorithms depends on their initial settings. In this study, we suggest two schemes to improve the performance of heuristic algorithms to solve the target problem. Most of all, we apply a Bayesian optimization to find the best parameters of the heuristic algorithm for solving the first NPE problem of the batch and apply the parameters of the heuristic algorithm for solving other NPE problems. Besides, we save a list of simulation outputs obtained from the Bayesian optimization and then use the list to construct the initial population set of the heuristic algorithm. The suggested schemes were tested in two simulation studies and were applied to a real example of measuring the critical dimensions of a 2-dimensional high-aspect-ratio structure of a wafer in semiconductor manufacturing.

A new hybrid meta-heuristic for structural design: ranked particles optimization

Kaveh, A.,Nasrollahi, A. Techno-Press 2014 Structural Engineering and Mechanics, An Int'l Jou Vol.52 No.2

In this paper, a new meta-heuristic algorithm named Ranked Particles Optimization (RPO), is presented. This algorithm is not inspired from natural or physical phenomena. However, it is based on numerous researches in the field of meta-heuristic optimization algorithms. In this algorithm, like other meta-heuristic algorithms, optimization process starts with by producing a population of random solutions, Particles, located in the feasible search space. In the next step, cost functions corresponding to all random particles are evaluated and some of those having minimum cost functions are stored. These particles are ranked and their weighted average is calculated and named Ranked Center. New solutions are produced by moving each particle along its previous motion, the ranked center, and the best particle found thus far. The robustness of this algorithm is verified by solving some mathematical and structural optimization problems. Simplicity of implementation and reaching to desired solution are two main characteristics of this algorithm.

글로벌 라우팅 유전자 알고리즘의 설계와 구현

송호정,송기용 한국융합신호처리학회 2002 융합신호처리학회 논문지 (JISPS) Vol.3 No.2

글로벌 라우팅(global routing)은 VLSI 설계 과정중의 하나로, 네트리스트의 모든 네트들을 연결하기 위하여 각 네트들을 라우팅 영역(routing area)에 할당시키는 문제이며, 글로벌 라우팅에서 최적의 해를 얻기 위해 maze routing 알고리즘, line-probe 알고리즘, shortest path 기반 알고리즘, Steiner tree 기반 알고리즘등이 이용된다. 본 논문에서는 라우팅 그래프에서 최단 경로 Steiner tree 탐색방법인 weighted network heuristic(WNH)과 이를 기반으로 하는 글로벌 라우팅 유전자 알고리즘(genetic algorithm; GA)을 제안하였으며, 제안한 방식을 시뮬레이티드 어닐링(SA) 방식과 비교, 분석하였다. Global routing is to assign each net to routing regions to accomplish the required interconnections. The most popular algorithms for global routing inlcude maze routing algorithm, line-probe algorithm, shortest path based algorithm, and Steiner tree based algorithm. In this paper we propose weighted network heuristic(WNH) as a minimal Steiner tree search method in a routing graph and a genetic algorithm based on WNH for the global routing. We compare the genetic algorithm(GA) with simulated annealing(SA) by analyzing the results of each implementation.

PSA: A Photon Search Algorithm

Yongli Liu,Renjie Li 한국정보처리학회 2020 Journal of information processing systems Vol.16 No.2

We designed a new metaheuristic algorithm named Photon Search Algorithm (PSA) in this paper, which ismotivated by photon properties in the field of physics. The physical knowledge involved in this paper includesthree main concepts: Principle of Constancy of Light Velocity, Uncertainty Principle and Pauli ExclusionPrinciple. Based on these physical knowledges, we developed mathematical formulations and models of theproposed algorithm. Moreover, in order to confirm the convergence capability of the algorithm proposed, wecompared it with 7 unimodal benchmark functions and 23 multimodal benchmark functions. Experimentalresults indicate that PSA has better global convergence and higher searching efficiency. Although theperformance of the algorithm in solving the optimal solution of certain functions is slightly inferior to that ofthe existing heuristic algorithm, it is better than the existing algorithm in solving most functions. On balance,PSA has relatively better convergence performance than the existing metaheuristic algorithms.