개척자 기반 새로운 최적화 알고리즘: 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.

적합성 함수를 이용한 2차원 저장소 적재 문제의 휴리스틱 알고리즘

연용호,이선영,이종연 한국정보처리학회 2009 정보처리학회 논문지 Vol.16 No.5

2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다. 또한, 이들을 이용한 새로운 휴리스틱 알고리즘을 제안하였다. 끝으로 기존의 휴리스틱 또는 메타휴리스틱 기법과의 비교실험을 통해 기존의 휴리스틱 알고리즘인 와 에 비해 97%의 결과가 같거나 우수하였으며, 타부서치 알고리즘에 비해 86%의 결과가 같거나 우수한 것으로 나타났다. The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing approximation algorithms, such as branch-and-bound and tabu search, have shown the low efficiency and the long execution time due to a large of iterations. To solve these problems, we first define the fitness function to simplify and increase the utility of algorithm. The function decides whether an item is packed into a given area, and as an important information for a packing strategy, the number of subarea that can accommodate a given item is obtained from the variant of the fitness function. Then we present a heuristic algorithm for 2D bin packing, constructed by the fitness function and subarea. Finally, the effectiveness of the proposed algorithm will be expressed by the comparison experiments with the heuristic and the metaheuristic of the literatures. As comparing with existing heuristic algorithms and metaheuristic algorithms, it has been found that the packing rate of algorithm BP is the same as 97% as existing heuristic algorithms, FFF and FBS, or better than them. Also, it has been shown the same as 86% as tabu search algorithm or better.

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.

무기할당문제에서 유전자 알고리즘의 성능을 개선하기 위한 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.

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

고정운(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.

An RNA evolutionary algorithm based on gradient descent for function optimization

Wu Qiuxuan,Zhao Zikai,Chen Mingming,Chi Xiaoni,Zhang Botao,Wang Jian,Zhilenkov Anton A,Chepinskiy Sergey A 한국CDE학회 2024 Journal of computational design and engineering Vol.11 No.4

The optimization of numerical functions with multiple independent variables was a significant challenge with numerous practical applications in process control systems, data fitting, and engineering designs. Although RNA genetic algorithms offer clear benefits in function optimization, including rapid convergence, they have low accuracy and can easily become trapped in local optima. To address these issues, a new heuristic algorithm was proposed, a gradient descent-based RNA genetic algorithm. Specifically, adaptive moment estimation (Adam) was employed as a mutation operator to improve the local development ability of the algorithm. Additionally, two new operators inspired by the inner-loop structure of RNA molecules were introduced: an inner-loop crossover operator and an inner-loop mutation operator. These operators enhance the global exploration ability of the algorithm in the early stages of evolution and enable it to escape from local optima. The algorithm consists of two stages: a pre-evolutionary stage that employs RNA genetic algorithms to identify individuals in the vicinity of the optimal region and a post-evolutionary stage that applies a adaptive gradient descent mutation to further enhance the solution’s quality. When compared with the current advanced algorithms for solving function optimization problems, Adam RNA Genetic Algorithm (RNA-GA) produced better optimal solutions. In comparison with RNA-GA and Genetic Algorithm (GA) across 17 benchmark functions, Adam RNA-GA ranked first with the best result of an average rank of 1.58 according to the Friedman test. In the set of 29 functions of the CEC2017 suite, compared with heuristic algorithms such as African Vulture Optimization Algorithm, Dung Beetle Optimization, Whale Optimization Algorithm, and Grey Wolf Optimizer, Adam RNA-GA ranked first with the best result of an average rank of 1.724 according to the Friedman test. Our algorithm not only achieved significant improvements over RNA-GA but also performed excellently among various current advanced algorithms for solving function optimization problems, achieving high precision in function optimization.

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

이의훈(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.

Improved NEH-Heuristic Job Scheduling for An Optimal System Using Meta-Heuristic GA–INSMG

Jeeva Rathanam G,Dr. A. Rajaram 보안공학연구지원센터 2016 International Journal of u- and e- Service, Scienc Vol.9 No.7

The application of simulation-optimization technique is merged with viable reality for computation of the scheduling process in a cloud environment. The optical systems are needed to be scheduled for requirement satisfaction of IOT (Internet of Things) services and demand services of QoS. Normally in the rule based scheduling algorithm are widely used to schedule the sequence process efficiently. The significance of environmental factors is simulated with meta-heuristics scheduling and processed under an accurate hypothesis of stochastic processing. In order to overcome the issues of scheduling a heuristic approach is proposed with the function to obtain a feasible high quality scheduling solution. The proposed heuristic algorithm, named INSMG, is performed and analyzed with the other heuristic algorithm. The analysis result shows the proposed algorithm efficiency and possible alternative for solving scheduling issues. This paper aims to provide a more possibilities of sequences, minimize makespan and solutions to solve the scheduling problems. Moreover the scheduling process is evaluated by the improved meta-heuristic GA for better schedules to prove the efficiency and better performances than the existing system.

A Heuristic Algorithm for Alongside Replenishment Scheduling Problem of Ship Fleet with Time Constraint

Yu Peng,He Xue-jun,Ren Ai-di 보안공학연구지원센터 2014 International Journal of Control and Automation Vol.7 No.12

The alongside replenishment scheduling problem with time constraint determining the partition of the ships, the order of replenishment and the allocation of time to the ships at the same time is analyzed. It is equivalent to a multi-stage flow shop scheduling problem with the object of maximizing the effectiveness value of ship fleet. The problem solving process is divided into three steps, and based on the analysis of the three steps, a heuristic algorithm is proposed. The algorithm firstly considers the time allocated to each ship, and then sequences the ships by heuristic rule combining greed with insertion, finally determines the ships partitioning to the port and standard side. Emulating example with different problems’ scale and time constraints shows that the proposed heuristic algorithm is superior to some other algorithms.