Earticle

Traveling salesman problem is to minimize the total cost for a traveling salesman who wants to make a tour given finite number of cities along with the cost of travel between each pair them, visiting each cities exactly once before returning home. Traveling salesman problem is known to be NP-hard, and it needs a lot of computing time to get the optimal solution, so that heuristics are more frequently developed than optimal algorithms. This study suggests a hybrid parallel genetic algorithm(HPGA) for traveling salesman problem. The suggested algorithm combines parallel genetic algorithm, nearest neighbor search, and 2-opt. The suggested algorithm has been tested on 7 problems in TSPLIB and compared the results of existing methods(heuristics, meta-heuristics, hybrid, and parallel). Experimental results shows that HPGA could obtain good solution in total travel distance minimization.

본 연구에서는 코아분석자료와 다상 생산자료를 활용하여 공극률과 투과도 등의 저류층 특성을 규명하기 위해 3차원 저류 전산시뮬레이터와 실수코딩 유전자 알고리즘이 적용된 병렬처리 역산모델을 개발하였다. 개발된 모델을 3개의 층으로 구성된 불균질 저류층에 적용하여 다상 생산자료의 역산을 통해 공극률과 투과도 분포를 산출한 결과, 유전자 알고리즘은 43 세대만에 수렴하였으며 수렴 시 적합도는 0.00107로 양호한 것으로 나타났다. 산출된 최적 투과도 분포로부터 1번 층의 경우 좌측상부에서 우측하부에 걸쳐 저투과도 지역(LPZ)이 존재하고 2번과 3번 층의 경우 좌측과 우측하부에 각각 저투과도 지역이 존재하는 것이 확인되었다. 산출된 최적 공극률과 투과도 분포를 적용하여 저류 전산시뮬레이션을 통해 계산된 압력과 관측 압력을 비교한 결과, 생산정 1에서는 압력 상대오차의 합이 3.3%, 생산정 2는 5.4%로써 매우 양호한 일치를 보였다. 마지막으로, 3개의 노드로 구성된 클러스터에서 병렬처리 연산효율을 평가한 결과, 병렬처리 연산 시 일괄처리 연산에 비해 평균 2.9배 정도 연산시간이 단축됨을 알 수 있었다.

This paper presents the development of a parallelized inverse model equipped with real-coded genetic algorithm, and its application for the characterization of a heterogeneous reservoir with integration of the core analysis data and multi-phase production data. By utilizing the developed model in this study, we performed the inverse calculation with the observed production data obtained from three-layered reservoir system in order to estimate porosity and permeability distributions. As a result, number of generations for the convergence was 43 and the fitness was 0.00107. From the calculated distributions of porosity and permeability, it was confirmed to be low permeability zone located at left-top and right-bottom side in the layer 1. In the case of layer 2 and 3, its zone is located at left and right-bottom side, respectively. According to the pressure matching results, the sum of the relative errors at producer 1 and producer 2 were 3.3% and 5.4%, respectively, that is, it was found that the pressures observed at well almost identical to those calculated by the developed model. Finally, from the estimated calculating efficiency of parallel process with three-nodes cluster, it shows that parallel process was 2.9 times as fast as serial one on an average.

This work addresses the problem of instance reduction using a distributed implementation of genetic algorithms. Different existing parallel and distributed models for parallelizing genetic algorithms are investigated and applied here to solve the problem of instance reduction. a new parallel model is proposed and implemented we called Global Control Parallel Genetic Algorithm. The results showed enormous reduction in time of 90% over the other models. The resulted dataset showed an acceptable accuracy results on average over all datasets. The model achieved a better reduction in dataset size of 90.22% compared to the other models that didn’t get better that 87.91%. Thus, the proposed distributed system model for instance reduction showed better performance over all model in reducing the time and even reducing the training dataset size while maintaining the same level of accuracy of the original sequential genetic algorithm.

Based on the analysis on the basic principles and characteristics of the existing multi-objective genetic algorithm (MOGA), an improved multi-objective GA with elites maintain is put forward based on non-dominated sorting genetic algorithm (NSGA). NSGA-II algorithm theory and parallel hybrid evolutionary theory is described in detail. The design principle, process and detailed implementations of the improved MOGA are given. IMNSGA-II algorithm and NSGA-II algorithm are applied to test the performance of the two algorithms for different test function, experiments of example are preformed. Experimental results show that the improved MOGA achieved the optimal between the convergence and diversity.

This paper presents an application of the parallel Genetic Algorithm-Tabu Search (GA- TS) algorithm, and that is to search for an optimal solution of a reconfiguration in distribution systems. The aim of the reconfiguration of distribution systems is to determine the appropriate switch position to be opened for loss minimization in radial distribution systems, which is a discrete optimization problem. This problem has many constraints and it is very difficult to solve the optimal switch position because of its numerous local minima. This paper develops a parallel GA- TS algorithm for the reconfiguration of distribution systems. In parallel GA-TS, GA operators are executed for each processor. To prevent solution of low fitness from appearing in the next generation, strings below the average fitness are saved in the tabu list. If best fitness of the GA is not changed for several generations, TS operators are executed for the upper 10$\%$ of the population to enhance the local searching capabilities. With migration operation, the best string of each node is transferred to the neighboring node after predetermined iterations are executed. For parallel computing, we developed a PC-cluster system consisting of 8 PCs. Each PC employs the 2 GHz Pentium IV CPU and is connected with others through switch based rapid Ethernet. To demonstrate the usefulness of the proposed method, the developed algorithm was tested and is compared to a distribution system in the reference paper From the simulation results, we can find that the proposed algorithm is efficient and robust for the reconfiguration of distribution system in terms of the solution quality, speedup, efficiency, and computation time.

A computer model is developed to assess optimal ground water pumping rates and optimal locations of wells in a coastal region. A sharp interface model is used to simulate the freshwater and salt water flows. Drawdown, upconing, saltwater intrusion and the contamination of well are considered in this model. A genetic algorithm with parallel processing is used to identify the optimal solution.

The recognition of a person from his or her gait has been a recent focus in computer vision because of its unique advantages such as being non-invasive and human friendly. However, gait recognition is not as reliable an identifier as other biometrics. In this paper, we applied a hierarchical fair competition-based parallel genetic algorithm and a neural network ensemble to the gait recognition problem. A diverse set of potential neural networks are generated to increase the reliability of the gait recognition, not only the best ones. Furthermore, a set of component neural networks is selected to build a gait recognition system such that generalization errors are minimized and negative correlation is maximized. Experiments are carried out with the NLPR and SOTON gait databases and the effectiveness of the proposed method for gait recognition is demonstrated and compared to previous methods.

In case of the optimization problems that have many design variables, the conventional genetic algorithms(GA) fall into a trap of local minima with high probability. This problem is called the premature convergence problem. To overcome it, the parallel genetic algorithms which adopt the migration mechanism have been suggested. But it is hard to determine the several parameters such as the migration size and the migration interval for the parallel GAs. Therefore, we propose a new method to determine the migration interval automatically in this paper. To verify its validity, it is applied to some traditional mathematical optimization problems and is compared with the conventional parallel GA. It is also applied to the optimal design of the brushless DC motor for an electric wheel chair which is a real world problem and has five design variables.

This paper presents the development of reservoir characterization model equipped with parallelized genetic algorithm, and its application for a heterogeneous reservoir system with integration of the well data and multi-phase production data. A parallel processing method performed by PC-cluster was applied to the developed model in order to reduce time for an inverse calculation. By utilizing the developed model, we performed the inverse calculation with the production data obtained from three layered reservoir system to estimate porosity and permeability distribution. As a result, the pressures observed at well almost identical to those calculated by the developed model. Also, it was confirmed that parallel processing could be applied for reservoir characterization study efficiently.

In this paper, we applied the high-performance PGAP(Parallel Genetic Algorithm Processor) to recognizing rotated pattern. In order to perform this research efficiently, we used Multi-PGAP system consisted of four PGAP. In addition, we used mental rotation based on the rotated pattern recognition mechanism of human to reduce the number of operation. Also, we experimented with distinguishing specific pattern from similar coin patterns and determine rotated angle between patterns. The result showed that the development of future artificial recognition system is feasible by employing high performance PGAPS.

The Genetic Algorithm (GA), an optimization technique based on the theory of natural selection, has proven to be a relatively robust means of searching for global optimum. It converges to the global optimum point without auxiliary information such as differentiation of function. In the case of a complex problem, the GA involves a large population number and requires a lot of computing time. To improve the process, this research used parallel processing with several personal computers. Parallel process technique is classified into two methods according to subpopulation's size and number. One is the fine-grained method (FGM), and the other is the coarse-grained method (CGM). This study selected the CGM as a parallel process technique because the load is equally divided among several computers. The given design domain should be reduced according to the degree of feasibility, because mechanical system problems have constraints. The reduced domain is used as an initial design domain. It is consistent with the feasible domain and the infeasible domain around feasible domain boundary. This parallel process used the Message Passing Interface library.

유전자알고리즘을 병렬로 처리하려는 이유는 수행시간의 향상과 최적해의 향상이다. 하지만 이에 대한 연구와 응용이 적은데 이는 연구 환경이 열악하기 때문이다. 즉, 슈퍼컴퓨터와 같은 고가의 장비가 필요하며, 그것이 보편적으로 우리 주변에 있지 않다는 것이 가장 큰 장애가 되었다. 이를 극복하기 위한 방법은 에이전트라는 소프트웨어를 이용해서 유전자 알고리즘을 병렬로 처리를 하는 것이다. 이 연구에서는 이런 방법으로 유전자 알고리즘을 병렬로 처리를 하여도 수행시간의 향상과 최적해의 향상을 보일 수 있는지를 연구한다.

One of the drawbacks of GA-based structural optimization is that the fitness evaluation of a population of hundreds of individuals requiring hundreds of structural analyses at each CA generation is computational too expensive. Therefore, a parallel genetic algorithm is developed for structural optimization on a cluster of personal computers in this paper. Based on the parallel genetic algorithm, a population at every generation is partitioned into a number of sub-populations equal to the number of slave computers. Parallelism is exploited at sub-population level by allocationg each sub-population to a slave computer. Thus, fitness of a population at each generation can be concurrently evaluated on a cluster of personal computers. For implementation of the algorithm a virtual distributed computing system in a collection of personal computers connected via a 100 Mb/s Ethernet LAN. The algorithm is applied to the minimum weight design of a steel structure. The results show that the computational time requied for serial GA-based structural optimization process is drastically reduced.

유전 알고리즘은 자연 선택과 유전적 성질에 기반을 둔 알고리즘으로 기존 방법으로는 쉽게 해결할 수 없는 어려운 문제에서도 성공적으로 적용되었다. 기존의 유전 알고리즘은 해 집단이 큰 경우 시간이 많이 걸리는 문제점이 있다. 병렬 유전 알고리즘은 이러한 문제를 해결하기 위하여 제안된 기존의 유전 알고리즘의 확장이라 할 수 있다. 병렬 유전 알고리즘에서 중요한 요소는 이주와 유전 연산으로 이를 적절하게 설계함으로서 좋은 결과를 얻을 수 있다. 본 논문에서는 퍼지 논리를 이용하여 기존의 병렬 유전 알고리즘을 개선하고자 한다. 攀 †정 회 원:강남대학교 컴퓨터미디어공학부 교수††정 회 원:성균관대학교 정신통신학부 교수논문접수:2005년 11월 30일, 심사완료：2006년 2월 17일

Genetic algorithms(GA), which are based on the idea of natural selection and natural genetics, have proven successful in solving difficult problems that are not easily solved through conventional methods. The classical GA has the problem to spend much time when population is large. Parallel genetic algorithm(PGA) is an extension of the classical GA. The important aspect in PGA is migration and GA operation. This paper presents PGAs that use fuzzy logic. Experimental results show that the proposed methods exhibit good performance compared to the classical method.

This paper proposes a unit commitment scheduling method based on Parallel Genetic Algorithm(PGA). Due to a variety of constraints to be satisfied, such as the minimum up and down time constraints, the search space of the UC problem is highly nonconvex. So, we used transputer which is one of the practical parallel processors. It can give us fastness and effectiveness features of the proposed method for solving the problem. To show the effectiveness of the PGA based unit commitment scheduling, we tested results for system of 5 units and we can get desirable results.

Reliability has been considered as a one of the major design measures in various industrial and military systems. The main objective is to suggest a mathematical programming model and a hybrid parallel genetic algorithm(HPGA) for the problem that determines the optimal component reliability to maximize the system reliability under cost constraint in this study. Reliability optimization problem has been known as a NP-hard problem and normally formulated as a mixed binary integer programming model. Component structure, reliability, and cost were computed by using HPGA and compared with the results of existing meta-heuristic such as Ant Colony Optimization(ACO), Simulated Annealing(SA), Tabu Search(TS) and Reoptimization Procedure. The global optimal solutions of each problem are obtained by using CPLEX 11.1. The results of suggested algorithm give the same or better solutions than existing algorithms, because the suggested algorithm could paratactically evolved by operating several sub-populations and improving solution through swap and 2-opt processes.

본 논문에서는 유전자 알고리즘(Genetic Algorithm: GA)의 새로운 병렬화 방법을 제안 하고 있다. 기존의 병렬 유전자 알고리즘(Parallel Genetic Algorithm: PGA)은 전체 개체집단을 부개체집단 (Subpopulation)으로 나누어 해의 가능 영역을 동시에 탐색하는 것이 일반적인 방법인데 반해. 본 논문에서 제안하는 병렬화 방법은 전체 해의 영역을 나누어 각각의 영역에서 독립된 개체집단들이 서로 다른 영역을 탐색하게 하는 방법이다. 이 방법은 두 가지 단계의 병렬 유전자 알고리즘으로 구성된다. 먼저 적응교배 연산자(Adaptive Crossover Operator: ACO)를 이용한 PGA를 통해 지역해에 인접한 범위들로 해의 영역을 나누고, 이렇게 나누어진 각각의 영역들에서 다시 병렬로 GA를 적용시켜 자세하게 탐색하는 방법이다. 첫 번째 수행되는 PGA 단계에서는 탐색 시간을 줄이고 두 번째 PGA 단계에서는 보다 자세한 탐색을 하기 위해 정밀도(Precision)의 조정을 유전자 알고리즘의 병렬화에 적용하였으며. 이를 통해 빠르고 자세한 탐색이 가능한 유전자 알고리즘의 병렬화 방법을 제안하고 있다.

빅 데이터는 일반적으로 사용되는 데이터 관리 시스템으로 데이터의 처리, 수집, 저장, 탐색, 분석을 할 수 없는 큰 규모의 데이터를 말한다. 빅 데이터 기술인 맵 리듀스(MapReduce)를 이용한 병렬 GA 연구는 Hadoop 분산처리환경을 이용하여, 맵 리듀스에서 GA를 수행함으로써 GA의 병렬처리를 쉽게 구현할 수 있다. 기존의 맵 리듀스를 이용한 GA들은 GA를 맵 리듀스에 적절히 변형하여 적용하였지만 잦은 데이터 입출력에 의한 수행시간 지연으로 우수한 성능을 보이지 못하였다. 본 논문에서는 기존의 맵 리듀스를 이용한 GA의 성능을 개선하기 위해, 맵과 리듀싱과정을 개선하여 맵 리듀스 특징을 이용한 새로운 MRPGA(MapReduce Parallel Genetic Algorithm)기법을 제안하였다. 기존의 PGA의 topology 구성과 migration 및 local search기법을 MRPGA에 적용하여 최적해를 찾을 수 있었다. 제안한 기법은 기존에 맵 리듀스 SGA에 비해 수렴속도가 1.5배 빠르며, sub-generation 반복횟수에 따라 최적해를 빠르게 찾을 수 있었다. 또한, MRPGA를 활용하여 빅 데이터 기술의 처리 및 분석 성능을 향상시킬 수 있다.

Big Data is data of big size which is not processed, collected, stored, searched, analyzed by the existing database management system. The parallel genetic algorithm using the Hadoop for BigData technology is easily realized by implementing GA(Genetic Algorithm) using MapReduce in the Hadoop Distribution System. The previous study that the genetic algorithm using MapReduce is proposed suitable transforming for the GA by MapReduce. However, they did not show good performance because of frequently occurring data input and output. In this paper, we proposed the MRPGA(MapReduce Parallel Genetic Algorithm) using improvement Map and Reduce process and the parallel processing characteristic of MapReduce. The optimal solution can be found by using the topology, migration of parallel genetic algorithm and local search algorithm. The convergence speed of the proposal method is 1.5 times faster than that of the existing MapReduce SGA, and is the optimal solution can be found quickly by the number of sub-generation iteration. In addition, the MRPGA is able to improve the processing and analysis performance of Big Data technology.