Cooperative Coevolutionary Algorithm-Based Model Predictive Control Guaranteeing Stability of Multirobot Formation

Seung-Mok Lee,Hanguen Kim,Hyun Myung,Xin Yao IEEE 2015 IEEE transactions on control systems technology Vol.23 No.1

<P>This paper proposes a novel cooperative coevolutionary algorithm (CCEA)-based distributed model predictive control (MPC) that guarantees asymptotic stability of multiagent systems whose state vectors are coupled and nonseparable in a cost function. While conventional evolutionary algorithm-based MPC approaches cannot guarantee stability, the proposed CCEA-based MPC approach guarantees asymptotic stability regardless of the optimality of the solution that the CCEA-based algorithm generates with a small number of individuals. To guarantee stability, a terminal state constraint is found, and then a repair algorithm is applied to all candidate solutions to meet the constraint. Furthermore, as the proposed CCEA-based algorithm finds the Nash-equilibrium state in a distributed way, robots can quickly move into a desired formation from their locations. A novel dynamic cooperatively coevolving particle swarm optimization (CCPSO), dynamic CCPSO (dCCPSO) in short, is proposed to deal with the formation control problem based on the conventional CCPSO, which was the most recently developed algorithm among CCEAs. Numerical simulations and experimental results demonstrate that the CCEA-based MPC greatly improves the performance of multirobot formation control compared with conventional particle swarm optimization-based MPC.</P>

폐기물 입지 및 경로 문제를 위한 협력적 공진화 알고리즘과 이웃해 탐색의 결합해법

한용호(Yongho Han) 한국SCM학회 2015 한국SCM학회지 Vol.15 No.2

This paper addresses with a waste location-routing problem with multiple capacitated depots and one uncapacitated vehicle per depots and formulates the problem into a binary integer programming model in order to minimize the total cost. We suggest a cooperative coevolutionary algorithm (CCEA) combined with a local search to make location and routing decisions simultaneously. First, a solution is represented using two populations of chromosomes. One population represents an assignment configuration that gives the set of open depots. The other population is a permutation fixing the rank of a customer on a given route. And fitness function, fitness evaluation pattern, and genetic operators are defined. Then, local search (LS) is adopted to generate a local solution by exploring the neighborhood of an initial solution given by CCEA. We use four neighborhood structures including insertion move and swap move in LS. Finally, we combine the CCEA with the LS and suggest a CCEA-based hybrid algorithm. A computational study is carried out to compare our algorithm with other algorithms. Numerical experiments show that our CCEA-based hybrid algorithms outperform GA-based algorithms and CCEA-based hybrid algorithms outperform pure CCEAs.

협력적 공진화 알고리즘에 기반한 다단계 공급사슬 네트워크의 설계

한용호(Yongho Han) 한국SCM학회 2011 한국SCM학회지 Vol.11 No.2

We consider a network design problem in a four tier supply chain consisting of suppliers, plants, distribution centers and customers. We suggest a cooperative coevolutionary algorithm(CCEA) to solve the problem. First, the problem is decomposed into three subproblems for each of which the chromosome population is created correspondingly. Each chromosome in a population is represented as an integer denoting a supply node. Then an algorithm generating a solution from a chromosome representation is suggested. Also an algorithm evaluating the performance of a solution is suggested. Finally we set the operator of selection, crossover, and mutation. An experimental study is carried out to compare the performance of the CCEA with that of a genetic algorithm. The results show that the CCEA tends to generate better solutions than genetic algorithms.

공급사슬 네트워크 설계를 위한 협력적 공진화 알고리즘에서 집단들간 상호작용방식에 관한 연구

한용호(Yongho Han) 한국경영과학회 2014 經營 科學 Vol.31 No.3

Cooperative coevolutionary algorithm (CCEA) has proven to be a very powerful means of solving optimization problems through problem decomposition. CCEA implies the use of several populations, each population having the aim of finding a partial solution for a component of the considered problem. Populations evolve separately and they interact only when individuals are evaluated. Interactions are made to obtain complete solutions by combining partial solutions, or collaborators, from each of the populations. In this respect, we can think of various interaction modes. The goal of this research is to develop a CCEA for a supply chain network design (SCND) problem and identify which interaction mode gives the best performance for this problem. We present general design principle of CCEA for the SCND problem, which require several co-evolving populations. We classify these populations into two groups and classify the collaborator selection scheme into two types, the random-based one and the best fitness-based one. By combining both two groups of population and two types of collaborator selection schemes, we consider four possible interaction modes. We also consider two modes of updating populations, the sequential mode and the parallel mode. Therefore, by combining both four possible interaction modes and two modes of updating populations, we investigate seven possible solution algorithms. Experiments for each of these solution algorithms are conducted on a few test problems. The results show that the mode of the best fitness-based collaborator applied to both groups of populations combined with the sequential update mode outperforms the other modes for all the test problems.

역물류 네트워크 모델의 최적화를 위한 협력적 공진화 알고리즘

한용호(Yong Ho Han) 한국경영과학회 2010 經營 科學 Vol.27 No.3

We consider a reverse logistics network design problem for recycling. The problem consists of three stages of transportation. In the first stage products are transported from retrieval centers to disassembly centers. In the second stage disassembled modules are transported from disassembly centers to processing centers. Finally, in the third stage modules are transported from either processing centers or a supplier to a manufacturer, a recycling site, or a disposal site. The objective is to design a network which minimizes the total transportation cost. We design a cooperative coevolutionary algorithm to solve the problem. First, the problem is decomposed into three subproblems each of which corresponds to a stage of transportation. For subproblems 1 and 2, a population of chromosomes is constructed. Each chromosome in the population is coded as a permutation of integers and an algorithm which decodes a chromosome is suggested. For subproblem 3, an heuristic algorithm is utilized. Then, a performance evaluation procedure is suggested which combines the chromosomes from each of two populations and the heuristic algorithm for subproblem 3. An experiment was carried out using test problems. The experiments showed that the cooperative coevolutionary algorithm generally tends to show better performances than the previous genetic algorithm as the problem size gets larger.

2 단계 수송문제에 대한 협력적 공진화 알고리즘 기반의 혁신적 해법

한용호 경성대학교 산업개발연구소 2009 산업혁신연구 Vol.25 No.4

본 연구에서는 제품의 공급지, 유통센터 및 수요지의 3 계층으로 이루어진 공급사슬 상에서 각 공급지와 각 유통센터간의 1단계 수송비용, 각 유통센터와 각수요지 사이의 2단계 수송비용 및 유통센터의 운영비용의 합을 최소화할 수 있는 제품의 수송계획 문제를 대상으로 한다. 본 연구에서는 유전 알고리즘의 선행 연구를 바탕으로 이 문제에 대하여 우수한 해를 생성할 수 있는 협력적 공진화 알고리즘을 다음과 같이 설계한다. 먼저 이 문제를 2개의 부분문제로 분할하고, 각 부분문제에 대하여 우선순위 기반의 표현을 사용한 염색체 개체들로써 모집단을 구성한다. 그리고 두 모집단내 각 개체에 대한 적합도의 평가 원리를 소개하고, 사용할 적합도 함수를 설정하고, 각 개체에 대한 적합도 평가 알고리즘을 제시한다. 마지막으로 두 모집단의 세대교체에 사용될 선택, 교배 및 돌연변이 연산자를 선정한다. 이러한 설계를 기반으로 만들어진 협력적 공진화 알고리즘을 기존의 유전 알고리즘과 그 성능을 비교해 보기 위하여 여러 개의 테스트 문제에 대하여 반복 실험한다. 그 결과, 협력적 공진화 알고리즘은 문제의 크기가 커짐에 따라 기존의 유전 알고리즘에 비해 해의 평균적인 품질이나 해의 변동성 면에서 상대적으로 더 우수한 해를 얻을 수 있었다. 본 연구에서 제시한 협력적 공진화 알고리즘 기반의 해법은 현실적인 다단계 수송문제에도 확장 적용될 수 있다.

순열 표현 기반의 협력적 공진화 알고리즘을 사용한 다단계 공급사슬 네트워크의 설계

한용호(Yongho Han) 한국경영과학회 2012 經營 科學 Vol.29 No.2

This paper addresses a network design problem in a supply chain system that involves locating both plants and distribution centers, and determining the best strategy for distributing products from the suppliers to the plants, from the plants to the distribution centers and from the distribution centers to the customers. This paper suggests a cooperative coevolutionary algorithm (CCEA) approach to solve the model. First, the problem is decomposed into three subproblems for each of which the chromosome population is created correspondingly. Each chromosome in each population is represented as a permutation denoting the priority. Then an algorithm generating a solution from the combined set of chromosomes from each population is suggested. Also an algorithm evaluating the performance of a solution is suggested. An experimental study is carried out. The results show that our CCEA tends to generate better solutions than the previous CCEA as the problem size gets larger and that the permutation representation for chromosome used here is better than other representation.

5개 모집단의 협력적 공진화 알고리즘을 사용한 다단계 공급사슬 네트워크 설계

한용호(Yongho Han) 한국SCM학회 2012 한국SCM학회지 Vol.12 No.2

This paper suggests an efficient cooperative coevolutionary algorithm(CCEA) consisting of five populations of chromosomes to solve the multi-stage supply chain network design problem. The mathematical model is described. The problem is broken down into five subproblems. For each subproblem, a population of chromosomes is created and each chromosome is represented as a permutation of integers. For each chromosome in a population, a decoding method is suggested to get a partial solution to the corresponding subproblem. Then the procedure of combining all chromosomes from each of the five populations to achieve a feasible solution is suggested. Both the method of deciding the collaborator of a population and the method of combining it with other collaborators is designed to evaluate the suitability of a given chromosome. An experimental study is carried out. The results show that our CCEA generates better performance than the previous CCEA for larger problems and that the difference in performance between two algorithms tends to get larger.

다중 집단 기반의 협력적 공진화 알고리즘을 사용한 폐쇄루프 공급사슬 네트워크의 설계

한용호(Yongho Han) 한국SCM학회 2013 한국SCM학회지 Vol.13 No.1

Literature survey shows that only a few papers deal with comprehensive supply chain models with both forward and reverse flows. The goal of this study is to propose a comprehensive closed-loop model integrating forward and reverse logistics for the supply chain network design and to design a cooperative coevolutionary algorithm(CCEA) as a heuristic approach to get a good approximate solution. Mathematical model is formulated first, and then CCEA is designed as follows; First, the problem is broken down into eight subproblems. For each subproblem, a population of chromosomes is created, a chromosome is encoded using a permutation of integers, and a decoding method is suggested to get a partial solution. As genetic operators, binary tournament selection with elitist strategy, order crossover, and swap mutation are applied for evolving each of the subpopulations. To find feasible solutions satisfying a nonlinear constraint, a penalty method is adopted. The evaluation of a partial solution in a subpopulations is done by composing a complete solution with the best partial solutions from all the other subpopulations. Experimental results show that our CCEA in almost every case outperforms GA in terms of both the quality of solution obtained and the potential for solution improvement.

자동화 장치장의 재정돈 계획 최적화를 위한 협력적 공진화 알고리즘

박기역(Kiyeok Park),박태진(Taejin Park),류광렬(Kwang Ryel Ryu) 한국항해항만학회 2008 한국항해항만학회 학술대회논문집 Vol.2008 No.추계

본 논문은 재정돈 계획의 최적화를 위해 협력적 공진화 알고리즘을 이용하여 방법을 제안한다. 재정돈이란 컨테이너 터미널에서 적하 작업 시 발생하는 지연을 줄이기 위해 선박에 적하될 컨테이너의 위치를 사전에 변경하는 작업이다. 재정돈 계획 수립을 위해서는 적하 시 작업 효율이 최대가 되고 재정돈 시간이 최소가 되도록 컨테이너가 재정돈 후 배치될 장치형태와 재정돈 시 컨테이너를 옮길 순서를 결정해야 한다. 협력적 공진화 알고리즘은 주어진 문제가 세부 문제들로 분할 가능할 때 분할된 세부 문제들을 동시에 탐색하여 문제를 효율적으로 해결하는 방법이다. 이에 본 논문에서는 재정돈 계획 문제를 장치형태 결정 문제와 이동 우선순위 결정 문제로 분할하고 협력적 공진화 알고리즘을 적용하여 재정돈 계획을 최적화하였다. 실험결과 문제를 분할한 협력적 공진화 알고리즘이 문제를 분할하지 않은 접근 방법에 비해 더욱 효과적으로 재정돈하는 계획을 수립함을 확인할 수 있었다. In this paper, we propose optimizing a remarshaling plan in an automated stacking yard using a cooperative coevolutionary algorithm(CCEA). Remarshaling is the preparation task of rearranging the containers in such a way that the delay are minimized at the time of loading. A plan for remarshaling can be obtained by the following steps: first determining the target slots to which the individual containers are to be moved and then determining the order of movement of those containers. Where a given problem can be decomposed into some subproblems. CCEA efficiently searches subproblems for a solution. In our CCEA, the remarshaling problem is decomposed into two subproblems: one is the subproblem of determining the target slots and the other is that of determining the movement priority. Simulation experiments show that our CCEA derives a plan which is better in the efficiency of both loading and remarshaling compared to other methods which are not based on the idea of problem decomposition.