Study on Thinking Evolution based ant Colony Algorithm in Typical Production Scheduling Application

Xianmin Wei,Peng Zhang 보안공학연구지원센터 2015 International Journal of Hybrid Information Techno Vol.8 No.6

Aiming at solving the NP-hard workshop production scheduling problems, proposed one kind based on mind evolutionary algorithm. The algorithm in the traditional ant colony algorithm is established, and the combination of evolutionary thought and local optimization idea overcomes the basic ant colony algorithm is easy to fall into local optimal defects, the improved state transition rules, defining a pheromone range, improve the pheromone update strategy, and the increase of neighborhood search. Experimental results show that, for a typical production scheduling problems, based on mind evolutionary ant colony algorithm can obtain the optimal solution in theory, optimal solution, the solution and average three indicators are better than the basic ant colony algorithm, showed good performance.

게임 이론에 기반한 공진화 알고리즘

심귀보(Kwee-Bo Sim),김지윤(Ji-Youn Kim),이동욱(Dong-Wook Lee) 한국지능시스템학회 2004 한국지능시스템학회논문지 Vol.14 No.3

게임 이론은 의사 결정 문제와 관련 된 연구와 함께 정립 된 수학적 분석법으로써 1928년 Von Neumann이 유한개의 순수전략이 존재하는 2인 영합게임은 결정적(deterministic)이라는 것을 증명함으로써 수학적 기반을 정립하였고 50년대 초, Nash는 Von Neumann의 이론을 일반화하는 개념을 제안함으로써 현대적 게임이론의 장을 열었다. 이후 진화 생물학 연구자들에 의해 고전적인 게임 이론의 가정에 해당하는 참가자들의 합리성(rationality) 대신 다윈 선택(Darwinian selection)에 의해 게임의 해를 탐색하는 것이 가능하다는 것이 밝혀지게 되었고 진화 생물학자 Maynard Smith에 의해 진화적 안정 전략(Evolutionary Stable Strategy: ESS)의 개념이 정립되면서 현대적 게임 이론으로써 진화적 게임 이론이 체계화 되었다. 한편 이와 같은 진화적 게임 이론에 관한 연구와 함께 생태계의 공진화를 이용한 컴퓨터 시뮬레이션이 1991년 Hillis에 의해 처음으로 시도되었으며 Kauffman은 다른 종들 간의 공진화적 동역학(dynamics)을 분석하기 위한 NK 모델을 제안하였다. Kauffman은 이 모델을 이용하여 공진화 현상이 어떻게 정적 상태(static state)에 이르며 이 상태들은 게임 이론에서 소개되어진 내쉬 균형이나 ESS에 해당한다는 것을 보여주었다. 이후, 몇몇 연구자들 게임 이론과 진화 알고리즘에 기반한 연산 모델들을 제시해 왔으나 실용적인 문제의 적용에 대한 연구는 아직 미흡한 편이다. 이에 본 논문에서는 게임 이론에 기반 한 공진화 알고리즘을(Game theory based Co-Evolutionary Algorithm: GCEA) 제안하고 이 알고리즘을 이용하여 공진화적인 문제들을 효과적으로 해결할 수 있음을 확인하는 것을 목표로 한다. Game theory is mathematical analysis developed to study involved in making decisions. In 1928, Von Neumann proved that every two-person, zero-sum game with finitely many pure strategies for each player is deterministic. As well, in the early 50's, Nash presented another concept as the basis for a generalization of Von Neumann's theorem. Another central achievement of game theory is the introduction of evolutionary game theory, by which agents can play optimal strategies in the absence of rationality. Not the rationality but through the process of Darwinian selection, a population of agents can evolve to an Evolutionary Stable Strategy (ESS) introduced by Maynard Smith. Keeping pace with these game theoretical studies, the first computer simulation of co-evolution was tried out by Hillis in 1991. Moreover, Kauffman proposed NK model to analyze co-evolutionary dynamics between different species. He showed how co-evolutionary phenomenon reaches static states and that these states are Nash equilibrium or ESS introduced in game theory. Since the studies about co-evolutionary phenomenon were started, however many other researchers have developed co-evolutionary algorithms, in this paper we propose Game theory based Co-Evolutionary Algorithm (GCEA) and confirm that this algorithm can be a solution of evolutionary problems by searching the ESS.To evaluate newly designed GCEA approach, we solve several test Multi-objective Optimization Problems (MOPs). From the results of these evaluations, we confirm that evolutionary game can be embodied by co-evolutionary algorithm and analyze optimization performance of GCEA by comparing experimental results using GCEA with the results using other evolutionary optimization algorithms.

Improved Multi-objective Optimization Evolutionary Algorithm on Chaos

Xue Ding,Chuanxin Zhao 보안공학연구지원센터 2016 International Journal of Hybrid Information Techno Vol.9 No.3

In this paper, chaos theory and the traditional multi-objective optimization evolutionary algorithm is put forward, "Chaos-based multi-objective evolutionary algorithm", combines a variety of optimization strategies. The traditional multi-objective evolutionary algorithm for repeating individual causes of variation is based on chaotic analysis of multi-objective evolutionary algorithm and demonstration. According to the characteristics of chaotic map tent, NSGA-II algorithm in this paper on the basis of chaotic map was proposed based on chaotic tent initialization and chaotic mutation multi-objective evolutionary algorithm. The original NSGA-II algorithm is improved, and the introduction of adaptive mutation operator and a new crowding distance is calculated and applied to the design of the algorithm. Analysis and experimental results show that these methods can better improve the distribution of population performance.

Optimization of Grey Neural Network Model Based on Mind Evolutionary Algorithm

Zhang, Yong-Li(장영예),Na, Sang-Gyun(나상균),Wang, Bao-Shuai(왕바오슈아이) 한국산업경제학회 2017 산업경제연구 Vol.30 No.4

회색신경망모형은 제품의 주문 수량을 예측할 때 소 표본과 정보부족 등의 문제를 해결하는데 유용하게 사용할 수 있지만, 예측 시 무작위로 파라미터를 초기화하면 예측정확도가 낮아지는 단점이 있다. 따라서 본 연구에서는 전통적인 회색신경망모형의 단점을 보완하기 위해서 MEA(Mind Evolution Algorithm)를 적용한 최적화된 회색 신경망모형을 제시하였다. 본 연구 결과는 다음과 같다. 제품의 주문수량을 예측하기 위해서 MEA(Mind Evolution Algorithm)를 이용한 최적화된 회색신경망모형, PSO(Particle Swarm Optimization)를 이용한 최적화된 회색신경망모형, GA(Genetic Algorithm)을 이용한 최적화된 회색신경망모형, BP(Back Propagation)을 이용한 회색신경망모형에 대해 비교분석을 하였다. 분석결과를 보면, MEA(Mind Evolution Algorithm)를 이용한 최적화된 회색신경망모형의 예측 총오차 4457.6000, 평균루트오차 920.7372, 평균오차백분율 4.04%, 운영시간은 1.1509초로 분석되었다. 선행연구에서 제시한 가장 우수한 PSO(Particle Swarm Optimization)를 이용한 최적화된 회색 신경망모형 보다, MEA(Mind Evolution Algorithm)를 이용한 최적화된 회색신경망모형의 예측 총 오차가 16.12%, 평균루트오차 12.39%, 평균오차백분율 16.87%가 감소되어, 결과적으로 운영시간이 감소되면서 계산속도가 21.61%가 증가 되었다. 따라서 다른 지능알고리즘과 비교하면, MEA(Mind Evolution Algorithm)를 이용한 최적화된 회색신경망모형은 최고의 예측 정확도와 계산속도가 높다는 장점을 보유하고 있다. 따라서 기업에서 제품의 주문 수량을 예측할 때 소 표본과 정보부족 등의 문제가 발생할 경우, 최적화된 회색신경망모형을 이용하는 것이 필요하다. For the problem of randomized parameters and large error, the grey neural network model optimized by mind evolutionary algorithm(MEA-GNNM) was presented. The experiment results showed that the total error, root mean square error, mean percentage error, and running time of MEA-GNNM were 4457.6000, 920.7372, 4.04% and 1.1509 seconds; Compared with GA-GNNM, the total error, root mean square error and mean percentage error of MEA-GNNM had decreased by 16.12%, 12.39% and 16.87%, and the calculation speed increased by 21.61%. Compared with PSO-GNNM, the total error, root mean square error and mean percentage error of MEA-GNNM had decreased by 9.13%, 11.33% and 12.17%, but running time increased by 104.50%. The paper presents a new approach to optimize the parameters of grey neural network model, and also provides a new method having higher prediction accuracy for the time series prediction.

A Multi-Objective Evolutionary Algorithm for Scheduling Flexible Manufacturing Systems

Mehrdad Nouri Koupaei,Mohammad Mohammadi,Bahman Naderi 대한산업공학회 2017 Industrial Engineeering & Management Systems Vol.16 No.2

In recent decades, flexible manufacturing systems have emerged as a response to market demands of high product diversity. Scheduling is one important phase in production planning in all manufacturing systems. Although scheduling in classical manufacturing systems, such as flow and job shops, are well studied. Rarely, any paper studies scheduling of the more recent flexible manufacturing system. Since the problem class is NP-hard, different scheduling algorithms such as genetic algorithm (GA), simulated annealing (SA) algorithm, memetic algorithm (MA) and particle swarm algorithm (PSA) can be designed to solve this problem. This paper investigates a multi-objective evolutionary algorithm for scheduling flexible manufacturing systems to minimizing makespan, earliness and tardiness and startup costs. The distinctive feature of the proposed multi-objective evolutionary algorithm is its ability to search the solution space by an intelligent method, which is unlike other meta-heuristic algorithms avoid the coincidental method. Also, answer with the best quality and highest dispersion to obtain the dominant answer is used. Finally, we carry out computational experiments to demonstrate the effectiveness of our algorithm. The results show that the proposed algorithm has the ability to achieve the good solutions in reasonable computational time.

Hybrid genetic-paired-permutation algorithm for improved VLSI placement

Ignatyev, Vladimir V.,Kovalev, Andrey V.,Spiridonov, Oleg B.,Kureychik, Viktor M.,Ignatyeva, Alexandra S.,Safronenkova, Irina B. Electronics and Telecommunications Research Instit 2021 ETRI Journal Vol.43 No.2

This paper addresses Very large-scale integration (VLSI) placement optimization, which is important because of the rapid development of VLSI design technologies. The goal of this study is to develop a hybrid algorithm for VLSI placement. The proposed algorithm includes a sequential combination of a genetic algorithm and an evolutionary algorithm. It is commonly known that local search algorithms, such as random forest, hill climbing, and variable neighborhoods, can be effectively applied to NP-hard problem-solving. They provide improved solutions, which are obtained after a global search. The scientific novelty of this research is based on the development of systems, principles, and methods for creating a hybrid (combined) placement algorithm. The principal difference in the proposed algorithm is that it obtains a set of alternative solutions in parallel and then selects the best one. Nonstandard genetic operators, based on problem knowledge, are used in the proposed algorithm. An investigational study shows an objective-function improvement of 13%. The time complexity of the hybrid placement algorithm is O(N2).

Differential Evolution Algorithm for Job Shop Scheduling Problem

Warisa Wisittipanich,Voratas Kachitvichyanukul 대한산업공학회 2011 Industrial Engineeering & Management Systems Vol.10 No.3

Job shop scheduling is well-known as one of the hardest combinatorial optimization problems and has been demonstrated to be NP-hard problem. In the past decades, several researchers have devoted their effort to develop evolutionary algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) for job shop scheduling problem. Differential Evolution (DE) algorithm is a more recent evolutionary algorithm which has been widely applied and shown its strength in many application areas. However, the applications of DE on scheduling problems are still limited. This paper proposes a one-stage differential evolution algorithm (1ST-DE) for job shop scheduling problem. The proposed algorithm employs random key representation and permutation of m-job repetition to generate active schedules. The performance of proposed method is evaluated on a set of benchmark problems and compared with results from an existing PSO algorithm. The numerical results demonstrated that the proposed algorithm is able to provide good solutions especially for the large size problems with relatively fast computing time.

양떼의 유전 모델에 기초한 새로운 진화론적 알고리즘과 그 응용

김현철 경주대학교 2001 論文集 Vol.14 No.-

This Paper proposes a new evolutionary computation algorithm which is based on the sheep flocks heredity. The algorithm is developed for solving such a large problem that a chromosome consists of several sub-chromosome, which have the same structural configurations as a part of a chromosome, for example, each sub-chromosome represents the operational schedule of one machine for several consecutive years. Namely, the algorithm is effective for large scale scheduling problem spanning to several time periods. So as to cope with this special strong structure, hierarchical crossover(with mutation) operations are applied. They are, (1)sub-chromosome(local) level crossover and (2)chromosome (global) level crossover. This operation is named as “multi-stage genetic operation”. The proposed algorithm, based on the multi-stage genetic operation, can find better solution than those of the simple genetic algorithm. The validity and effectiveness of this algorithm is demonstrated through several scheduling problems.

Differential Evolution Algorithm for Job Shop Scheduling Problem

Wisittipanich, Warisa,Kachitvichyanukul, Voratas Korean Institute of Industrial Engineers 2011 Industrial Engineeering & Management Systems Vol.10 No.3

Job shop scheduling is well-known as one of the hardest combinatorial optimization problems and has been demonstrated to be NP-hard problem. In the past decades, several researchers have devoted their effort to develop evolutionary algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) for job shop scheduling problem. Differential Evolution (DE) algorithm is a more recent evolutionary algorithm which has been widely applied and shown its strength in many application areas. However, the applications of DE on scheduling problems are still limited. This paper proposes a one-stage differential evolution algorithm (1ST-DE) for job shop scheduling problem. The proposed algorithm employs random key representation and permutation of m-job repetition to generate active schedules. The performance of proposed method is evaluated on a set of benchmark problems and compared with results from an existing PSO algorithm. The numerical results demonstrated that the proposed algorithm is able to provide good solutions especially for the large size problems with relatively fast computing time.

고차상관관계를 표현하는 랜덤 하이퍼그래프 모델 진화를 위한 베이지안 샘플링 알고리즘

이시은(Si Eun Lee),이인희(In-Hee Lee),장병탁(Byoung-Tak Zhang) 한국정보과학회 2009 정보과학회논문지 : 소프트웨어 및 응용 Vol.36 No.3

유전자알고리즘의 교차나 돌연변이 연산을 직접적으로 사용하지 않고 개체군의 확률분포를 추정하여 보다 효율적인 탐색을 수행하려는 분포추정알고리즘이 여러 방법으로 제안되었다. 그러나 실제로 변수들간의 고차상관관계를 파악하는 일은 쉽지 않은 일이라 대부분의 경우 낮은 차수의 상관관계를 제한된 가정하에 추정하게 된다. 본 논문에서는 데이타의 고차상관관계를 표현할 수 있고 최적 해를 좀 더 효율적으로 찾을 수 있는 새로운 분포추정알고리즘을 제안한다. 제안된 알고리즘에서는 상관관계가 있을 것으로 추정되는 변수들의 집합으로 정의된 하이퍼에지로 구성된 랜덤 하이퍼그래프 모델을 구축하여 변수들 간의 고차상관관계를 표현하고, 베이지안 샘플링 알고리즘(Bayesian Sampling Algorithm)을 통해 다음 세대의 개체를 생성한다. 기만하는 빌딩블럭(deceptive building blocks)을 가진 분해가능(decomposable) 함수에 대하여 실험한 결과 성공적으로 최적해를 구할 수 있었으며 단순 유전자알고리즘과 BOA (Bayesian Optimization Algorithm)와 비교하여 좋은 성능을 얻을 수 있었다. A number of estimation of distribution algorithms have been proposed that do not use explicitly crossover and mutation of traditional genetic algorithms, but estimate the distribution of population for more efficient search. But because it is not easy to discover higher-order correlations of variables, lower-order correlations are estimated most cases under various constraints. In this paper, we propose a new estimation of distribution algorithm that represents higher-order correlations of the data and finds global optimum more efficiently. The proposed algorithm represents the higher-order correlations among variables by building random hypergraph model composed of hyperedges consisting of variables which are expected to be correlated, and generates the next population by Bayesian sampling algorithm. Experimental results show that the proposed algorithm can find global optimum and outperforms the simple genetic algorithm and BOA(Bayesian Optimization Algorithm) on decomposable functions with deceptive building blocks.